libstdc++
assoc_container.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2009, 2010 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/basic_tree_policy/traits.hpp>
00050 
00051 namespace __gnu_pbds
00052 {
00053   /** @defgroup pbds Policy-Based Data Structures
00054    *  @ingroup extensions
00055    *
00056    *  This is a library of policy-based elementary data structures:
00057    *  associative containers and priority queues. It is designed for
00058    *  high-performance, flexibility, semantic safety, and conformance
00059    *  to the corresponding containers in std (except for some points
00060    *  where it differs by design).
00061    *
00062    *  For details, see: 
00063    *  http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html
00064    *
00065    *  @{
00066    */
00067  
00068 #define PB_DS_BASE_C_DEC \
00069   detail::container_base_dispatch<Key, Mapped, Tag, Policy_Tl, Allocator>::type
00070 
00071   /// An abstract basic associative container.
00072   template<typename Key, 
00073        typename Mapped, 
00074        typename Tag, 
00075        typename Policy_Tl, 
00076        typename Allocator>
00077   class container_base : public PB_DS_BASE_C_DEC
00078   {
00079   private:
00080     typedef typename PB_DS_BASE_C_DEC           base_type;
00081 
00082   public:
00083     typedef Tag                     container_category;
00084     typedef Allocator                   allocator_type;
00085     typedef typename allocator_type::size_type      size_type;
00086     typedef typename allocator_type::difference_type    difference_type;
00087 
00088     // key_type
00089     typedef typename allocator_type::template rebind<Key>::other::value_type key_type;
00090     typedef typename allocator_type::template rebind<key_type>::other key_rebind;
00091     typedef typename key_rebind::reference      key_reference;
00092     typedef typename key_rebind::const_reference    const_key_reference;
00093     typedef typename key_rebind::pointer        key_pointer;
00094     typedef typename key_rebind::const_pointer      const_key_pointer;
00095 
00096     // mapped_type
00097     typedef Mapped                  mapped_type;
00098     typedef typename allocator_type::template rebind<mapped_type>::other mapped_rebind;
00099     typedef typename mapped_rebind::reference       mapped_reference;
00100     typedef typename mapped_rebind::const_reference const_mapped_reference;
00101     typedef typename mapped_rebind::pointer         mapped_pointer;
00102     typedef typename mapped_rebind::const_pointer   const_mapped_pointer;
00103 
00104     // value_type
00105     typedef typename base_type::value_type      value_type;
00106     typedef typename allocator_type::template rebind<value_type>::other value_rebind;
00107     typedef typename value_rebind::reference        reference;
00108     typedef typename value_rebind::const_reference  const_reference;
00109     typedef typename value_rebind::pointer      pointer;
00110     typedef typename value_rebind::const_pointer    const_pointer;
00111 
00112     // iterators
00113     typedef typename base_type::iterator        iterator;
00114     typedef typename base_type::const_iterator      const_iterator;
00115     typedef typename base_type::point_iterator      point_iterator;
00116     typedef typename base_type::const_point_iterator    const_point_iterator;
00117 
00118     virtual
00119     ~container_base() { }
00120 
00121   protected:
00122 #define PB_DS_CLASS_NAME        container_base
00123 #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
00124 #undef PB_DS_CLASS_NAME
00125   };
00126 
00127 #undef PB_DS_BASE_C_DEC
00128 
00129 
00130 #define PB_DS_BASE_C_DEC \
00131   container_base<Key, Mapped, Tag, typename __gnu_cxx::typelist::append< \
00132   typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, detail::integral_constant<int, Store_Hash> >::type, Policy_TL>::type, Allocator>
00133 
00134   /// An abstract basic hash-based associative container.
00135   template<typename Key,
00136        typename Mapped,
00137        typename Hash_Fn,
00138        typename Eq_Fn,
00139        typename Resize_Policy,
00140        bool Store_Hash,
00141        typename Tag,
00142        typename Policy_TL,
00143        typename Allocator>
00144   class basic_hash_table : public PB_DS_BASE_C_DEC
00145   {
00146   private:
00147     typedef PB_DS_BASE_C_DEC base_type;
00148 
00149   public:
00150     virtual
00151     ~basic_hash_table() { }
00152 
00153   protected:
00154 #define PB_DS_CLASS_NAME basic_hash_table
00155 #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
00156 #undef PB_DS_CLASS_NAME
00157 
00158   private:
00159     basic_hash_table& 
00160     operator=(const base_type&);
00161   };
00162 
00163 #undef PB_DS_BASE_C_DEC
00164 
00165 
00166 #define PB_DS_BASE_C_DEC \
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, Allocator>
00170 
00171   /// A concrete collision-chaining hash-based associative container.
00172   template<typename Key,
00173        typename Mapped,
00174        typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
00175        typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
00176        typename Comb_Hash_Fn = detail::default_comb_hash_fn::type,
00177        typename Resize_Policy = typename detail::default_resize_policy<Comb_Hash_Fn>::type,
00178        bool Store_Hash = detail::default_store_hash,
00179        typename Allocator = std::allocator<char> >
00180   class cc_hash_table :  public PB_DS_BASE_C_DEC
00181   {
00182   private:
00183     typedef PB_DS_BASE_C_DEC    base_type;
00184 
00185   public:
00186     typedef Hash_Fn         hash_fn;
00187     typedef Eq_Fn       eq_fn;
00188     typedef Resize_Policy   resize_policy;
00189     typedef Comb_Hash_Fn    comb_hash_fn;
00190 
00191     // Default constructor.
00192     cc_hash_table() { }
00193 
00194     // Constructor taking some policy objects. r_hash_fn will be
00195     // copied by the Hash_Fn object of the container object.
00196     cc_hash_table(const hash_fn& h) 
00197     : base_type(h) { }
00198 
00199     // Constructor taking some policy objects. r_hash_fn will be
00200     // copied by the hash_fn object of the container object, and
00201     // r_eq_fn will be copied by the eq_fn object of the container
00202     // object.
00203     cc_hash_table(const hash_fn& h, const eq_fn& e)
00204     : base_type(h, e) { }
00205 
00206     // Constructor taking some policy objects. r_hash_fn will be
00207     // copied by the hash_fn object of the container object, r_eq_fn
00208     // will be copied by the eq_fn object of the container object, and
00209     // r_comb_hash_fn will be copied by the comb_hash_fn object of the
00210     // container object.
00211     cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch)
00212     : base_type(h, e, ch) { }
00213 
00214     // Constructor taking some policy objects. r_hash_fn will be
00215     // copied by the hash_fn object of the container object, r_eq_fn
00216     // will be copied by the eq_fn object of the container object,
00217     // r_comb_hash_fn will be copied by the comb_hash_fn object of the
00218     // container object, and r_resize_policy will be copied by the
00219     // resize_policy object of the container object.
00220     cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch, 
00221           const resize_policy& rp)    
00222     : base_type(h, e, ch, rp) { }
00223 
00224     // Constructor taking __iterators to a range of value_types. The
00225     // value_types between first_it and last_it will be inserted into
00226     // the container object.
00227     template<typename It>
00228     cc_hash_table(It first, It last)
00229     { base_type::copy_from_range(first, last); }
00230 
00231     // Constructor taking __iterators to a range of value_types and
00232     // some policy objects. The value_types between first_it and
00233     // last_it will be inserted into the container object.
00234     template<typename It>
00235     cc_hash_table(It first, It last, const hash_fn& h)
00236     : base_type(h)
00237     { copy_from_range(first, last); }
00238 
00239     // Constructor taking __iterators to a range of value_types and
00240     // some policy objects The value_types between first_it and
00241     // last_it will be inserted into the container object. r_hash_fn
00242     // will be copied by the hash_fn object of the container object,
00243     // and r_eq_fn will be copied by the eq_fn object of the container
00244     // object.
00245     template<typename It>
00246     cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
00247     : base_type(h, e)
00248     { copy_from_range(first, last); }
00249 
00250     // Constructor taking __iterators to a range of value_types and
00251     // some policy objects The value_types between first_it and
00252     // last_it will be inserted into the container object. r_hash_fn
00253     // will be copied by the hash_fn object of the container object,
00254     // r_eq_fn will be copied by the eq_fn object of the container
00255     // object, and r_comb_hash_fn will be copied by the comb_hash_fn
00256     // object of the container object.
00257     template<typename It>
00258     cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
00259           const comb_hash_fn& ch)
00260     : base_type(h, e, ch)
00261     { copy_from_range(first, last); }
00262 
00263     // Constructor taking __iterators to a range of value_types and
00264     // some policy objects The value_types between first_it and
00265     // last_it will be inserted into the container object. r_hash_fn
00266     // will be copied by the hash_fn object of the container object,
00267     // r_eq_fn will be copied by the eq_fn object of the container
00268     // object, r_comb_hash_fn will be copied by the comb_hash_fn
00269     // object of the container object, and r_resize_policy will be
00270     // copied by the resize_policy object of the container object.
00271     template<typename It>
00272     cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 
00273           const comb_hash_fn& ch, const resize_policy& rp)
00274     : base_type(h, e, ch, rp)
00275     { copy_from_range(first, last); }
00276 
00277     cc_hash_table(const cc_hash_table& other)
00278     : base_type((const base_type&)other)
00279     { }
00280 
00281     virtual
00282     ~cc_hash_table() { }
00283 
00284     cc_hash_table& 
00285     operator=(const cc_hash_table& other)
00286     {
00287       if (this != &other)
00288     {
00289       cc_hash_table tmp(other);
00290       swap(tmp);
00291     }
00292       return *this;
00293     }
00294 
00295     void
00296     swap(cc_hash_table& other)
00297     { base_type::swap(other); }
00298   };
00299 
00300 #undef PB_DS_BASE_C_DEC
00301 
00302 
00303 #define PB_DS_BASE_C_DEC \
00304   basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
00305            gp_hash_tag, \
00306            typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, Allocator>
00307 
00308   /// A concrete general-probing hash-based associative container.
00309   template<typename Key,
00310        typename Mapped,
00311        typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
00312        typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
00313        typename Comb_Probe_Fn = detail::default_comb_hash_fn::type,
00314        typename Probe_Fn = typename detail::default_probe_fn<Comb_Probe_Fn>::type,
00315        typename Resize_Policy = typename detail::default_resize_policy<Comb_Probe_Fn>::type,
00316        bool Store_Hash = detail::default_store_hash,
00317        typename Allocator = std::allocator<char> >
00318   class gp_hash_table : public PB_DS_BASE_C_DEC
00319   {
00320   private:
00321     typedef PB_DS_BASE_C_DEC    base_type;
00322 
00323   public:
00324     typedef Hash_Fn         hash_fn;
00325     typedef Eq_Fn       eq_fn;
00326     typedef Comb_Probe_Fn   comb_probe_fn;
00327     typedef Probe_Fn        probe_fn;
00328     typedef Resize_Policy   resize_policy;
00329 
00330     // Default constructor.
00331     gp_hash_table() { }
00332 
00333     // Constructor taking some policy objects. r_hash_fn will be
00334     // copied by the hash_fn object of the container object.
00335     gp_hash_table(const hash_fn& h)
00336     : base_type(h) { }
00337 
00338     // Constructor taking some policy objects. r_hash_fn will be
00339     // copied by the hash_fn object of the container object, and
00340     // r_eq_fn will be copied by the eq_fn object of the container
00341     // object.
00342     gp_hash_table(const hash_fn& h, const eq_fn& e)
00343     : base_type(h, e) { }
00344 
00345     // Constructor taking some policy objects. r_hash_fn will be
00346     // copied by the hash_fn object of the container object, r_eq_fn
00347     // will be copied by the eq_fn object of the container object, and
00348     // r_comb_probe_fn will be copied by the comb_probe_fn object of
00349     // the container object.
00350     gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp)
00351     : base_type(h, e, cp) { }
00352 
00353     // Constructor taking some policy objects. r_hash_fn will be
00354     // copied by the hash_fn object of the container object, r_eq_fn
00355     // will be copied by the eq_fn object of the container object,
00356     // r_comb_probe_fn will be copied by the comb_probe_fn object of
00357     // the container object, and r_probe_fn will be copied by the
00358     // probe_fn object of the container object.
00359     gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, 
00360           const probe_fn& p)
00361     : base_type(h, e, cp, p) { }
00362 
00363     // Constructor taking some policy objects. r_hash_fn will be
00364     // copied by the hash_fn object of the container object, r_eq_fn
00365     // will be copied by the eq_fn object of the container object,
00366     // r_comb_probe_fn will be copied by the comb_probe_fn object of
00367     // the container object, r_probe_fn will be copied by the probe_fn
00368     // object of the container object, and r_resize_policy will be
00369     // copied by the Resize_Policy object of the container object.
00370     gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, 
00371           const probe_fn& p, const resize_policy& rp)
00372     : base_type(h, e, cp, p, rp) { }
00373 
00374     // Constructor taking __iterators to a range of value_types. The
00375     // value_types between first_it and last_it will be inserted into
00376     // the container object.
00377     template<typename It>
00378     gp_hash_table(It first, It last)
00379     { base_type::copy_from_range(first, last); }
00380 
00381     // Constructor taking __iterators to a range of value_types and
00382     // some policy objects. The value_types between first_it and
00383     // last_it will be inserted into the container object. r_hash_fn
00384     // will be copied by the hash_fn object of the container object.
00385     template<typename It>
00386     gp_hash_table(It first, It last, const hash_fn& h)
00387     : base_type(h)
00388     { base_type::copy_from_range(first, last); }
00389 
00390     // Constructor taking __iterators to a range of value_types and
00391     // some policy objects. The value_types between first_it and
00392     // last_it will be inserted into the container object. r_hash_fn
00393     // will be copied by the hash_fn object of the container object,
00394     // and r_eq_fn will be copied by the eq_fn object of the container
00395     // object.
00396     template<typename It>
00397     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
00398     : base_type(h, e)
00399     { base_type::copy_from_range(first, last); }
00400 
00401     // Constructor taking __iterators to a range of value_types and
00402     // some policy objects. The value_types between first_it and
00403     // last_it will be inserted into the container object. r_hash_fn
00404     // will be copied by the hash_fn object of the container object,
00405     // r_eq_fn will be copied by the eq_fn object of the container
00406     // object, and r_comb_probe_fn will be copied by the comb_probe_fn
00407     // object of the container object.
00408     template<typename It>
00409     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 
00410           const comb_probe_fn& cp)
00411     : base_type(h, e, cp)
00412     { base_type::copy_from_range(first, last); }
00413 
00414     // Constructor taking __iterators to a range of value_types and
00415     // some policy objects. The value_types between first_it and
00416     // last_it will be inserted into the container object. r_hash_fn
00417     // will be copied by the hash_fn object of the container object,
00418     // r_eq_fn will be copied by the eq_fn object of the container
00419     // object, r_comb_probe_fn will be copied by the comb_probe_fn
00420     // object of the container object, and r_probe_fn will be copied
00421     // by the probe_fn object of the container object.
00422     template<typename It>
00423     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 
00424           const comb_probe_fn& cp, const probe_fn& p)
00425     : base_type(h, e, cp, p)
00426     { base_type::copy_from_range(first, last); }
00427 
00428     // Constructor taking __iterators to a range of value_types and
00429     // some policy objects. The value_types between first_it and
00430     // last_it will be inserted into the container object. r_hash_fn
00431     // will be copied by the hash_fn object of the container object,
00432     // r_eq_fn will be copied by the eq_fn object of the container
00433     // object, r_comb_probe_fn will be copied by the comb_probe_fn
00434     // object of the container object, r_probe_fn will be copied by
00435     // the probe_fn object of the container object, and
00436     // r_resize_policy will be copied by the resize_policy object of
00437     // the container object.
00438     template<typename It>
00439     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 
00440           const comb_probe_fn& cp, const probe_fn& p, 
00441           const resize_policy& rp)
00442     : base_type(h, e, cp, p, rp)
00443     { base_type::copy_from_range(first, last); }
00444 
00445     gp_hash_table(const gp_hash_table& other)
00446     : base_type((const base_type&)other)
00447     { }
00448 
00449     virtual
00450     ~gp_hash_table() { }
00451 
00452     gp_hash_table& 
00453     operator=(const gp_hash_table& other)
00454     {
00455       if (this != &other)
00456     {
00457       gp_hash_table tmp(other);
00458       swap(tmp);
00459     }
00460       return *this;
00461     }
00462 
00463     void
00464     swap(gp_hash_table& other)
00465     { base_type::swap(other); }
00466   };
00467 
00468 #undef PB_DS_BASE_C_DEC
00469 
00470 
00471 #define PB_DS_BASE_C_DEC \
00472   container_base<Key, Mapped, Tag, Policy_Tl, Allocator>
00473 
00474   /// An abstract basic tree-like (tree, trie) associative container.
00475   template<typename Key, typename Mapped, typename Tag, 
00476        typename Node_Update, typename Policy_Tl, typename Allocator>
00477   class basic_tree : public PB_DS_BASE_C_DEC
00478   {
00479   private:
00480     typedef PB_DS_BASE_C_DEC    base_type;
00481 
00482   public:
00483     typedef Node_Update     node_update;
00484 
00485     virtual
00486     ~basic_tree() { }
00487 
00488   protected:
00489 #define PB_DS_CLASS_NAME        basic_tree
00490 #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
00491 #undef PB_DS_CLASS_NAME
00492   };
00493 
00494 #undef PB_DS_BASE_C_DEC
00495 
00496 
00497 #define PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC \
00498   detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag, Allocator>
00499 
00500 #define PB_DS_BASE_C_DEC \
00501   basic_tree<Key,Mapped,Tag,typename PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC::node_update, \
00502          typename __gnu_cxx::typelist::create2<Cmp_Fn, PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC >::type, Allocator>
00503 
00504   /// A concrete basic tree-based associative container.
00505   template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>,
00506        typename Tag = rb_tree_tag,
00507        template<typename Const_Node_Iterator, typename Node_Iterator, typename Cmp_Fn_, typename Allocator_>
00508   class Node_Update = __gnu_pbds::null_tree_node_update,
00509        typename Allocator = std::allocator<char> >
00510   class tree : public PB_DS_BASE_C_DEC
00511   {
00512   private:
00513     typedef PB_DS_BASE_C_DEC    base_type;
00514 
00515   public:
00516     // Comparison functor type.
00517     typedef Cmp_Fn      cmp_fn;
00518 
00519     tree() { }
00520 
00521     // Constructor taking some policy objects. r_cmp_fn will be copied
00522     // by the Cmp_Fn object of the container object.
00523     tree(const cmp_fn& c)
00524     : base_type(c) { }
00525 
00526     // Constructor taking __iterators to a range of value_types. The
00527     // value_types between first_it and last_it will be inserted into
00528     // the container object.
00529     template<typename It>
00530     tree(It first, It last)
00531     { base_type::copy_from_range(first, last); }
00532 
00533     // Constructor taking __iterators to a range of value_types and
00534     // some policy objects The value_types between first_it and
00535     // last_it will be inserted into the container object. r_cmp_fn
00536     // will be copied by the cmp_fn object of the container object.
00537     template<typename It>
00538     tree(It first, It last, const cmp_fn& c)
00539       : base_type(c)
00540     { base_type::copy_from_range(first, last); }
00541 
00542     tree(const tree& other)
00543     : base_type((const base_type&)other) { }
00544 
00545     virtual
00546     ~tree() { }
00547 
00548     tree& 
00549     operator=(const tree& other)
00550     {
00551       if (this != &other)
00552     {
00553       tree tmp(other);
00554       swap(tmp);
00555     }
00556       return *this;
00557     }
00558 
00559     void
00560     swap(tree& other)
00561     { base_type::swap(other); }
00562   };
00563 
00564 #undef PB_DS_BASE_C_DEC
00565 #undef PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC
00566 
00567 
00568 #define PB_DS_TRIE_NODE_AND_ITS_TRAITS \
00569   detail::trie_traits<Key,Mapped,E_Access_Traits,Node_Update,Tag,Allocator>
00570 
00571 #define PB_DS_BASE_C_DEC \
00572   basic_tree<Key,Mapped,Tag, typename PB_DS_TRIE_NODE_AND_ITS_TRAITS::node_update, \
00573          typename __gnu_cxx::typelist::create2<E_Access_Traits, PB_DS_TRIE_NODE_AND_ITS_TRAITS >::type, Allocator>
00574 
00575   /// A concrete basic trie-based associative container.
00576   template<typename Key,
00577        typename Mapped,
00578        typename E_Access_Traits = typename detail::default_trie_e_access_traits<Key>::type,
00579        typename Tag = pat_trie_tag,
00580        template<typename Const_Node_Iterator,
00581             typename Node_Iterator,
00582             typename E_Access_Traits_,
00583             typename Allocator_>
00584   class Node_Update = null_trie_node_update,
00585        typename Allocator = std::allocator<char> >
00586   class trie : public PB_DS_BASE_C_DEC
00587   {
00588   private:
00589     typedef PB_DS_BASE_C_DEC base_type;
00590 
00591   public:
00592     // Element access traits type.
00593     typedef E_Access_Traits e_access_traits;
00594 
00595     trie() { }
00596 
00597     // Constructor taking some policy objects. r_e_access_traits will
00598     // be copied by the E_Access_Traits object of the container
00599     // object.
00600     trie(const e_access_traits& t)
00601     : base_type(t) { }
00602 
00603     // Constructor taking __iterators to a range of value_types. The
00604     // value_types between first_it and last_it will be inserted into
00605     // the container object.
00606     template<typename It>
00607     trie(It first, It last)
00608     { base_type::copy_from_range(first, last); }
00609 
00610     // Constructor taking __iterators to a range of value_types and
00611     // some policy objects. The value_types between first_it and
00612     // last_it will be inserted into the container object.
00613     template<typename It>
00614     trie(It first, It last, const e_access_traits& t)
00615     : base_type(t)
00616     { base_type::copy_from_range(first, last); }
00617 
00618     trie(const trie& other)
00619     : base_type((const base_type&)other) { }
00620 
00621     virtual
00622     ~trie() { }
00623 
00624     trie& 
00625     operator=(const trie& other)
00626     {
00627       if (this != &other)
00628     {
00629       trie tmp(other);
00630       swap(tmp);
00631     }
00632       return *this;
00633     }
00634 
00635     void
00636     swap(trie& other)
00637     { base_type::swap(other); }
00638   };
00639 
00640 #undef PB_DS_BASE_C_DEC
00641 #undef PB_DS_TRIE_NODE_AND_ITS_TRAITS
00642 
00643 
00644 #define PB_DS_BASE_C_DEC \
00645   container_base<Key, Mapped, list_update_tag, \
00646          typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type, Allocator>
00647 
00648   /// A list-update based associative container.
00649   template<typename Key,
00650        typename Mapped,
00651        class Eq_Fn = typename detail::default_eq_fn<Key>::type,
00652        class Update_Policy = detail::default_update_policy::type,
00653        class Allocator = std::allocator<char> >
00654   class list_update : public PB_DS_BASE_C_DEC
00655   {
00656   private:
00657     typedef PB_DS_BASE_C_DEC    base_type;
00658 
00659   public:
00660     typedef Eq_Fn       eq_fn;
00661     typedef Update_Policy   update_policy;
00662     typedef Allocator       allocator;
00663 
00664     list_update() { }
00665 
00666     // Constructor taking __iterators to a range of value_types. The
00667     // value_types between first_it and last_it will be inserted into
00668     // the container object.
00669     template<typename It>
00670     list_update(It first, It last)
00671     { base_type::copy_from_range(first, last); }
00672 
00673     list_update(const list_update& other)
00674     : base_type((const base_type&)other) { }
00675 
00676     virtual
00677     ~list_update() { }
00678 
00679     list_update& 
00680     operator=(const list_update& other)
00681     {
00682       if (this !=& other)
00683     {
00684       list_update tmp(other);
00685       swap(tmp);
00686     }
00687       return *this;
00688     }
00689 
00690     void
00691     swap(list_update& other)
00692     { base_type::swap(other); }
00693   };
00694 
00695 #undef PB_DS_BASE_C_DEC
00696 
00697   // @} group pbds
00698 } // namespace __gnu_pbds
00699 
00700 #endif