l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.4/include/ext/pb_ds/assoc_container.hpp

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