]> rtime.felk.cvut.cz Git - l4.git/blob - l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.5/include/ext/pb_ds/assoc_container.hpp
update
[l4.git] / l4 / pkg / libstdc++-v3 / contrib / libstdc++-v3-4.5 / include / ext / pb_ds / assoc_container.hpp
1 // -*- C++ -*-
2
3 // Copyright (C) 2005, 2006, 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 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 <ext/typelist.h>
45 #include <ext/pb_ds/tag_and_trait.hpp>
46 #include <ext/pb_ds/detail/standard_policies.hpp>
47 #include <ext/pb_ds/detail/container_base_dispatch.hpp>
48 #include <ext/pb_ds/detail/basic_tree_policy/traits.hpp>
49
50 namespace __gnu_pbds
51 {
52   /** @defgroup pbds Policy-Based Data Structures
53    *  @ingroup extensions
54    *
55    *  This is a library of policy-based elementary data structures:
56    *  associative containers and priority queues. It is designed for
57    *  high-performance, flexibility, semantic safety, and conformance
58    *  to the corresponding containers in std (except for some points
59    *  where it differs by design).
60    *
61    *  For details, see: 
62    *  http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html
63    *
64    *  @{
65    */
66  
67 #define PB_DS_BASE_C_DEC \
68   detail::container_base_dispatch<Key, Mapped, Tag, Policy_Tl, Allocator>::type
69
70   /// An abstract basic associative container.
71   template<typename Key, 
72            typename Mapped, 
73            typename Tag, 
74            typename Policy_Tl, 
75            typename Allocator>
76   class container_base : public PB_DS_BASE_C_DEC
77   {
78   private:
79     typedef typename PB_DS_BASE_C_DEC                   base_type;
80
81   public:
82     typedef Tag                                         container_category;
83     typedef Allocator                                   allocator_type;
84     typedef typename allocator_type::size_type          size_type;
85     typedef typename allocator_type::difference_type    difference_type;
86
87     // key_type
88     typedef typename allocator_type::template rebind<Key>::other::value_type key_type;
89     typedef typename allocator_type::template rebind<key_type>::other key_rebind;
90     typedef typename key_rebind::reference              key_reference;
91     typedef typename key_rebind::const_reference        const_key_reference;
92     typedef typename key_rebind::pointer                key_pointer;
93     typedef typename key_rebind::const_pointer          const_key_pointer;
94
95     // mapped_type
96     typedef Mapped                                      mapped_type;
97     typedef typename allocator_type::template rebind<mapped_type>::other mapped_rebind;
98     typedef typename mapped_rebind::reference           mapped_reference;
99     typedef typename mapped_rebind::const_reference     const_mapped_reference;
100     typedef typename mapped_rebind::pointer             mapped_pointer;
101     typedef typename mapped_rebind::const_pointer       const_mapped_pointer;
102
103     // value_type
104     typedef typename base_type::value_type              value_type;
105     typedef typename allocator_type::template rebind<value_type>::other value_rebind;
106     typedef typename value_rebind::reference            reference;
107     typedef typename value_rebind::const_reference      const_reference;
108     typedef typename value_rebind::pointer              pointer;
109     typedef typename value_rebind::const_pointer        const_pointer;
110
111     // iterators
112     typedef typename base_type::iterator                iterator;
113     typedef typename base_type::const_iterator          const_iterator;
114     typedef typename base_type::point_iterator          point_iterator;
115     typedef typename base_type::const_point_iterator    const_point_iterator;
116
117     virtual
118     ~container_base() { }
119
120   protected:
121 #define PB_DS_CLASS_NAME                container_base
122 #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
123 #undef PB_DS_CLASS_NAME
124   };
125
126 #undef PB_DS_BASE_C_DEC
127
128
129 #define PB_DS_BASE_C_DEC \
130   container_base<Key, Mapped, Tag, typename __gnu_cxx::typelist::append< \
131   typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, detail::integral_constant<int, Store_Hash> >::type, Policy_TL>::type, Allocator>
132
133   /// An abstract basic hash-based associative container.
134   template<typename Key,
135            typename Mapped,
136            typename Hash_Fn,
137            typename Eq_Fn,
138            typename Resize_Policy,
139            bool Store_Hash,
140            typename Tag,
141            typename Policy_TL,
142            typename Allocator>
143   class basic_hash_table : public PB_DS_BASE_C_DEC
144   {
145   private:
146     typedef PB_DS_BASE_C_DEC base_type;
147
148   public:
149     virtual
150     ~basic_hash_table() { }
151
152   protected:
153 #define PB_DS_CLASS_NAME basic_hash_table
154 #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
155 #undef PB_DS_CLASS_NAME
156
157   private:
158     basic_hash_table& 
159     operator=(const base_type&);
160   };
161
162 #undef PB_DS_BASE_C_DEC
163
164
165 #define PB_DS_BASE_C_DEC \
166   basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
167                    cc_hash_tag, \
168           typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, Allocator>
169
170   /// A concrete collision-chaining hash-based associative container.
171   template<typename Key,
172            typename Mapped,
173            typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
174            typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
175            typename Comb_Hash_Fn = detail::default_comb_hash_fn::type,
176            typename Resize_Policy = typename detail::default_resize_policy<Comb_Hash_Fn>::type,
177            bool Store_Hash = detail::default_store_hash,
178            typename Allocator = std::allocator<char> >
179   class cc_hash_table :  public PB_DS_BASE_C_DEC
180   {
181   private:
182     typedef PB_DS_BASE_C_DEC    base_type;
183
184   public:
185     typedef Hash_Fn             hash_fn;
186     typedef Eq_Fn               eq_fn;
187     typedef Resize_Policy       resize_policy;
188     typedef Comb_Hash_Fn        comb_hash_fn;
189
190     // Default constructor.
191     cc_hash_table() { }
192
193     // Constructor taking some policy objects. r_hash_fn will be
194     // copied by the Hash_Fn object of the container object.
195     cc_hash_table(const hash_fn& h) 
196     : base_type(h) { }
197
198     // Constructor taking some policy objects. r_hash_fn will be
199     // copied by the hash_fn object of the container object, and
200     // r_eq_fn will be copied by the eq_fn object of the container
201     // object.
202     cc_hash_table(const hash_fn& h, const eq_fn& e)
203     : base_type(h, e) { }
204
205     // Constructor taking some policy objects. r_hash_fn will be
206     // copied by the hash_fn object of the container object, r_eq_fn
207     // will be copied by the eq_fn object of the container object, and
208     // r_comb_hash_fn will be copied by the comb_hash_fn object of the
209     // container object.
210     cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch)
211     : base_type(h, e, ch) { }
212
213     // Constructor taking some policy objects. r_hash_fn will be
214     // copied by the hash_fn object of the container object, r_eq_fn
215     // will be copied by the eq_fn object of the container object,
216     // r_comb_hash_fn will be copied by the comb_hash_fn object of the
217     // container object, and r_resize_policy will be copied by the
218     // resize_policy object of the container object.
219     cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch, 
220                   const resize_policy& rp)    
221     : base_type(h, e, ch, rp) { }
222
223     // Constructor taking __iterators to a range of value_types. The
224     // value_types between first_it and last_it will be inserted into
225     // the container object.
226     template<typename It>
227     cc_hash_table(It first, It last)
228     { base_type::copy_from_range(first, last); }
229
230     // Constructor taking __iterators to a range of value_types and
231     // some policy objects. The value_types between first_it and
232     // last_it will be inserted into the container object.
233     template<typename It>
234     cc_hash_table(It first, It last, const hash_fn& h)
235     : base_type(h)
236     { copy_from_range(first, last); }
237
238     // Constructor taking __iterators to a range of value_types and
239     // some policy objects The value_types between first_it and
240     // last_it will be inserted into the container object. r_hash_fn
241     // will be copied by the hash_fn object of the container object,
242     // and r_eq_fn will be copied by the eq_fn object of the container
243     // object.
244     template<typename It>
245     cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
246     : base_type(h, e)
247     { copy_from_range(first, last); }
248
249     // Constructor taking __iterators to a range of value_types and
250     // some policy objects The value_types between first_it and
251     // last_it will be inserted into the container object. r_hash_fn
252     // will be copied by the hash_fn object of the container object,
253     // r_eq_fn will be copied by the eq_fn object of the container
254     // object, and r_comb_hash_fn will be copied by the comb_hash_fn
255     // object of the container object.
256     template<typename It>
257     cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
258                   const comb_hash_fn& ch)
259     : base_type(h, e, ch)
260     { copy_from_range(first, last); }
261
262     // Constructor taking __iterators to a range of value_types and
263     // some policy objects The value_types between first_it and
264     // last_it will be inserted into the container object. r_hash_fn
265     // will be copied by the hash_fn object of the container object,
266     // r_eq_fn will be copied by the eq_fn object of the container
267     // object, r_comb_hash_fn will be copied by the comb_hash_fn
268     // object of the container object, and r_resize_policy will be
269     // copied by the resize_policy object of the container object.
270     template<typename It>
271     cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 
272                   const comb_hash_fn& ch, const resize_policy& rp)
273     : base_type(h, e, ch, rp)
274     { copy_from_range(first, last); }
275
276     cc_hash_table(const cc_hash_table& other)
277     : base_type((const base_type&)other)
278     { }
279
280     virtual
281     ~cc_hash_table() { }
282
283     cc_hash_table& 
284     operator=(const cc_hash_table& other)
285     {
286       if (this != &other)
287         {
288           cc_hash_table tmp(other);
289           swap(tmp);
290         }
291       return *this;
292     }
293
294     void
295     swap(cc_hash_table& other)
296     { base_type::swap(other); }
297   };
298
299 #undef PB_DS_BASE_C_DEC
300
301
302 #define PB_DS_BASE_C_DEC \
303   basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
304                    gp_hash_tag, \
305                    typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, Allocator>
306
307   /// A concrete general-probing hash-based associative container.
308   template<typename Key,
309            typename Mapped,
310            typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
311            typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
312            typename Comb_Probe_Fn = detail::default_comb_hash_fn::type,
313            typename Probe_Fn = typename detail::default_probe_fn<Comb_Probe_Fn>::type,
314            typename Resize_Policy = typename detail::default_resize_policy<Comb_Probe_Fn>::type,
315            bool Store_Hash = detail::default_store_hash,
316            typename Allocator = std::allocator<char> >
317   class gp_hash_table : public PB_DS_BASE_C_DEC
318   {
319   private:
320     typedef PB_DS_BASE_C_DEC    base_type;
321
322   public:
323     typedef Hash_Fn             hash_fn;
324     typedef Eq_Fn               eq_fn;
325     typedef Comb_Probe_Fn       comb_probe_fn;
326     typedef Probe_Fn            probe_fn;
327     typedef Resize_Policy       resize_policy;
328
329     // Default constructor.
330     gp_hash_table() { }
331
332     // Constructor taking some policy objects. r_hash_fn will be
333     // copied by the hash_fn object of the container object.
334     gp_hash_table(const hash_fn& h)
335     : base_type(h) { }
336
337     // Constructor taking some policy objects. r_hash_fn will be
338     // copied by the hash_fn object of the container object, and
339     // r_eq_fn will be copied by the eq_fn object of the container
340     // object.
341     gp_hash_table(const hash_fn& h, const eq_fn& e)
342     : base_type(h, e) { }
343
344     // Constructor taking some policy objects. r_hash_fn will be
345     // copied by the hash_fn object of the container object, r_eq_fn
346     // will be copied by the eq_fn object of the container object, and
347     // r_comb_probe_fn will be copied by the comb_probe_fn object of
348     // the container object.
349     gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp)
350     : base_type(h, e, cp) { }
351
352     // Constructor taking some policy objects. r_hash_fn will be
353     // copied by the hash_fn object of the container object, r_eq_fn
354     // will be copied by the eq_fn object of the container object,
355     // r_comb_probe_fn will be copied by the comb_probe_fn object of
356     // the container object, and r_probe_fn will be copied by the
357     // probe_fn object of the container object.
358     gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, 
359                   const probe_fn& p)
360     : base_type(h, e, cp, p) { }
361
362     // Constructor taking some policy objects. r_hash_fn will be
363     // copied by the hash_fn object of the container object, r_eq_fn
364     // will be copied by the eq_fn object of the container object,
365     // r_comb_probe_fn will be copied by the comb_probe_fn object of
366     // the container object, r_probe_fn will be copied by the probe_fn
367     // object of the container object, and r_resize_policy will be
368     // copied by the Resize_Policy object of the container object.
369     gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, 
370                   const probe_fn& p, const resize_policy& rp)
371     : base_type(h, e, cp, p, rp) { }
372
373     // Constructor taking __iterators to a range of value_types. The
374     // value_types between first_it and last_it will be inserted into
375     // the container object.
376     template<typename It>
377     gp_hash_table(It first, It last)
378     { base_type::copy_from_range(first, last); }
379
380     // Constructor taking __iterators to a range of value_types and
381     // some policy objects. The value_types between first_it and
382     // last_it will be inserted into the container object. r_hash_fn
383     // will be copied by the hash_fn object of the container object.
384     template<typename It>
385     gp_hash_table(It first, It last, const hash_fn& h)
386     : base_type(h)
387     { base_type::copy_from_range(first, last); }
388
389     // Constructor taking __iterators to a range of value_types and
390     // some policy objects. The value_types between first_it and
391     // last_it will be inserted into the container object. r_hash_fn
392     // will be copied by the hash_fn object of the container object,
393     // and r_eq_fn will be copied by the eq_fn object of the container
394     // object.
395     template<typename It>
396     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
397     : base_type(h, e)
398     { base_type::copy_from_range(first, last); }
399
400     // Constructor taking __iterators to a range of value_types and
401     // some policy objects. The value_types between first_it and
402     // last_it will be inserted into the container object. r_hash_fn
403     // will be copied by the hash_fn object of the container object,
404     // r_eq_fn will be copied by the eq_fn object of the container
405     // object, and r_comb_probe_fn will be copied by the comb_probe_fn
406     // object of the container object.
407     template<typename It>
408     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 
409                   const comb_probe_fn& cp)
410     : base_type(h, e, cp)
411     { base_type::copy_from_range(first, last); }
412
413     // Constructor taking __iterators to a range of value_types and
414     // some policy objects. The value_types between first_it and
415     // last_it will be inserted into the container object. r_hash_fn
416     // will be copied by the hash_fn object of the container object,
417     // r_eq_fn will be copied by the eq_fn object of the container
418     // object, r_comb_probe_fn will be copied by the comb_probe_fn
419     // object of the container object, and r_probe_fn will be copied
420     // by the probe_fn object of the container object.
421     template<typename It>
422     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 
423                   const comb_probe_fn& cp, const probe_fn& p)
424     : base_type(h, e, cp, p)
425     { base_type::copy_from_range(first, last); }
426
427     // Constructor taking __iterators to a range of value_types and
428     // some policy objects. The value_types between first_it and
429     // last_it will be inserted into the container object. r_hash_fn
430     // will be copied by the hash_fn object of the container object,
431     // r_eq_fn will be copied by the eq_fn object of the container
432     // object, r_comb_probe_fn will be copied by the comb_probe_fn
433     // object of the container object, r_probe_fn will be copied by
434     // the probe_fn object of the container object, and
435     // r_resize_policy will be copied by the resize_policy object of
436     // the container object.
437     template<typename It>
438     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 
439                   const comb_probe_fn& cp, const probe_fn& p, 
440                   const resize_policy& rp)
441     : base_type(h, e, cp, p, rp)
442     { base_type::copy_from_range(first, last); }
443
444     gp_hash_table(const gp_hash_table& other)
445     : base_type((const base_type&)other)
446     { }
447
448     virtual
449     ~gp_hash_table() { }
450
451     gp_hash_table& 
452     operator=(const gp_hash_table& other)
453     {
454       if (this != &other)
455         {
456           gp_hash_table tmp(other);
457           swap(tmp);
458         }
459       return *this;
460     }
461
462     void
463     swap(gp_hash_table& other)
464     { base_type::swap(other); }
465   };
466
467 #undef PB_DS_BASE_C_DEC
468
469
470 #define PB_DS_BASE_C_DEC \
471   container_base<Key, Mapped, Tag, Policy_Tl, Allocator>
472
473   /// An abstract basic tree-like (tree, trie) associative container.
474   template<typename Key, typename Mapped, typename Tag, 
475            typename Node_Update, typename Policy_Tl, typename Allocator>
476   class basic_tree : public PB_DS_BASE_C_DEC
477   {
478   private:
479     typedef PB_DS_BASE_C_DEC    base_type;
480
481   public:
482     typedef Node_Update         node_update;
483
484     virtual
485     ~basic_tree() { }
486
487   protected:
488 #define PB_DS_CLASS_NAME                basic_tree
489 #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
490 #undef PB_DS_CLASS_NAME
491   };
492
493 #undef PB_DS_BASE_C_DEC
494
495
496 #define PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC \
497   detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag, Allocator>
498
499 #define PB_DS_BASE_C_DEC \
500   basic_tree<Key,Mapped,Tag,typename PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC::node_update, \
501              typename __gnu_cxx::typelist::create2<Cmp_Fn, PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC >::type, Allocator>
502
503   /// A concrete basic tree-based associative container.
504   template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>,
505            typename Tag = rb_tree_tag,
506            template<typename Const_Node_Iterator, typename Node_Iterator, typename Cmp_Fn_, typename Allocator_>
507   class Node_Update = __gnu_pbds::null_tree_node_update,
508            typename Allocator = std::allocator<char> >
509   class tree : public PB_DS_BASE_C_DEC
510   {
511   private:
512     typedef PB_DS_BASE_C_DEC    base_type;
513
514   public:
515     // Comparison functor type.
516     typedef Cmp_Fn              cmp_fn;
517
518     tree() { }
519
520     // Constructor taking some policy objects. r_cmp_fn will be copied
521     // by the Cmp_Fn object of the container object.
522     tree(const cmp_fn& c)
523     : base_type(c) { }
524
525     // Constructor taking __iterators to a range of value_types. The
526     // value_types between first_it and last_it will be inserted into
527     // the container object.
528     template<typename It>
529     tree(It first, It last)
530     { base_type::copy_from_range(first, last); }
531
532     // Constructor taking __iterators to a range of value_types and
533     // some policy objects The value_types between first_it and
534     // last_it will be inserted into the container object. r_cmp_fn
535     // will be copied by the cmp_fn object of the container object.
536     template<typename It>
537     tree(It first, It last, const cmp_fn& c)
538       : base_type(c)
539     { base_type::copy_from_range(first, last); }
540
541     tree(const tree& other)
542     : base_type((const base_type&)other) { }
543
544     virtual
545     ~tree() { }
546
547     tree& 
548     operator=(const tree& other)
549     {
550       if (this != &other)
551         {
552           tree tmp(other);
553           swap(tmp);
554         }
555       return *this;
556     }
557
558     void
559     swap(tree& other)
560     { base_type::swap(other); }
561   };
562
563 #undef PB_DS_BASE_C_DEC
564 #undef PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC
565
566
567 #define PB_DS_TRIE_NODE_AND_ITS_TRAITS \
568   detail::trie_traits<Key,Mapped,E_Access_Traits,Node_Update,Tag,Allocator>
569
570 #define PB_DS_BASE_C_DEC \
571   basic_tree<Key,Mapped,Tag, typename PB_DS_TRIE_NODE_AND_ITS_TRAITS::node_update, \
572              typename __gnu_cxx::typelist::create2<E_Access_Traits, PB_DS_TRIE_NODE_AND_ITS_TRAITS >::type, Allocator>
573
574   /// A concrete basic trie-based associative container.
575   template<typename Key,
576            typename Mapped,
577            typename E_Access_Traits = typename detail::default_trie_e_access_traits<Key>::type,
578            typename Tag = pat_trie_tag,
579            template<typename Const_Node_Iterator,
580                     typename Node_Iterator,
581                     typename E_Access_Traits_,
582                     typename Allocator_>
583   class Node_Update = null_trie_node_update,
584            typename Allocator = std::allocator<char> >
585   class trie : public PB_DS_BASE_C_DEC
586   {
587   private:
588     typedef PB_DS_BASE_C_DEC base_type;
589
590   public:
591     // Element access traits type.
592     typedef E_Access_Traits e_access_traits;
593
594     trie() { }
595
596     // Constructor taking some policy objects. r_e_access_traits will
597     // be copied by the E_Access_Traits object of the container
598     // object.
599     trie(const e_access_traits& t)
600     : base_type(t) { }
601
602     // Constructor taking __iterators to a range of value_types. The
603     // value_types between first_it and last_it will be inserted into
604     // the container object.
605     template<typename It>
606     trie(It first, It last)
607     { base_type::copy_from_range(first, last); }
608
609     // Constructor taking __iterators to a range of value_types and
610     // some policy objects. The value_types between first_it and
611     // last_it will be inserted into the container object.
612     template<typename It>
613     trie(It first, It last, const e_access_traits& t)
614     : base_type(t)
615     { base_type::copy_from_range(first, last); }
616
617     trie(const trie& other)
618     : base_type((const base_type&)other) { }
619
620     virtual
621     ~trie() { }
622
623     trie& 
624     operator=(const trie& other)
625     {
626       if (this != &other)
627         {
628           trie tmp(other);
629           swap(tmp);
630         }
631       return *this;
632     }
633
634     void
635     swap(trie& other)
636     { base_type::swap(other); }
637   };
638
639 #undef PB_DS_BASE_C_DEC
640 #undef PB_DS_TRIE_NODE_AND_ITS_TRAITS
641
642
643 #define PB_DS_BASE_C_DEC \
644   container_base<Key, Mapped, list_update_tag, \
645                  typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type, Allocator>
646
647   /// A list-update based associative container.
648   template<typename Key,
649            typename Mapped,
650            class Eq_Fn = typename detail::default_eq_fn<Key>::type,
651            class Update_Policy = detail::default_update_policy::type,
652            class Allocator = std::allocator<char> >
653   class list_update : public PB_DS_BASE_C_DEC
654   {
655   private:
656     typedef PB_DS_BASE_C_DEC    base_type;
657
658   public:
659     typedef Eq_Fn               eq_fn;
660     typedef Update_Policy       update_policy;
661     typedef Allocator           allocator;
662
663     list_update() { }
664
665     // Constructor taking __iterators to a range of value_types. The
666     // value_types between first_it and last_it will be inserted into
667     // the container object.
668     template<typename It>
669     list_update(It first, It last)
670     { base_type::copy_from_range(first, last); }
671
672     list_update(const list_update& other)
673     : base_type((const base_type&)other) { }
674
675     virtual
676     ~list_update() { }
677
678     list_update& 
679     operator=(const list_update& other)
680     {
681       if (this !=& other)
682         {
683           list_update tmp(other);
684           swap(tmp);
685         }
686       return *this;
687     }
688
689     void
690     swap(list_update& other)
691     { base_type::swap(other); }
692   };
693
694 #undef PB_DS_BASE_C_DEC
695
696   // @} group pbds
697 } // namespace __gnu_pbds
698
699 #endif