libstdc++-v3/include/ext/pb_ds/assoc_container.hpp

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