assoc_container.hpp

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

Generated on Thu Jul 23 21:15:57 2009 for libstdc++ by  doxygen 1.5.8