libstdc++
tag_and_trait.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005, 2006, 2008, 2009, 2010 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 
45 #include <bits/c++config.h>
47 
48 /**
49  * @namespace __gnu_pbds
50  * @brief GNU extensions for policy-based data structures for public use.
51  */
52 namespace __gnu_pbds
53 {
54  // A trivial iterator tag. Signifies that the iterators has none of
55  // the STL's movement abilities.
56  struct trivial_iterator_tag
57  { };
58 
59  // Prohibit moving trivial iterators.
60  typedef void trivial_iterator_difference_type;
61 
62 
63  // Signifies a basic invalidation guarantee that any iterator,
64  // pointer, or reference to a container object's mapped value type
65  // is valid as long as the container is not modified.
66  struct basic_invalidation_guarantee
67  { };
68 
69  // Signifies an invalidation guarantee that includes all those of
70  // its base, and additionally, that any point-type iterator,
71  // pointer, or reference to a container object's mapped value type
72  // is valid as long as its corresponding entry has not be erased,
73  // regardless of modifications to the container object.
74  struct point_invalidation_guarantee : public basic_invalidation_guarantee
75  { };
76 
77  // Signifies an invalidation guarantee that includes all those of
78  // its base, and additionally, that any range-type iterator
79  // (including the returns of begin() and end()) is in the correct
80  // relative positions to other range-type iterators as long as its
81  // corresponding entry has not be erased, regardless of
82  // modifications to the container object.
83  struct range_invalidation_guarantee : public point_invalidation_guarantee
84  { };
85 
86 
87  /// A mapped-policy indicating that an associative container is a set.
88  // XXX should this be a trait of the form is_set<T> ??
89  struct null_mapped_type { };
90 
91 
92  /// Base data structure tag.
94  { };
95 
96  /// Basic string container, inclusive of strings, ropes, etc.
97  struct string_tag : public container_tag { };
98 
99  /// Basic sequence.
100  struct sequence_tag : public container_tag { };
101 
102  /// Basic associative-container.
104 
105  /// Basic hash.
107 
108  /// Collision-chaining hash.
109  struct cc_hash_tag : public basic_hash_tag { };
110 
111  /// General-probing hash.
112  struct gp_hash_tag : public basic_hash_tag { };
113 
114  /// Basic tree.
116 
117  /// tree.
118  struct tree_tag : public basic_tree_tag { };
119 
120  /// Red-black tree.
121  struct rb_tree_tag : public tree_tag { };
122 
123  /// Splay tree.
124  struct splay_tree_tag : public tree_tag { };
125 
126  /// Ordered-vector tree.
127  struct ov_tree_tag : public tree_tag { };
128 
129  /// trie.
130  struct trie_tag : public basic_tree_tag { };
131 
132  /// PATRICIA trie.
133  struct pat_trie_tag : public trie_tag { };
134 
135  /// List-update.
137 
138  /// Basic priority-queue.
139  struct priority_queue_tag : public container_tag { };
140 
141  /// Pairing-heap.
143 
144  /// Binomial-heap.
146 
147  /// Redundant-counter binomial-heap.
149 
150  /// Binary-heap (array-based).
151  struct binary_heap_tag : public priority_queue_tag { };
152 
153  /// Thin heap.
154  struct thin_heap_tag : public priority_queue_tag { };
155 
156 
157  /// Base traits type for containers.
158  template<typename Tag>
160 
161  template<>
163  {
164  typedef cc_hash_tag container_category;
165  typedef point_invalidation_guarantee invalidation_guarantee;
166 
167  enum
168  {
169  order_preserving = false,
170  erase_can_throw = false,
171  split_join_can_throw = false,
172  reverse_iteration = false
173  };
174  };
175 
176  template<>
177  struct container_traits_base<gp_hash_tag>
178  {
179  typedef gp_hash_tag container_category;
180  typedef basic_invalidation_guarantee invalidation_guarantee;
181 
182  enum
183  {
184  order_preserving = false,
185  erase_can_throw = false,
186  split_join_can_throw = false,
187  reverse_iteration = false
188  };
189  };
190 
191  template<>
192  struct container_traits_base<rb_tree_tag>
193  {
194  typedef rb_tree_tag container_category;
195  typedef range_invalidation_guarantee invalidation_guarantee;
196 
197  enum
198  {
199  order_preserving = true,
200  erase_can_throw = false,
201  split_join_can_throw = false,
202  reverse_iteration = true
203  };
204  };
205 
206  template<>
207  struct container_traits_base<splay_tree_tag>
208  {
209  typedef splay_tree_tag container_category;
210  typedef range_invalidation_guarantee invalidation_guarantee;
211 
212  enum
213  {
214  order_preserving = true,
215  erase_can_throw = false,
216  split_join_can_throw = false,
217  reverse_iteration = true
218  };
219  };
220 
221  template<>
222  struct container_traits_base<ov_tree_tag>
223  {
224  typedef ov_tree_tag container_category;
225  typedef basic_invalidation_guarantee invalidation_guarantee;
226 
227  enum
228  {
229  order_preserving = true,
230  erase_can_throw = true,
231  split_join_can_throw = true,
232  reverse_iteration = false
233  };
234  };
235 
236  template<>
237  struct container_traits_base<pat_trie_tag>
238  {
239  typedef pat_trie_tag container_category;
240  typedef range_invalidation_guarantee invalidation_guarantee;
241 
242  enum
243  {
244  order_preserving = true,
245  erase_can_throw = false,
246  split_join_can_throw = true,
247  reverse_iteration = true
248  };
249  };
250 
251  template<>
252  struct container_traits_base<list_update_tag>
253  {
254  typedef list_update_tag container_category;
255  typedef point_invalidation_guarantee invalidation_guarantee;
256 
257  enum
258  {
259  order_preserving = false,
260  erase_can_throw = false,
261  split_join_can_throw = false,
262  reverse_iteration = false
263  };
264  };
265 
266 
267  template<>
268  struct container_traits_base<pairing_heap_tag>
269  {
270  typedef pairing_heap_tag container_category;
271  typedef point_invalidation_guarantee invalidation_guarantee;
272 
273  enum
274  {
275  order_preserving = false,
276  erase_can_throw = false,
277  split_join_can_throw = false,
278  reverse_iteration = false
279  };
280  };
281 
282  template<>
283  struct container_traits_base<thin_heap_tag>
284  {
285  typedef thin_heap_tag container_category;
286  typedef point_invalidation_guarantee invalidation_guarantee;
287 
288  enum
289  {
290  order_preserving = false,
291  erase_can_throw = false,
292  split_join_can_throw = false,
293  reverse_iteration = false
294  };
295  };
296 
297  template<>
298  struct container_traits_base<binomial_heap_tag>
299  {
300  typedef binomial_heap_tag container_category;
301  typedef point_invalidation_guarantee invalidation_guarantee;
302 
303  enum
304  {
305  order_preserving = false,
306  erase_can_throw = false,
307  split_join_can_throw = false,
308  reverse_iteration = false
309  };
310  };
311 
312  template<>
313  struct container_traits_base<rc_binomial_heap_tag>
314  {
315  typedef rc_binomial_heap_tag container_category;
316  typedef point_invalidation_guarantee invalidation_guarantee;
317 
318  enum
319  {
320  order_preserving = false,
321  erase_can_throw = false,
322  split_join_can_throw = false,
323  reverse_iteration = false
324  };
325  };
326 
327  template<>
328  struct container_traits_base<binary_heap_tag>
329  {
330  typedef binary_heap_tag container_category;
331  typedef basic_invalidation_guarantee invalidation_guarantee;
332 
333  enum
334  {
335  order_preserving = false,
336  erase_can_throw = false,
337  split_join_can_throw = true,
338  reverse_iteration = false
339  };
340  };
341 
342 
343  /// container_traits
344  // See Matt Austern for the name, S. Meyers MEFC++ #2, others.
345  template<typename Cntnr>
347  : public container_traits_base<typename Cntnr::container_category>
348  {
349  typedef Cntnr container_type;
350  typedef typename Cntnr::container_category container_category;
352  typedef typename base_type::invalidation_guarantee invalidation_guarantee;
353 
354  enum
355  {
356  order_preserving = base_type::order_preserving,
357  erase_can_throw = base_type::erase_can_throw,
358  split_join_can_throw = base_type::split_join_can_throw,
359  reverse_iteration = base_type::reverse_iteration
360  };
361  };
362 } // namespace __gnu_pbds
363 
364 #endif