1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the terms 7 // of the GNU General Public License as published by the Free Software 8 // Foundation; either version 2, or (at your option) any later 9 // version. 10 11 // This library is distributed in the hope that it will be useful, but 12 // WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 // General Public License for more details. 15 16 // You should have received a copy of the GNU General Public License 17 // along with this library; see the file COPYING. If not, write to 18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19 // MA 02111-1307, USA. 20 21 // As a special exception, you may use this file as part of a free 22 // software library without restriction. Specifically, if other files 23 // instantiate templates or use macros or inline functions from this 24 // file, or you compile this file and link it with other files to 25 // produce an executable, this file does not by itself cause the 26 // resulting executable to be covered by the GNU General Public 27 // License. This exception does not however invalidate any other 28 // reasons why the executable file might be covered by the GNU General 29 // Public License. 30 31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32 33 // Permission to use, copy, modify, sell, and distribute this software 34 // is hereby granted without fee, provided that the above copyright 35 // notice appears in all copies, and that both that copyright notice 36 // and this permission notice appear in supporting documentation. None 37 // of the above authors, nor IBM Haifa Research Laboratories, make any 38 // representation about the suitability of this software for any 39 // purpose. It is provided "as is" without express or implied 40 // warranty. 41 42 /** 43 * @file assoc_container.hpp 44 * Contains associative containers. 45 */ 46 47 #ifndef PB_DS_ASSOC_CNTNR_HPP 48 #define PB_DS_ASSOC_CNTNR_HPP 49 50 #include <ext/typelist.h> 51 #include <ext/pb_ds/tag_and_trait.hpp> 52 #include <ext/pb_ds/detail/standard_policies.hpp> 53 #include <ext/pb_ds/detail/container_base_dispatch.hpp> 54 #include <ext/pb_ds/detail/basic_tree_policy/traits.hpp> 55 56 namespace pb_ds 57 { 58 #define PB_DS_BASE_C_DEC \ 59 detail::container_base_dispatch<Key, Mapped, Tag, Policy_Tl, Allocator>::type 60 61 // An abstract basic associative container. 62 template<typename Key, 63 typename Mapped, 64 typename Tag, 65 typename Policy_Tl, 66 typename Allocator> 67 class container_base : public PB_DS_BASE_C_DEC 68 { 69 private: 70 typedef typename PB_DS_BASE_C_DEC base_type; 71 72 public: 73 typedef Tag container_category; 74 typedef Allocator allocator; 75 typedef typename allocator::size_type size_type; 76 typedef typename allocator::difference_type difference_type; 77 78 // key_type 79 typedef typename allocator::template rebind<Key>::other::value_type key_type; 80 typedef typename allocator::template rebind<key_type>::other key_rebind; 81 typedef typename key_rebind::reference key_reference; 82 typedef typename key_rebind::const_reference const_key_reference; 83 typedef typename key_rebind::pointer key_pointer; 84 typedef typename key_rebind::const_pointer const_key_pointer; 85 86 // mapped_type 87 typedef Mapped mapped_type; 88 typedef typename allocator::template rebind<mapped_type>::other mapped_rebind; 89 typedef typename mapped_rebind::reference mapped_reference; 90 typedef typename mapped_rebind::const_reference const_mapped_reference; 91 typedef typename mapped_rebind::pointer mapped_pointer; 92 typedef typename mapped_rebind::const_pointer const_mapped_pointer; 93 94 // value_type 95 typedef typename base_type::value_type value_type; 96 typedef typename allocator::template rebind<value_type>::other value_rebind; 97 typedef typename value_rebind::reference reference; 98 typedef typename value_rebind::const_reference const_reference; 99 typedef typename value_rebind::pointer pointer; 100 typedef typename value_rebind::const_pointer const_pointer; 101 102 // iterators 103 typedef typename base_type::iterator iterator; 104 typedef typename base_type::const_iterator const_iterator; 105 typedef typename base_type::point_iterator point_iterator; 106 typedef typename base_type::const_point_iterator const_point_iterator; 107 108 virtual ~container_base()109 ~container_base() { } 110 111 protected: 112 #define PB_DS_CLASS_NAME container_base 113 #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp> 114 #undef PB_DS_CLASS_NAME 115 }; 116 117 #undef PB_DS_BASE_C_DEC 118 119 120 #define PB_DS_BASE_C_DEC \ 121 container_base<Key, Mapped, Tag, typename __gnu_cxx::typelist::append< \ 122 typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, detail::integral_constant<int, Store_Hash> >::type, Policy_TL>::type, Allocator> 123 124 // An abstract basic hash-based associative container. 125 template<typename Key, 126 typename Mapped, 127 typename Hash_Fn, 128 typename Eq_Fn, 129 typename Resize_Policy, 130 bool Store_Hash, 131 typename Tag, 132 typename Policy_TL, 133 typename Allocator> 134 class basic_hash_table : public PB_DS_BASE_C_DEC 135 { 136 private: 137 typedef PB_DS_BASE_C_DEC base_type; 138 139 public: 140 virtual ~basic_hash_table()141 ~basic_hash_table() { } 142 143 protected: 144 #define PB_DS_CLASS_NAME basic_hash_table 145 #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp> 146 #undef PB_DS_CLASS_NAME 147 148 private: 149 basic_hash_table& 150 operator=(const base_type&); 151 }; 152 153 #undef PB_DS_BASE_C_DEC 154 155 156 #define PB_DS_BASE_C_DEC \ 157 basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \ 158 cc_hash_tag, \ 159 typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, Allocator> 160 161 // A concrete collision-chaining hash-based associative container. 162 template<typename Key, 163 typename Mapped, 164 typename Hash_Fn = typename detail::default_hash_fn<Key>::type, 165 typename Eq_Fn = typename detail::default_eq_fn<Key>::type, 166 typename Comb_Hash_Fn = detail::default_comb_hash_fn::type, 167 typename Resize_Policy = typename detail::default_resize_policy<Comb_Hash_Fn>::type, 168 bool Store_Hash = detail::default_store_hash, 169 typename Allocator = std::allocator<char> > 170 class cc_hash_table : public PB_DS_BASE_C_DEC 171 { 172 private: 173 typedef PB_DS_BASE_C_DEC base_type; 174 175 public: 176 typedef Hash_Fn hash_fn; 177 typedef Eq_Fn eq_fn; 178 typedef Resize_Policy resize_policy; 179 typedef Comb_Hash_Fn comb_hash_fn; 180 181 // Default constructor. cc_hash_table()182 cc_hash_table() { } 183 184 // Constructor taking some policy objects. r_hash_fn will be 185 // copied by the Hash_Fn object of the container object. cc_hash_table(const hash_fn & h)186 cc_hash_table(const hash_fn& h) 187 : base_type(h) { } 188 189 // Constructor taking some policy objects. r_hash_fn will be 190 // copied by the hash_fn object of the container object, and 191 // r_eq_fn will be copied by the eq_fn object of the container 192 // object. cc_hash_table(const hash_fn & h,const eq_fn & e)193 cc_hash_table(const hash_fn& h, const eq_fn& e) 194 : base_type(h, e) { } 195 196 // Constructor taking some policy objects. r_hash_fn will be 197 // copied by the hash_fn object of the container object, r_eq_fn 198 // will be copied by the eq_fn object of the container object, and 199 // r_comb_hash_fn will be copied by the comb_hash_fn object of the 200 // container object. cc_hash_table(const hash_fn & h,const eq_fn & e,const comb_hash_fn & ch)201 cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch) 202 : base_type(h, e, ch) { } 203 204 // Constructor taking some policy objects. r_hash_fn will be 205 // copied by the hash_fn object of the container object, r_eq_fn 206 // will be copied by the eq_fn object of the container object, 207 // r_comb_hash_fn will be copied by the comb_hash_fn object of the 208 // container object, and r_resize_policy will be copied by the 209 // 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)210 cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch, 211 const resize_policy& rp) 212 : base_type(h, e, ch, rp) { } 213 214 // Constructor taking __iterators to a range of value_types. The 215 // value_types between first_it and last_it will be inserted into 216 // the container object. 217 template<typename It> cc_hash_table(It first,It last)218 cc_hash_table(It first, It last) 219 { base_type::copy_from_range(first, last); } 220 221 // Constructor taking __iterators to a range of value_types and 222 // some policy objects. The value_types between first_it and 223 // last_it will be inserted into the container object. 224 template<typename It> cc_hash_table(It first,It last,const hash_fn & h)225 cc_hash_table(It first, It last, const hash_fn& h) 226 : base_type(h) 227 { copy_from_range(first, last); } 228 229 // Constructor taking __iterators to a range of value_types and 230 // some policy objects The value_types between first_it and 231 // last_it will be inserted into the container object. r_hash_fn 232 // will be copied by the hash_fn object of the container object, 233 // and r_eq_fn will be copied by the eq_fn object of the container 234 // object. 235 template<typename It> cc_hash_table(It first,It last,const hash_fn & h,const eq_fn & e)236 cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e) 237 : base_type(h, e) 238 { copy_from_range(first, last); } 239 240 // Constructor taking __iterators to a range of value_types and 241 // some policy objects The value_types between first_it and 242 // last_it will be inserted into the container object. r_hash_fn 243 // will be copied by the hash_fn object of the container object, 244 // r_eq_fn will be copied by the eq_fn object of the container 245 // object, and r_comb_hash_fn will be copied by the comb_hash_fn 246 // object of the container object. 247 template<typename It> cc_hash_table(It first,It last,const hash_fn & h,const eq_fn & e,const comb_hash_fn & ch)248 cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 249 const comb_hash_fn& ch) 250 : base_type(h, e, ch) 251 { copy_from_range(first, last); } 252 253 // Constructor taking __iterators to a range of value_types and 254 // some policy objects The value_types between first_it and 255 // last_it will be inserted into the container object. r_hash_fn 256 // will be copied by the hash_fn object of the container object, 257 // r_eq_fn will be copied by the eq_fn object of the container 258 // object, r_comb_hash_fn will be copied by the comb_hash_fn 259 // object of the container object, and r_resize_policy will be 260 // copied by the resize_policy object of the container object. 261 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)262 cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 263 const comb_hash_fn& ch, const resize_policy& rp) 264 : base_type(h, e, ch, rp) 265 { copy_from_range(first, last); } 266 cc_hash_table(const cc_hash_table & other)267 cc_hash_table(const cc_hash_table& other) 268 : base_type((const base_type&)other) 269 { } 270 271 virtual ~cc_hash_table()272 ~cc_hash_table() { } 273 274 cc_hash_table& operator =(const cc_hash_table & other)275 operator=(const cc_hash_table& other) 276 { 277 if (this != &other) 278 { 279 cc_hash_table tmp(other); 280 swap(tmp); 281 } 282 return *this; 283 } 284 285 void swap(cc_hash_table & other)286 swap(cc_hash_table& other) 287 { base_type::swap(other); } 288 }; 289 290 #undef PB_DS_BASE_C_DEC 291 292 293 #define PB_DS_BASE_C_DEC \ 294 basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \ 295 gp_hash_tag, \ 296 typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, Allocator> 297 298 // A concrete general-probing hash-based associative container. 299 template<typename Key, 300 typename Mapped, 301 typename Hash_Fn = typename detail::default_hash_fn<Key>::type, 302 typename Eq_Fn = typename detail::default_eq_fn<Key>::type, 303 typename Comb_Probe_Fn = detail::default_comb_hash_fn::type, 304 typename Probe_Fn = typename detail::default_probe_fn<Comb_Probe_Fn>::type, 305 typename Resize_Policy = typename detail::default_resize_policy<Comb_Probe_Fn>::type, 306 bool Store_Hash = detail::default_store_hash, 307 typename Allocator = std::allocator<char> > 308 class gp_hash_table : public PB_DS_BASE_C_DEC 309 { 310 private: 311 typedef PB_DS_BASE_C_DEC base_type; 312 313 public: 314 typedef Hash_Fn hash_fn; 315 typedef Eq_Fn eq_fn; 316 typedef Comb_Probe_Fn comb_probe_fn; 317 typedef Probe_Fn probe_fn; 318 typedef Resize_Policy resize_policy; 319 320 // Default constructor. gp_hash_table()321 gp_hash_table() { } 322 323 // Constructor taking some policy objects. r_hash_fn will be 324 // copied by the hash_fn object of the container object. gp_hash_table(const hash_fn & h)325 gp_hash_table(const hash_fn& h) 326 : base_type(h) { } 327 328 // Constructor taking some policy objects. r_hash_fn will be 329 // copied by the hash_fn object of the container object, and 330 // r_eq_fn will be copied by the eq_fn object of the container 331 // object. gp_hash_table(const hash_fn & h,const eq_fn & e)332 gp_hash_table(const hash_fn& h, const eq_fn& e) 333 : base_type(h, e) { } 334 335 // Constructor taking some policy objects. r_hash_fn will be 336 // copied by the hash_fn object of the container object, r_eq_fn 337 // will be copied by the eq_fn object of the container object, and 338 // r_comb_probe_fn will be copied by the comb_probe_fn object of 339 // the container object. gp_hash_table(const hash_fn & h,const eq_fn & e,const comb_probe_fn & cp)340 gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp) 341 : base_type(h, e, cp) { } 342 343 // Constructor taking some policy objects. r_hash_fn will be 344 // copied by the hash_fn object of the container object, r_eq_fn 345 // will be copied by the eq_fn object of the container object, 346 // r_comb_probe_fn will be copied by the comb_probe_fn object of 347 // the container object, and r_probe_fn will be copied by the 348 // 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)349 gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, 350 const probe_fn& p) 351 : base_type(h, e, cp, p) { } 352 353 // Constructor taking some policy objects. r_hash_fn will be 354 // copied by the hash_fn object of the container object, r_eq_fn 355 // will be copied by the eq_fn object of the container object, 356 // r_comb_probe_fn will be copied by the comb_probe_fn object of 357 // the container object, r_probe_fn will be copied by the probe_fn 358 // object of the container object, and r_resize_policy will be 359 // 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)360 gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, 361 const probe_fn& p, const resize_policy& rp) 362 : base_type(h, e, cp, p, rp) { } 363 364 // Constructor taking __iterators to a range of value_types. The 365 // value_types between first_it and last_it will be inserted into 366 // the container object. 367 template<typename It> gp_hash_table(It first,It last)368 gp_hash_table(It first, It last) 369 { base_type::copy_from_range(first, last); } 370 371 // Constructor taking __iterators to a range of value_types and 372 // some policy objects. The value_types between first_it and 373 // last_it will be inserted into the container object. r_hash_fn 374 // will be copied by the hash_fn object of the container object. 375 template<typename It> gp_hash_table(It first,It last,const hash_fn & h)376 gp_hash_table(It first, It last, const hash_fn& h) 377 : base_type(h) 378 { base_type::copy_from_range(first, last); } 379 380 // Constructor taking __iterators to a range of value_types and 381 // some policy objects. The value_types between first_it and 382 // last_it will be inserted into the container object. r_hash_fn 383 // will be copied by the hash_fn object of the container object, 384 // and r_eq_fn will be copied by the eq_fn object of the container 385 // object. 386 template<typename It> gp_hash_table(It first,It last,const hash_fn & h,const eq_fn & e)387 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e) 388 : base_type(h, e) 389 { base_type::copy_from_range(first, last); } 390 391 // Constructor taking __iterators to a range of value_types and 392 // some policy objects. The value_types between first_it and 393 // last_it will be inserted into the container object. r_hash_fn 394 // will be copied by the hash_fn object of the container object, 395 // r_eq_fn will be copied by the eq_fn object of the container 396 // object, and r_comb_probe_fn will be copied by the comb_probe_fn 397 // object of the container object. 398 template<typename It> gp_hash_table(It first,It last,const hash_fn & h,const eq_fn & e,const comb_probe_fn & cp)399 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 400 const comb_probe_fn& cp) 401 : base_type(h, e, cp) 402 { base_type::copy_from_range(first, last); } 403 404 // Constructor taking __iterators to a range of value_types and 405 // some policy objects. The value_types between first_it and 406 // last_it will be inserted into the container object. r_hash_fn 407 // will be copied by the hash_fn object of the container object, 408 // r_eq_fn will be copied by the eq_fn object of the container 409 // object, r_comb_probe_fn will be copied by the comb_probe_fn 410 // object of the container object, and r_probe_fn will be copied 411 // by the probe_fn object of the container object. 412 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)413 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 414 const comb_probe_fn& cp, const probe_fn& p) 415 : base_type(h, e, cp, p) 416 { base_type::copy_from_range(first, last); } 417 418 // Constructor taking __iterators to a range of value_types and 419 // some policy objects. The value_types between first_it and 420 // last_it will be inserted into the container object. r_hash_fn 421 // will be copied by the hash_fn object of the container object, 422 // r_eq_fn will be copied by the eq_fn object of the container 423 // object, r_comb_probe_fn will be copied by the comb_probe_fn 424 // object of the container object, r_probe_fn will be copied by 425 // the probe_fn object of the container object, and 426 // r_resize_policy will be copied by the resize_policy object of 427 // the container object. 428 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)429 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 430 const comb_probe_fn& cp, const probe_fn& p, 431 const resize_policy& rp) 432 : base_type(h, e, cp, p, rp) 433 { base_type::copy_from_range(first, last); } 434 gp_hash_table(const gp_hash_table & other)435 gp_hash_table(const gp_hash_table& other) 436 : base_type((const base_type&)other) 437 { } 438 439 virtual ~gp_hash_table()440 ~gp_hash_table() { } 441 442 gp_hash_table& operator =(const gp_hash_table & other)443 operator=(const gp_hash_table& other) 444 { 445 if (this != &other) 446 { 447 gp_hash_table tmp(other); 448 swap(tmp); 449 } 450 return *this; 451 } 452 453 void swap(gp_hash_table & other)454 swap(gp_hash_table& other) 455 { base_type::swap(other); } 456 }; 457 458 #undef PB_DS_BASE_C_DEC 459 460 461 #define PB_DS_BASE_C_DEC \ 462 container_base<Key, Mapped, Tag, Policy_Tl, Allocator> 463 464 // An abstract basic tree-like (tree, trie) associative container. 465 template<typename Key, typename Mapped, typename Tag, 466 typename Node_Update, typename Policy_Tl, typename Allocator> 467 class basic_tree : public PB_DS_BASE_C_DEC 468 { 469 private: 470 typedef PB_DS_BASE_C_DEC base_type; 471 472 public: 473 typedef Node_Update node_update; 474 475 virtual ~basic_tree()476 ~basic_tree() { } 477 478 protected: 479 #define PB_DS_CLASS_NAME basic_tree 480 #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp> 481 #undef PB_DS_CLASS_NAME 482 }; 483 484 #undef PB_DS_BASE_C_DEC 485 486 487 #define PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC \ 488 detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag, Allocator> 489 490 #define PB_DS_BASE_C_DEC \ 491 basic_tree<Key,Mapped,Tag,typename PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC::node_update, \ 492 typename __gnu_cxx::typelist::create2<Cmp_Fn, PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC >::type, Allocator> 493 494 // A concrete basic tree-based associative container. 495 template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>, 496 typename Tag = rb_tree_tag, 497 template<typename Const_Node_Iterator, typename Node_Iterator, typename Cmp_Fn_, typename Allocator_> 498 class Node_Update = pb_ds::null_tree_node_update, 499 typename Allocator = std::allocator<char> > 500 class tree : public PB_DS_BASE_C_DEC 501 { 502 private: 503 typedef PB_DS_BASE_C_DEC base_type; 504 505 public: 506 // Comparison functor type. 507 typedef Cmp_Fn cmp_fn; 508 tree()509 tree() { } 510 511 // Constructor taking some policy objects. r_cmp_fn will be copied 512 // by the Cmp_Fn object of the container object. tree(const cmp_fn & c)513 tree(const cmp_fn& c) 514 : base_type(c) { } 515 516 // Constructor taking __iterators to a range of value_types. The 517 // value_types between first_it and last_it will be inserted into 518 // the container object. 519 template<typename It> tree(It first,It last)520 tree(It first, It last) 521 { base_type::copy_from_range(first, last); } 522 523 // Constructor taking __iterators to a range of value_types and 524 // some policy objects The value_types between first_it and 525 // last_it will be inserted into the container object. r_cmp_fn 526 // will be copied by the cmp_fn object of the container object. 527 template<typename It> tree(It first,It last,const cmp_fn & c)528 tree(It first, It last, const cmp_fn& c) 529 : base_type(c) 530 { base_type::copy_from_range(first, last); } 531 tree(const tree & other)532 tree(const tree& other) 533 : base_type((const base_type&)other) { } 534 535 virtual ~tree()536 ~tree() { } 537 538 tree& operator =(const tree & other)539 operator=(const tree& other) 540 { 541 if (this != &other) 542 { 543 tree tmp(other); 544 swap(tmp); 545 } 546 return *this; 547 } 548 549 void swap(tree & other)550 swap(tree& other) 551 { base_type::swap(other); } 552 }; 553 554 #undef PB_DS_BASE_C_DEC 555 #undef PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC 556 557 558 #define PB_DS_TRIE_NODE_AND_ITS_TRAITS \ 559 detail::trie_traits<Key,Mapped,E_Access_Traits,Node_Update,Tag,Allocator> 560 561 #define PB_DS_BASE_C_DEC \ 562 basic_tree<Key,Mapped,Tag, typename PB_DS_TRIE_NODE_AND_ITS_TRAITS::node_update, \ 563 typename __gnu_cxx::typelist::create2<E_Access_Traits, PB_DS_TRIE_NODE_AND_ITS_TRAITS >::type, Allocator> 564 565 // A concrete basic trie-based associative container. 566 template<typename Key, 567 typename Mapped, 568 typename E_Access_Traits = typename detail::default_trie_e_access_traits<Key>::type, 569 typename Tag = pat_trie_tag, 570 template<typename Const_Node_Iterator, 571 typename Node_Iterator, 572 typename E_Access_Traits_, 573 typename Allocator_> 574 class Node_Update = null_trie_node_update, 575 typename Allocator = std::allocator<char> > 576 class trie : public PB_DS_BASE_C_DEC 577 { 578 private: 579 typedef PB_DS_BASE_C_DEC base_type; 580 581 public: 582 // Element access traits type. 583 typedef E_Access_Traits e_access_traits; 584 trie()585 trie() { } 586 587 // Constructor taking some policy objects. r_e_access_traits will 588 // be copied by the E_Access_Traits object of the container 589 // object. trie(const e_access_traits & t)590 trie(const e_access_traits& t) 591 : base_type(t) { } 592 593 // Constructor taking __iterators to a range of value_types. The 594 // value_types between first_it and last_it will be inserted into 595 // the container object. 596 template<typename It> trie(It first,It last)597 trie(It first, It last) 598 { base_type::copy_from_range(first, last); } 599 600 // Constructor taking __iterators to a range of value_types and 601 // some policy objects. The value_types between first_it and 602 // last_it will be inserted into the container object. 603 template<typename It> trie(It first,It last,const e_access_traits & t)604 trie(It first, It last, const e_access_traits& t) 605 : base_type(t) 606 { base_type::copy_from_range(first, last); } 607 trie(const trie & other)608 trie(const trie& other) 609 : base_type((const base_type&)other) { } 610 611 virtual ~trie()612 ~trie() { } 613 614 trie& operator =(const trie & other)615 operator=(const trie& other) 616 { 617 if (this != &other) 618 { 619 trie tmp(other); 620 swap(tmp); 621 } 622 return *this; 623 } 624 625 void swap(trie & other)626 swap(trie& other) 627 { base_type::swap(other); } 628 }; 629 630 #undef PB_DS_BASE_C_DEC 631 #undef PB_DS_TRIE_NODE_AND_ITS_TRAITS 632 633 634 #define PB_DS_BASE_C_DEC \ 635 container_base<Key, Mapped, list_update_tag, \ 636 typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type, Allocator> 637 638 // A list-update based associative container. 639 template<typename Key, 640 typename Mapped, 641 class Eq_Fn = typename detail::default_eq_fn<Key>::type, 642 class Update_Policy = detail::default_update_policy::type, 643 class Allocator = std::allocator<char> > 644 class list_update : public PB_DS_BASE_C_DEC 645 { 646 private: 647 typedef PB_DS_BASE_C_DEC base_type; 648 649 public: 650 typedef Eq_Fn eq_fn; 651 typedef Update_Policy update_policy; 652 typedef Allocator allocator; 653 list_update()654 list_update() { } 655 656 // Constructor taking __iterators to a range of value_types. The 657 // value_types between first_it and last_it will be inserted into 658 // the container object. 659 template<typename It> list_update(It first,It last)660 list_update(It first, It last) 661 { base_type::copy_from_range(first, last); } 662 list_update(const list_update & other)663 list_update(const list_update& other) 664 : base_type((const base_type&)other) { } 665 666 virtual ~list_update()667 ~list_update() { } 668 669 list_update& operator =(const list_update & other)670 operator=(const list_update& other) 671 { 672 if (this !=& other) 673 { 674 list_update tmp(other); 675 swap(tmp); 676 } 677 return *this; 678 } 679 680 void swap(list_update & other)681 swap(list_update& other) 682 { base_type::swap(other); } 683 }; 684 685 #undef PB_DS_BASE_C_DEC 686 687 } // namespace pb_ds 688 689 #endif 690