1// -*- C++ -*- 2 3// Copyright (C) 2005-2022 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/branch_policy/traits.hpp> 50 51namespace __gnu_pbds 52{ 53 /** 54 * @defgroup containers-pbds Containers 55 * @ingroup pbds 56 * @{ 57 */ 58 59 /** 60 * @defgroup hash-based Hash-Based 61 * @ingroup containers-pbds 62 * @{ 63 */ 64#define PB_DS_HASH_BASE \ 65 detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, \ 66 typename __gnu_cxx::typelist::append< \ 67 typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, \ 68 detail::integral_constant<int, Store_Hash> >::type, Policy_Tl>::type>::type 69 70 /** 71 * @defgroup hash-detail Base and Policy Classes 72 * @ingroup hash-based 73 */ 74 75 /** 76 * A hashed container abstraction. 77 * 78 * @tparam Key Key type. 79 * @tparam Mapped Map type. 80 * @tparam Hash_Fn Hashing functor. 81 * @tparam Eq_Fn Equal functor. 82 * @tparam Resize_Policy Resizes hash. 83 * @tparam Store_Hash Indicates whether the hash value 84 * will be stored along with each key. 85 * @tparam Tag Instantiating data structure type, 86 * see container_tag. 87 * @tparam Policy_TL Policy typelist. 88 * @tparam _Alloc Allocator type. 89 * 90 * Base is dispatched at compile time via Tag, from the following 91 * choices: cc_hash_tag, gp_hash_tag, and descendants of basic_hash_tag. 92 * 93 * Base choices are: detail::cc_ht_map, detail::gp_ht_map 94 */ 95 template<typename Key, 96 typename Mapped, 97 typename Hash_Fn, 98 typename Eq_Fn, 99 typename Resize_Policy, 100 bool Store_Hash, 101 typename Tag, 102 typename Policy_Tl, 103 typename _Alloc> 104 class basic_hash_table : public PB_DS_HASH_BASE 105 { 106 private: 107 typedef typename PB_DS_HASH_BASE base_type; 108 109 public: 110 virtual 111 ~basic_hash_table() { } 112 113 protected: 114 basic_hash_table() { } 115 116 basic_hash_table(const basic_hash_table& other) 117 : base_type((const base_type&)other) { } 118 119 template<typename T0> 120 basic_hash_table(T0 t0) : base_type(t0) { } 121 122 template<typename T0, typename T1> 123 basic_hash_table(T0 t0, T1 t1) : base_type(t0, t1) { } 124 125 template<typename T0, typename T1, typename T2> 126 basic_hash_table(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { } 127 128 template<typename T0, typename T1, typename T2, typename T3> 129 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3) 130 : base_type(t0, t1, t2, t3) { } 131 132 template<typename T0, typename T1, typename T2, typename T3, typename T4> 133 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4) 134 : base_type(t0, t1, t2, t3, t4) { } 135 136 template<typename T0, typename T1, typename T2, typename T3, typename T4, 137 typename T5> 138 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5) 139 : base_type(t0, t1, t2, t3, t4, t5) { } 140 141 template<typename T0, typename T1, typename T2, typename T3, typename T4, 142 typename T5, typename T6> 143 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6) 144 : base_type(t0, t1, t2, t3, t4, t5, t6) { } 145 146 template<typename T0, typename T1, typename T2, typename T3, typename T4, 147 typename T5, typename T6, typename T7> 148 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6, T7 t7) 149 : base_type(t0, t1, t2, t3, t4, t5, t6, t7) { } 150 151 template<typename T0, typename T1, typename T2, typename T3, typename T4, 152 typename T5, typename T6, typename T7, typename T8> 153 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6, 154 T7 t7, T8 t8) 155 : base_type(t0, t1, t2, t3, t4, t5, t6, t7, t8) 156 { } 157 158 private: 159 basic_hash_table& 160 operator=(const base_type&); 161 }; 162 163#undef PB_DS_HASH_BASE 164 165 166#define PB_DS_CC_HASH_BASE \ 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, _Alloc> 170 171 172 /** 173 * A collision-chaining hash-based associative container. 174 * 175 * @tparam Key Key type. 176 * @tparam Mapped Map type. 177 * @tparam Hash_Fn Hashing functor. 178 * @tparam Eq_Fn Equal functor. 179 * @tparam Comb_Hash_Fn Combining hash functor. 180 * If Hash_Fn is not null_type, then this 181 * is the ranged-hash functor; otherwise, 182 * this is the range-hashing functor. 183 * XXX(See Design::Hash-Based Containers::Hash Policies.) 184 * @tparam Resize_Policy Resizes hash. 185 * @tparam Store_Hash Indicates whether the hash value 186 * will be stored along with each key. 187 * If Hash_Fn is null_type, then the 188 * container will not compile if this 189 * value is true 190 * @tparam _Alloc Allocator type. 191 * 192 * Base tag choices are: cc_hash_tag. 193 * 194 * Base is basic_hash_table. 195 */ 196 template<typename Key, 197 typename Mapped, 198 typename Hash_Fn = typename detail::default_hash_fn<Key>::type, 199 typename Eq_Fn = typename detail::default_eq_fn<Key>::type, 200 typename Comb_Hash_Fn = detail::default_comb_hash_fn::type, 201 typename Resize_Policy = typename detail::default_resize_policy<Comb_Hash_Fn>::type, 202 bool Store_Hash = detail::default_store_hash, 203 typename _Alloc = std::allocator<char> > 204 class cc_hash_table : public PB_DS_CC_HASH_BASE 205 { 206 private: 207 typedef PB_DS_CC_HASH_BASE base_type; 208 209 public: 210 typedef cc_hash_tag container_category; 211 typedef Hash_Fn hash_fn; 212 typedef Eq_Fn eq_fn; 213 typedef Resize_Policy resize_policy; 214 typedef Comb_Hash_Fn comb_hash_fn; 215 216 /// Default constructor. 217 cc_hash_table() { } 218 219 /// Constructor taking some policy objects. r_hash_fn will be 220 /// copied by the Hash_Fn object of the container object. 221 cc_hash_table(const hash_fn& h) 222 : base_type(h) { } 223 224 /// Constructor taking some policy objects. r_hash_fn will be 225 /// copied by the hash_fn object of the container object, and 226 /// r_eq_fn will be copied by the eq_fn object of the container 227 /// object. 228 cc_hash_table(const hash_fn& h, const eq_fn& e) 229 : base_type(h, e) { } 230 231 /// Constructor taking some policy objects. r_hash_fn will be 232 /// copied by the hash_fn object of the container object, r_eq_fn 233 /// will be copied by the eq_fn object of the container object, 234 /// and r_comb_hash_fn will be copied by the comb_hash_fn object 235 /// of the container object. 236 cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch) 237 : base_type(h, e, ch) { } 238 239 /// Constructor taking some policy objects. r_hash_fn will be 240 /// copied by the hash_fn object of the container object, r_eq_fn 241 /// will be copied by the eq_fn object of the container object, 242 /// r_comb_hash_fn will be copied by the comb_hash_fn object of 243 /// the container object, and r_resize_policy will be copied by 244 /// the resize_policy object of the container object. 245 cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch, 246 const resize_policy& rp) 247 : base_type(h, e, ch, rp) { } 248 249 /// Constructor taking __iterators to a range of value_types. The 250 /// value_types between first_it and last_it will be inserted into 251 /// the container object. 252 template<typename It> 253 cc_hash_table(It first, It last) 254 { base_type::copy_from_range(first, last); } 255 256 /// Constructor taking __iterators to a range of value_types and 257 /// some policy objects. The value_types between first_it and 258 /// last_it will be inserted into the container object. 259 template<typename It> 260 cc_hash_table(It first, It last, const hash_fn& h) 261 : base_type(h) 262 { this->copy_from_range(first, last); } 263 264 /// Constructor taking __iterators to a range of value_types and 265 /// some policy objects The value_types between first_it and 266 /// last_it will be inserted into the container object. r_hash_fn 267 /// will be copied by the hash_fn object of the container object, 268 /// and r_eq_fn will be copied by the eq_fn object of the 269 /// container object. 270 template<typename It> 271 cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e) 272 : base_type(h, e) 273 { this->copy_from_range(first, last); } 274 275 /// Constructor taking __iterators to a range of value_types and 276 /// some policy objects The value_types between first_it and 277 /// last_it will be inserted into the container object. r_hash_fn 278 /// will be copied by the hash_fn object of the container object, 279 /// r_eq_fn will be copied by the eq_fn object of the container 280 /// object, and r_comb_hash_fn will be copied by the comb_hash_fn 281 /// object of the container object. 282 template<typename It> 283 cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 284 const comb_hash_fn& ch) 285 : base_type(h, e, ch) 286 { this->copy_from_range(first, last); } 287 288 /// Constructor taking __iterators to a range of value_types and 289 /// some policy objects The value_types between first_it and 290 /// last_it will be inserted into the container object. r_hash_fn 291 /// will be copied by the hash_fn object of the container object, 292 /// r_eq_fn will be copied by the eq_fn object of the container 293 /// object, r_comb_hash_fn will be copied by the comb_hash_fn 294 /// object of the container object, and r_resize_policy will be 295 /// copied by the resize_policy object of the container object. 296 template<typename It> 297 cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 298 const comb_hash_fn& ch, const resize_policy& rp) 299 : base_type(h, e, ch, rp) 300 { this->copy_from_range(first, last); } 301 302 cc_hash_table(const cc_hash_table& other) 303 : base_type((const base_type&)other) 304 { } 305 306 virtual 307 ~cc_hash_table() { } 308 309 cc_hash_table& 310 operator=(const cc_hash_table& other) 311 { 312 if (this != &other) 313 { 314 cc_hash_table tmp(other); 315 swap(tmp); 316 } 317 return *this; 318 } 319 320 void 321 swap(cc_hash_table& other) 322 { base_type::swap(other); } 323 }; 324 325#undef PB_DS_CC_HASH_BASE 326 327 328#define PB_DS_GP_HASH_BASE \ 329 basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \ 330 gp_hash_tag, \ 331 typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, _Alloc> 332 333 334 /** 335 * A general-probing hash-based associative container. 336 * 337 * @tparam Key Key type. 338 * @tparam Mapped Map type. 339 * @tparam Hash_Fn Hashing functor. 340 * @tparam Eq_Fn Equal functor. 341 * @tparam Comb_Probe_Fn Combining probe functor. 342 * If Hash_Fn is not null_type, then this 343 * is the ranged-probe functor; otherwise, 344 * this is the range-hashing functor. 345 * XXX See Design::Hash-Based Containers::Hash Policies. 346 * @tparam Probe_Fn Probe functor. 347 * @tparam Resize_Policy Resizes hash. 348 * @tparam Store_Hash Indicates whether the hash value 349 * will be stored along with each key. 350 * If Hash_Fn is null_type, then the 351 * container will not compile if this 352 * value is true 353 * @tparam _Alloc Allocator type. 354 * 355 * Base tag choices are: gp_hash_tag. 356 * 357 * Base is basic_hash_table. 358 */ 359 template<typename Key, 360 typename Mapped, 361 typename Hash_Fn = typename detail::default_hash_fn<Key>::type, 362 typename Eq_Fn = typename detail::default_eq_fn<Key>::type, 363 typename Comb_Probe_Fn = detail::default_comb_hash_fn::type, 364 typename Probe_Fn = typename detail::default_probe_fn<Comb_Probe_Fn>::type, 365 typename Resize_Policy = typename detail::default_resize_policy<Comb_Probe_Fn>::type, 366 bool Store_Hash = detail::default_store_hash, 367 typename _Alloc = std::allocator<char> > 368 class gp_hash_table : public PB_DS_GP_HASH_BASE 369 { 370 private: 371 typedef PB_DS_GP_HASH_BASE base_type; 372 373 public: 374 typedef gp_hash_tag container_category; 375 typedef Hash_Fn hash_fn; 376 typedef Eq_Fn eq_fn; 377 typedef Comb_Probe_Fn comb_probe_fn; 378 typedef Probe_Fn probe_fn; 379 typedef Resize_Policy resize_policy; 380 381 /// Default constructor. 382 gp_hash_table() { } 383 384 /// Constructor taking some policy objects. r_hash_fn will be 385 /// copied by the hash_fn object of the container object. 386 gp_hash_table(const hash_fn& h) 387 : base_type(h) { } 388 389 /// Constructor taking some policy objects. r_hash_fn will be 390 /// copied by the hash_fn object of the container object, and 391 /// r_eq_fn will be copied by the eq_fn object of the container 392 /// object. 393 gp_hash_table(const hash_fn& h, const eq_fn& e) 394 : base_type(h, e) { } 395 396 /// Constructor taking some policy objects. r_hash_fn will be 397 /// copied by the hash_fn object of the container object, r_eq_fn 398 /// will be copied by the eq_fn object of the container object, 399 /// and r_comb_probe_fn will be copied by the comb_probe_fn object 400 /// of the container object. 401 gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp) 402 : base_type(h, e, cp) { } 403 404 /// Constructor taking some policy objects. r_hash_fn will be 405 /// copied by the hash_fn object of the container object, r_eq_fn 406 /// will be copied by the eq_fn object of the container object, 407 /// r_comb_probe_fn will be copied by the comb_probe_fn object of 408 /// the container object, and r_probe_fn will be copied by the 409 /// probe_fn object of the container object. 410 gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, 411 const probe_fn& p) 412 : base_type(h, e, cp, p) { } 413 414 /// Constructor taking some policy objects. r_hash_fn will be 415 /// copied by the hash_fn object of the container object, r_eq_fn 416 /// will be copied by the eq_fn object of the container object, 417 /// r_comb_probe_fn will be copied by the comb_probe_fn object of 418 /// the container object, r_probe_fn will be copied by the 419 /// probe_fn object of the container object, and r_resize_policy 420 /// will be copied by the Resize_Policy object of the container 421 /// object. 422 gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, 423 const probe_fn& p, const resize_policy& rp) 424 : base_type(h, e, cp, p, rp) { } 425 426 /// Constructor taking __iterators to a range of value_types. The 427 /// value_types between first_it and last_it will be inserted into 428 /// the container object. 429 template<typename It> 430 gp_hash_table(It first, It last) 431 { base_type::copy_from_range(first, last); } 432 433 /// Constructor taking __iterators to a range of value_types and 434 /// some policy objects. The value_types between first_it and 435 /// last_it will be inserted into the container object. r_hash_fn 436 /// will be copied by the hash_fn object of the container object. 437 template<typename It> 438 gp_hash_table(It first, It last, const hash_fn& h) 439 : base_type(h) 440 { base_type::copy_from_range(first, last); } 441 442 /// Constructor taking __iterators to a range of value_types and 443 /// some policy objects. The value_types between first_it and 444 /// last_it will be inserted into the container object. r_hash_fn 445 /// will be copied by the hash_fn object of the container object, 446 /// and r_eq_fn will be copied by the eq_fn object of the 447 /// container object. 448 template<typename It> 449 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e) 450 : base_type(h, e) 451 { base_type::copy_from_range(first, last); } 452 453 /// Constructor taking __iterators to a range of value_types and 454 /// some policy objects. The value_types between first_it and 455 /// last_it will be inserted into the container object. r_hash_fn 456 /// will be copied by the hash_fn object of the container object, 457 /// r_eq_fn will be copied by the eq_fn object of the container 458 /// object, and r_comb_probe_fn will be copied by the 459 /// comb_probe_fn object of the container object. 460 template<typename It> 461 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 462 const comb_probe_fn& cp) 463 : base_type(h, e, cp) 464 { base_type::copy_from_range(first, last); } 465 466 /// Constructor taking __iterators to a range of value_types and 467 /// some policy objects. The value_types between first_it and 468 /// last_it will be inserted into the container object. r_hash_fn 469 /// will be copied by the hash_fn object of the container object, 470 /// r_eq_fn will be copied by the eq_fn object of the container 471 /// object, r_comb_probe_fn will be copied by the comb_probe_fn 472 /// object of the container object, and r_probe_fn will be copied 473 /// by the probe_fn object of the container object. 474 template<typename It> 475 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 476 const comb_probe_fn& cp, const probe_fn& p) 477 : base_type(h, e, cp, p) 478 { base_type::copy_from_range(first, last); } 479 480 /// Constructor taking __iterators to a range of value_types and 481 /// some policy objects. The value_types between first_it and 482 /// last_it will be inserted into the container object. r_hash_fn 483 /// will be copied by the hash_fn object of the container object, 484 /// r_eq_fn will be copied by the eq_fn object of the container 485 /// object, r_comb_probe_fn will be copied by the comb_probe_fn 486 /// object of the container object, r_probe_fn will be copied by 487 /// the probe_fn object of the container object, and 488 /// r_resize_policy will be copied by the resize_policy object of 489 /// the container object. 490 template<typename It> 491 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, 492 const comb_probe_fn& cp, const probe_fn& p, 493 const resize_policy& rp) 494 : base_type(h, e, cp, p, rp) 495 { base_type::copy_from_range(first, last); } 496 497 gp_hash_table(const gp_hash_table& other) 498 : base_type((const base_type&)other) 499 { } 500 501 virtual 502 ~gp_hash_table() { } 503 504 gp_hash_table& 505 operator=(const gp_hash_table& other) 506 { 507 if (this != &other) 508 { 509 gp_hash_table tmp(other); 510 swap(tmp); 511 } 512 return *this; 513 } 514 515 void 516 swap(gp_hash_table& other) 517 { base_type::swap(other); } 518 }; 519 ///@} hash-based 520#undef PB_DS_GP_HASH_BASE 521 522 523 /** 524 * @defgroup branch-based Branch-Based 525 * @ingroup containers-pbds 526 * @{ 527 */ 528#define PB_DS_BRANCH_BASE \ 529 detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, Policy_Tl>::type 530 531 /** 532 * @defgroup branch-detail Base and Policy Classes 533 * @ingroup branch-based 534 */ 535 536 /** 537 * A branched, tree-like (tree, trie) container abstraction. 538 * 539 * @tparam Key Key type. 540 * @tparam Mapped Map type. 541 * @tparam Tag Instantiating data structure type, 542 * see container_tag. 543 * @tparam Node_Update Updates nodes, restores invariants. 544 * @tparam Policy_TL Policy typelist. 545 * @tparam _Alloc Allocator type. 546 * 547 * Base is dispatched at compile time via Tag, from the following 548 * choices: tree_tag, trie_tag, and their descendants. 549 * 550 * Base choices are: detail::ov_tree_map, detail::rb_tree_map, 551 * detail::splay_tree_map, and detail::pat_trie_map. 552 */ 553 template<typename Key, typename Mapped, typename Tag, 554 typename Node_Update, typename Policy_Tl, typename _Alloc> 555 class basic_branch : public PB_DS_BRANCH_BASE 556 { 557 private: 558 typedef typename PB_DS_BRANCH_BASE base_type; 559 560 public: 561 typedef Node_Update node_update; 562 563 virtual 564 ~basic_branch() { } 565 566 protected: 567 basic_branch() { } 568 569 basic_branch(const basic_branch& other) 570 : base_type((const base_type&)other) { } 571 572 template<typename T0> 573 basic_branch(T0 t0) : base_type(t0) { } 574 575 template<typename T0, typename T1> 576 basic_branch(T0 t0, T1 t1) : base_type(t0, t1) { } 577 578 template<typename T0, typename T1, typename T2> 579 basic_branch(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { } 580 581 template<typename T0, typename T1, typename T2, typename T3> 582 basic_branch(T0 t0, T1 t1, T2 t2, T3 t3) 583 : base_type(t0, t1, t2, t3) { } 584 585 template<typename T0, typename T1, typename T2, typename T3, typename T4> 586 basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4) 587 : base_type(t0, t1, t2, t3, t4) { } 588 589 template<typename T0, typename T1, typename T2, typename T3, typename T4, 590 typename T5> 591 basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5) 592 : base_type(t0, t1, t2, t3, t4, t5) { } 593 594 template<typename T0, typename T1, typename T2, typename T3, typename T4, 595 typename T5, typename T6> 596 basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6) 597 : base_type(t0, t1, t2, t3, t4, t5, t6) { } 598 }; 599#undef PB_DS_BRANCH_BASE 600 601 602#define PB_DS_TREE_NODE_AND_IT_TRAITS \ 603 detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag,_Alloc> 604 605#define PB_DS_TREE_BASE \ 606 basic_branch<Key,Mapped, Tag, \ 607 typename PB_DS_TREE_NODE_AND_IT_TRAITS::node_update, \ 608 typename __gnu_cxx::typelist::create2<Cmp_Fn, \ 609 PB_DS_TREE_NODE_AND_IT_TRAITS>::type, _Alloc> 610 611 612 /** 613 * A tree-based container. 614 * 615 * @tparam Key Key type. 616 * @tparam Mapped Map type. 617 * @tparam Cmp_Fn Comparison functor. 618 * @tparam Tag Instantiating data structure type, 619 * see container_tag. 620 * @tparam Node_Update Updates tree internal-nodes, 621 * restores invariants when invalidated. 622 * XXX See design::tree-based-containers::node invariants. 623 * @tparam _Alloc Allocator type. 624 * 625 * Base tag choices are: ov_tree_tag, rb_tree_tag, splay_tree_tag. 626 * 627 * Base is basic_branch. 628 */ 629 template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>, 630 typename Tag = rb_tree_tag, 631 template<typename Node_CItr, typename Node_Itr, 632 typename Cmp_Fn_, typename _Alloc_> 633 class Node_Update = null_node_update, 634 typename _Alloc = std::allocator<char> > 635 class tree : public PB_DS_TREE_BASE 636 { 637 private: 638 typedef PB_DS_TREE_BASE base_type; 639 640 public: 641 /// Comparison functor type. 642 typedef Cmp_Fn cmp_fn; 643 644 tree() { } 645 646 /// Constructor taking some policy objects. r_cmp_fn will be 647 /// copied by the Cmp_Fn object of the container object. 648 tree(const cmp_fn& c) 649 : base_type(c) { } 650 651 /// Constructor taking __iterators to a range of value_types. The 652 /// value_types between first_it and last_it will be inserted into 653 /// the container object. 654 template<typename It> 655 tree(It first, It last) 656 { base_type::copy_from_range(first, last); } 657 658 /// Constructor taking __iterators to a range of value_types and 659 /// some policy objects The value_types between first_it and 660 /// last_it will be inserted into the container object. r_cmp_fn 661 /// will be copied by the cmp_fn object of the container object. 662 template<typename It> 663 tree(It first, It last, const cmp_fn& c) 664 : base_type(c) 665 { base_type::copy_from_range(first, last); } 666 667 tree(const tree& other) 668 : base_type((const base_type&)other) { } 669 670 virtual 671 ~tree() { } 672 673 tree& 674 operator=(const tree& other) 675 { 676 if (this != &other) 677 { 678 tree tmp(other); 679 swap(tmp); 680 } 681 return *this; 682 } 683 684 void 685 swap(tree& other) 686 { base_type::swap(other); } 687 }; 688 689#undef PB_DS_TREE_BASE 690#undef PB_DS_TREE_NODE_AND_IT_TRAITS 691 692 693#define PB_DS_TRIE_NODE_AND_IT_TRAITS \ 694 detail::trie_traits<Key,Mapped,_ATraits,Node_Update,Tag,_Alloc> 695 696#define PB_DS_TRIE_BASE \ 697 basic_branch<Key,Mapped,Tag, \ 698 typename PB_DS_TRIE_NODE_AND_IT_TRAITS::node_update, \ 699 typename __gnu_cxx::typelist::create2<_ATraits, \ 700 PB_DS_TRIE_NODE_AND_IT_TRAITS >::type, _Alloc> 701 702 703 /** 704 * A trie-based container. 705 * 706 * @tparam Key Key type. 707 * @tparam Mapped Map type. 708 * @tparam _ATraits Element access traits. 709 * @tparam Tag Instantiating data structure type, 710 * see container_tag. 711 * @tparam Node_Update Updates trie internal-nodes, 712 * restores invariants when invalidated. 713 * XXX See design::tree-based-containers::node invariants. 714 * @tparam _Alloc Allocator type. 715 * 716 * Base tag choice is pat_trie_tag. 717 * 718 * Base is basic_branch. 719 */ 720 template<typename Key, 721 typename Mapped, 722 typename _ATraits = \ 723 typename detail::default_trie_access_traits<Key>::type, 724 typename Tag = pat_trie_tag, 725 template<typename Node_CItr, 726 typename Node_Itr, 727 typename _ATraits_, 728 typename _Alloc_> 729 class Node_Update = null_node_update, 730 typename _Alloc = std::allocator<char> > 731 class trie : public PB_DS_TRIE_BASE 732 { 733 private: 734 typedef PB_DS_TRIE_BASE base_type; 735 736 public: 737 /// Element access traits type. 738 typedef _ATraits access_traits; 739 740 trie() { } 741 742 /// Constructor taking some policy objects. r_access_traits will 743 /// be copied by the _ATraits object of the container object. 744 trie(const access_traits& t) 745 : base_type(t) { } 746 747 /// Constructor taking __iterators to a range of value_types. The 748 /// value_types between first_it and last_it will be inserted into 749 /// the container object. 750 template<typename It> 751 trie(It first, It last) 752 { base_type::copy_from_range(first, last); } 753 754 /// Constructor taking __iterators to a range of value_types and 755 /// some policy objects. The value_types between first_it and 756 /// last_it will be inserted into the container object. 757 template<typename It> 758 trie(It first, It last, const access_traits& t) 759 : base_type(t) 760 { base_type::copy_from_range(first, last); } 761 762 trie(const trie& other) 763 : base_type((const base_type&)other) { } 764 765 virtual 766 ~trie() { } 767 768 trie& 769 operator=(const trie& other) 770 { 771 if (this != &other) 772 { 773 trie tmp(other); 774 swap(tmp); 775 } 776 return *this; 777 } 778 779 void 780 swap(trie& other) 781 { base_type::swap(other); } 782 }; 783 ///@} branch-based 784#undef PB_DS_TRIE_BASE 785#undef PB_DS_TRIE_NODE_AND_IT_TRAITS 786 787 788 /** 789 * @defgroup list-based List-Based 790 * @ingroup containers-pbds 791 * @{ 792 */ 793#define PB_DS_LU_BASE \ 794 detail::container_base_dispatch<Key, Mapped, _Alloc, list_update_tag, \ 795 typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type>::type 796 797 798 /** 799 * A list-update based associative container. 800 * 801 * @tparam Key Key type. 802 * @tparam Mapped Map type. 803 * @tparam Eq_Fn Equal functor. 804 * @tparam Update_Policy Update policy, determines when an element 805 * will be moved to the front of the list. 806 * @tparam _Alloc Allocator type. 807 * 808 * Base is detail::lu_map. 809 */ 810 template<typename Key, 811 typename Mapped, 812 class Eq_Fn = typename detail::default_eq_fn<Key>::type, 813 class Update_Policy = detail::default_update_policy::type, 814 class _Alloc = std::allocator<char> > 815 class list_update : public PB_DS_LU_BASE 816 { 817 private: 818 typedef typename PB_DS_LU_BASE base_type; 819 820 public: 821 typedef list_update_tag container_category; 822 typedef Eq_Fn eq_fn; 823 typedef Update_Policy update_policy; 824 825 list_update() { } 826 827 /// Constructor taking __iterators to a range of value_types. The 828 /// value_types between first_it and last_it will be inserted into 829 /// the container object. 830 template<typename It> 831 list_update(It first, It last) 832 { base_type::copy_from_range(first, last); } 833 834 list_update(const list_update& other) 835 : base_type((const base_type&)other) { } 836 837 virtual 838 ~list_update() { } 839 840 list_update& 841 operator=(const list_update& other) 842 { 843 if (this !=& other) 844 { 845 list_update tmp(other); 846 swap(tmp); 847 } 848 return *this; 849 } 850 851 void 852 swap(list_update& other) 853 { base_type::swap(other); } 854 }; 855 ///@} list-based 856#undef PB_DS_LU_BASE 857 858 /// @} group containers-pbds 859} // namespace __gnu_pbds 860 861#endif 862