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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2016 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/branch_policy/traits.hpp>
  50
  51 namespace __gnu_pbds
  52 {
  53   /**
  54    *  @defgroup containers-pbds Containers
  55    *  @ingroup pbds
  56    *  @{
  57    */
  58
  59   /**
  60    *  @defgroup hash-based Hash-Based
  61    *  @ingroup containers-pbds
  62    *  @{
  63    */
  64 #define PB_DS_HASH_BASE \
  65   detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, \
  66     typename __gnu_cxx::typelist::append< \
  67     typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, \
  68     detail::integral_constant<int, Store_Hash> >::type, Policy_Tl>::type>::type
  69
  70   /**
  71    *  @defgroup hash-detail Base and Policy Classes
  72    *  @ingroup hash-based
  73    */
  74
  75   /**
  76    *  A hashed container abstraction.
  77    *
  78    *  @tparam Key               Key type.
  79    *  @tparam Mapped            Map type.
  80    *  @tparam Hash_Fn           Hashing functor.
  81    *  @tparam Eq_Fn             Equal functor.
  82    *  @tparam Resize_Policy     Resizes hash.
  83    *  @tparam Store_Hash        Indicates whether the hash value
  84    *                            will be stored along with each key.
  85    *  @tparam Tag               Instantiating data structure type,
  86    *                            see container_tag.
  87    *  @tparam Policy_TL         Policy typelist.
  88    *  @tparam _Alloc            Allocator type.
  89    *
  90    *  Base is dispatched at compile time via Tag, from the following
  91    *  choices: cc_hash_tag, gp_hash_tag, and descendants of basic_hash_tag.
  92    *
  93    *  Base choices are: detail::cc_ht_map, detail::gp_ht_map
  94    */
  95   template<typename Key,
  96            typename Mapped,
  97            typename Hash_Fn,
  98            typename Eq_Fn,
  99            typename Resize_Policy,
 100            bool Store_Hash,
 101            typename Tag,
 102            typename Policy_Tl,
 103            typename _Alloc>
 104   class basic_hash_table : public PB_DS_HASH_BASE
 105   {
 106   private:
 107     typedef typename PB_DS_HASH_BASE            base_type;
 108
 109   public:
 110     virtual
 111     ~basic_hash_table() { }
 112
 113   protected:
 114     basic_hash_table() { }
 115
 116     basic_hash_table(const basic_hash_table& other)
 117     : base_type((const base_type&)other) { }
 118
 119     template<typename T0>
 120       basic_hash_table(T0 t0) : base_type(t0) { }
 121
 122     template<typename T0, typename T1>
 123       _GLIBCXX_ABI_TAG_EMPTY
 124       basic_hash_table(T0 t0, T1 t1) : base_type(t0, t1) { }
 125
 126     template<typename T0, typename T1, typename T2>
 127       _GLIBCXX_ABI_TAG_EMPTY
 128       basic_hash_table(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { }
 129
 130     template<typename T0, typename T1, typename T2, typename T3>
 131       _GLIBCXX_ABI_TAG_EMPTY
 132       basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3)
 133       : base_type(t0, t1, t2, t3) { }
 134
 135     template<typename T0, typename T1, typename T2, typename T3, typename T4>
 136       _GLIBCXX_ABI_TAG_EMPTY
 137       basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4)
 138       : base_type(t0, t1, t2, t3, t4) { }
 139
 140     template<typename T0, typename T1, typename T2, typename T3, typename T4,
 141              typename T5>
 142       _GLIBCXX_ABI_TAG_EMPTY
 143       basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5)
 144       : base_type(t0, t1, t2, t3, t4, t5) { }
 145
 146     template<typename T0, typename T1, typename T2, typename T3, typename T4,
 147              typename T5, typename T6>
 148       _GLIBCXX_ABI_TAG_EMPTY
 149       basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6)
 150       : base_type(t0, t1, t2, t3, t4, t5, t6) { }
 151
 152     template<typename T0, typename T1, typename T2, typename T3, typename T4,
 153              typename T5, typename T6, typename T7>
 154       _GLIBCXX_ABI_TAG_EMPTY
 155       basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6, T7 t7)
 156       : base_type(t0, t1, t2, t3, t4, t5, t6, t7) { }
 157
 158     template<typename T0, typename T1, typename T2, typename T3, typename T4,
 159              typename T5, typename T6, typename T7, typename T8>
 160       _GLIBCXX_ABI_TAG_EMPTY
 161       basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6,
 162                        T7 t7, T8 t8)
 163       : base_type(t0, t1, t2, t3, t4, t5, t6, t7, t8)
 164       { }
 165
 166   private:
 167     basic_hash_table&
 168     operator=(const base_type&);
 169   };
 170
 171 #undef PB_DS_HASH_BASE
 172
 173
 174 #define PB_DS_CC_HASH_BASE \
 175   basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
 176                    cc_hash_tag, \
 177           typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, _Alloc>
 178
 179
 180   /**
 181    *  A collision-chaining hash-based associative container.
 182    *
 183    *  @tparam Key               Key type.
 184    *  @tparam Mapped            Map type.
 185    *  @tparam Hash_Fn           Hashing functor.
 186    *  @tparam Eq_Fn             Equal functor.
 187    *  @tparam Comb_Hash_Fn      Combining hash functor.
 188    *                            If Hash_Fn is not null_type, then this
 189    *                            is the ranged-hash functor; otherwise,
 190    *                            this is the range-hashing functor.
 191    *                    XXX(See Design::Hash-Based Containers::Hash Policies.)
 192    *  @tparam Resize_Policy     Resizes hash.
 193    *  @tparam Store_Hash        Indicates whether the hash value
 194    *                            will be stored along with each key.
 195    *                            If Hash_Fn is null_type, then the
 196    *                            container will not compile if this
 197    *                            value is true
 198    *  @tparam _Alloc            Allocator type.
 199    *
 200    *  Base tag choices are:     cc_hash_tag.
 201    *
 202    *  Base is basic_hash_table.
 203    */
 204   template<typename Key,
 205            typename Mapped,
 206            typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
 207            typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
 208            typename Comb_Hash_Fn = detail::default_comb_hash_fn::type,
 209            typename Resize_Policy = typename detail::default_resize_policy<Comb_Hash_Fn>::type,
 210            bool Store_Hash = detail::default_store_hash,
 211            typename _Alloc = std::allocator<char> >
 212   class cc_hash_table :  public PB_DS_CC_HASH_BASE
 213   {
 214   private:
 215     typedef PB_DS_CC_HASH_BASE                  base_type;
 216
 217   public:
 218     typedef cc_hash_tag                         container_category;
 219     typedef Hash_Fn                             hash_fn;
 220     typedef Eq_Fn                               eq_fn;
 221     typedef Resize_Policy                       resize_policy;
 222     typedef Comb_Hash_Fn                        comb_hash_fn;
 223
 224     /// Default constructor.
 225     cc_hash_table() { }
 226
 227     /// Constructor taking some policy objects. r_hash_fn will be
 228     /// copied by the Hash_Fn object of the container object.
 229     cc_hash_table(const hash_fn& h)
 230     : base_type(h) { }
 231
 232     /// Constructor taking some policy objects. r_hash_fn will be
 233     /// copied by the hash_fn object of the container object, and
 234     /// r_eq_fn will be copied by the eq_fn object of the container
 235     /// object.
 236     cc_hash_table(const hash_fn& h, const eq_fn& e)
 237     : base_type(h, e) { }
 238
 239     /// Constructor taking some policy objects. r_hash_fn will be
 240     /// copied by the hash_fn object of the container object, r_eq_fn
 241     /// will be copied by the eq_fn object of the container object,
 242     /// and r_comb_hash_fn will be copied by the comb_hash_fn object
 243     /// of the container object.
 244     cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch)
 245     : base_type(h, e, ch) { }
 246
 247     /// Constructor taking some policy objects. r_hash_fn will be
 248     /// copied by the hash_fn object of the container object, r_eq_fn
 249     /// will be copied by the eq_fn object of the container object,
 250     /// r_comb_hash_fn will be copied by the comb_hash_fn object of
 251     /// the container object, and r_resize_policy will be copied by
 252     /// the resize_policy object of the container object.
 253     cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch,
 254                   const resize_policy& rp)
 255     : base_type(h, e, ch, rp) { }
 256
 257     /// Constructor taking __iterators to a range of value_types. The
 258     /// value_types between first_it and last_it will be inserted into
 259     /// the container object.
 260     template<typename It>
 261     cc_hash_table(It first, It last)
 262     { base_type::copy_from_range(first, last); }
 263
 264     /// Constructor taking __iterators to a range of value_types and
 265     /// some policy objects. The value_types between first_it and
 266     /// last_it will be inserted into the container object.
 267     template<typename It>
 268     cc_hash_table(It first, It last, const hash_fn& h)
 269     : base_type(h)
 270     { this->copy_from_range(first, last); }
 271
 272     /// Constructor taking __iterators to a range of value_types and
 273     /// some policy objects The value_types between first_it and
 274     /// last_it will be inserted into the container object. r_hash_fn
 275     /// will be copied by the hash_fn object of the container object,
 276     /// and r_eq_fn will be copied by the eq_fn object of the
 277     /// container object.
 278     template<typename It>
 279     cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
 280     : base_type(h, e)
 281     { this->copy_from_range(first, last); }
 282
 283     /// Constructor taking __iterators to a range of value_types and
 284     /// some policy objects The value_types between first_it and
 285     /// last_it will be inserted into the container object. r_hash_fn
 286     /// will be copied by the hash_fn object of the container object,
 287     /// r_eq_fn will be copied by the eq_fn object of the container
 288     /// object, and r_comb_hash_fn will be copied by the comb_hash_fn
 289     /// object of the container object.
 290     template<typename It>
 291     cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
 292                   const comb_hash_fn& ch)
 293     : base_type(h, e, ch)
 294     { this->copy_from_range(first, last); }
 295
 296     /// Constructor taking __iterators to a range of value_types and
 297     /// some policy objects The value_types between first_it and
 298     /// last_it will be inserted into the container object. r_hash_fn
 299     /// will be copied by the hash_fn object of the container object,
 300     /// r_eq_fn will be copied by the eq_fn object of the container
 301     /// object, r_comb_hash_fn will be copied by the comb_hash_fn
 302     /// object of the container object, and r_resize_policy will be
 303     /// copied by the resize_policy object of the container object.
 304     template<typename It>
 305     cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
 306                   const comb_hash_fn& ch, const resize_policy& rp)
 307     : base_type(h, e, ch, rp)
 308     { this->copy_from_range(first, last); }
 309
 310     cc_hash_table(const cc_hash_table& other)
 311     : base_type((const base_type&)other)
 312     { }
 313
 314     virtual
 315     ~cc_hash_table() { }
 316
 317     cc_hash_table&
 318     operator=(const cc_hash_table& other)
 319     {
 320       if (this != &other)
 321         {
 322           cc_hash_table tmp(other);
 323           swap(tmp);
 324         }
 325       return *this;
 326     }
 327
 328     void
 329     swap(cc_hash_table& other)
 330     { base_type::swap(other); }
 331   };
 332
 333 #undef PB_DS_CC_HASH_BASE
 334
 335
 336 #define PB_DS_GP_HASH_BASE \
 337   basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
 338                    gp_hash_tag, \
 339   typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, _Alloc>
 340
 341
 342   /**
 343    *  A general-probing hash-based associative container.
 344    *
 345    *  @tparam Key               Key type.
 346    *  @tparam Mapped            Map type.
 347    *  @tparam Hash_Fn           Hashing functor.
 348    *  @tparam Eq_Fn             Equal functor.
 349    *  @tparam Comb_Probe_Fn     Combining probe functor.
 350    *                            If Hash_Fn is not null_type, then this
 351    *                            is the ranged-probe functor; otherwise,
 352    *                            this is the range-hashing functor.
 353    *                    XXX See Design::Hash-Based Containers::Hash Policies.
 354    *  @tparam Probe_Fn          Probe functor.
 355    *  @tparam Resize_Policy     Resizes hash.
 356    *  @tparam Store_Hash        Indicates whether the hash value
 357    *                            will be stored along with each key.
 358    *                            If Hash_Fn is null_type, then the
 359    *                            container will not compile if this
 360    *                            value is true
 361    *  @tparam _Alloc            Allocator type.
 362    *
 363    *  Base tag choices are:     gp_hash_tag.
 364    *
 365    *  Base is basic_hash_table.
 366    */
 367   template<typename Key,
 368            typename Mapped,
 369            typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
 370            typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
 371            typename Comb_Probe_Fn = detail::default_comb_hash_fn::type,
 372            typename Probe_Fn = typename detail::default_probe_fn<Comb_Probe_Fn>::type,
 373            typename Resize_Policy = typename detail::default_resize_policy<Comb_Probe_Fn>::type,
 374            bool Store_Hash = detail::default_store_hash,
 375            typename _Alloc = std::allocator<char> >
 376   class gp_hash_table : public PB_DS_GP_HASH_BASE
 377   {
 378   private:
 379     typedef PB_DS_GP_HASH_BASE                  base_type;
 380
 381   public:
 382     typedef gp_hash_tag                         container_category;
 383     typedef Hash_Fn                             hash_fn;
 384     typedef Eq_Fn                               eq_fn;
 385     typedef Comb_Probe_Fn                       comb_probe_fn;
 386     typedef Probe_Fn                            probe_fn;
 387     typedef Resize_Policy                       resize_policy;
 388
 389     /// Default constructor.
 390     gp_hash_table() { }
 391
 392     /// Constructor taking some policy objects. r_hash_fn will be
 393     /// copied by the hash_fn object of the container object.
 394     gp_hash_table(const hash_fn& h)
 395     : base_type(h) { }
 396
 397     /// Constructor taking some policy objects. r_hash_fn will be
 398     /// copied by the hash_fn object of the container object, and
 399     /// r_eq_fn will be copied by the eq_fn object of the container
 400     /// object.
 401     gp_hash_table(const hash_fn& h, const eq_fn& e)
 402     : base_type(h, e) { }
 403
 404     /// Constructor taking some policy objects. r_hash_fn will be
 405     /// copied by the hash_fn object of the container object, r_eq_fn
 406     /// will be copied by the eq_fn object of the container object,
 407     /// and r_comb_probe_fn will be copied by the comb_probe_fn object
 408     /// of the container object.
 409     gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp)
 410     : base_type(h, e, cp) { }
 411
 412     /// Constructor taking some policy objects. r_hash_fn will be
 413     /// copied by the hash_fn object of the container object, r_eq_fn
 414     /// will be copied by the eq_fn object of the container object,
 415     /// r_comb_probe_fn will be copied by the comb_probe_fn object of
 416     /// the container object, and r_probe_fn will be copied by the
 417     /// probe_fn object of the container object.
 418     gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
 419                   const probe_fn& p)
 420     : base_type(h, e, cp, p) { }
 421
 422     /// Constructor taking some policy objects. r_hash_fn will be
 423     /// copied by the hash_fn object of the container object, r_eq_fn
 424     /// will be copied by the eq_fn object of the container object,
 425     /// r_comb_probe_fn will be copied by the comb_probe_fn object of
 426     /// the container object, r_probe_fn will be copied by the
 427     /// probe_fn object of the container object, and r_resize_policy
 428     /// will be copied by the Resize_Policy object of the container
 429     /// object.
 430     gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
 431                   const probe_fn& p, const resize_policy& rp)
 432     : base_type(h, e, cp, p, rp) { }
 433
 434     /// Constructor taking __iterators to a range of value_types. The
 435     /// value_types between first_it and last_it will be inserted into
 436     /// the container object.
 437     template<typename It>
 438     gp_hash_table(It first, It last)
 439     { base_type::copy_from_range(first, last); }
 440
 441     /// Constructor taking __iterators to a range of value_types and
 442     /// some policy objects. The value_types between first_it and
 443     /// last_it will be inserted into the container object. r_hash_fn
 444     /// will be copied by the hash_fn object of the container object.
 445     template<typename It>
 446     gp_hash_table(It first, It last, const hash_fn& h)
 447     : base_type(h)
 448     { base_type::copy_from_range(first, last); }
 449
 450     /// Constructor taking __iterators to a range of value_types and
 451     /// some policy objects. The value_types between first_it and
 452     /// last_it will be inserted into the container object. r_hash_fn
 453     /// will be copied by the hash_fn object of the container object,
 454     /// and r_eq_fn will be copied by the eq_fn object of the
 455     /// container object.
 456     template<typename It>
 457     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
 458     : base_type(h, e)
 459     { base_type::copy_from_range(first, last); }
 460
 461     /// Constructor taking __iterators to a range of value_types and
 462     /// some policy objects. The value_types between first_it and
 463     /// last_it will be inserted into the container object. r_hash_fn
 464     /// will be copied by the hash_fn object of the container object,
 465     /// r_eq_fn will be copied by the eq_fn object of the container
 466     /// object, and r_comb_probe_fn will be copied by the
 467     /// comb_probe_fn object of the container object.
 468     template<typename It>
 469     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
 470                   const comb_probe_fn& cp)
 471     : base_type(h, e, cp)
 472     { base_type::copy_from_range(first, last); }
 473
 474     /// Constructor taking __iterators to a range of value_types and
 475     /// some policy objects. The value_types between first_it and
 476     /// last_it will be inserted into the container object. r_hash_fn
 477     /// will be copied by the hash_fn object of the container object,
 478     /// r_eq_fn will be copied by the eq_fn object of the container
 479     /// object, r_comb_probe_fn will be copied by the comb_probe_fn
 480     /// object of the container object, and r_probe_fn will be copied
 481     /// by the probe_fn object of the container object.
 482     template<typename It>
 483     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
 484                   const comb_probe_fn& cp, const probe_fn& p)
 485     : base_type(h, e, cp, p)
 486     { base_type::copy_from_range(first, last); }
 487
 488     /// Constructor taking __iterators to a range of value_types and
 489     /// some policy objects. The value_types between first_it and
 490     /// last_it will be inserted into the container object. r_hash_fn
 491     /// will be copied by the hash_fn object of the container object,
 492     /// r_eq_fn will be copied by the eq_fn object of the container
 493     /// object, r_comb_probe_fn will be copied by the comb_probe_fn
 494     /// object of the container object, r_probe_fn will be copied by
 495     /// the probe_fn object of the container object, and
 496     /// r_resize_policy will be copied by the resize_policy object of
 497     /// the container object.
 498     template<typename It>
 499     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
 500                   const comb_probe_fn& cp, const probe_fn& p,
 501                   const resize_policy& rp)
 502     : base_type(h, e, cp, p, rp)
 503     { base_type::copy_from_range(first, last); }
 504
 505     gp_hash_table(const gp_hash_table& other)
 506     : base_type((const base_type&)other)
 507     { }
 508
 509     virtual
 510     ~gp_hash_table() { }
 511
 512     gp_hash_table&
 513     operator=(const gp_hash_table& other)
 514     {
 515       if (this != &other)
 516         {
 517           gp_hash_table tmp(other);
 518           swap(tmp);
 519         }
 520       return *this;
 521     }
 522
 523     void
 524     swap(gp_hash_table& other)
 525     { base_type::swap(other); }
 526   };
 527   //@} hash-based
 528 #undef PB_DS_GP_HASH_BASE
 529
 530
 531   /**
 532    *  @defgroup branch-based Branch-Based
 533    *  @ingroup containers-pbds
 534    *  @{
 535    */
 536 #define PB_DS_BRANCH_BASE \
 537   detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, Policy_Tl>::type
 538
 539   /**
 540    *  @defgroup branch-detail Base and Policy Classes
 541    *  @ingroup branch-based
 542    */
 543
 544   /**
 545    *  A branched, tree-like (tree, trie) container abstraction.
 546    *
 547    *  @tparam Key               Key type.
 548    *  @tparam Mapped            Map type.
 549    *  @tparam Tag               Instantiating data structure type,
 550    *                            see container_tag.
 551    *  @tparam Node_Update       Updates nodes, restores invariants.
 552    *  @tparam Policy_TL         Policy typelist.
 553    *  @tparam _Alloc            Allocator type.
 554    *
 555    *  Base is dispatched at compile time via Tag, from the following
 556    *  choices: tree_tag, trie_tag, and their descendants.
 557    *
 558    *  Base choices are: detail::ov_tree_map, detail::rb_tree_map,
 559    *                    detail::splay_tree_map, and detail::pat_trie_map.
 560    */
 561   template<typename Key, typename Mapped, typename Tag,
 562            typename Node_Update, typename Policy_Tl, typename _Alloc>
 563   class basic_branch : public PB_DS_BRANCH_BASE
 564   {
 565   private:
 566     typedef typename PB_DS_BRANCH_BASE          base_type;
 567
 568   public:
 569     typedef Node_Update                         node_update;
 570
 571     virtual
 572     ~basic_branch() { }
 573
 574   protected:
 575     basic_branch() { }
 576
 577     basic_branch(const basic_branch& other)
 578     : base_type((const base_type&)other) { }
 579
 580     template<typename T0>
 581       basic_branch(T0 t0) : base_type(t0) { }
 582
 583     template<typename T0, typename T1>
 584       basic_branch(T0 t0, T1 t1) : base_type(t0, t1) { }
 585
 586     template<typename T0, typename T1, typename T2>
 587       basic_branch(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { }
 588
 589     template<typename T0, typename T1, typename T2, typename T3>
 590       basic_branch(T0 t0, T1 t1, T2 t2, T3 t3)
 591       : base_type(t0, t1, t2, t3) { }
 592
 593     template<typename T0, typename T1, typename T2, typename T3, typename T4>
 594       basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4)
 595       : base_type(t0, t1, t2, t3, t4) { }
 596
 597     template<typename T0, typename T1, typename T2, typename T3, typename T4,
 598              typename T5>
 599       basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5)
 600       : base_type(t0, t1, t2, t3, t4, t5) { }
 601
 602     template<typename T0, typename T1, typename T2, typename T3, typename T4,
 603              typename T5, typename T6>
 604       basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6)
 605       : base_type(t0, t1, t2, t3, t4, t5, t6) { }
 606   };
 607 #undef PB_DS_BRANCH_BASE
 608
 609
 610 #define PB_DS_TREE_NODE_AND_IT_TRAITS \
 611   detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag,_Alloc>
 612
 613 #define PB_DS_TREE_BASE \
 614   basic_branch<Key,Mapped, Tag, \
 615                typename PB_DS_TREE_NODE_AND_IT_TRAITS::node_update, \
 616                typename __gnu_cxx::typelist::create2<Cmp_Fn, \
 617                PB_DS_TREE_NODE_AND_IT_TRAITS>::type, _Alloc>
 618
 619
 620   /**
 621    *  A tree-based container.
 622    *
 623    *  @tparam Key               Key type.
 624    *  @tparam Mapped            Map type.
 625    *  @tparam Cmp_Fn            Comparison functor.
 626    *  @tparam Tag               Instantiating data structure type,
 627    *                            see container_tag.
 628    *  @tparam Node_Update       Updates tree internal-nodes,
 629    *                            restores invariants when invalidated.
 630    *                     XXX See design::tree-based-containers::node invariants.
 631    *  @tparam _Alloc            Allocator type.
 632    *
 633    *  Base tag choices are: ov_tree_tag, rb_tree_tag, splay_tree_tag.
 634    *
 635    *  Base is basic_branch.
 636    */
 637   template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>,
 638            typename Tag = rb_tree_tag,
 639            template<typename Node_CItr, typename Node_Itr,
 640                     typename Cmp_Fn_, typename _Alloc_>
 641            class Node_Update = null_node_update,
 642            typename _Alloc = std::allocator<char> >
 643   class tree : public PB_DS_TREE_BASE
 644   {
 645   private:
 646     typedef PB_DS_TREE_BASE                     base_type;
 647
 648   public:
 649     /// Comparison functor type.
 650     typedef Cmp_Fn                              cmp_fn;
 651
 652     tree() { }
 653
 654     /// Constructor taking some policy objects. r_cmp_fn will be
 655     /// copied by the Cmp_Fn object of the container object.
 656     tree(const cmp_fn& c)
 657     : base_type(c) { }
 658
 659     /// Constructor taking __iterators to a range of value_types. The
 660     /// value_types between first_it and last_it will be inserted into
 661     /// the container object.
 662     template<typename It>
 663     tree(It first, It last)
 664     { base_type::copy_from_range(first, last); }
 665
 666     /// Constructor taking __iterators to a range of value_types and
 667     /// some policy objects The value_types between first_it and
 668     /// last_it will be inserted into the container object. r_cmp_fn
 669     /// will be copied by the cmp_fn object of the container object.
 670     template<typename It>
 671     tree(It first, It last, const cmp_fn& c)
 672     : base_type(c)
 673     { base_type::copy_from_range(first, last); }
 674
 675     tree(const tree& other)
 676     : base_type((const base_type&)other) { }
 677
 678     virtual
 679     ~tree() { }
 680
 681     tree&
 682     operator=(const tree& other)
 683     {
 684       if (this != &other)
 685         {
 686           tree tmp(other);
 687           swap(tmp);
 688         }
 689       return *this;
 690     }
 691
 692     void
 693     swap(tree& other)
 694     { base_type::swap(other); }
 695   };
 696
 697 #undef PB_DS_TREE_BASE
 698 #undef PB_DS_TREE_NODE_AND_IT_TRAITS
 699
 700
 701 #define PB_DS_TRIE_NODE_AND_IT_TRAITS \
 702   detail::trie_traits<Key,Mapped,_ATraits,Node_Update,Tag,_Alloc>
 703
 704 #define PB_DS_TRIE_BASE \
 705   basic_branch<Key,Mapped,Tag, \
 706                typename PB_DS_TRIE_NODE_AND_IT_TRAITS::node_update, \
 707                typename __gnu_cxx::typelist::create2<_ATraits, \
 708                PB_DS_TRIE_NODE_AND_IT_TRAITS >::type, _Alloc>
 709
 710
 711   /**
 712    *  A trie-based container.
 713    *
 714    *  @tparam Key               Key type.
 715    *  @tparam Mapped            Map type.
 716    *  @tparam _ATraits          Element access traits.
 717    *  @tparam Tag               Instantiating data structure type,
 718    *                            see container_tag.
 719    *  @tparam Node_Update       Updates trie internal-nodes,
 720    *                            restores invariants when invalidated.
 721    *                     XXX See design::tree-based-containers::node invariants.
 722    *  @tparam _Alloc            Allocator type.
 723    *
 724    *  Base tag choice is pat_trie_tag.
 725    *
 726    *  Base is basic_branch.
 727    */
 728   template<typename Key,
 729            typename Mapped,
 730            typename _ATraits = \
 731                     typename detail::default_trie_access_traits<Key>::type,
 732            typename Tag = pat_trie_tag,
 733            template<typename Node_CItr,
 734                     typename Node_Itr,
 735                     typename _ATraits_,
 736                     typename _Alloc_>
 737            class Node_Update = null_node_update,
 738            typename _Alloc = std::allocator<char> >
 739   class trie : public PB_DS_TRIE_BASE
 740   {
 741   private:
 742     typedef PB_DS_TRIE_BASE                     base_type;
 743
 744   public:
 745     /// Element access traits type.
 746     typedef _ATraits                            access_traits;
 747
 748     trie() { }
 749
 750     /// Constructor taking some policy objects. r_access_traits will
 751     /// be copied by the _ATraits object of the container object.
 752     trie(const access_traits& t)
 753     : base_type(t) { }
 754
 755     /// Constructor taking __iterators to a range of value_types. The
 756     /// value_types between first_it and last_it will be inserted into
 757     /// the container object.
 758     template<typename It>
 759     trie(It first, It last)
 760     { base_type::copy_from_range(first, last); }
 761
 762     /// Constructor taking __iterators to a range of value_types and
 763     /// some policy objects. The value_types between first_it and
 764     /// last_it will be inserted into the container object.
 765     template<typename It>
 766     trie(It first, It last, const access_traits& t)
 767     : base_type(t)
 768     { base_type::copy_from_range(first, last); }
 769
 770     trie(const trie& other)
 771     : base_type((const base_type&)other) { }
 772
 773     virtual
 774     ~trie() { }
 775
 776     trie&
 777     operator=(const trie& other)
 778     {
 779       if (this != &other)
 780         {
 781           trie tmp(other);
 782           swap(tmp);
 783         }
 784       return *this;
 785     }
 786
 787     void
 788     swap(trie& other)
 789     { base_type::swap(other); }
 790   };
 791   //@} branch-based
 792 #undef PB_DS_TRIE_BASE
 793 #undef PB_DS_TRIE_NODE_AND_IT_TRAITS
 794
 795
 796   /**
 797    *  @defgroup list-based List-Based
 798    *  @ingroup containers-pbds
 799    *  @{
 800    */
 801 #define PB_DS_LU_BASE \
 802   detail::container_base_dispatch<Key, Mapped, _Alloc, list_update_tag, \
 803     typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type>::type
 804
 805
 806   /**
 807    *  A list-update based associative container.
 808    *
 809    *  @tparam Key               Key type.
 810    *  @tparam Mapped            Map type.
 811    *  @tparam Eq_Fn             Equal functor.
 812    *  @tparam Update_Policy     Update policy, determines when an element
 813    *                            will be moved to the front of the list.
 814    *  @tparam _Alloc            Allocator type.
 815    *
 816    *  Base is detail::lu_map.
 817    */
 818   template<typename Key,
 819            typename Mapped,
 820            class Eq_Fn = typename detail::default_eq_fn<Key>::type,
 821            class Update_Policy = detail::default_update_policy::type,
 822            class _Alloc = std::allocator<char> >
 823   class list_update : public PB_DS_LU_BASE
 824   {
 825   private:
 826     typedef typename PB_DS_LU_BASE              base_type;
 827
 828   public:
 829     typedef list_update_tag                     container_category;
 830     typedef Eq_Fn                               eq_fn;
 831     typedef Update_Policy                       update_policy;
 832
 833     list_update() { }
 834
 835     /// Constructor taking __iterators to a range of value_types. The
 836     /// value_types between first_it and last_it will be inserted into
 837     /// the container object.
 838     template<typename It>
 839     list_update(It first, It last)
 840     { base_type::copy_from_range(first, last); }
 841
 842     list_update(const list_update& other)
 843     : base_type((const base_type&)other) { }
 844
 845     virtual
 846     ~list_update() { }
 847
 848     list_update&
 849     operator=(const list_update& other)
 850     {
 851       if (this !=& other)
 852         {
 853           list_update tmp(other);
 854           swap(tmp);
 855         }
 856       return *this;
 857     }
 858
 859     void
 860     swap(list_update& other)
 861     { base_type::swap(other); }
 862   };
 863   //@} list-based
 864 #undef PB_DS_LU_BASE
 865
 866   // @} group containers-pbds
 867 } // namespace __gnu_pbds
 868
 869 #endif