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