libstdc++
|
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