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