libstdc++-v3/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