Edit File: assoc_container.hpp
// -*- C++ -*- // Copyright (C) 2005-2013 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 3, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // Under Section 7 of GPL version 3, you are granted additional // permissions described in the GCC Runtime Library Exception, version // 3.1, as published by the Free Software Foundation. // You should have received a copy of the GNU General Public License and // a copy of the GCC Runtime Library Exception along with this program; // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see // <http://www.gnu.org/licenses/>. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file assoc_container.hpp * Contains associative containers. */ #ifndef PB_DS_ASSOC_CNTNR_HPP #define PB_DS_ASSOC_CNTNR_HPP #include <bits/c++config.h> #include <ext/typelist.h> #include <ext/pb_ds/tag_and_trait.hpp> #include <ext/pb_ds/detail/standard_policies.hpp> #include <ext/pb_ds/detail/container_base_dispatch.hpp> #include <ext/pb_ds/detail/branch_policy/traits.hpp> namespace __gnu_pbds { /** * @defgroup containers-pbds Containers * @ingroup pbds * @{ */ /** * @defgroup hash-based Hash-Based * @ingroup containers-pbds * @{ */ #define PB_DS_HASH_BASE \ detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, \ typename __gnu_cxx::typelist::append< \ typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, \ detail::integral_constant<int, Store_Hash> >::type, Policy_Tl>::type>::type /** * @defgroup hash-detail Base and Policy Classes * @ingroup hash-based */ /** * A hashed container abstraction. * * @tparam Key Key type. * @tparam Mapped Map type. * @tparam Hash_Fn Hashing functor. * @tparam Eq_Fn Equal functor. * @tparam Resize_Policy Resizes hash. * @tparam Store_Hash Indicates whether the hash value * will be stored along with each key. * @tparam Tag Instantiating data structure type, * see container_tag. * @tparam Policy_TL Policy typelist. * @tparam _Alloc Allocator type. * * Base is dispatched at compile time via Tag, from the following * choices: cc_hash_tag, gp_hash_tag, and descendants of basic_hash_tag. * * Base choices are: detail::cc_ht_map, detail::gp_ht_map */ template<typename Key, typename Mapped, typename Hash_Fn, typename Eq_Fn, typename Resize_Policy, bool Store_Hash, typename Tag, typename Policy_Tl, typename _Alloc> class basic_hash_table : public PB_DS_HASH_BASE { private: typedef typename PB_DS_HASH_BASE base_type; public: virtual ~basic_hash_table() { } protected: basic_hash_table() { } basic_hash_table(const basic_hash_table& other) : base_type((const base_type&)other) { } template<typename T0> basic_hash_table(T0 t0) : base_type(t0) { } template<typename T0, typename T1> basic_hash_table(T0 t0, T1 t1) : base_type(t0, t1) { } template<typename T0, typename T1, typename T2> basic_hash_table(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { } template<typename T0, typename T1, typename T2, typename T3> basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3) : base_type(t0, t1, t2, t3) { } template<typename T0, typename T1, typename T2, typename T3, typename T4> basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4) : base_type(t0, t1, t2, t3, t4) { } template<typename T0, typename T1, typename T2, typename T3, typename T4, typename T5> basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5) : base_type(t0, t1, t2, t3, t4, t5) { } template<typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6> basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6) : base_type(t0, t1, t2, t3, t4, t5, t6) { } template<typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7> basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6, T7 t7) : base_type(t0, t1, t2, t3, t4, t5, t6, t7) { } template<typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6, typename T7, typename T8> basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6, T7 t7, T8 t8) : base_type(t0, t1, t2, t3, t4, t5, t6, t7, t8) { } private: basic_hash_table& operator=(const base_type&); }; #undef PB_DS_HASH_BASE #define PB_DS_CC_HASH_BASE \ basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \ cc_hash_tag, \ typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, _Alloc> /** * A collision-chaining hash-based associative container. * * @tparam Key Key type. * @tparam Mapped Map type. * @tparam Hash_Fn Hashing functor. * @tparam Eq_Fn Equal functor. * @tparam Comb_Hash_Fn Combining hash functor. * If Hash_Fn is not null_type, then this * is the ranged-hash functor; otherwise, * this is the range-hashing functor. * XXX(See Design::Hash-Based Containers::Hash Policies.) * @tparam Resize_Policy Resizes hash. * @tparam Store_Hash Indicates whether the hash value * will be stored along with each key. * If Hash_Fn is null_type, then the * container will not compile if this * value is true * @tparam _Alloc Allocator type. * * Base tag choices are: cc_hash_tag. * * Base is basic_hash_table. */ template<typename Key, typename Mapped, typename Hash_Fn = typename detail::default_hash_fn<Key>::type, typename Eq_Fn = typename detail::default_eq_fn<Key>::type, typename Comb_Hash_Fn = detail::default_comb_hash_fn::type, typename Resize_Policy = typename detail::default_resize_policy<Comb_Hash_Fn>::type, bool Store_Hash = detail::default_store_hash, typename _Alloc = std::allocator<char> > class cc_hash_table : public PB_DS_CC_HASH_BASE { private: typedef PB_DS_CC_HASH_BASE base_type; public: typedef cc_hash_tag container_category; typedef Hash_Fn hash_fn; typedef Eq_Fn eq_fn; typedef Resize_Policy resize_policy; typedef Comb_Hash_Fn comb_hash_fn; /// Default constructor. cc_hash_table() { } /// Constructor taking some policy objects. r_hash_fn will be /// copied by the Hash_Fn object of the container object. cc_hash_table(const hash_fn& h) : base_type(h) { } /// Constructor taking some policy objects. r_hash_fn will be /// copied by the hash_fn object of the container object, and /// r_eq_fn will be copied by the eq_fn object of the container /// object. cc_hash_table(const hash_fn& h, const eq_fn& e) : base_type(h, e) { } /// Constructor taking some policy objects. r_hash_fn will be /// copied by the hash_fn object of the container object, r_eq_fn /// will be copied by the eq_fn object of the container object, /// and r_comb_hash_fn will be copied by the comb_hash_fn object /// of the container object. cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch) : base_type(h, e, ch) { } /// Constructor taking some policy objects. r_hash_fn will be /// copied by the hash_fn object of the container object, r_eq_fn /// will be copied by the eq_fn object of the container object, /// r_comb_hash_fn will be copied by the comb_hash_fn object of /// the container object, and r_resize_policy will be copied by /// the resize_policy object of the container object. cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch, const resize_policy& rp) : base_type(h, e, ch, rp) { } /// Constructor taking __iterators to a range of value_types. The /// value_types between first_it and last_it will be inserted into /// the container object. template<typename It> cc_hash_table(It first, It last) { base_type::copy_from_range(first, last); } /// Constructor taking __iterators to a range of value_types and /// some policy objects. The value_types between first_it and /// last_it will be inserted into the container object. template<typename It> cc_hash_table(It first, It last, const hash_fn& h) : base_type(h) { this->copy_from_range(first, last); } /// Constructor taking __iterators to a range of value_types and /// some policy objects The value_types between first_it and /// last_it will be inserted into the container object. r_hash_fn /// will be copied by the hash_fn object of the container object, /// and r_eq_fn will be copied by the eq_fn object of the /// container object. template<typename It> cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e) : base_type(h, e) { this->copy_from_range(first, last); } /// Constructor taking __iterators to a range of value_types and /// some policy objects The value_types between first_it and /// last_it will be inserted into the container object. r_hash_fn /// will be copied by the hash_fn object of the container object, /// r_eq_fn will be copied by the eq_fn object of the container /// object, and r_comb_hash_fn will be copied by the comb_hash_fn /// object of the container object. template<typename It> cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch) : base_type(h, e, ch) { this->copy_from_range(first, last); } /// Constructor taking __iterators to a range of value_types and /// some policy objects The value_types between first_it and /// last_it will be inserted into the container object. r_hash_fn /// will be copied by the hash_fn object of the container object, /// r_eq_fn will be copied by the eq_fn object of the container /// object, r_comb_hash_fn will be copied by the comb_hash_fn /// object of the container object, and r_resize_policy will be /// copied by the resize_policy object of the container object. template<typename It> cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch, const resize_policy& rp) : base_type(h, e, ch, rp) { this->copy_from_range(first, last); } cc_hash_table(const cc_hash_table& other) : base_type((const base_type&)other) { } virtual ~cc_hash_table() { } cc_hash_table& operator=(const cc_hash_table& other) { if (this != &other) { cc_hash_table tmp(other); swap(tmp); } return *this; } void swap(cc_hash_table& other) { base_type::swap(other); } }; #undef PB_DS_CC_HASH_BASE #define PB_DS_GP_HASH_BASE \ basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \ gp_hash_tag, \ typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, _Alloc> /** * A general-probing hash-based associative container. * * @tparam Key Key type. * @tparam Mapped Map type. * @tparam Hash_Fn Hashing functor. * @tparam Eq_Fn Equal functor. * @tparam Comb_Probe_Fn Combining probe functor. * If Hash_Fn is not null_type, then this * is the ranged-probe functor; otherwise, * this is the range-hashing functor. * XXX See Design::Hash-Based Containers::Hash Policies. * @tparam Probe_Fn Probe functor. * @tparam Resize_Policy Resizes hash. * @tparam Store_Hash Indicates whether the hash value * will be stored along with each key. * If Hash_Fn is null_type, then the * container will not compile if this * value is true * @tparam _Alloc Allocator type. * * Base tag choices are: gp_hash_tag. * * Base is basic_hash_table. */ template<typename Key, typename Mapped, typename Hash_Fn = typename detail::default_hash_fn<Key>::type, typename Eq_Fn = typename detail::default_eq_fn<Key>::type, typename Comb_Probe_Fn = detail::default_comb_hash_fn::type, typename Probe_Fn = typename detail::default_probe_fn<Comb_Probe_Fn>::type, typename Resize_Policy = typename detail::default_resize_policy<Comb_Probe_Fn>::type, bool Store_Hash = detail::default_store_hash, typename _Alloc = std::allocator<char> > class gp_hash_table : public PB_DS_GP_HASH_BASE { private: typedef PB_DS_GP_HASH_BASE base_type; public: typedef gp_hash_tag container_category; typedef Hash_Fn hash_fn; typedef Eq_Fn eq_fn; typedef Comb_Probe_Fn comb_probe_fn; typedef Probe_Fn probe_fn; typedef Resize_Policy resize_policy; /// Default constructor. gp_hash_table() { } /// Constructor taking some policy objects. r_hash_fn will be /// copied by the hash_fn object of the container object. gp_hash_table(const hash_fn& h) : base_type(h) { } /// Constructor taking some policy objects. r_hash_fn will be /// copied by the hash_fn object of the container object, and /// r_eq_fn will be copied by the eq_fn object of the container /// object. gp_hash_table(const hash_fn& h, const eq_fn& e) : base_type(h, e) { } /// Constructor taking some policy objects. r_hash_fn will be /// copied by the hash_fn object of the container object, r_eq_fn /// will be copied by the eq_fn object of the container object, /// and r_comb_probe_fn will be copied by the comb_probe_fn object /// of the container object. gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp) : base_type(h, e, cp) { } /// Constructor taking some policy objects. r_hash_fn will be /// copied by the hash_fn object of the container object, r_eq_fn /// will be copied by the eq_fn object of the container object, /// r_comb_probe_fn will be copied by the comb_probe_fn object of /// the container object, and r_probe_fn will be copied by the /// probe_fn object of the container object. gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, const probe_fn& p) : base_type(h, e, cp, p) { } /// Constructor taking some policy objects. r_hash_fn will be /// copied by the hash_fn object of the container object, r_eq_fn /// will be copied by the eq_fn object of the container object, /// r_comb_probe_fn will be copied by the comb_probe_fn object of /// the container object, r_probe_fn will be copied by the /// probe_fn object of the container object, and r_resize_policy /// will be copied by the Resize_Policy object of the container /// object. gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, const probe_fn& p, const resize_policy& rp) : base_type(h, e, cp, p, rp) { } /// Constructor taking __iterators to a range of value_types. The /// value_types between first_it and last_it will be inserted into /// the container object. template<typename It> gp_hash_table(It first, It last) { base_type::copy_from_range(first, last); } /// Constructor taking __iterators to a range of value_types and /// some policy objects. The value_types between first_it and /// last_it will be inserted into the container object. r_hash_fn /// will be copied by the hash_fn object of the container object. template<typename It> gp_hash_table(It first, It last, const hash_fn& h) : base_type(h) { base_type::copy_from_range(first, last); } /// Constructor taking __iterators to a range of value_types and /// some policy objects. The value_types between first_it and /// last_it will be inserted into the container object. r_hash_fn /// will be copied by the hash_fn object of the container object, /// and r_eq_fn will be copied by the eq_fn object of the /// container object. template<typename It> gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e) : base_type(h, e) { base_type::copy_from_range(first, last); } /// Constructor taking __iterators to a range of value_types and /// some policy objects. The value_types between first_it and /// last_it will be inserted into the container object. r_hash_fn /// will be copied by the hash_fn object of the container object, /// r_eq_fn will be copied by the eq_fn object of the container /// object, and r_comb_probe_fn will be copied by the /// comb_probe_fn object of the container object. template<typename It> gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp) : base_type(h, e, cp) { base_type::copy_from_range(first, last); } /// Constructor taking __iterators to a range of value_types and /// some policy objects. The value_types between first_it and /// last_it will be inserted into the container object. r_hash_fn /// will be copied by the hash_fn object of the container object, /// r_eq_fn will be copied by the eq_fn object of the container /// object, r_comb_probe_fn will be copied by the comb_probe_fn /// object of the container object, and r_probe_fn will be copied /// by the probe_fn object of the container object. template<typename It> gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, const probe_fn& p) : base_type(h, e, cp, p) { base_type::copy_from_range(first, last); } /// Constructor taking __iterators to a range of value_types and /// some policy objects. The value_types between first_it and /// last_it will be inserted into the container object. r_hash_fn /// will be copied by the hash_fn object of the container object, /// r_eq_fn will be copied by the eq_fn object of the container /// object, r_comb_probe_fn will be copied by the comb_probe_fn /// object of the container object, r_probe_fn will be copied by /// the probe_fn object of the container object, and /// r_resize_policy will be copied by the resize_policy object of /// the container object. template<typename It> gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, const probe_fn& p, const resize_policy& rp) : base_type(h, e, cp, p, rp) { base_type::copy_from_range(first, last); } gp_hash_table(const gp_hash_table& other) : base_type((const base_type&)other) { } virtual ~gp_hash_table() { } gp_hash_table& operator=(const gp_hash_table& other) { if (this != &other) { gp_hash_table tmp(other); swap(tmp); } return *this; } void swap(gp_hash_table& other) { base_type::swap(other); } }; //@} hash-based #undef PB_DS_GP_HASH_BASE /** * @defgroup branch-based Branch-Based * @ingroup containers-pbds * @{ */ #define PB_DS_BRANCH_BASE \ detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, Policy_Tl>::type /** * @defgroup branch-detail Base and Policy Classes * @ingroup branch-based */ /** * A branched, tree-like (tree, trie) container abstraction. * * @tparam Key Key type. * @tparam Mapped Map type. * @tparam Tag Instantiating data structure type, * see container_tag. * @tparam Node_Update Updates nodes, restores invariants. * @tparam Policy_TL Policy typelist. * @tparam _Alloc Allocator type. * * Base is dispatched at compile time via Tag, from the following * choices: tree_tag, trie_tag, and their descendants. * * Base choices are: detail::ov_tree_map, detail::rb_tree_map, * detail::splay_tree_map, and detail::pat_trie_map. */ template<typename Key, typename Mapped, typename Tag, typename Node_Update, typename Policy_Tl, typename _Alloc> class basic_branch : public PB_DS_BRANCH_BASE { private: typedef typename PB_DS_BRANCH_BASE base_type; public: typedef Node_Update node_update; virtual ~basic_branch() { } protected: basic_branch() { } basic_branch(const basic_branch& other) : base_type((const base_type&)other) { } template<typename T0> basic_branch(T0 t0) : base_type(t0) { } template<typename T0, typename T1> basic_branch(T0 t0, T1 t1) : base_type(t0, t1) { } template<typename T0, typename T1, typename T2> basic_branch(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { } template<typename T0, typename T1, typename T2, typename T3> basic_branch(T0 t0, T1 t1, T2 t2, T3 t3) : base_type(t0, t1, t2, t3) { } template<typename T0, typename T1, typename T2, typename T3, typename T4> basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4) : base_type(t0, t1, t2, t3, t4) { } template<typename T0, typename T1, typename T2, typename T3, typename T4, typename T5> basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5) : base_type(t0, t1, t2, t3, t4, t5) { } template<typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6> basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6) : base_type(t0, t1, t2, t3, t4, t5, t6) { } }; #undef PB_DS_BRANCH_BASE #define PB_DS_TREE_NODE_AND_IT_TRAITS \ detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag,_Alloc> #define PB_DS_TREE_BASE \ basic_branch<Key,Mapped, Tag, \ typename PB_DS_TREE_NODE_AND_IT_TRAITS::node_update, \ typename __gnu_cxx::typelist::create2<Cmp_Fn, \ PB_DS_TREE_NODE_AND_IT_TRAITS>::type, _Alloc> /** * A tree-based container. * * @tparam Key Key type. * @tparam Mapped Map type. * @tparam Cmp_Fn Comparison functor. * @tparam Tag Instantiating data structure type, * see container_tag. * @tparam Node_Update Updates tree internal-nodes, * restores invariants when invalidated. * XXX See design::tree-based-containers::node invariants. * @tparam _Alloc Allocator type. * * Base tag choices are: ov_tree_tag, rb_tree_tag, splay_tree_tag. * * Base is basic_branch. */ template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>, typename Tag = rb_tree_tag, template<typename Node_CItr, typename Node_Itr, typename Cmp_Fn_, typename _Alloc_> class Node_Update = null_node_update, typename _Alloc = std::allocator<char> > class tree : public PB_DS_TREE_BASE { private: typedef PB_DS_TREE_BASE base_type; public: /// Comparison functor type. typedef Cmp_Fn cmp_fn; tree() { } /// Constructor taking some policy objects. r_cmp_fn will be /// copied by the Cmp_Fn object of the container object. tree(const cmp_fn& c) : base_type(c) { } /// Constructor taking __iterators to a range of value_types. The /// value_types between first_it and last_it will be inserted into /// the container object. template<typename It> tree(It first, It last) { base_type::copy_from_range(first, last); } /// Constructor taking __iterators to a range of value_types and /// some policy objects The value_types between first_it and /// last_it will be inserted into the container object. r_cmp_fn /// will be copied by the cmp_fn object of the container object. template<typename It> tree(It first, It last, const cmp_fn& c) : base_type(c) { base_type::copy_from_range(first, last); } tree(const tree& other) : base_type((const base_type&)other) { } virtual ~tree() { } tree& operator=(const tree& other) { if (this != &other) { tree tmp(other); swap(tmp); } return *this; } void swap(tree& other) { base_type::swap(other); } }; #undef PB_DS_TREE_BASE #undef PB_DS_TREE_NODE_AND_IT_TRAITS #define PB_DS_TRIE_NODE_AND_IT_TRAITS \ detail::trie_traits<Key,Mapped,_ATraits,Node_Update,Tag,_Alloc> #define PB_DS_TRIE_BASE \ basic_branch<Key,Mapped,Tag, \ typename PB_DS_TRIE_NODE_AND_IT_TRAITS::node_update, \ typename __gnu_cxx::typelist::create2<_ATraits, \ PB_DS_TRIE_NODE_AND_IT_TRAITS >::type, _Alloc> /** * A trie-based container. * * @tparam Key Key type. * @tparam Mapped Map type. * @tparam _ATraits Element access traits. * @tparam Tag Instantiating data structure type, * see container_tag. * @tparam Node_Update Updates trie internal-nodes, * restores invariants when invalidated. * XXX See design::tree-based-containers::node invariants. * @tparam _Alloc Allocator type. * * Base tag choice is pat_trie_tag. * * Base is basic_branch. */ template<typename Key, typename Mapped, typename _ATraits = \ typename detail::default_trie_access_traits<Key>::type, typename Tag = pat_trie_tag, template<typename Node_CItr, typename Node_Itr, typename _ATraits_, typename _Alloc_> class Node_Update = null_node_update, typename _Alloc = std::allocator<char> > class trie : public PB_DS_TRIE_BASE { private: typedef PB_DS_TRIE_BASE base_type; public: /// Element access traits type. typedef _ATraits access_traits; trie() { } /// Constructor taking some policy objects. r_access_traits will /// be copied by the _ATraits object of the container object. trie(const access_traits& t) : base_type(t) { } /// Constructor taking __iterators to a range of value_types. The /// value_types between first_it and last_it will be inserted into /// the container object. template<typename It> trie(It first, It last) { base_type::copy_from_range(first, last); } /// Constructor taking __iterators to a range of value_types and /// some policy objects. The value_types between first_it and /// last_it will be inserted into the container object. template<typename It> trie(It first, It last, const access_traits& t) : base_type(t) { base_type::copy_from_range(first, last); } trie(const trie& other) : base_type((const base_type&)other) { } virtual ~trie() { } trie& operator=(const trie& other) { if (this != &other) { trie tmp(other); swap(tmp); } return *this; } void swap(trie& other) { base_type::swap(other); } }; //@} branch-based #undef PB_DS_TRIE_BASE #undef PB_DS_TRIE_NODE_AND_IT_TRAITS /** * @defgroup list-based List-Based * @ingroup containers-pbds * @{ */ #define PB_DS_LU_BASE \ detail::container_base_dispatch<Key, Mapped, _Alloc, list_update_tag, \ typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type>::type /** * A list-update based associative container. * * @tparam Key Key type. * @tparam Mapped Map type. * @tparam Eq_Fn Equal functor. * @tparam Update_Policy Update policy, determines when an element * will be moved to the front of the list. * @tparam _Alloc Allocator type. * * Base is detail::lu_map. */ template<typename Key, typename Mapped, class Eq_Fn = typename detail::default_eq_fn<Key>::type, class Update_Policy = detail::default_update_policy::type, class _Alloc = std::allocator<char> > class list_update : public PB_DS_LU_BASE { private: typedef typename PB_DS_LU_BASE base_type; public: typedef list_update_tag container_category; typedef Eq_Fn eq_fn; typedef Update_Policy update_policy; list_update() { } /// Constructor taking __iterators to a range of value_types. The /// value_types between first_it and last_it will be inserted into /// the container object. template<typename It> list_update(It first, It last) { base_type::copy_from_range(first, last); } list_update(const list_update& other) : base_type((const base_type&)other) { } virtual ~list_update() { } list_update& operator=(const list_update& other) { if (this !=& other) { list_update tmp(other); swap(tmp); } return *this; } void swap(list_update& other) { base_type::swap(other); } }; //@} list-based #undef PB_DS_LU_BASE // @} group containers-pbds } // namespace __gnu_pbds #endif