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 56namespace 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 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 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. 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. 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. 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. 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. 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> 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> 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> 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> 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> 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 267 cc_hash_table(const cc_hash_table& other) 268 : base_type((const base_type&)other) 269 { } 270 271 virtual 272 ~cc_hash_table() { } 273 274 cc_hash_table& 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 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. 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. 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. 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. 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. 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. 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> 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> 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> 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> 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> 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> 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 435 gp_hash_table(const gp_hash_table& other) 436 : base_type((const base_type&)other) 437 { } 438 439 virtual 440 ~gp_hash_table() { } 441 442 gp_hash_table& 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 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 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 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. 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> 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> 528 tree(It first, It last, const cmp_fn& c) 529 : base_type(c) 530 { base_type::copy_from_range(first, last); } 531 532 tree(const tree& other) 533 : base_type((const base_type&)other) { } 534 535 virtual 536 ~tree() { } 537 538 tree& 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 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 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. 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> 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> 604 trie(It first, It last, const e_access_traits& t) 605 : base_type(t) 606 { base_type::copy_from_range(first, last); } 607 608 trie(const trie& other) 609 : base_type((const base_type&)other) { } 610 611 virtual 612 ~trie() { } 613 614 trie& 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 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 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> 660 list_update(It first, It last) 661 { base_type::copy_from_range(first, last); } 662 663 list_update(const list_update& other) 664 : base_type((const base_type&)other) { } 665 666 virtual 667 ~list_update() { } 668 669 list_update& 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 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