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