libstdc++
tag_and_trait.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005, 2006, 2008, 2009 Free Software Foundation, Inc.
4 //
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 3, or (at your option) any later
9 // version.
10 
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.
15 
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24 
25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
26 
27 // Permission to use, copy, modify, sell, and distribute this software
28 // is hereby granted without fee, provided that the above copyright
29 // notice appears in all copies, and that both that copyright notice
30 // and this permission notice appear in supporting documentation. None
31 // of the above authors, nor IBM Haifa Research Laboratories, make any
32 // representation about the suitability of this software for any
33 // purpose. It is provided "as is" without express or implied
34 // warranty.
35 
36 /**
37  * @file tag_and_trait.hpp
38  * Contains tags and traits, e.g., ones describing underlying
39  * data structures.
40  */
41 
42 #ifndef PB_DS_TAG_AND_TRAIT_HPP
43 #define PB_DS_TAG_AND_TRAIT_HPP
44 
46 
47 /**
48  * @namespace __gnu_pbds
49  * @brief GNU extensions for policy-based data structures for public use.
50  */
51 namespace __gnu_pbds
52 {
53  // A trivial iterator tag. Signifies that the iterators has none of
54  // the STL's movement abilities.
55  struct trivial_iterator_tag
56  { };
57 
58  // Prohibit moving trivial iterators.
59  typedef void trivial_iterator_difference_type;
60 
61 
62  // Signifies a basic invalidation guarantee that any iterator,
63  // pointer, or reference to a container object's mapped value type
64  // is valid as long as the container is not modified.
65  struct basic_invalidation_guarantee
66  { };
67 
68  // Signifies an invalidation guarantee that includes all those of
69  // its base, and additionally, that any point-type iterator,
70  // pointer, or reference to a container object's mapped value type
71  // is valid as long as its corresponding entry has not be erased,
72  // regardless of modifications to the container object.
73  struct point_invalidation_guarantee : public basic_invalidation_guarantee
74  { };
75 
76  // Signifies an invalidation guarantee that includes all those of
77  // its base, and additionally, that any range-type iterator
78  // (including the returns of begin() and end()) is in the correct
79  // relative positions to other range-type iterators as long as its
80  // corresponding entry has not be erased, regardless of
81  // modifications to the container object.
82  struct range_invalidation_guarantee : public point_invalidation_guarantee
83  { };
84 
85 
86  /// A mapped-policy indicating that an associative container is a set.
87  // XXX should this be a trait of the form is_set<T> ??
88  struct null_mapped_type { };
89 
90 
91  /// Base data structure tag.
93  { };
94 
95  /// Basic string container, inclusive of strings, ropes, etc.
96  struct string_tag : public container_tag { };
97 
98  /// Basic sequence.
99  struct sequence_tag : public container_tag { };
100 
101  /// Basic associative-container.
103 
104  /// Basic hash.
106 
107  /// Collision-chaining hash.
108  struct cc_hash_tag : public basic_hash_tag { };
109 
110  /// General-probing hash.
111  struct gp_hash_tag : public basic_hash_tag { };
112 
113  /// Basic tree.
115 
116  /// tree.
117  struct tree_tag : public basic_tree_tag { };
118 
119  /// Red-black tree.
120  struct rb_tree_tag : public tree_tag { };
121 
122  /// Splay tree.
123  struct splay_tree_tag : public tree_tag { };
124 
125  /// Ordered-vector tree.
126  struct ov_tree_tag : public tree_tag { };
127 
128  /// trie.
129  struct trie_tag : public basic_tree_tag { };
130 
131  /// PATRICIA trie.
132  struct pat_trie_tag : public trie_tag { };
133 
134  /// List-update.
136 
137  /// Basic priority-queue.
138  struct priority_queue_tag : public container_tag { };
139 
140  /// Pairing-heap.
142 
143  /// Binomial-heap.
145 
146  /// Redundant-counter binomial-heap.
148 
149  /// Binary-heap (array-based).
150  struct binary_heap_tag : public priority_queue_tag { };
151 
152  /// Thin heap.
153  struct thin_heap_tag : public priority_queue_tag { };
154 
155 
156  /// Base traits type for containers.
157  template<typename Tag>
159 
160  template<>
162  {
163  typedef cc_hash_tag container_category;
164  typedef point_invalidation_guarantee invalidation_guarantee;
165 
166  enum
167  {
168  order_preserving = false,
169  erase_can_throw = false,
170  split_join_can_throw = false,
171  reverse_iteration = false
172  };
173  };
174 
175  template<>
176  struct container_traits_base<gp_hash_tag>
177  {
178  typedef gp_hash_tag container_category;
179  typedef basic_invalidation_guarantee invalidation_guarantee;
180 
181  enum
182  {
183  order_preserving = false,
184  erase_can_throw = false,
185  split_join_can_throw = false,
186  reverse_iteration = false
187  };
188  };
189 
190  template<>
191  struct container_traits_base<rb_tree_tag>
192  {
193  typedef rb_tree_tag container_category;
194  typedef range_invalidation_guarantee invalidation_guarantee;
195 
196  enum
197  {
198  order_preserving = true,
199  erase_can_throw = false,
200  split_join_can_throw = false,
201  reverse_iteration = true
202  };
203  };
204 
205  template<>
206  struct container_traits_base<splay_tree_tag>
207  {
208  typedef splay_tree_tag container_category;
209  typedef range_invalidation_guarantee invalidation_guarantee;
210 
211  enum
212  {
213  order_preserving = true,
214  erase_can_throw = false,
215  split_join_can_throw = false,
216  reverse_iteration = true
217  };
218  };
219 
220  template<>
221  struct container_traits_base<ov_tree_tag>
222  {
223  typedef ov_tree_tag container_category;
224  typedef basic_invalidation_guarantee invalidation_guarantee;
225 
226  enum
227  {
228  order_preserving = true,
229  erase_can_throw = true,
230  split_join_can_throw = true,
231  reverse_iteration = false
232  };
233  };
234 
235  template<>
236  struct container_traits_base<pat_trie_tag>
237  {
238  typedef pat_trie_tag container_category;
239  typedef range_invalidation_guarantee invalidation_guarantee;
240 
241  enum
242  {
243  order_preserving = true,
244  erase_can_throw = false,
245  split_join_can_throw = true,
246  reverse_iteration = true
247  };
248  };
249 
250  template<>
251  struct container_traits_base<list_update_tag>
252  {
253  typedef list_update_tag container_category;
254  typedef point_invalidation_guarantee invalidation_guarantee;
255 
256  enum
257  {
258  order_preserving = false,
259  erase_can_throw = false,
260  split_join_can_throw = false,
261  reverse_iteration = false
262  };
263  };
264 
265 
266  template<>
267  struct container_traits_base<pairing_heap_tag>
268  {
269  typedef pairing_heap_tag container_category;
270  typedef point_invalidation_guarantee invalidation_guarantee;
271 
272  enum
273  {
274  order_preserving = false,
275  erase_can_throw = false,
276  split_join_can_throw = false,
277  reverse_iteration = false
278  };
279  };
280 
281  template<>
282  struct container_traits_base<thin_heap_tag>
283  {
284  typedef thin_heap_tag container_category;
285  typedef point_invalidation_guarantee invalidation_guarantee;
286 
287  enum
288  {
289  order_preserving = false,
290  erase_can_throw = false,
291  split_join_can_throw = false,
292  reverse_iteration = false
293  };
294  };
295 
296  template<>
297  struct container_traits_base<binomial_heap_tag>
298  {
299  typedef binomial_heap_tag container_category;
300  typedef point_invalidation_guarantee invalidation_guarantee;
301 
302  enum
303  {
304  order_preserving = false,
305  erase_can_throw = false,
306  split_join_can_throw = false,
307  reverse_iteration = false
308  };
309  };
310 
311  template<>
312  struct container_traits_base<rc_binomial_heap_tag>
313  {
314  typedef rc_binomial_heap_tag container_category;
315  typedef point_invalidation_guarantee invalidation_guarantee;
316 
317  enum
318  {
319  order_preserving = false,
320  erase_can_throw = false,
321  split_join_can_throw = false,
322  reverse_iteration = false
323  };
324  };
325 
326  template<>
327  struct container_traits_base<binary_heap_tag>
328  {
329  typedef binary_heap_tag container_category;
330  typedef basic_invalidation_guarantee invalidation_guarantee;
331 
332  enum
333  {
334  order_preserving = false,
335  erase_can_throw = false,
336  split_join_can_throw = true,
337  reverse_iteration = false
338  };
339  };
340 
341 
342  /// container_traits
343  // See Matt Austern for the name, S. Meyers MEFC++ #2, others.
344  template<typename Cntnr>
346  : public container_traits_base<typename Cntnr::container_category>
347  {
348  typedef Cntnr container_type;
349  typedef typename Cntnr::container_category container_category;
351  typedef typename base_type::invalidation_guarantee invalidation_guarantee;
352 
353  enum
354  {
355  order_preserving = base_type::order_preserving,
356  erase_can_throw = base_type::erase_can_throw,
357  split_join_can_throw = base_type::split_join_can_throw,
358  reverse_iteration = base_type::reverse_iteration
359  };
360  };
361 } // namespace __gnu_pbds
362 
363 #endif