libstdc++
assoc_container.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2009, 2010, 2011 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00026 
00027 // Permission to use, copy, modify, sell, and distribute this software
00028 // is hereby granted without fee, provided that the above copyright
00029 // notice appears in all copies, and that both that copyright notice
00030 // and this permission notice appear in supporting documentation. None
00031 // of the above authors, nor IBM Haifa Research Laboratories, make any
00032 // representation about the suitability of this software for any
00033 // purpose. It is provided "as is" without express or implied
00034 // warranty.
00035 
00036 /**
00037  * @file assoc_container.hpp
00038  * Contains associative containers.
00039  */
00040 
00041 #ifndef PB_DS_ASSOC_CNTNR_HPP
00042 #define PB_DS_ASSOC_CNTNR_HPP
00043 
00044 #include <bits/c++config.h>
00045 #include <ext/typelist.h>
00046 #include <ext/pb_ds/tag_and_trait.hpp>
00047 #include <ext/pb_ds/detail/standard_policies.hpp>
00048 #include <ext/pb_ds/detail/container_base_dispatch.hpp>
00049 #include <ext/pb_ds/detail/branch_policy/traits.hpp>
00050 
00051 namespace __gnu_pbds
00052 {
00053   /**
00054    *  @defgroup containers-pbds Containers
00055    *  @ingroup pbds
00056    *  @{
00057    */
00058 
00059   /**
00060    *  @defgroup hash-based
00061    *  @ingroup containers-pbds
00062    *  @{
00063    */
00064 #define PB_DS_HASH_BASE \
00065   detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, \
00066     typename __gnu_cxx::typelist::append< \
00067     typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, \
00068     detail::integral_constant<int, Store_Hash> >::type, Policy_Tl>::type>::type
00069 
00070   /**
00071    *  @defgroup hash-detail Base and Policy Classes
00072    *  @ingroup hash-based
00073    */
00074 
00075   /**
00076    *  A hashed container abstraction.
00077    *
00078    *  @tparam Key           Key type.
00079    *  @tparam Mapped            Map type.
00080    *  @tparam Hash_Fn           Hashing functor.
00081    *  @tparam Eq_Fn         Equal functor.
00082    *  @tparam Resize_Policy     Resizes hash.
00083    *  @tparam Store_Hash        Indicates whether the hash value
00084    *                            will be stored along with each key.
00085    *  @tparam Tag           Instantiating data structure type,
00086    *                    see container_tag.
00087    *  @tparam Policy_TL         Policy typelist.
00088    *  @tparam _Alloc            Allocator type.
00089    *
00090    *  Base is dispatched at compile time via Tag, from the following
00091    *  choices: cc_hash_tag, gp_hash_tag, and descendants of basic_hash_tag.
00092    *
00093    *  Base choices are: detail::cc_ht_map, detail::gp_ht_map
00094    */
00095   template<typename Key,
00096        typename Mapped,
00097        typename Hash_Fn,
00098        typename Eq_Fn,
00099        typename Resize_Policy,
00100        bool Store_Hash,
00101        typename Tag,
00102        typename Policy_Tl,
00103        typename _Alloc>
00104   class basic_hash_table : public PB_DS_HASH_BASE
00105   {
00106   private:
00107     typedef typename PB_DS_HASH_BASE        base_type;
00108 
00109   public:
00110     virtual
00111     ~basic_hash_table() { }
00112 
00113   protected:
00114     basic_hash_table() { }
00115 
00116     basic_hash_table(const basic_hash_table& other)
00117     : base_type((const base_type&)other) { }
00118 
00119     template<typename T0>
00120       basic_hash_table(T0 t0) : base_type(t0) { }
00121 
00122     template<typename T0, typename T1>
00123       basic_hash_table(T0 t0, T1 t1) : base_type(t0, t1) { }
00124 
00125     template<typename T0, typename T1, typename T2>
00126       basic_hash_table(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { }
00127 
00128     template<typename T0, typename T1, typename T2, typename T3>
00129       basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3)
00130       : base_type(t0, t1, t2, t3) { }
00131 
00132     template<typename T0, typename T1, typename T2, typename T3, typename T4>
00133       basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4)
00134       : base_type(t0, t1, t2, t3, t4) { }
00135 
00136     template<typename T0, typename T1, typename T2, typename T3, typename T4,
00137          typename T5>
00138       basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5)
00139       : base_type(t0, t1, t2, t3, t4, t5) { }
00140 
00141     template<typename T0, typename T1, typename T2, typename T3, typename T4,
00142          typename T5, typename T6>
00143       basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6)
00144       : base_type(t0, t1, t2, t3, t4, t5, t6) { }
00145 
00146     template<typename T0, typename T1, typename T2, typename T3, typename T4,
00147          typename T5, typename T6, typename T7>
00148       basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6, T7 t7)
00149       : base_type(t0, t1, t2, t3, t4, t5, t6, t7) { }
00150 
00151     template<typename T0, typename T1, typename T2, typename T3, typename T4,
00152          typename T5, typename T6, typename T7, typename T8>
00153       basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6,
00154                T7 t7, T8 t8)
00155       : base_type(t0, t1, t2, t3, t4, t5, t6, t7, t8)
00156       { }
00157 
00158   private:
00159     basic_hash_table&
00160     operator=(const base_type&);
00161   };
00162 
00163 #undef PB_DS_HASH_BASE
00164 
00165 
00166 #define PB_DS_CC_HASH_BASE \
00167   basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
00168            cc_hash_tag, \
00169       typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, _Alloc>
00170 
00171 
00172   /**
00173    *  A collision-chaining hash-based associative container.
00174    *
00175    *  @tparam Key           Key type.
00176    *  @tparam Mapped            Map type.
00177    *  @tparam Hash_Fn           Hashing functor.
00178    *  @tparam Eq_Fn         Equal functor.
00179    *  @tparam Comb_Hash_Fn  Combining hash functor.
00180    *                            If Hash_Fn is not null_type, then this
00181    *                            is the ranged-hash functor; otherwise,
00182    *                            this is the range-hashing functor.
00183    *                    XXX(See Design::Hash-Based Containers::Hash Policies.)
00184    *  @tparam Resize_Policy     Resizes hash.
00185    *  @tparam Store_Hash        Indicates whether the hash value
00186    *                            will be stored along with each key.
00187    *                            If Hash_Fn is null_type, then the
00188    *                            container will not compile if this
00189    *                            value is true
00190    *  @tparam _Alloc            Allocator type.
00191    *
00192    *  Base tag choices are:     cc_hash_tag.
00193    *
00194    *  Base is basic_hash_table.
00195    */
00196   template<typename Key,
00197        typename Mapped,
00198        typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
00199        typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
00200        typename Comb_Hash_Fn = detail::default_comb_hash_fn::type,
00201        typename Resize_Policy = typename detail::default_resize_policy<Comb_Hash_Fn>::type,
00202        bool Store_Hash = detail::default_store_hash,
00203        typename _Alloc = std::allocator<char> >
00204   class cc_hash_table :  public PB_DS_CC_HASH_BASE
00205   {
00206   private:
00207     typedef PB_DS_CC_HASH_BASE          base_type;
00208 
00209   public:
00210     typedef cc_hash_tag                 container_category;
00211     typedef Hash_Fn                 hash_fn;
00212     typedef Eq_Fn               eq_fn;
00213     typedef Resize_Policy           resize_policy;
00214     typedef Comb_Hash_Fn            comb_hash_fn;
00215 
00216     /// Default constructor.
00217     cc_hash_table() { }
00218 
00219     /// Constructor taking some policy objects. r_hash_fn will be
00220     /// copied by the Hash_Fn object of the container object.
00221     cc_hash_table(const hash_fn& h)
00222     : base_type(h) { }
00223 
00224     /// Constructor taking some policy objects. r_hash_fn will be
00225     /// copied by the hash_fn object of the container object, and
00226     /// r_eq_fn will be copied by the eq_fn object of the container
00227     /// object.
00228     cc_hash_table(const hash_fn& h, const eq_fn& e)
00229     : base_type(h, e) { }
00230 
00231     /// Constructor taking some policy objects. r_hash_fn will be
00232     /// copied by the hash_fn object of the container object, r_eq_fn
00233     /// will be copied by the eq_fn object of the container object,
00234     /// and r_comb_hash_fn will be copied by the comb_hash_fn object
00235     /// of the container object.
00236     cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch)
00237     : base_type(h, e, ch) { }
00238 
00239     /// Constructor taking some policy objects. r_hash_fn will be
00240     /// copied by the hash_fn object of the container object, r_eq_fn
00241     /// will be copied by the eq_fn object of the container object,
00242     /// r_comb_hash_fn will be copied by the comb_hash_fn object of
00243     /// the container object, and r_resize_policy will be copied by
00244     /// the resize_policy object of the container object.
00245     cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch,
00246           const resize_policy& rp)
00247     : base_type(h, e, ch, rp) { }
00248 
00249     /// Constructor taking __iterators to a range of value_types. The
00250     /// value_types between first_it and last_it will be inserted into
00251     /// the container object.
00252     template<typename It>
00253     cc_hash_table(It first, It last)
00254     { base_type::copy_from_range(first, last); }
00255 
00256     /// Constructor taking __iterators to a range of value_types and
00257     /// some policy objects. The value_types between first_it and
00258     /// last_it will be inserted into the container object.
00259     template<typename It>
00260     cc_hash_table(It first, It last, const hash_fn& h)
00261     : base_type(h)
00262     { this->copy_from_range(first, last); }
00263 
00264     /// Constructor taking __iterators to a range of value_types and
00265     /// some policy objects The value_types between first_it and
00266     /// last_it will be inserted into the container object. r_hash_fn
00267     /// will be copied by the hash_fn object of the container object,
00268     /// and r_eq_fn will be copied by the eq_fn object of the
00269     /// container object.
00270     template<typename It>
00271     cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
00272     : base_type(h, e)
00273     { this->copy_from_range(first, last); }
00274 
00275     /// Constructor taking __iterators to a range of value_types and
00276     /// some policy objects The value_types between first_it and
00277     /// last_it will be inserted into the container object. r_hash_fn
00278     /// will be copied by the hash_fn object of the container object,
00279     /// r_eq_fn will be copied by the eq_fn object of the container
00280     /// object, and r_comb_hash_fn will be copied by the comb_hash_fn
00281     /// object of the container object.
00282     template<typename It>
00283     cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
00284           const comb_hash_fn& ch)
00285     : base_type(h, e, ch)
00286     { this->copy_from_range(first, last); }
00287 
00288     /// Constructor taking __iterators to a range of value_types and
00289     /// some policy objects The value_types between first_it and
00290     /// last_it will be inserted into the container object. r_hash_fn
00291     /// will be copied by the hash_fn object of the container object,
00292     /// r_eq_fn will be copied by the eq_fn object of the container
00293     /// object, r_comb_hash_fn will be copied by the comb_hash_fn
00294     /// object of the container object, and r_resize_policy will be
00295     /// copied by the resize_policy object of the container object.
00296     template<typename It>
00297     cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
00298           const comb_hash_fn& ch, const resize_policy& rp)
00299     : base_type(h, e, ch, rp)
00300     { this->copy_from_range(first, last); }
00301 
00302     cc_hash_table(const cc_hash_table& other)
00303     : base_type((const base_type&)other)
00304     { }
00305 
00306     virtual
00307     ~cc_hash_table() { }
00308 
00309     cc_hash_table&
00310     operator=(const cc_hash_table& other)
00311     {
00312       if (this != &other)
00313     {
00314       cc_hash_table tmp(other);
00315       swap(tmp);
00316     }
00317       return *this;
00318     }
00319 
00320     void
00321     swap(cc_hash_table& other)
00322     { base_type::swap(other); }
00323   };
00324 
00325 #undef PB_DS_CC_HASH_BASE
00326 
00327 
00328 #define PB_DS_GP_HASH_BASE \
00329   basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
00330            gp_hash_tag, \
00331   typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, _Alloc>
00332 
00333 
00334   /**
00335    *  A general-probing hash-based associative container.
00336    *
00337    *  @tparam Key           Key type.
00338    *  @tparam Mapped            Map type.
00339    *  @tparam Hash_Fn           Hashing functor.
00340    *  @tparam Eq_Fn         Equal functor.
00341    *  @tparam Comb_Probe_Fn Combining probe functor.
00342    *                            If Hash_Fn is not null_type, then this
00343    *                            is the ranged-probe functor; otherwise,
00344    *                            this is the range-hashing functor.
00345    *                    XXX See Design::Hash-Based Containers::Hash Policies.
00346    *  @tparam Probe_Fn      Probe functor.
00347    *  @tparam Resize_Policy     Resizes hash.
00348    *  @tparam Store_Hash        Indicates whether the hash value
00349    *                            will be stored along with each key.
00350    *                            If Hash_Fn is null_type, then the
00351    *                            container will not compile if this
00352    *                            value is true
00353    *  @tparam _Alloc            Allocator type.
00354    *
00355    *  Base tag choices are:     gp_hash_tag.
00356    *
00357    *  Base is basic_hash_table.
00358    */
00359   template<typename Key,
00360        typename Mapped,
00361        typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
00362        typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
00363        typename Comb_Probe_Fn = detail::default_comb_hash_fn::type,
00364        typename Probe_Fn = typename detail::default_probe_fn<Comb_Probe_Fn>::type,
00365        typename Resize_Policy = typename detail::default_resize_policy<Comb_Probe_Fn>::type,
00366        bool Store_Hash = detail::default_store_hash,
00367        typename _Alloc = std::allocator<char> >
00368   class gp_hash_table : public PB_DS_GP_HASH_BASE
00369   {
00370   private:
00371     typedef PB_DS_GP_HASH_BASE          base_type;
00372 
00373   public:
00374     typedef gp_hash_tag                 container_category;
00375     typedef Hash_Fn                 hash_fn;
00376     typedef Eq_Fn               eq_fn;
00377     typedef Comb_Probe_Fn           comb_probe_fn;
00378     typedef Probe_Fn                probe_fn;
00379     typedef Resize_Policy           resize_policy;
00380 
00381     /// Default constructor.
00382     gp_hash_table() { }
00383 
00384     /// Constructor taking some policy objects. r_hash_fn will be
00385     /// copied by the hash_fn object of the container object.
00386     gp_hash_table(const hash_fn& h)
00387     : base_type(h) { }
00388 
00389     /// Constructor taking some policy objects. r_hash_fn will be
00390     /// copied by the hash_fn object of the container object, and
00391     /// r_eq_fn will be copied by the eq_fn object of the container
00392     /// object.
00393     gp_hash_table(const hash_fn& h, const eq_fn& e)
00394     : base_type(h, e) { }
00395 
00396     /// Constructor taking some policy objects. r_hash_fn will be
00397     /// copied by the hash_fn object of the container object, r_eq_fn
00398     /// will be copied by the eq_fn object of the container object,
00399     /// and r_comb_probe_fn will be copied by the comb_probe_fn object
00400     /// of the container object.
00401     gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp)
00402     : base_type(h, e, cp) { }
00403 
00404     /// Constructor taking some policy objects. r_hash_fn will be
00405     /// copied by the hash_fn object of the container object, r_eq_fn
00406     /// will be copied by the eq_fn object of the container object,
00407     /// r_comb_probe_fn will be copied by the comb_probe_fn object of
00408     /// the container object, and r_probe_fn will be copied by the
00409     /// probe_fn object of the container object.
00410     gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
00411           const probe_fn& p)
00412     : base_type(h, e, cp, p) { }
00413 
00414     /// Constructor taking some policy objects. r_hash_fn will be
00415     /// copied by the hash_fn object of the container object, r_eq_fn
00416     /// will be copied by the eq_fn object of the container object,
00417     /// r_comb_probe_fn will be copied by the comb_probe_fn object of
00418     /// the container object, r_probe_fn will be copied by the
00419     /// probe_fn object of the container object, and r_resize_policy
00420     /// will be copied by the Resize_Policy object of the container
00421     /// object.
00422     gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
00423           const probe_fn& p, const resize_policy& rp)
00424     : base_type(h, e, cp, p, rp) { }
00425 
00426     /// Constructor taking __iterators to a range of value_types. The
00427     /// value_types between first_it and last_it will be inserted into
00428     /// the container object.
00429     template<typename It>
00430     gp_hash_table(It first, It last)
00431     { base_type::copy_from_range(first, last); }
00432 
00433     /// Constructor taking __iterators to a range of value_types and
00434     /// some policy objects. The value_types between first_it and
00435     /// last_it will be inserted into the container object. r_hash_fn
00436     /// will be copied by the hash_fn object of the container object.
00437     template<typename It>
00438     gp_hash_table(It first, It last, const hash_fn& h)
00439     : base_type(h)
00440     { base_type::copy_from_range(first, last); }
00441 
00442     /// Constructor taking __iterators to a range of value_types and
00443     /// some policy objects. The value_types between first_it and
00444     /// last_it will be inserted into the container object. r_hash_fn
00445     /// will be copied by the hash_fn object of the container object,
00446     /// and r_eq_fn will be copied by the eq_fn object of the
00447     /// container object.
00448     template<typename It>
00449     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
00450     : base_type(h, e)
00451     { base_type::copy_from_range(first, last); }
00452 
00453     /// Constructor taking __iterators to a range of value_types and
00454     /// some policy objects. The value_types between first_it and
00455     /// last_it will be inserted into the container object. r_hash_fn
00456     /// will be copied by the hash_fn object of the container object,
00457     /// r_eq_fn will be copied by the eq_fn object of the container
00458     /// object, and r_comb_probe_fn will be copied by the
00459     /// comb_probe_fn object of the container object.
00460     template<typename It>
00461     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
00462           const comb_probe_fn& cp)
00463     : base_type(h, e, cp)
00464     { base_type::copy_from_range(first, last); }
00465 
00466     /// Constructor taking __iterators to a range of value_types and
00467     /// some policy objects. The value_types between first_it and
00468     /// last_it will be inserted into the container object. r_hash_fn
00469     /// will be copied by the hash_fn object of the container object,
00470     /// r_eq_fn will be copied by the eq_fn object of the container
00471     /// object, r_comb_probe_fn will be copied by the comb_probe_fn
00472     /// object of the container object, and r_probe_fn will be copied
00473     /// by the probe_fn object of the container object.
00474     template<typename It>
00475     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
00476           const comb_probe_fn& cp, const probe_fn& p)
00477     : base_type(h, e, cp, p)
00478     { base_type::copy_from_range(first, last); }
00479 
00480     /// Constructor taking __iterators to a range of value_types and
00481     /// some policy objects. The value_types between first_it and
00482     /// last_it will be inserted into the container object. r_hash_fn
00483     /// will be copied by the hash_fn object of the container object,
00484     /// r_eq_fn will be copied by the eq_fn object of the container
00485     /// object, r_comb_probe_fn will be copied by the comb_probe_fn
00486     /// object of the container object, r_probe_fn will be copied by
00487     /// the probe_fn object of the container object, and
00488     /// r_resize_policy will be copied by the resize_policy object of
00489     /// the container object.
00490     template<typename It>
00491     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
00492           const comb_probe_fn& cp, const probe_fn& p,
00493           const resize_policy& rp)
00494     : base_type(h, e, cp, p, rp)
00495     { base_type::copy_from_range(first, last); }
00496 
00497     gp_hash_table(const gp_hash_table& other)
00498     : base_type((const base_type&)other)
00499     { }
00500 
00501     virtual
00502     ~gp_hash_table() { }
00503 
00504     gp_hash_table&
00505     operator=(const gp_hash_table& other)
00506     {
00507       if (this != &other)
00508     {
00509       gp_hash_table tmp(other);
00510       swap(tmp);
00511     }
00512       return *this;
00513     }
00514 
00515     void
00516     swap(gp_hash_table& other)
00517     { base_type::swap(other); }
00518   };
00519   //@} hash-based
00520 #undef PB_DS_GP_HASH_BASE
00521 
00522 
00523   /**
00524    *  @defgroup branch-based
00525    *  @ingroup containers-pbds
00526    *  @{
00527    */
00528 #define PB_DS_BRANCH_BASE \
00529   detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, Policy_Tl>::type
00530 
00531   /**
00532    *  @defgroup branch-detail Base and Policy Classes
00533    *  @ingroup branch-based
00534    */
00535 
00536   /**
00537    *  A branched, tree-like (tree, trie) container abstraction.
00538    *
00539    *  @tparam Key       Key type.
00540    *  @tparam Mapped        Map type.
00541    *  @tparam Tag       Instantiating data structure type,
00542    *                            see container_tag.
00543    *  @tparam Node_Update   Updates nodes, restores invariants.
00544    *  @tparam Policy_TL         Policy typelist.
00545    *  @tparam _Alloc        Allocator type.
00546    *
00547    *  Base is dispatched at compile time via Tag, from the following
00548    *  choices: tree_tag, trie_tag, and their descendants.
00549    *
00550    *  Base choices are: detail::ov_tree_map, detail::rb_tree_map,
00551    *                detail::splay_tree_map, and detail::pat_trie_map.
00552    */
00553   template<typename Key, typename Mapped, typename Tag,
00554        typename Node_Update, typename Policy_Tl, typename _Alloc>
00555   class basic_branch : public PB_DS_BRANCH_BASE
00556   {
00557   private:
00558     typedef typename PB_DS_BRANCH_BASE          base_type;
00559 
00560   public:
00561     typedef Node_Update             node_update;
00562 
00563     virtual
00564     ~basic_branch() { }
00565 
00566   protected:
00567     basic_branch() { }
00568 
00569     basic_branch(const basic_branch& other)
00570     : base_type((const base_type&)other) { }
00571 
00572     template<typename T0>
00573       basic_branch(T0 t0) : base_type(t0) { }
00574 
00575     template<typename T0, typename T1>
00576       basic_branch(T0 t0, T1 t1) : base_type(t0, t1) { }
00577 
00578     template<typename T0, typename T1, typename T2>
00579       basic_branch(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { }
00580 
00581     template<typename T0, typename T1, typename T2, typename T3>
00582       basic_branch(T0 t0, T1 t1, T2 t2, T3 t3)
00583       : base_type(t0, t1, t2, t3) { }
00584 
00585     template<typename T0, typename T1, typename T2, typename T3, typename T4>
00586       basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4)
00587       : base_type(t0, t1, t2, t3, t4) { }
00588 
00589     template<typename T0, typename T1, typename T2, typename T3, typename T4,
00590          typename T5>
00591       basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5)
00592       : base_type(t0, t1, t2, t3, t4, t5) { }
00593 
00594     template<typename T0, typename T1, typename T2, typename T3, typename T4,
00595          typename T5, typename T6>
00596       basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6)
00597       : base_type(t0, t1, t2, t3, t4, t5, t6) { }
00598   };
00599 #undef PB_DS_BRANCH_BASE
00600 
00601 
00602 #define PB_DS_TREE_NODE_AND_IT_TRAITS \
00603   detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag,_Alloc>
00604 
00605 #define PB_DS_TREE_BASE \
00606   basic_branch<Key,Mapped, Tag, \
00607            typename PB_DS_TREE_NODE_AND_IT_TRAITS::node_update, \
00608            typename __gnu_cxx::typelist::create2<Cmp_Fn, \
00609            PB_DS_TREE_NODE_AND_IT_TRAITS>::type, _Alloc>
00610 
00611 
00612   /**
00613    *  A tree-based container.
00614    *
00615    *  @tparam Key       Key type.
00616    *  @tparam Mapped        Map type.
00617    *  @tparam Cmp_Fn        Comparison functor.
00618    *  @tparam Tag       Instantiating data structure type,
00619    *                            see container_tag.
00620    *  @tparam Node_Update   Updates nodes,
00621    *                            restores invariants when invalidated.
00622    *                     XXX See design::tree-based-containers::node invariants.
00623    *  @tparam _Alloc        Allocator type.
00624    *
00625    *  Base tag choices are: ov_tree_tag, rb_tree_tag, splay_tree_tag.
00626    *
00627    *  Base is basic_branch.
00628    */
00629   template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>,
00630        typename Tag = rb_tree_tag,
00631        template<typename Node_CItr, typename Node_Itr,
00632             typename Cmp_Fn_, typename _Alloc_>
00633        class Node_Update = null_node_update,
00634        typename _Alloc = std::allocator<char> >
00635   class tree : public PB_DS_TREE_BASE
00636   {
00637   private:
00638     typedef PB_DS_TREE_BASE             base_type;
00639 
00640   public:
00641     /// Comparison functor type.
00642     typedef Cmp_Fn              cmp_fn;
00643 
00644     tree() { }
00645 
00646     /// Constructor taking some policy objects. r_cmp_fn will be
00647     /// copied by the Cmp_Fn object of the container object.
00648     tree(const cmp_fn& c)
00649     : base_type(c) { }
00650 
00651     /// Constructor taking __iterators to a range of value_types. The
00652     /// value_types between first_it and last_it will be inserted into
00653     /// the container object.
00654     template<typename It>
00655     tree(It first, It last)
00656     { base_type::copy_from_range(first, last); }
00657 
00658     /// Constructor taking __iterators to a range of value_types and
00659     /// some policy objects The value_types between first_it and
00660     /// last_it will be inserted into the container object. r_cmp_fn
00661     /// will be copied by the cmp_fn object of the container object.
00662     template<typename It>
00663     tree(It first, It last, const cmp_fn& c)
00664     : base_type(c)
00665     { base_type::copy_from_range(first, last); }
00666 
00667     tree(const tree& other)
00668     : base_type((const base_type&)other) { }
00669 
00670     virtual
00671     ~tree() { }
00672 
00673     tree&
00674     operator=(const tree& other)
00675     {
00676       if (this != &other)
00677     {
00678       tree tmp(other);
00679       swap(tmp);
00680     }
00681       return *this;
00682     }
00683 
00684     void
00685     swap(tree& other)
00686     { base_type::swap(other); }
00687   };
00688 
00689 #undef PB_DS_TREE_BASE
00690 #undef PB_DS_TREE_NODE_AND_IT_TRAITS
00691 
00692 
00693 #define PB_DS_TRIE_NODE_AND_IT_TRAITS \
00694   detail::trie_traits<Key,Mapped,_ATraits,Node_Update,Tag,_Alloc>
00695 
00696 #define PB_DS_TRIE_BASE \
00697   basic_branch<Key,Mapped,Tag, \
00698            typename PB_DS_TRIE_NODE_AND_IT_TRAITS::node_update, \
00699            typename __gnu_cxx::typelist::create2<_ATraits, \
00700            PB_DS_TRIE_NODE_AND_IT_TRAITS >::type, _Alloc>
00701 
00702 
00703   /**
00704    *  A trie-based container.
00705    *
00706    *  @tparam Key       Key type.
00707    *  @tparam Mapped        Map type.
00708    *  @tparam _ATraits      Element access traits.
00709    *  @tparam Tag       Instantiating data structure type,
00710    *                            see container_tag.
00711    *  @tparam Node_Update   Updates trie nodes,
00712    *                            restores invariants when invalidated.
00713    *                     XXX See design::tree-based-containers::node invariants.
00714    *  @tparam _Alloc        Allocator type.
00715    *
00716    *  Base tag choice is pat_trie_tag.
00717    *
00718    *  Base is basic_branch.
00719    */
00720   template<typename Key,
00721        typename Mapped,
00722        typename _ATraits = \
00723             typename detail::default_trie_access_traits<Key>::type,
00724        typename Tag = pat_trie_tag,
00725        template<typename Node_CItr,
00726             typename Node_Itr,
00727             typename _ATraits_,
00728             typename _Alloc_>
00729        class Node_Update = null_node_update,
00730        typename _Alloc = std::allocator<char> >
00731   class trie : public PB_DS_TRIE_BASE
00732   {
00733   private:
00734     typedef PB_DS_TRIE_BASE         base_type;
00735 
00736   public:
00737     /// Element access traits type.
00738     typedef _ATraits                access_traits;
00739 
00740     trie() { }
00741 
00742     /// Constructor taking some policy objects. r_access_traits will
00743     /// be copied by the _ATraits object of the container object.
00744     trie(const access_traits& t)
00745     : base_type(t) { }
00746 
00747     /// Constructor taking __iterators to a range of value_types. The
00748     /// value_types between first_it and last_it will be inserted into
00749     /// the container object.
00750     template<typename It>
00751     trie(It first, It last)
00752     { base_type::copy_from_range(first, last); }
00753 
00754     /// Constructor taking __iterators to a range of value_types and
00755     /// some policy objects. The value_types between first_it and
00756     /// last_it will be inserted into the container object.
00757     template<typename It>
00758     trie(It first, It last, const access_traits& t)
00759     : base_type(t)
00760     { base_type::copy_from_range(first, last); }
00761 
00762     trie(const trie& other)
00763     : base_type((const base_type&)other) { }
00764 
00765     virtual
00766     ~trie() { }
00767 
00768     trie&
00769     operator=(const trie& other)
00770     {
00771       if (this != &other)
00772     {
00773       trie tmp(other);
00774       swap(tmp);
00775     }
00776       return *this;
00777     }
00778 
00779     void
00780     swap(trie& other)
00781     { base_type::swap(other); }
00782   };
00783   //@} branch-based
00784 #undef PB_DS_TRIE_BASE
00785 #undef PB_DS_TRIE_NODE_AND_IT_TRAITS
00786 
00787 
00788   /**
00789    *  @defgroup list-based
00790    *  @ingroup containers-pbds
00791    *  @{
00792    */
00793 #define PB_DS_LU_BASE \
00794   detail::container_base_dispatch<Key, Mapped, _Alloc, list_update_tag, \
00795     typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type>::type
00796 
00797 
00798   /**
00799    *  A list-update based associative container.
00800    *
00801    *  @tparam Key           Key type.
00802    *  @tparam Mapped            Map type.
00803    *  @tparam Eq_Fn         Equal functor.
00804    *  @tparam Update_Policy Update policy, determines when an element
00805    *                            will be moved to the front of the list.
00806    *  @tparam _Alloc            Allocator type.
00807    *
00808    *  Base is detail::lu_map.
00809    */
00810   template<typename Key,
00811        typename Mapped,
00812        class Eq_Fn = typename detail::default_eq_fn<Key>::type,
00813        class Update_Policy = detail::default_update_policy::type,
00814        class _Alloc = std::allocator<char> >
00815   class list_update : public PB_DS_LU_BASE
00816   {
00817   private:
00818     typedef typename PB_DS_LU_BASE      base_type;
00819 
00820   public:
00821     typedef list_update_tag             container_category;
00822     typedef Eq_Fn               eq_fn;
00823     typedef Update_Policy           update_policy;
00824 
00825     list_update() { }
00826 
00827     /// Constructor taking __iterators to a range of value_types. The
00828     /// value_types between first_it and last_it will be inserted into
00829     /// the container object.
00830     template<typename It>
00831     list_update(It first, It last)
00832     { base_type::copy_from_range(first, last); }
00833 
00834     list_update(const list_update& other)
00835     : base_type((const base_type&)other) { }
00836 
00837     virtual
00838     ~list_update() { }
00839 
00840     list_update&
00841     operator=(const list_update& other)
00842     {
00843       if (this !=& other)
00844     {
00845       list_update tmp(other);
00846       swap(tmp);
00847     }
00848       return *this;
00849     }
00850 
00851     void
00852     swap(list_update& other)
00853     { base_type::swap(other); }
00854   };
00855   //@} list-based
00856 #undef PB_DS_LU_BASE
00857 
00858   // @} group containers-pbds
00859 } // namespace __gnu_pbds
00860 
00861 #endif