libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2009, 2010, 2011 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/branch_policy/traits.hpp> 00050 00051 namespace __gnu_pbds 00052 { 00053 /** 00054 * @defgroup containers-pbds Containers 00055 * @ingroup pbds 00056 * @{ 00057 */ 00058 00059 /** 00060 * @defgroup hash-based 00061 * @ingroup containers-pbds 00062 * @{ 00063 */ 00064 #define PB_DS_HASH_BASE \ 00065 detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, \ 00066 typename __gnu_cxx::typelist::append< \ 00067 typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, \ 00068 detail::integral_constant<int, Store_Hash> >::type, Policy_Tl>::type>::type 00069 00070 /** 00071 * @defgroup hash-detail Base and Policy Classes 00072 * @ingroup hash-based 00073 */ 00074 00075 /** 00076 * A hashed container abstraction. 00077 * 00078 * @tparam Key Key type. 00079 * @tparam Mapped Map type. 00080 * @tparam Hash_Fn Hashing functor. 00081 * @tparam Eq_Fn Equal functor. 00082 * @tparam Resize_Policy Resizes hash. 00083 * @tparam Store_Hash Indicates whether the hash value 00084 * will be stored along with each key. 00085 * @tparam Tag Instantiating data structure type, 00086 * see container_tag. 00087 * @tparam Policy_TL Policy typelist. 00088 * @tparam _Alloc Allocator type. 00089 * 00090 * Base is dispatched at compile time via Tag, from the following 00091 * choices: cc_hash_tag, gp_hash_tag, and descendants of basic_hash_tag. 00092 * 00093 * Base choices are: detail::cc_ht_map, detail::gp_ht_map 00094 */ 00095 template<typename Key, 00096 typename Mapped, 00097 typename Hash_Fn, 00098 typename Eq_Fn, 00099 typename Resize_Policy, 00100 bool Store_Hash, 00101 typename Tag, 00102 typename Policy_Tl, 00103 typename _Alloc> 00104 class basic_hash_table : public PB_DS_HASH_BASE 00105 { 00106 private: 00107 typedef typename PB_DS_HASH_BASE base_type; 00108 00109 public: 00110 virtual 00111 ~basic_hash_table() { } 00112 00113 protected: 00114 basic_hash_table() { } 00115 00116 basic_hash_table(const basic_hash_table& other) 00117 : base_type((const base_type&)other) { } 00118 00119 template<typename T0> 00120 basic_hash_table(T0 t0) : base_type(t0) { } 00121 00122 template<typename T0, typename T1> 00123 basic_hash_table(T0 t0, T1 t1) : base_type(t0, t1) { } 00124 00125 template<typename T0, typename T1, typename T2> 00126 basic_hash_table(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { } 00127 00128 template<typename T0, typename T1, typename T2, typename T3> 00129 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3) 00130 : base_type(t0, t1, t2, t3) { } 00131 00132 template<typename T0, typename T1, typename T2, typename T3, typename T4> 00133 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4) 00134 : base_type(t0, t1, t2, t3, t4) { } 00135 00136 template<typename T0, typename T1, typename T2, typename T3, typename T4, 00137 typename T5> 00138 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5) 00139 : base_type(t0, t1, t2, t3, t4, t5) { } 00140 00141 template<typename T0, typename T1, typename T2, typename T3, typename T4, 00142 typename T5, typename T6> 00143 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6) 00144 : base_type(t0, t1, t2, t3, t4, t5, t6) { } 00145 00146 template<typename T0, typename T1, typename T2, typename T3, typename T4, 00147 typename T5, typename T6, typename T7> 00148 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6, T7 t7) 00149 : base_type(t0, t1, t2, t3, t4, t5, t6, t7) { } 00150 00151 template<typename T0, typename T1, typename T2, typename T3, typename T4, 00152 typename T5, typename T6, typename T7, typename T8> 00153 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6, 00154 T7 t7, T8 t8) 00155 : base_type(t0, t1, t2, t3, t4, t5, t6, t7, t8) 00156 { } 00157 00158 private: 00159 basic_hash_table& 00160 operator=(const base_type&); 00161 }; 00162 00163 #undef PB_DS_HASH_BASE 00164 00165 00166 #define PB_DS_CC_HASH_BASE \ 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, _Alloc> 00170 00171 00172 /** 00173 * A collision-chaining hash-based associative container. 00174 * 00175 * @tparam Key Key type. 00176 * @tparam Mapped Map type. 00177 * @tparam Hash_Fn Hashing functor. 00178 * @tparam Eq_Fn Equal functor. 00179 * @tparam Comb_Hash_Fn Combining hash functor. 00180 * If Hash_Fn is not null_type, then this 00181 * is the ranged-hash functor; otherwise, 00182 * this is the range-hashing functor. 00183 * XXX(See Design::Hash-Based Containers::Hash Policies.) 00184 * @tparam Resize_Policy Resizes hash. 00185 * @tparam Store_Hash Indicates whether the hash value 00186 * will be stored along with each key. 00187 * If Hash_Fn is null_type, then the 00188 * container will not compile if this 00189 * value is true 00190 * @tparam _Alloc Allocator type. 00191 * 00192 * Base tag choices are: cc_hash_tag. 00193 * 00194 * Base is basic_hash_table. 00195 */ 00196 template<typename Key, 00197 typename Mapped, 00198 typename Hash_Fn = typename detail::default_hash_fn<Key>::type, 00199 typename Eq_Fn = typename detail::default_eq_fn<Key>::type, 00200 typename Comb_Hash_Fn = detail::default_comb_hash_fn::type, 00201 typename Resize_Policy = typename detail::default_resize_policy<Comb_Hash_Fn>::type, 00202 bool Store_Hash = detail::default_store_hash, 00203 typename _Alloc = std::allocator<char> > 00204 class cc_hash_table : public PB_DS_CC_HASH_BASE 00205 { 00206 private: 00207 typedef PB_DS_CC_HASH_BASE base_type; 00208 00209 public: 00210 typedef cc_hash_tag container_category; 00211 typedef Hash_Fn hash_fn; 00212 typedef Eq_Fn eq_fn; 00213 typedef Resize_Policy resize_policy; 00214 typedef Comb_Hash_Fn comb_hash_fn; 00215 00216 /// Default constructor. 00217 cc_hash_table() { } 00218 00219 /// Constructor taking some policy objects. r_hash_fn will be 00220 /// copied by the Hash_Fn object of the container object. 00221 cc_hash_table(const hash_fn& h) 00222 : base_type(h) { } 00223 00224 /// Constructor taking some policy objects. r_hash_fn will be 00225 /// copied by the hash_fn object of the container object, and 00226 /// r_eq_fn will be copied by the eq_fn object of the container 00227 /// object. 00228 cc_hash_table(const hash_fn& h, const eq_fn& e) 00229 : base_type(h, e) { } 00230 00231 /// Constructor taking some policy objects. r_hash_fn will be 00232 /// copied by the hash_fn object of the container object, r_eq_fn 00233 /// will be copied by the eq_fn object of the container object, 00234 /// and r_comb_hash_fn will be copied by the comb_hash_fn object 00235 /// of the container object. 00236 cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch) 00237 : base_type(h, e, ch) { } 00238 00239 /// Constructor taking some policy objects. r_hash_fn will be 00240 /// copied by the hash_fn object of the container object, r_eq_fn 00241 /// will be copied by the eq_fn object of the container object, 00242 /// r_comb_hash_fn will be copied by the comb_hash_fn object of 00243 /// the container object, and r_resize_policy will be copied by 00244 /// the resize_policy object of the container object. 00245 cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch, 00246 const resize_policy& rp) 00247 : base_type(h, e, ch, rp) { } 00248 00249 /// Constructor taking __iterators to a range of value_types. The 00250 /// value_types between first_it and last_it will be inserted into 00251 /// the container object. 00252 template<typename It> 00253 cc_hash_table(It first, It last) 00254 { base_type::copy_from_range(first, last); } 00255 00256 /// Constructor taking __iterators to a range of value_types and 00257 /// some policy objects. The value_types between first_it and 00258 /// last_it will be inserted into the container object. 00259 template<typename It> 00260 cc_hash_table(It first, It last, const hash_fn& h) 00261 : base_type(h) 00262 { this->copy_from_range(first, last); } 00263 00264 /// Constructor taking __iterators to a range of value_types and 00265 /// some policy objects The value_types between first_it and 00266 /// last_it will be inserted into the container object. r_hash_fn 00267 /// will be copied by the hash_fn object of the container object, 00268 /// and r_eq_fn will be copied by the eq_fn object of the 00269 /// container object. 00270 template<typename It> 00271 cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e) 00272 : base_type(h, e) 00273 { this->copy_from_range(first, last); } 00274 00275 /// Constructor taking __iterators to a range of value_types and 00276 /// some policy objects The value_types between first_it and 00277 /// last_it will be inserted into the container object. r_hash_fn 00278 /// will be copied by the hash_fn object of the container object, 00279 /// r_eq_fn will be copied by the eq_fn object of the container 00280 /// object, and r_comb_hash_fn will be copied by the comb_hash_fn 00281 /// object of the container object. 00282 template<typename It> 00283 cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 00284 const comb_hash_fn& ch) 00285 : base_type(h, e, ch) 00286 { this->copy_from_range(first, last); } 00287 00288 /// Constructor taking __iterators to a range of value_types and 00289 /// some policy objects The value_types between first_it and 00290 /// last_it will be inserted into the container object. r_hash_fn 00291 /// will be copied by the hash_fn object of the container object, 00292 /// r_eq_fn will be copied by the eq_fn object of the container 00293 /// object, r_comb_hash_fn will be copied by the comb_hash_fn 00294 /// object of the container object, and r_resize_policy will be 00295 /// copied by the resize_policy object of the container object. 00296 template<typename It> 00297 cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 00298 const comb_hash_fn& ch, const resize_policy& rp) 00299 : base_type(h, e, ch, rp) 00300 { this->copy_from_range(first, last); } 00301 00302 cc_hash_table(const cc_hash_table& other) 00303 : base_type((const base_type&)other) 00304 { } 00305 00306 virtual 00307 ~cc_hash_table() { } 00308 00309 cc_hash_table& 00310 operator=(const cc_hash_table& other) 00311 { 00312 if (this != &other) 00313 { 00314 cc_hash_table tmp(other); 00315 swap(tmp); 00316 } 00317 return *this; 00318 } 00319 00320 void 00321 swap(cc_hash_table& other) 00322 { base_type::swap(other); } 00323 }; 00324 00325 #undef PB_DS_CC_HASH_BASE 00326 00327 00328 #define PB_DS_GP_HASH_BASE \ 00329 basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \ 00330 gp_hash_tag, \ 00331 typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, _Alloc> 00332 00333 00334 /** 00335 * A general-probing hash-based associative container. 00336 * 00337 * @tparam Key Key type. 00338 * @tparam Mapped Map type. 00339 * @tparam Hash_Fn Hashing functor. 00340 * @tparam Eq_Fn Equal functor. 00341 * @tparam Comb_Probe_Fn Combining probe functor. 00342 * If Hash_Fn is not null_type, then this 00343 * is the ranged-probe functor; otherwise, 00344 * this is the range-hashing functor. 00345 * XXX See Design::Hash-Based Containers::Hash Policies. 00346 * @tparam Probe_Fn Probe functor. 00347 * @tparam Resize_Policy Resizes hash. 00348 * @tparam Store_Hash Indicates whether the hash value 00349 * will be stored along with each key. 00350 * If Hash_Fn is null_type, then the 00351 * container will not compile if this 00352 * value is true 00353 * @tparam _Alloc Allocator type. 00354 * 00355 * Base tag choices are: gp_hash_tag. 00356 * 00357 * Base is basic_hash_table. 00358 */ 00359 template<typename Key, 00360 typename Mapped, 00361 typename Hash_Fn = typename detail::default_hash_fn<Key>::type, 00362 typename Eq_Fn = typename detail::default_eq_fn<Key>::type, 00363 typename Comb_Probe_Fn = detail::default_comb_hash_fn::type, 00364 typename Probe_Fn = typename detail::default_probe_fn<Comb_Probe_Fn>::type, 00365 typename Resize_Policy = typename detail::default_resize_policy<Comb_Probe_Fn>::type, 00366 bool Store_Hash = detail::default_store_hash, 00367 typename _Alloc = std::allocator<char> > 00368 class gp_hash_table : public PB_DS_GP_HASH_BASE 00369 { 00370 private: 00371 typedef PB_DS_GP_HASH_BASE base_type; 00372 00373 public: 00374 typedef gp_hash_tag container_category; 00375 typedef Hash_Fn hash_fn; 00376 typedef Eq_Fn eq_fn; 00377 typedef Comb_Probe_Fn comb_probe_fn; 00378 typedef Probe_Fn probe_fn; 00379 typedef Resize_Policy resize_policy; 00380 00381 /// Default constructor. 00382 gp_hash_table() { } 00383 00384 /// Constructor taking some policy objects. r_hash_fn will be 00385 /// copied by the hash_fn object of the container object. 00386 gp_hash_table(const hash_fn& h) 00387 : base_type(h) { } 00388 00389 /// Constructor taking some policy objects. r_hash_fn will be 00390 /// copied by the hash_fn object of the container object, and 00391 /// r_eq_fn will be copied by the eq_fn object of the container 00392 /// object. 00393 gp_hash_table(const hash_fn& h, const eq_fn& e) 00394 : base_type(h, e) { } 00395 00396 /// Constructor taking some policy objects. r_hash_fn will be 00397 /// copied by the hash_fn object of the container object, r_eq_fn 00398 /// will be copied by the eq_fn object of the container object, 00399 /// and r_comb_probe_fn will be copied by the comb_probe_fn object 00400 /// of the container object. 00401 gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp) 00402 : base_type(h, e, cp) { } 00403 00404 /// Constructor taking some policy objects. r_hash_fn will be 00405 /// copied by the hash_fn object of the container object, r_eq_fn 00406 /// will be copied by the eq_fn object of the container object, 00407 /// r_comb_probe_fn will be copied by the comb_probe_fn object of 00408 /// the container object, and r_probe_fn will be copied by the 00409 /// probe_fn object of the container object. 00410 gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, 00411 const probe_fn& p) 00412 : base_type(h, e, cp, p) { } 00413 00414 /// Constructor taking some policy objects. r_hash_fn will be 00415 /// copied by the hash_fn object of the container object, r_eq_fn 00416 /// will be copied by the eq_fn object of the container object, 00417 /// r_comb_probe_fn will be copied by the comb_probe_fn object of 00418 /// the container object, r_probe_fn will be copied by the 00419 /// probe_fn object of the container object, and r_resize_policy 00420 /// will be copied by the Resize_Policy object of the container 00421 /// object. 00422 gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, 00423 const probe_fn& p, const resize_policy& rp) 00424 : base_type(h, e, cp, p, rp) { } 00425 00426 /// Constructor taking __iterators to a range of value_types. The 00427 /// value_types between first_it and last_it will be inserted into 00428 /// the container object. 00429 template<typename It> 00430 gp_hash_table(It first, It last) 00431 { base_type::copy_from_range(first, last); } 00432 00433 /// Constructor taking __iterators to a range of value_types and 00434 /// some policy objects. The value_types between first_it and 00435 /// last_it will be inserted into the container object. r_hash_fn 00436 /// will be copied by the hash_fn object of the container object. 00437 template<typename It> 00438 gp_hash_table(It first, It last, const hash_fn& h) 00439 : base_type(h) 00440 { base_type::copy_from_range(first, last); } 00441 00442 /// Constructor taking __iterators to a range of value_types and 00443 /// some policy objects. The value_types between first_it and 00444 /// last_it will be inserted into the container object. r_hash_fn 00445 /// will be copied by the hash_fn object of the container object, 00446 /// and r_eq_fn will be copied by the eq_fn object of the 00447 /// container object. 00448 template<typename It> 00449 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e) 00450 : base_type(h, e) 00451 { base_type::copy_from_range(first, last); } 00452 00453 /// Constructor taking __iterators to a range of value_types and 00454 /// some policy objects. The value_types between first_it and 00455 /// last_it will be inserted into the container object. r_hash_fn 00456 /// will be copied by the hash_fn object of the container object, 00457 /// r_eq_fn will be copied by the eq_fn object of the container 00458 /// object, and r_comb_probe_fn will be copied by the 00459 /// comb_probe_fn object of the container object. 00460 template<typename It> 00461 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 00462 const comb_probe_fn& cp) 00463 : base_type(h, e, cp) 00464 { base_type::copy_from_range(first, last); } 00465 00466 /// Constructor taking __iterators to a range of value_types and 00467 /// some policy objects. The value_types between first_it and 00468 /// last_it will be inserted into the container object. r_hash_fn 00469 /// will be copied by the hash_fn object of the container object, 00470 /// r_eq_fn will be copied by the eq_fn object of the container 00471 /// object, r_comb_probe_fn will be copied by the comb_probe_fn 00472 /// object of the container object, and r_probe_fn will be copied 00473 /// by the probe_fn object of the container object. 00474 template<typename It> 00475 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 00476 const comb_probe_fn& cp, const probe_fn& p) 00477 : base_type(h, e, cp, p) 00478 { base_type::copy_from_range(first, last); } 00479 00480 /// Constructor taking __iterators to a range of value_types and 00481 /// some policy objects. The value_types between first_it and 00482 /// last_it will be inserted into the container object. r_hash_fn 00483 /// will be copied by the hash_fn object of the container object, 00484 /// r_eq_fn will be copied by the eq_fn object of the container 00485 /// object, r_comb_probe_fn will be copied by the comb_probe_fn 00486 /// object of the container object, r_probe_fn will be copied by 00487 /// the probe_fn object of the container object, and 00488 /// r_resize_policy will be copied by the resize_policy object of 00489 /// the container object. 00490 template<typename It> 00491 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 00492 const comb_probe_fn& cp, const probe_fn& p, 00493 const resize_policy& rp) 00494 : base_type(h, e, cp, p, rp) 00495 { base_type::copy_from_range(first, last); } 00496 00497 gp_hash_table(const gp_hash_table& other) 00498 : base_type((const base_type&)other) 00499 { } 00500 00501 virtual 00502 ~gp_hash_table() { } 00503 00504 gp_hash_table& 00505 operator=(const gp_hash_table& other) 00506 { 00507 if (this != &other) 00508 { 00509 gp_hash_table tmp(other); 00510 swap(tmp); 00511 } 00512 return *this; 00513 } 00514 00515 void 00516 swap(gp_hash_table& other) 00517 { base_type::swap(other); } 00518 }; 00519 //@} hash-based 00520 #undef PB_DS_GP_HASH_BASE 00521 00522 00523 /** 00524 * @defgroup branch-based 00525 * @ingroup containers-pbds 00526 * @{ 00527 */ 00528 #define PB_DS_BRANCH_BASE \ 00529 detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, Policy_Tl>::type 00530 00531 /** 00532 * @defgroup branch-detail Base and Policy Classes 00533 * @ingroup branch-based 00534 */ 00535 00536 /** 00537 * A branched, tree-like (tree, trie) container abstraction. 00538 * 00539 * @tparam Key Key type. 00540 * @tparam Mapped Map type. 00541 * @tparam Tag Instantiating data structure type, 00542 * see container_tag. 00543 * @tparam Node_Update Updates nodes, restores invariants. 00544 * @tparam Policy_TL Policy typelist. 00545 * @tparam _Alloc Allocator type. 00546 * 00547 * Base is dispatched at compile time via Tag, from the following 00548 * choices: tree_tag, trie_tag, and their descendants. 00549 * 00550 * Base choices are: detail::ov_tree_map, detail::rb_tree_map, 00551 * detail::splay_tree_map, and detail::pat_trie_map. 00552 */ 00553 template<typename Key, typename Mapped, typename Tag, 00554 typename Node_Update, typename Policy_Tl, typename _Alloc> 00555 class basic_branch : public PB_DS_BRANCH_BASE 00556 { 00557 private: 00558 typedef typename PB_DS_BRANCH_BASE base_type; 00559 00560 public: 00561 typedef Node_Update node_update; 00562 00563 virtual 00564 ~basic_branch() { } 00565 00566 protected: 00567 basic_branch() { } 00568 00569 basic_branch(const basic_branch& other) 00570 : base_type((const base_type&)other) { } 00571 00572 template<typename T0> 00573 basic_branch(T0 t0) : base_type(t0) { } 00574 00575 template<typename T0, typename T1> 00576 basic_branch(T0 t0, T1 t1) : base_type(t0, t1) { } 00577 00578 template<typename T0, typename T1, typename T2> 00579 basic_branch(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { } 00580 00581 template<typename T0, typename T1, typename T2, typename T3> 00582 basic_branch(T0 t0, T1 t1, T2 t2, T3 t3) 00583 : base_type(t0, t1, t2, t3) { } 00584 00585 template<typename T0, typename T1, typename T2, typename T3, typename T4> 00586 basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4) 00587 : base_type(t0, t1, t2, t3, t4) { } 00588 00589 template<typename T0, typename T1, typename T2, typename T3, typename T4, 00590 typename T5> 00591 basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5) 00592 : base_type(t0, t1, t2, t3, t4, t5) { } 00593 00594 template<typename T0, typename T1, typename T2, typename T3, typename T4, 00595 typename T5, typename T6> 00596 basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6) 00597 : base_type(t0, t1, t2, t3, t4, t5, t6) { } 00598 }; 00599 #undef PB_DS_BRANCH_BASE 00600 00601 00602 #define PB_DS_TREE_NODE_AND_IT_TRAITS \ 00603 detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag,_Alloc> 00604 00605 #define PB_DS_TREE_BASE \ 00606 basic_branch<Key,Mapped, Tag, \ 00607 typename PB_DS_TREE_NODE_AND_IT_TRAITS::node_update, \ 00608 typename __gnu_cxx::typelist::create2<Cmp_Fn, \ 00609 PB_DS_TREE_NODE_AND_IT_TRAITS>::type, _Alloc> 00610 00611 00612 /** 00613 * A tree-based container. 00614 * 00615 * @tparam Key Key type. 00616 * @tparam Mapped Map type. 00617 * @tparam Cmp_Fn Comparison functor. 00618 * @tparam Tag Instantiating data structure type, 00619 * see container_tag. 00620 * @tparam Node_Update Updates nodes, 00621 * restores invariants when invalidated. 00622 * XXX See design::tree-based-containers::node invariants. 00623 * @tparam _Alloc Allocator type. 00624 * 00625 * Base tag choices are: ov_tree_tag, rb_tree_tag, splay_tree_tag. 00626 * 00627 * Base is basic_branch. 00628 */ 00629 template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>, 00630 typename Tag = rb_tree_tag, 00631 template<typename Node_CItr, typename Node_Itr, 00632 typename Cmp_Fn_, typename _Alloc_> 00633 class Node_Update = null_node_update, 00634 typename _Alloc = std::allocator<char> > 00635 class tree : public PB_DS_TREE_BASE 00636 { 00637 private: 00638 typedef PB_DS_TREE_BASE base_type; 00639 00640 public: 00641 /// Comparison functor type. 00642 typedef Cmp_Fn cmp_fn; 00643 00644 tree() { } 00645 00646 /// Constructor taking some policy objects. r_cmp_fn will be 00647 /// copied by the Cmp_Fn object of the container object. 00648 tree(const cmp_fn& c) 00649 : base_type(c) { } 00650 00651 /// Constructor taking __iterators to a range of value_types. The 00652 /// value_types between first_it and last_it will be inserted into 00653 /// the container object. 00654 template<typename It> 00655 tree(It first, It last) 00656 { base_type::copy_from_range(first, last); } 00657 00658 /// Constructor taking __iterators to a range of value_types and 00659 /// some policy objects The value_types between first_it and 00660 /// last_it will be inserted into the container object. r_cmp_fn 00661 /// will be copied by the cmp_fn object of the container object. 00662 template<typename It> 00663 tree(It first, It last, const cmp_fn& c) 00664 : base_type(c) 00665 { base_type::copy_from_range(first, last); } 00666 00667 tree(const tree& other) 00668 : base_type((const base_type&)other) { } 00669 00670 virtual 00671 ~tree() { } 00672 00673 tree& 00674 operator=(const tree& other) 00675 { 00676 if (this != &other) 00677 { 00678 tree tmp(other); 00679 swap(tmp); 00680 } 00681 return *this; 00682 } 00683 00684 void 00685 swap(tree& other) 00686 { base_type::swap(other); } 00687 }; 00688 00689 #undef PB_DS_TREE_BASE 00690 #undef PB_DS_TREE_NODE_AND_IT_TRAITS 00691 00692 00693 #define PB_DS_TRIE_NODE_AND_IT_TRAITS \ 00694 detail::trie_traits<Key,Mapped,_ATraits,Node_Update,Tag,_Alloc> 00695 00696 #define PB_DS_TRIE_BASE \ 00697 basic_branch<Key,Mapped,Tag, \ 00698 typename PB_DS_TRIE_NODE_AND_IT_TRAITS::node_update, \ 00699 typename __gnu_cxx::typelist::create2<_ATraits, \ 00700 PB_DS_TRIE_NODE_AND_IT_TRAITS >::type, _Alloc> 00701 00702 00703 /** 00704 * A trie-based container. 00705 * 00706 * @tparam Key Key type. 00707 * @tparam Mapped Map type. 00708 * @tparam _ATraits Element access traits. 00709 * @tparam Tag Instantiating data structure type, 00710 * see container_tag. 00711 * @tparam Node_Update Updates trie nodes, 00712 * restores invariants when invalidated. 00713 * XXX See design::tree-based-containers::node invariants. 00714 * @tparam _Alloc Allocator type. 00715 * 00716 * Base tag choice is pat_trie_tag. 00717 * 00718 * Base is basic_branch. 00719 */ 00720 template<typename Key, 00721 typename Mapped, 00722 typename _ATraits = \ 00723 typename detail::default_trie_access_traits<Key>::type, 00724 typename Tag = pat_trie_tag, 00725 template<typename Node_CItr, 00726 typename Node_Itr, 00727 typename _ATraits_, 00728 typename _Alloc_> 00729 class Node_Update = null_node_update, 00730 typename _Alloc = std::allocator<char> > 00731 class trie : public PB_DS_TRIE_BASE 00732 { 00733 private: 00734 typedef PB_DS_TRIE_BASE base_type; 00735 00736 public: 00737 /// Element access traits type. 00738 typedef _ATraits access_traits; 00739 00740 trie() { } 00741 00742 /// Constructor taking some policy objects. r_access_traits will 00743 /// be copied by the _ATraits object of the container object. 00744 trie(const access_traits& t) 00745 : base_type(t) { } 00746 00747 /// Constructor taking __iterators to a range of value_types. The 00748 /// value_types between first_it and last_it will be inserted into 00749 /// the container object. 00750 template<typename It> 00751 trie(It first, It last) 00752 { base_type::copy_from_range(first, last); } 00753 00754 /// Constructor taking __iterators to a range of value_types and 00755 /// some policy objects. The value_types between first_it and 00756 /// last_it will be inserted into the container object. 00757 template<typename It> 00758 trie(It first, It last, const access_traits& t) 00759 : base_type(t) 00760 { base_type::copy_from_range(first, last); } 00761 00762 trie(const trie& other) 00763 : base_type((const base_type&)other) { } 00764 00765 virtual 00766 ~trie() { } 00767 00768 trie& 00769 operator=(const trie& other) 00770 { 00771 if (this != &other) 00772 { 00773 trie tmp(other); 00774 swap(tmp); 00775 } 00776 return *this; 00777 } 00778 00779 void 00780 swap(trie& other) 00781 { base_type::swap(other); } 00782 }; 00783 //@} branch-based 00784 #undef PB_DS_TRIE_BASE 00785 #undef PB_DS_TRIE_NODE_AND_IT_TRAITS 00786 00787 00788 /** 00789 * @defgroup list-based 00790 * @ingroup containers-pbds 00791 * @{ 00792 */ 00793 #define PB_DS_LU_BASE \ 00794 detail::container_base_dispatch<Key, Mapped, _Alloc, list_update_tag, \ 00795 typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type>::type 00796 00797 00798 /** 00799 * A list-update based associative container. 00800 * 00801 * @tparam Key Key type. 00802 * @tparam Mapped Map type. 00803 * @tparam Eq_Fn Equal functor. 00804 * @tparam Update_Policy Update policy, determines when an element 00805 * will be moved to the front of the list. 00806 * @tparam _Alloc Allocator type. 00807 * 00808 * Base is detail::lu_map. 00809 */ 00810 template<typename Key, 00811 typename Mapped, 00812 class Eq_Fn = typename detail::default_eq_fn<Key>::type, 00813 class Update_Policy = detail::default_update_policy::type, 00814 class _Alloc = std::allocator<char> > 00815 class list_update : public PB_DS_LU_BASE 00816 { 00817 private: 00818 typedef typename PB_DS_LU_BASE base_type; 00819 00820 public: 00821 typedef list_update_tag container_category; 00822 typedef Eq_Fn eq_fn; 00823 typedef Update_Policy update_policy; 00824 00825 list_update() { } 00826 00827 /// Constructor taking __iterators to a range of value_types. The 00828 /// value_types between first_it and last_it will be inserted into 00829 /// the container object. 00830 template<typename It> 00831 list_update(It first, It last) 00832 { base_type::copy_from_range(first, last); } 00833 00834 list_update(const list_update& other) 00835 : base_type((const base_type&)other) { } 00836 00837 virtual 00838 ~list_update() { } 00839 00840 list_update& 00841 operator=(const list_update& other) 00842 { 00843 if (this !=& other) 00844 { 00845 list_update tmp(other); 00846 swap(tmp); 00847 } 00848 return *this; 00849 } 00850 00851 void 00852 swap(list_update& other) 00853 { base_type::swap(other); } 00854 }; 00855 //@} list-based 00856 #undef PB_DS_LU_BASE 00857 00858 // @} group containers-pbds 00859 } // namespace __gnu_pbds 00860 00861 #endif