libstdc++
assoc_container.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005, 2006, 2009, 2010, 2011 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 assoc_container.hpp
38  * Contains associative containers.
39  */
40 
41 #ifndef PB_DS_ASSOC_CNTNR_HPP
42 #define PB_DS_ASSOC_CNTNR_HPP
43 
44 #include <bits/c++config.h>
45 #include <ext/typelist.h>
50 
51 namespace __gnu_pbds
52 {
53  /**
54  * @defgroup containers-pbds Containers
55  * @ingroup pbds
56  * @{
57  */
58 
59  /**
60  * @defgroup hash-based
61  * @ingroup containers-pbds
62  * @{
63  */
64 #define PB_DS_HASH_BASE \
65  detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, \
66  typename __gnu_cxx::typelist::append< \
67  typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, \
68  detail::integral_constant<int, Store_Hash> >::type, Policy_Tl>::type>::type
69 
70  /**
71  * @defgroup hash-detail Base and Policy Classes
72  * @ingroup hash-based
73  */
74 
75  /**
76  * A hashed container abstraction.
77  *
78  * @tparam Key Key type.
79  * @tparam Mapped Map type.
80  * @tparam Hash_Fn Hashing functor.
81  * @tparam Eq_Fn Equal functor.
82  * @tparam Resize_Policy Resizes hash.
83  * @tparam Store_Hash Indicates whether the hash value
84  * will be stored along with each key.
85  * @tparam Tag Instantiating data structure type,
86  * see container_tag.
87  * @tparam Policy_TL Policy typelist.
88  * @tparam _Alloc Allocator type.
89  *
90  * Base is dispatched at compile time via Tag, from the following
91  * choices: cc_hash_tag, gp_hash_tag, and descendants of basic_hash_tag.
92  *
93  * Base choices are: detail::cc_ht_map, detail::gp_ht_map
94  */
95  template<typename Key,
96  typename Mapped,
97  typename Hash_Fn,
98  typename Eq_Fn,
99  typename Resize_Policy,
100  bool Store_Hash,
101  typename Tag,
102  typename Policy_Tl,
103  typename _Alloc>
104  class basic_hash_table : public PB_DS_HASH_BASE
105  {
106  private:
107  typedef typename PB_DS_HASH_BASE base_type;
108 
109  public:
110  virtual
111  ~basic_hash_table() { }
112 
113  protected:
114  basic_hash_table() { }
115 
116  basic_hash_table(const basic_hash_table& other)
117  : base_type((const base_type&)other) { }
118 
119  template<typename T0>
120  basic_hash_table(T0 t0) : base_type(t0) { }
121 
122  template<typename T0, typename T1>
123  basic_hash_table(T0 t0, T1 t1) : base_type(t0, t1) { }
124 
125  template<typename T0, typename T1, typename T2>
126  basic_hash_table(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { }
127 
128  template<typename T0, typename T1, typename T2, typename T3>
129  basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3)
130  : base_type(t0, t1, t2, t3) { }
131 
132  template<typename T0, typename T1, typename T2, typename T3, typename T4>
133  basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4)
134  : base_type(t0, t1, t2, t3, t4) { }
135 
136  template<typename T0, typename T1, typename T2, typename T3, typename T4,
137  typename T5>
138  basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5)
139  : base_type(t0, t1, t2, t3, t4, t5) { }
140 
141  template<typename T0, typename T1, typename T2, typename T3, typename T4,
142  typename T5, typename T6>
143  basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6)
144  : base_type(t0, t1, t2, t3, t4, t5, t6) { }
145 
146  template<typename T0, typename T1, typename T2, typename T3, typename T4,
147  typename T5, typename T6, typename T7>
148  basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6, T7 t7)
149  : base_type(t0, t1, t2, t3, t4, t5, t6, t7) { }
150 
151  template<typename T0, typename T1, typename T2, typename T3, typename T4,
152  typename T5, typename T6, typename T7, typename T8>
153  basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6,
154  T7 t7, T8 t8)
155  : base_type(t0, t1, t2, t3, t4, t5, t6, t7, t8)
156  { }
157 
158  private:
159  basic_hash_table&
160  operator=(const base_type&);
161  };
162 
163 #undef PB_DS_HASH_BASE
164 
165 
166 #define PB_DS_CC_HASH_BASE \
167  basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
168  cc_hash_tag, \
169  typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, _Alloc>
170 
171 
172  /**
173  * A collision-chaining hash-based associative container.
174  *
175  * @tparam Key Key type.
176  * @tparam Mapped Map type.
177  * @tparam Hash_Fn Hashing functor.
178  * @tparam Eq_Fn Equal functor.
179  * @tparam Comb_Hash_Fn Combining hash functor.
180  * If Hash_Fn is not null_type, then this
181  * is the ranged-hash functor; otherwise,
182  * this is the range-hashing functor.
183  * XXX(See Design::Hash-Based Containers::Hash Policies.)
184  * @tparam Resize_Policy Resizes hash.
185  * @tparam Store_Hash Indicates whether the hash value
186  * will be stored along with each key.
187  * If Hash_Fn is null_type, then the
188  * container will not compile if this
189  * value is true
190  * @tparam _Alloc Allocator type.
191  *
192  * Base tag choices are: cc_hash_tag.
193  *
194  * Base is basic_hash_table.
195  */
196  template<typename Key,
197  typename Mapped,
198  typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
199  typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
200  typename Comb_Hash_Fn = detail::default_comb_hash_fn::type,
201  typename Resize_Policy = typename detail::default_resize_policy<Comb_Hash_Fn>::type,
202  bool Store_Hash = detail::default_store_hash,
203  typename _Alloc = std::allocator<char> >
204  class cc_hash_table : public PB_DS_CC_HASH_BASE
205  {
206  private:
207  typedef PB_DS_CC_HASH_BASE base_type;
208 
209  public:
211  typedef Hash_Fn hash_fn;
212  typedef Eq_Fn eq_fn;
213  typedef Resize_Policy resize_policy;
214  typedef Comb_Hash_Fn comb_hash_fn;
215 
216  /// Default constructor.
218 
219  /// Constructor taking some policy objects. r_hash_fn will be
220  /// copied by the Hash_Fn object of the container object.
221  cc_hash_table(const hash_fn& h)
222  : base_type(h) { }
223 
224  /// Constructor taking some policy objects. r_hash_fn will be
225  /// copied by the hash_fn object of the container object, and
226  /// r_eq_fn will be copied by the eq_fn object of the container
227  /// object.
228  cc_hash_table(const hash_fn& h, const eq_fn& e)
229  : base_type(h, e) { }
230 
231  /// Constructor taking some policy objects. r_hash_fn will be
232  /// copied by the hash_fn object of the container object, r_eq_fn
233  /// will be copied by the eq_fn object of the container object,
234  /// and r_comb_hash_fn will be copied by the comb_hash_fn object
235  /// of the container object.
236  cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch)
237  : base_type(h, e, ch) { }
238 
239  /// Constructor taking some policy objects. r_hash_fn will be
240  /// copied by the hash_fn object of the container object, r_eq_fn
241  /// will be copied by the eq_fn object of the container object,
242  /// r_comb_hash_fn will be copied by the comb_hash_fn object of
243  /// the container object, and r_resize_policy will be copied by
244  /// the resize_policy object of the container object.
245  cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch,
246  const resize_policy& rp)
247  : base_type(h, e, ch, rp) { }
248 
249  /// Constructor taking __iterators to a range of value_types. The
250  /// value_types between first_it and last_it will be inserted into
251  /// the container object.
252  template<typename It>
253  cc_hash_table(It first, It last)
254  { base_type::copy_from_range(first, last); }
255 
256  /// Constructor taking __iterators to a range of value_types and
257  /// some policy objects. The value_types between first_it and
258  /// last_it will be inserted into the container object.
259  template<typename It>
260  cc_hash_table(It first, It last, const hash_fn& h)
261  : base_type(h)
262  { this->copy_from_range(first, last); }
263 
264  /// Constructor taking __iterators to a range of value_types and
265  /// some policy objects The value_types between first_it and
266  /// last_it will be inserted into the container object. r_hash_fn
267  /// will be copied by the hash_fn object of the container object,
268  /// and r_eq_fn will be copied by the eq_fn object of the
269  /// container object.
270  template<typename It>
271  cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
272  : base_type(h, e)
273  { this->copy_from_range(first, last); }
274 
275  /// Constructor taking __iterators to a range of value_types and
276  /// some policy objects The value_types between first_it and
277  /// last_it will be inserted into the container object. r_hash_fn
278  /// will be copied by the hash_fn object of the container object,
279  /// r_eq_fn will be copied by the eq_fn object of the container
280  /// object, and r_comb_hash_fn will be copied by the comb_hash_fn
281  /// object of the container object.
282  template<typename It>
283  cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
284  const comb_hash_fn& ch)
285  : base_type(h, e, ch)
286  { this->copy_from_range(first, last); }
287 
288  /// Constructor taking __iterators to a range of value_types and
289  /// some policy objects The value_types between first_it and
290  /// last_it will be inserted into the container object. r_hash_fn
291  /// will be copied by the hash_fn object of the container object,
292  /// r_eq_fn will be copied by the eq_fn object of the container
293  /// object, r_comb_hash_fn will be copied by the comb_hash_fn
294  /// object of the container object, and r_resize_policy will be
295  /// copied by the resize_policy object of the container object.
296  template<typename It>
297  cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
298  const comb_hash_fn& ch, const resize_policy& rp)
299  : base_type(h, e, ch, rp)
300  { this->copy_from_range(first, last); }
301 
302  cc_hash_table(const cc_hash_table& other)
303  : base_type((const base_type&)other)
304  { }
305 
306  virtual
307  ~cc_hash_table() { }
308 
310  operator=(const cc_hash_table& other)
311  {
312  if (this != &other)
313  {
314  cc_hash_table tmp(other);
315  swap(tmp);
316  }
317  return *this;
318  }
319 
320  void
321  swap(cc_hash_table& other)
322  { base_type::swap(other); }
323  };
324 
325 #undef PB_DS_CC_HASH_BASE
326 
327 
328 #define PB_DS_GP_HASH_BASE \
329  basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
330  gp_hash_tag, \
331  typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, _Alloc>
332 
333 
334  /**
335  * A general-probing hash-based associative container.
336  *
337  * @tparam Key Key type.
338  * @tparam Mapped Map type.
339  * @tparam Hash_Fn Hashing functor.
340  * @tparam Eq_Fn Equal functor.
341  * @tparam Comb_Probe_Fn Combining probe functor.
342  * If Hash_Fn is not null_type, then this
343  * is the ranged-probe functor; otherwise,
344  * this is the range-hashing functor.
345  * XXX See Design::Hash-Based Containers::Hash Policies.
346  * @tparam Probe_Fn Probe functor.
347  * @tparam Resize_Policy Resizes hash.
348  * @tparam Store_Hash Indicates whether the hash value
349  * will be stored along with each key.
350  * If Hash_Fn is null_type, then the
351  * container will not compile if this
352  * value is true
353  * @tparam _Alloc Allocator type.
354  *
355  * Base tag choices are: gp_hash_tag.
356  *
357  * Base is basic_hash_table.
358  */
359  template<typename Key,
360  typename Mapped,
361  typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
362  typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
363  typename Comb_Probe_Fn = detail::default_comb_hash_fn::type,
364  typename Probe_Fn = typename detail::default_probe_fn<Comb_Probe_Fn>::type,
365  typename Resize_Policy = typename detail::default_resize_policy<Comb_Probe_Fn>::type,
366  bool Store_Hash = detail::default_store_hash,
367  typename _Alloc = std::allocator<char> >
368  class gp_hash_table : public PB_DS_GP_HASH_BASE
369  {
370  private:
371  typedef PB_DS_GP_HASH_BASE base_type;
372 
373  public:
375  typedef Hash_Fn hash_fn;
376  typedef Eq_Fn eq_fn;
377  typedef Comb_Probe_Fn comb_probe_fn;
378  typedef Probe_Fn probe_fn;
379  typedef Resize_Policy resize_policy;
380 
381  /// Default constructor.
383 
384  /// Constructor taking some policy objects. r_hash_fn will be
385  /// copied by the hash_fn object of the container object.
386  gp_hash_table(const hash_fn& h)
387  : base_type(h) { }
388 
389  /// Constructor taking some policy objects. r_hash_fn will be
390  /// copied by the hash_fn object of the container object, and
391  /// r_eq_fn will be copied by the eq_fn object of the container
392  /// object.
393  gp_hash_table(const hash_fn& h, const eq_fn& e)
394  : base_type(h, e) { }
395 
396  /// Constructor taking some policy objects. r_hash_fn will be
397  /// copied by the hash_fn object of the container object, r_eq_fn
398  /// will be copied by the eq_fn object of the container object,
399  /// and r_comb_probe_fn will be copied by the comb_probe_fn object
400  /// of the container object.
401  gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp)
402  : base_type(h, e, cp) { }
403 
404  /// Constructor taking some policy objects. r_hash_fn will be
405  /// copied by the hash_fn object of the container object, r_eq_fn
406  /// will be copied by the eq_fn object of the container object,
407  /// r_comb_probe_fn will be copied by the comb_probe_fn object of
408  /// the container object, and r_probe_fn will be copied by the
409  /// probe_fn object of the container object.
410  gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
411  const probe_fn& p)
412  : base_type(h, e, cp, p) { }
413 
414  /// Constructor taking some policy objects. r_hash_fn will be
415  /// copied by the hash_fn object of the container object, r_eq_fn
416  /// will be copied by the eq_fn object of the container object,
417  /// r_comb_probe_fn will be copied by the comb_probe_fn object of
418  /// the container object, r_probe_fn will be copied by the
419  /// probe_fn object of the container object, and r_resize_policy
420  /// will be copied by the Resize_Policy object of the container
421  /// object.
422  gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
423  const probe_fn& p, const resize_policy& rp)
424  : base_type(h, e, cp, p, rp) { }
425 
426  /// Constructor taking __iterators to a range of value_types. The
427  /// value_types between first_it and last_it will be inserted into
428  /// the container object.
429  template<typename It>
430  gp_hash_table(It first, It last)
431  { base_type::copy_from_range(first, last); }
432 
433  /// Constructor taking __iterators to a range of value_types and
434  /// some policy objects. The value_types between first_it and
435  /// last_it will be inserted into the container object. r_hash_fn
436  /// will be copied by the hash_fn object of the container object.
437  template<typename It>
438  gp_hash_table(It first, It last, const hash_fn& h)
439  : base_type(h)
440  { base_type::copy_from_range(first, last); }
441 
442  /// Constructor taking __iterators to a range of value_types and
443  /// some policy objects. The value_types between first_it and
444  /// last_it will be inserted into the container object. r_hash_fn
445  /// will be copied by the hash_fn object of the container object,
446  /// and r_eq_fn will be copied by the eq_fn object of the
447  /// container object.
448  template<typename It>
449  gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
450  : base_type(h, e)
451  { base_type::copy_from_range(first, last); }
452 
453  /// Constructor taking __iterators to a range of value_types and
454  /// some policy objects. The value_types between first_it and
455  /// last_it will be inserted into the container object. r_hash_fn
456  /// will be copied by the hash_fn object of the container object,
457  /// r_eq_fn will be copied by the eq_fn object of the container
458  /// object, and r_comb_probe_fn will be copied by the
459  /// comb_probe_fn object of the container object.
460  template<typename It>
461  gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
462  const comb_probe_fn& cp)
463  : base_type(h, e, cp)
464  { base_type::copy_from_range(first, last); }
465 
466  /// Constructor taking __iterators to a range of value_types and
467  /// some policy objects. The value_types between first_it and
468  /// last_it will be inserted into the container object. r_hash_fn
469  /// will be copied by the hash_fn object of the container object,
470  /// r_eq_fn will be copied by the eq_fn object of the container
471  /// object, r_comb_probe_fn will be copied by the comb_probe_fn
472  /// object of the container object, and r_probe_fn will be copied
473  /// by the probe_fn object of the container object.
474  template<typename It>
475  gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
476  const comb_probe_fn& cp, const probe_fn& p)
477  : base_type(h, e, cp, p)
478  { base_type::copy_from_range(first, last); }
479 
480  /// Constructor taking __iterators to a range of value_types and
481  /// some policy objects. The value_types between first_it and
482  /// last_it will be inserted into the container object. r_hash_fn
483  /// will be copied by the hash_fn object of the container object,
484  /// r_eq_fn will be copied by the eq_fn object of the container
485  /// object, r_comb_probe_fn will be copied by the comb_probe_fn
486  /// object of the container object, r_probe_fn will be copied by
487  /// the probe_fn object of the container object, and
488  /// r_resize_policy will be copied by the resize_policy object of
489  /// the container object.
490  template<typename It>
491  gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
492  const comb_probe_fn& cp, const probe_fn& p,
493  const resize_policy& rp)
494  : base_type(h, e, cp, p, rp)
495  { base_type::copy_from_range(first, last); }
496 
497  gp_hash_table(const gp_hash_table& other)
498  : base_type((const base_type&)other)
499  { }
500 
501  virtual
502  ~gp_hash_table() { }
503 
505  operator=(const gp_hash_table& other)
506  {
507  if (this != &other)
508  {
509  gp_hash_table tmp(other);
510  swap(tmp);
511  }
512  return *this;
513  }
514 
515  void
516  swap(gp_hash_table& other)
517  { base_type::swap(other); }
518  };
519  //@} hash-based
520 #undef PB_DS_GP_HASH_BASE
521 
522 
523  /**
524  * @defgroup branch-based
525  * @ingroup containers-pbds
526  * @{
527  */
528 #define PB_DS_BRANCH_BASE \
529  detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, Policy_Tl>::type
530 
531  /**
532  * @defgroup branch-detail Base and Policy Classes
533  * @ingroup branch-based
534  */
535 
536  /**
537  * A branched, tree-like (tree, trie) container abstraction.
538  *
539  * @tparam Key Key type.
540  * @tparam Mapped Map type.
541  * @tparam Tag Instantiating data structure type,
542  * see container_tag.
543  * @tparam Node_Update Updates nodes, restores invariants.
544  * @tparam Policy_TL Policy typelist.
545  * @tparam _Alloc Allocator type.
546  *
547  * Base is dispatched at compile time via Tag, from the following
548  * choices: tree_tag, trie_tag, and their descendants.
549  *
550  * Base choices are: detail::ov_tree_map, detail::rb_tree_map,
551  * detail::splay_tree_map, and detail::pat_trie_map.
552  */
553  template<typename Key, typename Mapped, typename Tag,
554  typename Node_Update, typename Policy_Tl, typename _Alloc>
555  class basic_branch : public PB_DS_BRANCH_BASE
556  {
557  private:
558  typedef typename PB_DS_BRANCH_BASE base_type;
559 
560  public:
561  typedef Node_Update node_update;
562 
563  virtual
564  ~basic_branch() { }
565 
566  protected:
567  basic_branch() { }
568 
569  basic_branch(const basic_branch& other)
570  : base_type((const base_type&)other) { }
571 
572  template<typename T0>
573  basic_branch(T0 t0) : base_type(t0) { }
574 
575  template<typename T0, typename T1>
576  basic_branch(T0 t0, T1 t1) : base_type(t0, t1) { }
577 
578  template<typename T0, typename T1, typename T2>
579  basic_branch(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { }
580 
581  template<typename T0, typename T1, typename T2, typename T3>
582  basic_branch(T0 t0, T1 t1, T2 t2, T3 t3)
583  : base_type(t0, t1, t2, t3) { }
584 
585  template<typename T0, typename T1, typename T2, typename T3, typename T4>
586  basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4)
587  : base_type(t0, t1, t2, t3, t4) { }
588 
589  template<typename T0, typename T1, typename T2, typename T3, typename T4,
590  typename T5>
591  basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5)
592  : base_type(t0, t1, t2, t3, t4, t5) { }
593 
594  template<typename T0, typename T1, typename T2, typename T3, typename T4,
595  typename T5, typename T6>
596  basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6)
597  : base_type(t0, t1, t2, t3, t4, t5, t6) { }
598  };
599 #undef PB_DS_BRANCH_BASE
600 
601 
602 #define PB_DS_TREE_NODE_AND_IT_TRAITS \
603  detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag,_Alloc>
604 
605 #define PB_DS_TREE_BASE \
606  basic_branch<Key,Mapped, Tag, \
607  typename PB_DS_TREE_NODE_AND_IT_TRAITS::node_update, \
608  typename __gnu_cxx::typelist::create2<Cmp_Fn, \
609  PB_DS_TREE_NODE_AND_IT_TRAITS>::type, _Alloc>
610 
611 
612  /**
613  * A tree-based container.
614  *
615  * @tparam Key Key type.
616  * @tparam Mapped Map type.
617  * @tparam Cmp_Fn Comparison functor.
618  * @tparam Tag Instantiating data structure type,
619  * see container_tag.
620  * @tparam Node_Update Updates nodes,
621  * restores invariants when invalidated.
622  * XXX See design::tree-based-containers::node invariants.
623  * @tparam _Alloc Allocator type.
624  *
625  * Base tag choices are: ov_tree_tag, rb_tree_tag, splay_tree_tag.
626  *
627  * Base is basic_branch.
628  */
629  template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>,
630  typename Tag = rb_tree_tag,
631  template<typename Node_CItr, typename Node_Itr,
632  typename Cmp_Fn_, typename _Alloc_>
633  class Node_Update = null_node_update,
634  typename _Alloc = std::allocator<char> >
635  class tree : public PB_DS_TREE_BASE
636  {
637  private:
638  typedef PB_DS_TREE_BASE base_type;
639 
640  public:
641  /// Comparison functor type.
642  typedef Cmp_Fn cmp_fn;
643 
644  tree() { }
645 
646  /// Constructor taking some policy objects. r_cmp_fn will be
647  /// copied by the Cmp_Fn object of the container object.
648  tree(const cmp_fn& c)
649  : base_type(c) { }
650 
651  /// Constructor taking __iterators to a range of value_types. The
652  /// value_types between first_it and last_it will be inserted into
653  /// the container object.
654  template<typename It>
655  tree(It first, It last)
656  { base_type::copy_from_range(first, last); }
657 
658  /// Constructor taking __iterators to a range of value_types and
659  /// some policy objects The value_types between first_it and
660  /// last_it will be inserted into the container object. r_cmp_fn
661  /// will be copied by the cmp_fn object of the container object.
662  template<typename It>
663  tree(It first, It last, const cmp_fn& c)
664  : base_type(c)
665  { base_type::copy_from_range(first, last); }
666 
667  tree(const tree& other)
668  : base_type((const base_type&)other) { }
669 
670  virtual
671  ~tree() { }
672 
673  tree&
674  operator=(const tree& other)
675  {
676  if (this != &other)
677  {
678  tree tmp(other);
679  swap(tmp);
680  }
681  return *this;
682  }
683 
684  void
685  swap(tree& other)
686  { base_type::swap(other); }
687  };
688 
689 #undef PB_DS_TREE_BASE
690 #undef PB_DS_TREE_NODE_AND_IT_TRAITS
691 
692 
693 #define PB_DS_TRIE_NODE_AND_IT_TRAITS \
694  detail::trie_traits<Key,Mapped,_ATraits,Node_Update,Tag,_Alloc>
695 
696 #define PB_DS_TRIE_BASE \
697  basic_branch<Key,Mapped,Tag, \
698  typename PB_DS_TRIE_NODE_AND_IT_TRAITS::node_update, \
699  typename __gnu_cxx::typelist::create2<_ATraits, \
700  PB_DS_TRIE_NODE_AND_IT_TRAITS >::type, _Alloc>
701 
702 
703  /**
704  * A trie-based container.
705  *
706  * @tparam Key Key type.
707  * @tparam Mapped Map type.
708  * @tparam _ATraits Element access traits.
709  * @tparam Tag Instantiating data structure type,
710  * see container_tag.
711  * @tparam Node_Update Updates trie nodes,
712  * restores invariants when invalidated.
713  * XXX See design::tree-based-containers::node invariants.
714  * @tparam _Alloc Allocator type.
715  *
716  * Base tag choice is pat_trie_tag.
717  *
718  * Base is basic_branch.
719  */
720  template<typename Key,
721  typename Mapped,
722  typename _ATraits = \
723  typename detail::default_trie_access_traits<Key>::type,
724  typename Tag = pat_trie_tag,
725  template<typename Node_CItr,
726  typename Node_Itr,
727  typename _ATraits_,
728  typename _Alloc_>
729  class Node_Update = null_node_update,
730  typename _Alloc = std::allocator<char> >
731  class trie : public PB_DS_TRIE_BASE
732  {
733  private:
734  typedef PB_DS_TRIE_BASE base_type;
735 
736  public:
737  /// Element access traits type.
738  typedef _ATraits access_traits;
739 
740  trie() { }
741 
742  /// Constructor taking some policy objects. r_access_traits will
743  /// be copied by the _ATraits object of the container object.
744  trie(const access_traits& t)
745  : base_type(t) { }
746 
747  /// Constructor taking __iterators to a range of value_types. The
748  /// value_types between first_it and last_it will be inserted into
749  /// the container object.
750  template<typename It>
751  trie(It first, It last)
752  { base_type::copy_from_range(first, last); }
753 
754  /// Constructor taking __iterators to a range of value_types and
755  /// some policy objects. The value_types between first_it and
756  /// last_it will be inserted into the container object.
757  template<typename It>
758  trie(It first, It last, const access_traits& t)
759  : base_type(t)
760  { base_type::copy_from_range(first, last); }
761 
762  trie(const trie& other)
763  : base_type((const base_type&)other) { }
764 
765  virtual
766  ~trie() { }
767 
768  trie&
769  operator=(const trie& other)
770  {
771  if (this != &other)
772  {
773  trie tmp(other);
774  swap(tmp);
775  }
776  return *this;
777  }
778 
779  void
780  swap(trie& other)
781  { base_type::swap(other); }
782  };
783  //@} branch-based
784 #undef PB_DS_TRIE_BASE
785 #undef PB_DS_TRIE_NODE_AND_IT_TRAITS
786 
787 
788  /**
789  * @defgroup list-based
790  * @ingroup containers-pbds
791  * @{
792  */
793 #define PB_DS_LU_BASE \
794  detail::container_base_dispatch<Key, Mapped, _Alloc, list_update_tag, \
795  typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type>::type
796 
797 
798  /**
799  * A list-update based associative container.
800  *
801  * @tparam Key Key type.
802  * @tparam Mapped Map type.
803  * @tparam Eq_Fn Equal functor.
804  * @tparam Update_Policy Update policy, determines when an element
805  * will be moved to the front of the list.
806  * @tparam _Alloc Allocator type.
807  *
808  * Base is detail::lu_map.
809  */
810  template<typename Key,
811  typename Mapped,
812  class Eq_Fn = typename detail::default_eq_fn<Key>::type,
813  class Update_Policy = detail::default_update_policy::type,
814  class _Alloc = std::allocator<char> >
815  class list_update : public PB_DS_LU_BASE
816  {
817  private:
818  typedef typename PB_DS_LU_BASE base_type;
819 
820  public:
822  typedef Eq_Fn eq_fn;
823  typedef Update_Policy update_policy;
824 
825  list_update() { }
826 
827  /// Constructor taking __iterators to a range of value_types. The
828  /// value_types between first_it and last_it will be inserted into
829  /// the container object.
830  template<typename It>
831  list_update(It first, It last)
832  { base_type::copy_from_range(first, last); }
833 
834  list_update(const list_update& other)
835  : base_type((const base_type&)other) { }
836 
837  virtual
838  ~list_update() { }
839 
840  list_update&
841  operator=(const list_update& other)
842  {
843  if (this !=& other)
844  {
845  list_update tmp(other);
846  swap(tmp);
847  }
848  return *this;
849  }
850 
851  void
852  swap(list_update& other)
853  { base_type::swap(other); }
854  };
855  //@} list-based
856 #undef PB_DS_LU_BASE
857 
858  // @} group containers-pbds
859 } // namespace __gnu_pbds
860 
861 #endif