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