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