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 extension policy-based data structures for public use.
60 // A trivial iterator tag. Signifies that the iterators has none of
61 // the STL's movement abilities.
62 struct trivial_iterator_tag
65 // Prohibit moving trivial iterators.
66 typedef void trivial_iterator_difference_type
;
69 // Signifies a basic invalidation guarantee that any iterator,
70 // pointer, or reference to a container object's mapped value type
71 // is valid as long as the container is not modified.
72 struct basic_invalidation_guarantee
75 // Signifies an invalidation guarantee that includes all those of
76 // its base, and additionally, that any point-type iterator,
77 // pointer, or reference to a container object's mapped value type
78 // is valid as long as its corresponding entry has not be erased,
79 // regardless of modifications to the container object.
80 struct point_invalidation_guarantee
: public basic_invalidation_guarantee
83 // Signifies an invalidation guarantee that includes all those of
84 // its base, and additionally, that any range-type iterator
85 // (including the returns of begin() and end()) is in the correct
86 // relative positions to other range-type iterators as long as its
87 // corresponding entry has not be erased, regardless of
88 // modifications to the container object.
89 struct range_invalidation_guarantee
: public point_invalidation_guarantee
93 // A mapped-policy indicating that an associative container is a set.
94 // XXX should this be a trait of the form is_set<T> ??
95 struct null_mapped_type
{ };
98 // Base data structure tag.
102 // Basic associative-container.
103 struct associative_container_tag
: public container_tag
{ };
106 struct basic_hash_tag
: public associative_container_tag
{ };
108 // Collision-chaining hash.
109 struct cc_hash_tag
: public basic_hash_tag
{ };
111 // General-probing hash.
112 struct gp_hash_tag
: public basic_hash_tag
{ };
115 struct basic_tree_tag
: public associative_container_tag
{ };
118 struct tree_tag
: public basic_tree_tag
{ };
121 struct rb_tree_tag
: public tree_tag
{ };
124 struct splay_tree_tag
: public tree_tag
{ };
126 // Ordered-vector tree.
127 struct ov_tree_tag
: public tree_tag
{ };
130 struct trie_tag
: public basic_tree_tag
{ };
133 struct pat_trie_tag
: public trie_tag
{ };
136 struct list_update_tag
: public associative_container_tag
{ };
138 // Basic priority-queue.
139 struct priority_queue_tag
: public container_tag
{ };
142 struct pairing_heap_tag
: public priority_queue_tag
{ };
145 struct binomial_heap_tag
: public priority_queue_tag
{ };
147 // Redundant-counter binomial-heap.
148 struct rc_binomial_heap_tag
: public priority_queue_tag
{ };
150 // Binary-heap (array-based).
151 struct binary_heap_tag
: public priority_queue_tag
{ };
154 struct thin_heap_tag
: public priority_queue_tag
{ };
157 template<typename Tag
>
158 struct container_traits_base
;
161 struct container_traits_base
<cc_hash_tag
>
163 typedef cc_hash_tag container_category
;
164 typedef point_invalidation_guarantee invalidation_guarantee
;
168 order_preserving
= false,
169 erase_can_throw
= false,
170 split_join_can_throw
= false,
171 reverse_iteration
= false
176 struct container_traits_base
<gp_hash_tag
>
178 typedef gp_hash_tag container_category
;
179 typedef basic_invalidation_guarantee invalidation_guarantee
;
183 order_preserving
= false,
184 erase_can_throw
= false,
185 split_join_can_throw
= false,
186 reverse_iteration
= false
191 struct container_traits_base
<rb_tree_tag
>
193 typedef rb_tree_tag container_category
;
194 typedef range_invalidation_guarantee invalidation_guarantee
;
198 order_preserving
= true,
199 erase_can_throw
= false,
200 split_join_can_throw
= false,
201 reverse_iteration
= true
206 struct container_traits_base
<splay_tree_tag
>
208 typedef splay_tree_tag container_category
;
209 typedef range_invalidation_guarantee invalidation_guarantee
;
213 order_preserving
= true,
214 erase_can_throw
= false,
215 split_join_can_throw
= false,
216 reverse_iteration
= true
221 struct container_traits_base
<ov_tree_tag
>
223 typedef ov_tree_tag container_category
;
224 typedef basic_invalidation_guarantee invalidation_guarantee
;
228 order_preserving
= true,
229 erase_can_throw
= true,
230 split_join_can_throw
= true,
231 reverse_iteration
= false
236 struct container_traits_base
<pat_trie_tag
>
238 typedef pat_trie_tag container_category
;
239 typedef range_invalidation_guarantee invalidation_guarantee
;
243 order_preserving
= true,
244 erase_can_throw
= false,
245 split_join_can_throw
= true,
246 reverse_iteration
= true
251 struct container_traits_base
<list_update_tag
>
253 typedef list_update_tag container_category
;
254 typedef point_invalidation_guarantee invalidation_guarantee
;
258 order_preserving
= false,
259 erase_can_throw
= false,
260 split_join_can_throw
= false,
261 reverse_iteration
= false
267 struct container_traits_base
<pairing_heap_tag
>
269 typedef pairing_heap_tag container_category
;
270 typedef point_invalidation_guarantee invalidation_guarantee
;
274 order_preserving
= false,
275 erase_can_throw
= false,
276 split_join_can_throw
= false,
277 reverse_iteration
= false
282 struct container_traits_base
<thin_heap_tag
>
284 typedef thin_heap_tag container_category
;
285 typedef point_invalidation_guarantee invalidation_guarantee
;
289 order_preserving
= false,
290 erase_can_throw
= false,
291 split_join_can_throw
= false,
292 reverse_iteration
= false
297 struct container_traits_base
<binomial_heap_tag
>
299 typedef binomial_heap_tag container_category
;
300 typedef point_invalidation_guarantee invalidation_guarantee
;
304 order_preserving
= false,
305 erase_can_throw
= false,
306 split_join_can_throw
= false,
307 reverse_iteration
= false
312 struct container_traits_base
<rc_binomial_heap_tag
>
314 typedef rc_binomial_heap_tag container_category
;
315 typedef point_invalidation_guarantee invalidation_guarantee
;
319 order_preserving
= false,
320 erase_can_throw
= false,
321 split_join_can_throw
= false,
322 reverse_iteration
= false
327 struct container_traits_base
<binary_heap_tag
>
329 typedef binary_heap_tag container_category
;
330 typedef basic_invalidation_guarantee invalidation_guarantee
;
334 order_preserving
= false,
335 erase_can_throw
= false,
336 split_join_can_throw
= true,
337 reverse_iteration
= false
342 // See Matt Austern for the name, S. Meyers MEFC++ #2, others.
343 template<typename Cntnr
>
344 struct container_traits
345 : public container_traits_base
<typename
Cntnr::container_category
>
347 typedef Cntnr container_type
;
348 typedef typename
Cntnr::container_category container_category
;
349 typedef container_traits_base
<container_category
> base_type
;
350 typedef typename
base_type::invalidation_guarantee invalidation_guarantee
;
354 order_preserving
= base_type::order_preserving
,
355 erase_can_throw
= base_type::erase_can_throw
,
356 split_join_can_throw
= base_type::split_join_can_throw
,
357 reverse_iteration
= base_type::reverse_iteration
360 } // namespace __gnu_pbds