3 // Copyright (C) 2005, 2006 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 2, or (at your option) any later
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
16 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING. If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction. Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License. This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
33 // Permission to use, copy, modify, sell, and distribute this software
34 // is hereby granted without fee, provided that the above copyright
35 // notice appears in all copies, and that both that copyright notice
36 // and this permission notice appear in supporting documentation. None
37 // of the above authors, nor IBM Haifa Research Laboratories, make any
38 // representation about the suitability of this software for any
39 // purpose. It is provided "as is" without express or implied
43 * @file tag_and_trait.hpp
44 * Contains tags and traits, e.g., ones describing underlying
48 #ifndef PB_DS_TAG_AND_TRAIT_HPP
49 #define PB_DS_TAG_AND_TRAIT_HPP
51 #include <ext/pb_ds/detail/type_utils.hpp>
54 * @namespace __gnu_pbds
55 * @brief GNU extensions for policy-based data structures for public use.
59 // A trivial iterator tag. Signifies that the iterators has none of
60 // the STL's movement abilities.
61 struct trivial_iterator_tag
64 // Prohibit moving trivial iterators.
65 typedef void trivial_iterator_difference_type
;
68 // Signifies a basic invalidation guarantee that any iterator,
69 // pointer, or reference to a container object's mapped value type
70 // is valid as long as the container is not modified.
71 struct basic_invalidation_guarantee
74 // Signifies an invalidation guarantee that includes all those of
75 // its base, and additionally, that any point-type iterator,
76 // pointer, or reference to a container object's mapped value type
77 // is valid as long as its corresponding entry has not be erased,
78 // regardless of modifications to the container object.
79 struct point_invalidation_guarantee
: public basic_invalidation_guarantee
82 // Signifies an invalidation guarantee that includes all those of
83 // its base, and additionally, that any range-type iterator
84 // (including the returns of begin() and end()) is in the correct
85 // relative positions to other range-type iterators as long as its
86 // corresponding entry has not be erased, regardless of
87 // modifications to the container object.
88 struct range_invalidation_guarantee
: public point_invalidation_guarantee
92 // A mapped-policy indicating that an associative container is a set.
93 // XXX should this be a trait of the form is_set<T> ??
94 struct null_mapped_type
{ };
97 // Base data structure tag.
101 // Basic associative-container.
102 struct associative_container_tag
: public container_tag
{ };
105 struct basic_hash_tag
: public associative_container_tag
{ };
107 // Collision-chaining hash.
108 struct cc_hash_tag
: public basic_hash_tag
{ };
110 // General-probing hash.
111 struct gp_hash_tag
: public basic_hash_tag
{ };
114 struct basic_tree_tag
: public associative_container_tag
{ };
117 struct tree_tag
: public basic_tree_tag
{ };
120 struct rb_tree_tag
: public tree_tag
{ };
123 struct splay_tree_tag
: public tree_tag
{ };
125 // Ordered-vector tree.
126 struct ov_tree_tag
: public tree_tag
{ };
129 struct trie_tag
: public basic_tree_tag
{ };
132 struct pat_trie_tag
: public trie_tag
{ };
135 struct list_update_tag
: public associative_container_tag
{ };
137 // Basic priority-queue.
138 struct priority_queue_tag
: public container_tag
{ };
141 struct pairing_heap_tag
: public priority_queue_tag
{ };
144 struct binomial_heap_tag
: public priority_queue_tag
{ };
146 // Redundant-counter binomial-heap.
147 struct rc_binomial_heap_tag
: public priority_queue_tag
{ };
149 // Binary-heap (array-based).
150 struct binary_heap_tag
: public priority_queue_tag
{ };
153 struct thin_heap_tag
: public priority_queue_tag
{ };
156 template<typename Tag
>
157 struct container_traits_base
;
160 struct container_traits_base
<cc_hash_tag
>
162 typedef cc_hash_tag container_category
;
163 typedef point_invalidation_guarantee invalidation_guarantee
;
167 order_preserving
= false,
168 erase_can_throw
= false,
169 split_join_can_throw
= false,
170 reverse_iteration
= false
175 struct container_traits_base
<gp_hash_tag
>
177 typedef gp_hash_tag container_category
;
178 typedef basic_invalidation_guarantee invalidation_guarantee
;
182 order_preserving
= false,
183 erase_can_throw
= false,
184 split_join_can_throw
= false,
185 reverse_iteration
= false
190 struct container_traits_base
<rb_tree_tag
>
192 typedef rb_tree_tag container_category
;
193 typedef range_invalidation_guarantee invalidation_guarantee
;
197 order_preserving
= true,
198 erase_can_throw
= false,
199 split_join_can_throw
= false,
200 reverse_iteration
= true
205 struct container_traits_base
<splay_tree_tag
>
207 typedef splay_tree_tag container_category
;
208 typedef range_invalidation_guarantee invalidation_guarantee
;
212 order_preserving
= true,
213 erase_can_throw
= false,
214 split_join_can_throw
= false,
215 reverse_iteration
= true
220 struct container_traits_base
<ov_tree_tag
>
222 typedef ov_tree_tag container_category
;
223 typedef basic_invalidation_guarantee invalidation_guarantee
;
227 order_preserving
= true,
228 erase_can_throw
= true,
229 split_join_can_throw
= true,
230 reverse_iteration
= false
235 struct container_traits_base
<pat_trie_tag
>
237 typedef pat_trie_tag container_category
;
238 typedef range_invalidation_guarantee invalidation_guarantee
;
242 order_preserving
= true,
243 erase_can_throw
= false,
244 split_join_can_throw
= true,
245 reverse_iteration
= true
250 struct container_traits_base
<list_update_tag
>
252 typedef list_update_tag container_category
;
253 typedef point_invalidation_guarantee invalidation_guarantee
;
257 order_preserving
= false,
258 erase_can_throw
= false,
259 split_join_can_throw
= false,
260 reverse_iteration
= false
266 struct container_traits_base
<pairing_heap_tag
>
268 typedef pairing_heap_tag container_category
;
269 typedef point_invalidation_guarantee invalidation_guarantee
;
273 order_preserving
= false,
274 erase_can_throw
= false,
275 split_join_can_throw
= false,
276 reverse_iteration
= false
281 struct container_traits_base
<thin_heap_tag
>
283 typedef thin_heap_tag container_category
;
284 typedef point_invalidation_guarantee invalidation_guarantee
;
288 order_preserving
= false,
289 erase_can_throw
= false,
290 split_join_can_throw
= false,
291 reverse_iteration
= false
296 struct container_traits_base
<binomial_heap_tag
>
298 typedef binomial_heap_tag container_category
;
299 typedef point_invalidation_guarantee invalidation_guarantee
;
303 order_preserving
= false,
304 erase_can_throw
= false,
305 split_join_can_throw
= false,
306 reverse_iteration
= false
311 struct container_traits_base
<rc_binomial_heap_tag
>
313 typedef rc_binomial_heap_tag container_category
;
314 typedef point_invalidation_guarantee invalidation_guarantee
;
318 order_preserving
= false,
319 erase_can_throw
= false,
320 split_join_can_throw
= false,
321 reverse_iteration
= false
326 struct container_traits_base
<binary_heap_tag
>
328 typedef binary_heap_tag container_category
;
329 typedef basic_invalidation_guarantee invalidation_guarantee
;
333 order_preserving
= false,
334 erase_can_throw
= false,
335 split_join_can_throw
= true,
336 reverse_iteration
= false
341 // See Matt Austern for the name, S. Meyers MEFC++ #2, others.
342 template<typename Cntnr
>
343 struct container_traits
344 : public container_traits_base
<typename
Cntnr::container_category
>
346 typedef Cntnr container_type
;
347 typedef typename
Cntnr::container_category container_category
;
348 typedef container_traits_base
<container_category
> base_type
;
349 typedef typename
base_type::invalidation_guarantee invalidation_guarantee
;
353 order_preserving
= base_type::order_preserving
,
354 erase_can_throw
= base_type::erase_can_throw
,
355 split_join_can_throw
= base_type::split_join_can_throw
,
356 reverse_iteration
= base_type::reverse_iteration
359 } // namespace __gnu_pbds