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>
55 // A trivial iterator tag. Signifies that the iterators has none of
56 // the STL's movement abilities.
57 struct trivial_iterator_tag
60 // Prohibit moving trivial iterators.
61 typedef void trivial_iterator_difference_type;
64 // Signifies a basic invalidation guarantee that any iterator,
65 // pointer, or reference to a container object's mapped value type
66 // is valid as long as the container is not modified.
67 struct basic_invalidation_guarantee
70 // Signifies an invalidation guarantee that includes all those of
71 // its base, and additionally, that any point-type iterator,
72 // pointer, or reference to a container object's mapped value type
73 // is valid as long as its corresponding entry has not be erased,
74 // regardless of modifications to the container object.
75 struct point_invalidation_guarantee : public basic_invalidation_guarantee
78 // Signifies an invalidation guarantee that includes all those of
79 // its base, and additionally, that any range-type iterator
80 // (including the returns of begin() and end()) is in the correct
81 // relative positions to other range-type iterators as long as its
82 // corresponding entry has not be erased, regardless of
83 // modifications to the container object.
84 struct range_invalidation_guarantee : public point_invalidation_guarantee
88 // A mapped-policy indicating that an associative container is a set.
89 // XXX should this be a trait of the form is_set<T> ??
90 struct null_mapped_type { };
93 // Base data structure tag.
97 // Basic associative-container.
98 struct associative_container_tag : public container_tag { };
101 struct basic_hash_tag : public associative_container_tag { };
103 // Collision-chaining hash.
104 struct cc_hash_tag : public basic_hash_tag { };
106 // General-probing hash.
107 struct gp_hash_tag : public basic_hash_tag { };
110 struct basic_tree_tag : public associative_container_tag { };
113 struct tree_tag : public basic_tree_tag { };
116 struct rb_tree_tag : public tree_tag { };
119 struct splay_tree_tag : public tree_tag { };
121 // Ordered-vector tree.
122 struct ov_tree_tag : public tree_tag { };
125 struct trie_tag : public basic_tree_tag { };
128 struct pat_trie_tag : public trie_tag { };
131 struct list_update_tag : public associative_container_tag { };
133 // Basic priority-queue.
134 struct priority_queue_tag : public container_tag { };
137 struct pairing_heap_tag : public priority_queue_tag { };
140 struct binomial_heap_tag : public priority_queue_tag { };
142 // Redundant-counter binomial-heap.
143 struct rc_binomial_heap_tag : public priority_queue_tag { };
145 // Binary-heap (array-based).
146 struct binary_heap_tag : public priority_queue_tag { };
149 struct thin_heap_tag : public priority_queue_tag { };
152 template<typename Tag>
153 struct container_traits_base;
156 struct container_traits_base<cc_hash_tag>
158 typedef cc_hash_tag container_category;
159 typedef point_invalidation_guarantee invalidation_guarantee;
163 order_preserving = false,
164 erase_can_throw = false,
165 split_join_can_throw = false,
166 reverse_iteration = false
171 struct container_traits_base<gp_hash_tag>
173 typedef gp_hash_tag container_category;
174 typedef basic_invalidation_guarantee invalidation_guarantee;
178 order_preserving = false,
179 erase_can_throw = false,
180 split_join_can_throw = false,
181 reverse_iteration = false
186 struct container_traits_base<rb_tree_tag>
188 typedef rb_tree_tag container_category;
189 typedef range_invalidation_guarantee invalidation_guarantee;
193 order_preserving = true,
194 erase_can_throw = false,
195 split_join_can_throw = false,
196 reverse_iteration = true
201 struct container_traits_base<splay_tree_tag>
203 typedef splay_tree_tag container_category;
204 typedef range_invalidation_guarantee invalidation_guarantee;
208 order_preserving = true,
209 erase_can_throw = false,
210 split_join_can_throw = false,
211 reverse_iteration = true
216 struct container_traits_base<ov_tree_tag>
218 typedef ov_tree_tag container_category;
219 typedef basic_invalidation_guarantee invalidation_guarantee;
223 order_preserving = true,
224 erase_can_throw = true,
225 split_join_can_throw = true,
226 reverse_iteration = false
231 struct container_traits_base<pat_trie_tag>
233 typedef pat_trie_tag container_category;
234 typedef range_invalidation_guarantee invalidation_guarantee;
238 order_preserving = true,
239 erase_can_throw = false,
240 split_join_can_throw = true,
241 reverse_iteration = true
246 struct container_traits_base<list_update_tag>
248 typedef list_update_tag container_category;
249 typedef point_invalidation_guarantee invalidation_guarantee;
253 order_preserving = false,
254 erase_can_throw = false,
255 split_join_can_throw = false,
256 reverse_iteration = false
262 struct container_traits_base<pairing_heap_tag>
264 typedef pairing_heap_tag container_category;
265 typedef point_invalidation_guarantee invalidation_guarantee;
269 order_preserving = false,
270 erase_can_throw = false,
271 split_join_can_throw = false,
272 reverse_iteration = false
277 struct container_traits_base<thin_heap_tag>
279 typedef thin_heap_tag container_category;
280 typedef point_invalidation_guarantee invalidation_guarantee;
284 order_preserving = false,
285 erase_can_throw = false,
286 split_join_can_throw = false,
287 reverse_iteration = false
292 struct container_traits_base<binomial_heap_tag>
294 typedef binomial_heap_tag container_category;
295 typedef point_invalidation_guarantee invalidation_guarantee;
299 order_preserving = false,
300 erase_can_throw = false,
301 split_join_can_throw = false,
302 reverse_iteration = false
307 struct container_traits_base<rc_binomial_heap_tag>
309 typedef rc_binomial_heap_tag container_category;
310 typedef point_invalidation_guarantee invalidation_guarantee;
314 order_preserving = false,
315 erase_can_throw = false,
316 split_join_can_throw = false,
317 reverse_iteration = false
322 struct container_traits_base<binary_heap_tag>
324 typedef binary_heap_tag container_category;
325 typedef basic_invalidation_guarantee invalidation_guarantee;
329 order_preserving = false,
330 erase_can_throw = false,
331 split_join_can_throw = true,
332 reverse_iteration = false
337 // See Matt Austern for the name, S. Meyers MEFC++ #2, others.
338 template<typename Cntnr>
339 struct container_traits
340 : public container_traits_base<typename Cntnr::container_category>
342 typedef Cntnr container_type;
343 typedef typename Cntnr::container_category container_category;
344 typedef container_traits_base<container_category> base_type;
345 typedef typename base_type::invalidation_guarantee invalidation_guarantee;
349 order_preserving = base_type::order_preserving,
350 erase_can_throw = base_type::erase_can_throw,
351 split_join_can_throw = base_type::split_join_can_throw,
352 reverse_iteration = base_type::reverse_iteration