1 // unordered_set implementation -*- C++ -*- 2 3 // Copyright (C) 2010-2016 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 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU 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 /** @file bits/unordered_set.h 26 * This is an internal header file, included by other library headers. 27 * Do not attempt to use it directly. @headername{unordered_set} 28 */ 29 30 #ifndef _UNORDERED_SET_H 31 #define _UNORDERED_SET_H 32 33 namespace std _GLIBCXX_VISIBILITY(default) 34 { 35 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 36 37 /// Base types for unordered_set. 38 template<bool _Cache> 39 using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>; 40 41 template<typename _Value, 42 typename _Hash = hash<_Value>, 43 typename _Pred = std::equal_to<_Value>, 44 typename _Alloc = std::allocator<_Value>, 45 typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value>> 46 using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc, 47 __detail::_Identity, _Pred, _Hash, 48 __detail::_Mod_range_hashing, 49 __detail::_Default_ranged_hash, 50 __detail::_Prime_rehash_policy, _Tr>; 51 52 /// Base types for unordered_multiset. 53 template<bool _Cache> 54 using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>; 55 56 template<typename _Value, 57 typename _Hash = hash<_Value>, 58 typename _Pred = std::equal_to<_Value>, 59 typename _Alloc = std::allocator<_Value>, 60 typename _Tr = __umset_traits<__cache_default<_Value, _Hash>::value>> 61 using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc, 62 __detail::_Identity, 63 _Pred, _Hash, 64 __detail::_Mod_range_hashing, 65 __detail::_Default_ranged_hash, 66 __detail::_Prime_rehash_policy, _Tr>; 67 68 /** 69 * @brief A standard container composed of unique keys (containing 70 * at most one of each key value) in which the elements' keys are 71 * the elements themselves. 72 * 73 * @ingroup unordered_associative_containers 74 * 75 * @tparam _Value Type of key objects. 76 * @tparam _Hash Hashing function object type, defaults to hash<_Value>. 77 78 * @tparam _Pred Predicate function object type, defaults to 79 * equal_to<_Value>. 80 * 81 * @tparam _Alloc Allocator type, defaults to allocator<_Key>. 82 * 83 * Meets the requirements of a <a href="tables.html#65">container</a>, and 84 * <a href="tables.html#xx">unordered associative container</a> 85 * 86 * Base is _Hashtable, dispatched at compile time via template 87 * alias __uset_hashtable. 88 */ 89 template<class _Value, 90 class _Hash = hash<_Value>, 91 class _Pred = std::equal_to<_Value>, 92 class _Alloc = std::allocator<_Value> > 93 class unordered_set 94 { 95 typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable; 96 _Hashtable _M_h; 97 98 public: 99 // typedefs: 100 //@{ 101 /// Public typedefs. 102 typedef typename _Hashtable::key_type key_type; 103 typedef typename _Hashtable::value_type value_type; 104 typedef typename _Hashtable::hasher hasher; 105 typedef typename _Hashtable::key_equal key_equal; 106 typedef typename _Hashtable::allocator_type allocator_type; 107 //@} 108 109 //@{ 110 /// Iterator-related typedefs. 111 typedef typename _Hashtable::pointer pointer; 112 typedef typename _Hashtable::const_pointer const_pointer; 113 typedef typename _Hashtable::reference reference; 114 typedef typename _Hashtable::const_reference const_reference; 115 typedef typename _Hashtable::iterator iterator; 116 typedef typename _Hashtable::const_iterator const_iterator; 117 typedef typename _Hashtable::local_iterator local_iterator; 118 typedef typename _Hashtable::const_local_iterator const_local_iterator; 119 typedef typename _Hashtable::size_type size_type; 120 typedef typename _Hashtable::difference_type difference_type; 121 //@} 122 123 // construct/destroy/copy 124 125 /// Default constructor. 126 unordered_set() = default; 127 128 /** 129 * @brief Default constructor creates no elements. 130 * @param __n Minimal initial number of buckets. 131 * @param __hf A hash functor. 132 * @param __eql A key equality functor. 133 * @param __a An allocator object. 134 */ 135 explicit 136 unordered_set(size_type __n, 137 const hasher& __hf = hasher(), 138 const key_equal& __eql = key_equal(), 139 const allocator_type& __a = allocator_type()) 140 : _M_h(__n, __hf, __eql, __a) 141 { } 142 143 /** 144 * @brief Builds an %unordered_set from a range. 145 * @param __first An input iterator. 146 * @param __last An input iterator. 147 * @param __n Minimal initial number of buckets. 148 * @param __hf A hash functor. 149 * @param __eql A key equality functor. 150 * @param __a An allocator object. 151 * 152 * Create an %unordered_set consisting of copies of the elements from 153 * [__first,__last). This is linear in N (where N is 154 * distance(__first,__last)). 155 */ 156 template<typename _InputIterator> 157 unordered_set(_InputIterator __first, _InputIterator __last, 158 size_type __n = 0, 159 const hasher& __hf = hasher(), 160 const key_equal& __eql = key_equal(), 161 const allocator_type& __a = allocator_type()) 162 : _M_h(__first, __last, __n, __hf, __eql, __a) 163 { } 164 165 /// Copy constructor. 166 unordered_set(const unordered_set&) = default; 167 168 /// Move constructor. 169 unordered_set(unordered_set&&) = default; 170 171 /** 172 * @brief Creates an %unordered_set with no elements. 173 * @param __a An allocator object. 174 */ 175 explicit 176 unordered_set(const allocator_type& __a) 177 : _M_h(__a) 178 { } 179 180 /* 181 * @brief Copy constructor with allocator argument. 182 * @param __uset Input %unordered_set to copy. 183 * @param __a An allocator object. 184 */ 185 unordered_set(const unordered_set& __uset, 186 const allocator_type& __a) 187 : _M_h(__uset._M_h, __a) 188 { } 189 190 /* 191 * @brief Move constructor with allocator argument. 192 * @param __uset Input %unordered_set to move. 193 * @param __a An allocator object. 194 */ 195 unordered_set(unordered_set&& __uset, 196 const allocator_type& __a) 197 : _M_h(std::move(__uset._M_h), __a) 198 { } 199 200 /** 201 * @brief Builds an %unordered_set from an initializer_list. 202 * @param __l An initializer_list. 203 * @param __n Minimal initial number of buckets. 204 * @param __hf A hash functor. 205 * @param __eql A key equality functor. 206 * @param __a An allocator object. 207 * 208 * Create an %unordered_set consisting of copies of the elements in the 209 * list. This is linear in N (where N is @a __l.size()). 210 */ 211 unordered_set(initializer_list<value_type> __l, 212 size_type __n = 0, 213 const hasher& __hf = hasher(), 214 const key_equal& __eql = key_equal(), 215 const allocator_type& __a = allocator_type()) 216 : _M_h(__l, __n, __hf, __eql, __a) 217 { } 218 219 unordered_set(size_type __n, const allocator_type& __a) 220 : unordered_set(__n, hasher(), key_equal(), __a) 221 { } 222 223 unordered_set(size_type __n, const hasher& __hf, 224 const allocator_type& __a) 225 : unordered_set(__n, __hf, key_equal(), __a) 226 { } 227 228 template<typename _InputIterator> 229 unordered_set(_InputIterator __first, _InputIterator __last, 230 size_type __n, 231 const allocator_type& __a) 232 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) 233 { } 234 235 template<typename _InputIterator> 236 unordered_set(_InputIterator __first, _InputIterator __last, 237 size_type __n, const hasher& __hf, 238 const allocator_type& __a) 239 : unordered_set(__first, __last, __n, __hf, key_equal(), __a) 240 { } 241 242 unordered_set(initializer_list<value_type> __l, 243 size_type __n, 244 const allocator_type& __a) 245 : unordered_set(__l, __n, hasher(), key_equal(), __a) 246 { } 247 248 unordered_set(initializer_list<value_type> __l, 249 size_type __n, const hasher& __hf, 250 const allocator_type& __a) 251 : unordered_set(__l, __n, __hf, key_equal(), __a) 252 { } 253 254 /// Copy assignment operator. 255 unordered_set& 256 operator=(const unordered_set&) = default; 257 258 /// Move assignment operator. 259 unordered_set& 260 operator=(unordered_set&&) = default; 261 262 /** 263 * @brief %Unordered_set list assignment operator. 264 * @param __l An initializer_list. 265 * 266 * This function fills an %unordered_set with copies of the elements in 267 * the initializer list @a __l. 268 * 269 * Note that the assignment completely changes the %unordered_set and 270 * that the resulting %unordered_set's size is the same as the number 271 * of elements assigned. Old data may be lost. 272 */ 273 unordered_set& 274 operator=(initializer_list<value_type> __l) 275 { 276 _M_h = __l; 277 return *this; 278 } 279 280 /// Returns the allocator object with which the %unordered_set was 281 /// constructed. 282 allocator_type 283 get_allocator() const noexcept 284 { return _M_h.get_allocator(); } 285 286 // size and capacity: 287 288 /// Returns true if the %unordered_set is empty. 289 bool 290 empty() const noexcept 291 { return _M_h.empty(); } 292 293 /// Returns the size of the %unordered_set. 294 size_type 295 size() const noexcept 296 { return _M_h.size(); } 297 298 /// Returns the maximum size of the %unordered_set. 299 size_type 300 max_size() const noexcept 301 { return _M_h.max_size(); } 302 303 // iterators. 304 305 //@{ 306 /** 307 * Returns a read-only (constant) iterator that points to the first 308 * element in the %unordered_set. 309 */ 310 iterator 311 begin() noexcept 312 { return _M_h.begin(); } 313 314 const_iterator 315 begin() const noexcept 316 { return _M_h.begin(); } 317 //@} 318 319 //@{ 320 /** 321 * Returns a read-only (constant) iterator that points one past the last 322 * element in the %unordered_set. 323 */ 324 iterator 325 end() noexcept 326 { return _M_h.end(); } 327 328 const_iterator 329 end() const noexcept 330 { return _M_h.end(); } 331 //@} 332 333 /** 334 * Returns a read-only (constant) iterator that points to the first 335 * element in the %unordered_set. 336 */ 337 const_iterator 338 cbegin() const noexcept 339 { return _M_h.begin(); } 340 341 /** 342 * Returns a read-only (constant) iterator that points one past the last 343 * element in the %unordered_set. 344 */ 345 const_iterator 346 cend() const noexcept 347 { return _M_h.end(); } 348 349 // modifiers. 350 351 /** 352 * @brief Attempts to build and insert an element into the 353 * %unordered_set. 354 * @param __args Arguments used to generate an element. 355 * @return A pair, of which the first element is an iterator that points 356 * to the possibly inserted element, and the second is a bool 357 * that is true if the element was actually inserted. 358 * 359 * This function attempts to build and insert an element into the 360 * %unordered_set. An %unordered_set relies on unique keys and thus an 361 * element is only inserted if it is not already present in the 362 * %unordered_set. 363 * 364 * Insertion requires amortized constant time. 365 */ 366 template<typename... _Args> 367 std::pair<iterator, bool> 368 emplace(_Args&&... __args) 369 { return _M_h.emplace(std::forward<_Args>(__args)...); } 370 371 /** 372 * @brief Attempts to insert an element into the %unordered_set. 373 * @param __pos An iterator that serves as a hint as to where the 374 * element should be inserted. 375 * @param __args Arguments used to generate the element to be 376 * inserted. 377 * @return An iterator that points to the element with key equivalent to 378 * the one generated from @a __args (may or may not be the 379 * element itself). 380 * 381 * This function is not concerned about whether the insertion took place, 382 * and thus does not return a boolean like the single-argument emplace() 383 * does. Note that the first parameter is only a hint and can 384 * potentially improve the performance of the insertion process. A bad 385 * hint would cause no gains in efficiency. 386 * 387 * For more on @a hinting, see: 388 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 389 * 390 * Insertion requires amortized constant time. 391 */ 392 template<typename... _Args> 393 iterator 394 emplace_hint(const_iterator __pos, _Args&&... __args) 395 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); } 396 397 //@{ 398 /** 399 * @brief Attempts to insert an element into the %unordered_set. 400 * @param __x Element to be inserted. 401 * @return A pair, of which the first element is an iterator that points 402 * to the possibly inserted element, and the second is a bool 403 * that is true if the element was actually inserted. 404 * 405 * This function attempts to insert an element into the %unordered_set. 406 * An %unordered_set relies on unique keys and thus an element is only 407 * inserted if it is not already present in the %unordered_set. 408 * 409 * Insertion requires amortized constant time. 410 */ 411 std::pair<iterator, bool> 412 insert(const value_type& __x) 413 { return _M_h.insert(__x); } 414 415 std::pair<iterator, bool> 416 insert(value_type&& __x) 417 { return _M_h.insert(std::move(__x)); } 418 //@} 419 420 //@{ 421 /** 422 * @brief Attempts to insert an element into the %unordered_set. 423 * @param __hint An iterator that serves as a hint as to where the 424 * element should be inserted. 425 * @param __x Element to be inserted. 426 * @return An iterator that points to the element with key of 427 * @a __x (may or may not be the element passed in). 428 * 429 * This function is not concerned about whether the insertion took place, 430 * and thus does not return a boolean like the single-argument insert() 431 * does. Note that the first parameter is only a hint and can 432 * potentially improve the performance of the insertion process. A bad 433 * hint would cause no gains in efficiency. 434 * 435 * For more on @a hinting, see: 436 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 437 * 438 * Insertion requires amortized constant. 439 */ 440 iterator 441 insert(const_iterator __hint, const value_type& __x) 442 { return _M_h.insert(__hint, __x); } 443 444 iterator 445 insert(const_iterator __hint, value_type&& __x) 446 { return _M_h.insert(__hint, std::move(__x)); } 447 //@} 448 449 /** 450 * @brief A template function that attempts to insert a range of 451 * elements. 452 * @param __first Iterator pointing to the start of the range to be 453 * inserted. 454 * @param __last Iterator pointing to the end of the range. 455 * 456 * Complexity similar to that of the range constructor. 457 */ 458 template<typename _InputIterator> 459 void 460 insert(_InputIterator __first, _InputIterator __last) 461 { _M_h.insert(__first, __last); } 462 463 /** 464 * @brief Attempts to insert a list of elements into the %unordered_set. 465 * @param __l A std::initializer_list<value_type> of elements 466 * to be inserted. 467 * 468 * Complexity similar to that of the range constructor. 469 */ 470 void 471 insert(initializer_list<value_type> __l) 472 { _M_h.insert(__l); } 473 474 //@{ 475 /** 476 * @brief Erases an element from an %unordered_set. 477 * @param __position An iterator pointing to the element to be erased. 478 * @return An iterator pointing to the element immediately following 479 * @a __position prior to the element being erased. If no such 480 * element exists, end() is returned. 481 * 482 * This function erases an element, pointed to by the given iterator, 483 * from an %unordered_set. Note that this function only erases the 484 * element, and that if the element is itself a pointer, the pointed-to 485 * memory is not touched in any way. Managing the pointer is the user's 486 * responsibility. 487 */ 488 iterator 489 erase(const_iterator __position) 490 { return _M_h.erase(__position); } 491 492 // LWG 2059. 493 iterator 494 erase(iterator __position) 495 { return _M_h.erase(__position); } 496 //@} 497 498 /** 499 * @brief Erases elements according to the provided key. 500 * @param __x Key of element to be erased. 501 * @return The number of elements erased. 502 * 503 * This function erases all the elements located by the given key from 504 * an %unordered_set. For an %unordered_set the result of this function 505 * can only be 0 (not present) or 1 (present). 506 * Note that this function only erases the element, and that if 507 * the element is itself a pointer, the pointed-to memory is not touched 508 * in any way. Managing the pointer is the user's responsibility. 509 */ 510 size_type 511 erase(const key_type& __x) 512 { return _M_h.erase(__x); } 513 514 /** 515 * @brief Erases a [__first,__last) range of elements from an 516 * %unordered_set. 517 * @param __first Iterator pointing to the start of the range to be 518 * erased. 519 * @param __last Iterator pointing to the end of the range to 520 * be erased. 521 * @return The iterator @a __last. 522 * 523 * This function erases a sequence of elements from an %unordered_set. 524 * Note that this function only erases the element, and that if 525 * the element is itself a pointer, the pointed-to memory is not touched 526 * in any way. Managing the pointer is the user's responsibility. 527 */ 528 iterator 529 erase(const_iterator __first, const_iterator __last) 530 { return _M_h.erase(__first, __last); } 531 532 /** 533 * Erases all elements in an %unordered_set. Note that this function only 534 * erases the elements, and that if the elements themselves are pointers, 535 * the pointed-to memory is not touched in any way. Managing the pointer 536 * is the user's responsibility. 537 */ 538 void 539 clear() noexcept 540 { _M_h.clear(); } 541 542 /** 543 * @brief Swaps data with another %unordered_set. 544 * @param __x An %unordered_set of the same element and allocator 545 * types. 546 * 547 * This exchanges the elements between two sets in constant time. 548 * Note that the global std::swap() function is specialized such that 549 * std::swap(s1,s2) will feed to this function. 550 */ 551 void 552 swap(unordered_set& __x) 553 noexcept( noexcept(_M_h.swap(__x._M_h)) ) 554 { _M_h.swap(__x._M_h); } 555 556 // observers. 557 558 /// Returns the hash functor object with which the %unordered_set was 559 /// constructed. 560 hasher 561 hash_function() const 562 { return _M_h.hash_function(); } 563 564 /// Returns the key comparison object with which the %unordered_set was 565 /// constructed. 566 key_equal 567 key_eq() const 568 { return _M_h.key_eq(); } 569 570 // lookup. 571 572 //@{ 573 /** 574 * @brief Tries to locate an element in an %unordered_set. 575 * @param __x Element to be located. 576 * @return Iterator pointing to sought-after element, or end() if not 577 * found. 578 * 579 * This function takes a key and tries to locate the element with which 580 * the key matches. If successful the function returns an iterator 581 * pointing to the sought after element. If unsuccessful it returns the 582 * past-the-end ( @c end() ) iterator. 583 */ 584 iterator 585 find(const key_type& __x) 586 { return _M_h.find(__x); } 587 588 const_iterator 589 find(const key_type& __x) const 590 { return _M_h.find(__x); } 591 //@} 592 593 /** 594 * @brief Finds the number of elements. 595 * @param __x Element to located. 596 * @return Number of elements with specified key. 597 * 598 * This function only makes sense for unordered_multisets; for 599 * unordered_set the result will either be 0 (not present) or 1 600 * (present). 601 */ 602 size_type 603 count(const key_type& __x) const 604 { return _M_h.count(__x); } 605 606 //@{ 607 /** 608 * @brief Finds a subsequence matching given key. 609 * @param __x Key to be located. 610 * @return Pair of iterators that possibly points to the subsequence 611 * matching given key. 612 * 613 * This function probably only makes sense for multisets. 614 */ 615 std::pair<iterator, iterator> 616 equal_range(const key_type& __x) 617 { return _M_h.equal_range(__x); } 618 619 std::pair<const_iterator, const_iterator> 620 equal_range(const key_type& __x) const 621 { return _M_h.equal_range(__x); } 622 //@} 623 624 // bucket interface. 625 626 /// Returns the number of buckets of the %unordered_set. 627 size_type 628 bucket_count() const noexcept 629 { return _M_h.bucket_count(); } 630 631 /// Returns the maximum number of buckets of the %unordered_set. 632 size_type 633 max_bucket_count() const noexcept 634 { return _M_h.max_bucket_count(); } 635 636 /* 637 * @brief Returns the number of elements in a given bucket. 638 * @param __n A bucket index. 639 * @return The number of elements in the bucket. 640 */ 641 size_type 642 bucket_size(size_type __n) const 643 { return _M_h.bucket_size(__n); } 644 645 /* 646 * @brief Returns the bucket index of a given element. 647 * @param __key A key instance. 648 * @return The key bucket index. 649 */ 650 size_type 651 bucket(const key_type& __key) const 652 { return _M_h.bucket(__key); } 653 654 //@{ 655 /** 656 * @brief Returns a read-only (constant) iterator pointing to the first 657 * bucket element. 658 * @param __n The bucket index. 659 * @return A read-only local iterator. 660 */ 661 local_iterator 662 begin(size_type __n) 663 { return _M_h.begin(__n); } 664 665 const_local_iterator 666 begin(size_type __n) const 667 { return _M_h.begin(__n); } 668 669 const_local_iterator 670 cbegin(size_type __n) const 671 { return _M_h.cbegin(__n); } 672 //@} 673 674 //@{ 675 /** 676 * @brief Returns a read-only (constant) iterator pointing to one past 677 * the last bucket elements. 678 * @param __n The bucket index. 679 * @return A read-only local iterator. 680 */ 681 local_iterator 682 end(size_type __n) 683 { return _M_h.end(__n); } 684 685 const_local_iterator 686 end(size_type __n) const 687 { return _M_h.end(__n); } 688 689 const_local_iterator 690 cend(size_type __n) const 691 { return _M_h.cend(__n); } 692 //@} 693 694 // hash policy. 695 696 /// Returns the average number of elements per bucket. 697 float 698 load_factor() const noexcept 699 { return _M_h.load_factor(); } 700 701 /// Returns a positive number that the %unordered_set tries to keep the 702 /// load factor less than or equal to. 703 float 704 max_load_factor() const noexcept 705 { return _M_h.max_load_factor(); } 706 707 /** 708 * @brief Change the %unordered_set maximum load factor. 709 * @param __z The new maximum load factor. 710 */ 711 void 712 max_load_factor(float __z) 713 { _M_h.max_load_factor(__z); } 714 715 /** 716 * @brief May rehash the %unordered_set. 717 * @param __n The new number of buckets. 718 * 719 * Rehash will occur only if the new number of buckets respect the 720 * %unordered_set maximum load factor. 721 */ 722 void 723 rehash(size_type __n) 724 { _M_h.rehash(__n); } 725 726 /** 727 * @brief Prepare the %unordered_set for a specified number of 728 * elements. 729 * @param __n Number of elements required. 730 * 731 * Same as rehash(ceil(n / max_load_factor())). 732 */ 733 void 734 reserve(size_type __n) 735 { _M_h.reserve(__n); } 736 737 template<typename _Value1, typename _Hash1, typename _Pred1, 738 typename _Alloc1> 739 friend bool 740 operator==(const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&, 741 const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&); 742 }; 743 744 /** 745 * @brief A standard container composed of equivalent keys 746 * (possibly containing multiple of each key value) in which the 747 * elements' keys are the elements themselves. 748 * 749 * @ingroup unordered_associative_containers 750 * 751 * @tparam _Value Type of key objects. 752 * @tparam _Hash Hashing function object type, defaults to hash<_Value>. 753 * @tparam _Pred Predicate function object type, defaults 754 * to equal_to<_Value>. 755 * @tparam _Alloc Allocator type, defaults to allocator<_Key>. 756 * 757 * Meets the requirements of a <a href="tables.html#65">container</a>, and 758 * <a href="tables.html#xx">unordered associative container</a> 759 * 760 * Base is _Hashtable, dispatched at compile time via template 761 * alias __umset_hashtable. 762 */ 763 template<class _Value, 764 class _Hash = hash<_Value>, 765 class _Pred = std::equal_to<_Value>, 766 class _Alloc = std::allocator<_Value> > 767 class unordered_multiset 768 { 769 typedef __umset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable; 770 _Hashtable _M_h; 771 772 public: 773 // typedefs: 774 //@{ 775 /// Public typedefs. 776 typedef typename _Hashtable::key_type key_type; 777 typedef typename _Hashtable::value_type value_type; 778 typedef typename _Hashtable::hasher hasher; 779 typedef typename _Hashtable::key_equal key_equal; 780 typedef typename _Hashtable::allocator_type allocator_type; 781 //@} 782 783 //@{ 784 /// Iterator-related typedefs. 785 typedef typename _Hashtable::pointer pointer; 786 typedef typename _Hashtable::const_pointer const_pointer; 787 typedef typename _Hashtable::reference reference; 788 typedef typename _Hashtable::const_reference const_reference; 789 typedef typename _Hashtable::iterator iterator; 790 typedef typename _Hashtable::const_iterator const_iterator; 791 typedef typename _Hashtable::local_iterator local_iterator; 792 typedef typename _Hashtable::const_local_iterator const_local_iterator; 793 typedef typename _Hashtable::size_type size_type; 794 typedef typename _Hashtable::difference_type difference_type; 795 //@} 796 797 // construct/destroy/copy 798 799 /// Default constructor. 800 unordered_multiset() = default; 801 802 /** 803 * @brief Default constructor creates no elements. 804 * @param __n Minimal initial number of buckets. 805 * @param __hf A hash functor. 806 * @param __eql A key equality functor. 807 * @param __a An allocator object. 808 */ 809 explicit 810 unordered_multiset(size_type __n, 811 const hasher& __hf = hasher(), 812 const key_equal& __eql = key_equal(), 813 const allocator_type& __a = allocator_type()) 814 : _M_h(__n, __hf, __eql, __a) 815 { } 816 817 /** 818 * @brief Builds an %unordered_multiset from a range. 819 * @param __first An input iterator. 820 * @param __last An input iterator. 821 * @param __n Minimal initial number of buckets. 822 * @param __hf A hash functor. 823 * @param __eql A key equality functor. 824 * @param __a An allocator object. 825 * 826 * Create an %unordered_multiset consisting of copies of the elements 827 * from [__first,__last). This is linear in N (where N is 828 * distance(__first,__last)). 829 */ 830 template<typename _InputIterator> 831 unordered_multiset(_InputIterator __first, _InputIterator __last, 832 size_type __n = 0, 833 const hasher& __hf = hasher(), 834 const key_equal& __eql = key_equal(), 835 const allocator_type& __a = allocator_type()) 836 : _M_h(__first, __last, __n, __hf, __eql, __a) 837 { } 838 839 /// Copy constructor. 840 unordered_multiset(const unordered_multiset&) = default; 841 842 /// Move constructor. 843 unordered_multiset(unordered_multiset&&) = default; 844 845 /** 846 * @brief Builds an %unordered_multiset from an initializer_list. 847 * @param __l An initializer_list. 848 * @param __n Minimal initial number of buckets. 849 * @param __hf A hash functor. 850 * @param __eql A key equality functor. 851 * @param __a An allocator object. 852 * 853 * Create an %unordered_multiset consisting of copies of the elements in 854 * the list. This is linear in N (where N is @a __l.size()). 855 */ 856 unordered_multiset(initializer_list<value_type> __l, 857 size_type __n = 0, 858 const hasher& __hf = hasher(), 859 const key_equal& __eql = key_equal(), 860 const allocator_type& __a = allocator_type()) 861 : _M_h(__l, __n, __hf, __eql, __a) 862 { } 863 864 /// Copy assignment operator. 865 unordered_multiset& 866 operator=(const unordered_multiset&) = default; 867 868 /// Move assignment operator. 869 unordered_multiset& 870 operator=(unordered_multiset&&) = default; 871 872 /** 873 * @brief Creates an %unordered_multiset with no elements. 874 * @param __a An allocator object. 875 */ 876 explicit 877 unordered_multiset(const allocator_type& __a) 878 : _M_h(__a) 879 { } 880 881 /* 882 * @brief Copy constructor with allocator argument. 883 * @param __uset Input %unordered_multiset to copy. 884 * @param __a An allocator object. 885 */ 886 unordered_multiset(const unordered_multiset& __umset, 887 const allocator_type& __a) 888 : _M_h(__umset._M_h, __a) 889 { } 890 891 /* 892 * @brief Move constructor with allocator argument. 893 * @param __umset Input %unordered_multiset to move. 894 * @param __a An allocator object. 895 */ 896 unordered_multiset(unordered_multiset&& __umset, 897 const allocator_type& __a) 898 : _M_h(std::move(__umset._M_h), __a) 899 { } 900 901 unordered_multiset(size_type __n, const allocator_type& __a) 902 : unordered_multiset(__n, hasher(), key_equal(), __a) 903 { } 904 905 unordered_multiset(size_type __n, const hasher& __hf, 906 const allocator_type& __a) 907 : unordered_multiset(__n, __hf, key_equal(), __a) 908 { } 909 910 template<typename _InputIterator> 911 unordered_multiset(_InputIterator __first, _InputIterator __last, 912 size_type __n, 913 const allocator_type& __a) 914 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) 915 { } 916 917 template<typename _InputIterator> 918 unordered_multiset(_InputIterator __first, _InputIterator __last, 919 size_type __n, const hasher& __hf, 920 const allocator_type& __a) 921 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) 922 { } 923 924 unordered_multiset(initializer_list<value_type> __l, 925 size_type __n, 926 const allocator_type& __a) 927 : unordered_multiset(__l, __n, hasher(), key_equal(), __a) 928 { } 929 930 unordered_multiset(initializer_list<value_type> __l, 931 size_type __n, const hasher& __hf, 932 const allocator_type& __a) 933 : unordered_multiset(__l, __n, __hf, key_equal(), __a) 934 { } 935 936 /** 937 * @brief %Unordered_multiset list assignment operator. 938 * @param __l An initializer_list. 939 * 940 * This function fills an %unordered_multiset with copies of the elements 941 * in the initializer list @a __l. 942 * 943 * Note that the assignment completely changes the %unordered_multiset 944 * and that the resulting %unordered_multiset's size is the same as the 945 * number of elements assigned. Old data may be lost. 946 */ 947 unordered_multiset& 948 operator=(initializer_list<value_type> __l) 949 { 950 _M_h = __l; 951 return *this; 952 } 953 954 /// Returns the allocator object with which the %unordered_multiset was 955 /// constructed. 956 allocator_type 957 get_allocator() const noexcept 958 { return _M_h.get_allocator(); } 959 960 // size and capacity: 961 962 /// Returns true if the %unordered_multiset is empty. 963 bool 964 empty() const noexcept 965 { return _M_h.empty(); } 966 967 /// Returns the size of the %unordered_multiset. 968 size_type 969 size() const noexcept 970 { return _M_h.size(); } 971 972 /// Returns the maximum size of the %unordered_multiset. 973 size_type 974 max_size() const noexcept 975 { return _M_h.max_size(); } 976 977 // iterators. 978 979 //@{ 980 /** 981 * Returns a read-only (constant) iterator that points to the first 982 * element in the %unordered_multiset. 983 */ 984 iterator 985 begin() noexcept 986 { return _M_h.begin(); } 987 988 const_iterator 989 begin() const noexcept 990 { return _M_h.begin(); } 991 //@} 992 993 //@{ 994 /** 995 * Returns a read-only (constant) iterator that points one past the last 996 * element in the %unordered_multiset. 997 */ 998 iterator 999 end() noexcept 1000 { return _M_h.end(); } 1001 1002 const_iterator 1003 end() const noexcept 1004 { return _M_h.end(); } 1005 //@} 1006 1007 /** 1008 * Returns a read-only (constant) iterator that points to the first 1009 * element in the %unordered_multiset. 1010 */ 1011 const_iterator 1012 cbegin() const noexcept 1013 { return _M_h.begin(); } 1014 1015 /** 1016 * Returns a read-only (constant) iterator that points one past the last 1017 * element in the %unordered_multiset. 1018 */ 1019 const_iterator 1020 cend() const noexcept 1021 { return _M_h.end(); } 1022 1023 // modifiers. 1024 1025 /** 1026 * @brief Builds and insert an element into the %unordered_multiset. 1027 * @param __args Arguments used to generate an element. 1028 * @return An iterator that points to the inserted element. 1029 * 1030 * Insertion requires amortized constant time. 1031 */ 1032 template<typename... _Args> 1033 iterator 1034 emplace(_Args&&... __args) 1035 { return _M_h.emplace(std::forward<_Args>(__args)...); } 1036 1037 /** 1038 * @brief Inserts an element into the %unordered_multiset. 1039 * @param __pos An iterator that serves as a hint as to where the 1040 * element should be inserted. 1041 * @param __args Arguments used to generate the element to be 1042 * inserted. 1043 * @return An iterator that points to the inserted element. 1044 * 1045 * Note that the first parameter is only a hint and can potentially 1046 * improve the performance of the insertion process. A bad hint would 1047 * cause no gains in efficiency. 1048 * 1049 * For more on @a hinting, see: 1050 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 1051 * 1052 * Insertion requires amortized constant time. 1053 */ 1054 template<typename... _Args> 1055 iterator 1056 emplace_hint(const_iterator __pos, _Args&&... __args) 1057 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); } 1058 1059 //@{ 1060 /** 1061 * @brief Inserts an element into the %unordered_multiset. 1062 * @param __x Element to be inserted. 1063 * @return An iterator that points to the inserted element. 1064 * 1065 * Insertion requires amortized constant time. 1066 */ 1067 iterator 1068 insert(const value_type& __x) 1069 { return _M_h.insert(__x); } 1070 1071 iterator 1072 insert(value_type&& __x) 1073 { return _M_h.insert(std::move(__x)); } 1074 //@} 1075 1076 //@{ 1077 /** 1078 * @brief Inserts an element into the %unordered_multiset. 1079 * @param __hint An iterator that serves as a hint as to where the 1080 * element should be inserted. 1081 * @param __x Element to be inserted. 1082 * @return An iterator that points to the inserted element. 1083 * 1084 * Note that the first parameter is only a hint and can potentially 1085 * improve the performance of the insertion process. A bad hint would 1086 * cause no gains in efficiency. 1087 * 1088 * For more on @a hinting, see: 1089 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 1090 * 1091 * Insertion requires amortized constant. 1092 */ 1093 iterator 1094 insert(const_iterator __hint, const value_type& __x) 1095 { return _M_h.insert(__hint, __x); } 1096 1097 iterator 1098 insert(const_iterator __hint, value_type&& __x) 1099 { return _M_h.insert(__hint, std::move(__x)); } 1100 //@} 1101 1102 /** 1103 * @brief A template function that inserts a range of elements. 1104 * @param __first Iterator pointing to the start of the range to be 1105 * inserted. 1106 * @param __last Iterator pointing to the end of the range. 1107 * 1108 * Complexity similar to that of the range constructor. 1109 */ 1110 template<typename _InputIterator> 1111 void 1112 insert(_InputIterator __first, _InputIterator __last) 1113 { _M_h.insert(__first, __last); } 1114 1115 /** 1116 * @brief Inserts a list of elements into the %unordered_multiset. 1117 * @param __l A std::initializer_list<value_type> of elements to be 1118 * inserted. 1119 * 1120 * Complexity similar to that of the range constructor. 1121 */ 1122 void 1123 insert(initializer_list<value_type> __l) 1124 { _M_h.insert(__l); } 1125 1126 //@{ 1127 /** 1128 * @brief Erases an element from an %unordered_multiset. 1129 * @param __position An iterator pointing to the element to be erased. 1130 * @return An iterator pointing to the element immediately following 1131 * @a __position prior to the element being erased. If no such 1132 * element exists, end() is returned. 1133 * 1134 * This function erases an element, pointed to by the given iterator, 1135 * from an %unordered_multiset. 1136 * 1137 * Note that this function only erases the element, and that if the 1138 * element is itself a pointer, the pointed-to memory is not touched in 1139 * any way. Managing the pointer is the user's responsibility. 1140 */ 1141 iterator 1142 erase(const_iterator __position) 1143 { return _M_h.erase(__position); } 1144 1145 // LWG 2059. 1146 iterator 1147 erase(iterator __position) 1148 { return _M_h.erase(__position); } 1149 //@} 1150 1151 1152 /** 1153 * @brief Erases elements according to the provided key. 1154 * @param __x Key of element to be erased. 1155 * @return The number of elements erased. 1156 * 1157 * This function erases all the elements located by the given key from 1158 * an %unordered_multiset. 1159 * 1160 * Note that this function only erases the element, and that if the 1161 * element is itself a pointer, the pointed-to memory is not touched in 1162 * any way. Managing the pointer is the user's responsibility. 1163 */ 1164 size_type 1165 erase(const key_type& __x) 1166 { return _M_h.erase(__x); } 1167 1168 /** 1169 * @brief Erases a [__first,__last) range of elements from an 1170 * %unordered_multiset. 1171 * @param __first Iterator pointing to the start of the range to be 1172 * erased. 1173 * @param __last Iterator pointing to the end of the range to 1174 * be erased. 1175 * @return The iterator @a __last. 1176 * 1177 * This function erases a sequence of elements from an 1178 * %unordered_multiset. 1179 * 1180 * Note that this function only erases the element, and that if 1181 * the element is itself a pointer, the pointed-to memory is not touched 1182 * in any way. Managing the pointer is the user's responsibility. 1183 */ 1184 iterator 1185 erase(const_iterator __first, const_iterator __last) 1186 { return _M_h.erase(__first, __last); } 1187 1188 /** 1189 * Erases all elements in an %unordered_multiset. 1190 * 1191 * Note that this function only erases the elements, and that if the 1192 * elements themselves are pointers, the pointed-to memory is not touched 1193 * in any way. Managing the pointer is the user's responsibility. 1194 */ 1195 void 1196 clear() noexcept 1197 { _M_h.clear(); } 1198 1199 /** 1200 * @brief Swaps data with another %unordered_multiset. 1201 * @param __x An %unordered_multiset of the same element and allocator 1202 * types. 1203 * 1204 * This exchanges the elements between two sets in constant time. 1205 * Note that the global std::swap() function is specialized such that 1206 * std::swap(s1,s2) will feed to this function. 1207 */ 1208 void 1209 swap(unordered_multiset& __x) 1210 noexcept( noexcept(_M_h.swap(__x._M_h)) ) 1211 { _M_h.swap(__x._M_h); } 1212 1213 // observers. 1214 1215 /// Returns the hash functor object with which the %unordered_multiset 1216 /// was constructed. 1217 hasher 1218 hash_function() const 1219 { return _M_h.hash_function(); } 1220 1221 /// Returns the key comparison object with which the %unordered_multiset 1222 /// was constructed. 1223 key_equal 1224 key_eq() const 1225 { return _M_h.key_eq(); } 1226 1227 // lookup. 1228 1229 //@{ 1230 /** 1231 * @brief Tries to locate an element in an %unordered_multiset. 1232 * @param __x Element to be located. 1233 * @return Iterator pointing to sought-after element, or end() if not 1234 * found. 1235 * 1236 * This function takes a key and tries to locate the element with which 1237 * the key matches. If successful the function returns an iterator 1238 * pointing to the sought after element. If unsuccessful it returns the 1239 * past-the-end ( @c end() ) iterator. 1240 */ 1241 iterator 1242 find(const key_type& __x) 1243 { return _M_h.find(__x); } 1244 1245 const_iterator 1246 find(const key_type& __x) const 1247 { return _M_h.find(__x); } 1248 //@} 1249 1250 /** 1251 * @brief Finds the number of elements. 1252 * @param __x Element to located. 1253 * @return Number of elements with specified key. 1254 */ 1255 size_type 1256 count(const key_type& __x) const 1257 { return _M_h.count(__x); } 1258 1259 //@{ 1260 /** 1261 * @brief Finds a subsequence matching given key. 1262 * @param __x Key to be located. 1263 * @return Pair of iterators that possibly points to the subsequence 1264 * matching given key. 1265 */ 1266 std::pair<iterator, iterator> 1267 equal_range(const key_type& __x) 1268 { return _M_h.equal_range(__x); } 1269 1270 std::pair<const_iterator, const_iterator> 1271 equal_range(const key_type& __x) const 1272 { return _M_h.equal_range(__x); } 1273 //@} 1274 1275 // bucket interface. 1276 1277 /// Returns the number of buckets of the %unordered_multiset. 1278 size_type 1279 bucket_count() const noexcept 1280 { return _M_h.bucket_count(); } 1281 1282 /// Returns the maximum number of buckets of the %unordered_multiset. 1283 size_type 1284 max_bucket_count() const noexcept 1285 { return _M_h.max_bucket_count(); } 1286 1287 /* 1288 * @brief Returns the number of elements in a given bucket. 1289 * @param __n A bucket index. 1290 * @return The number of elements in the bucket. 1291 */ 1292 size_type 1293 bucket_size(size_type __n) const 1294 { return _M_h.bucket_size(__n); } 1295 1296 /* 1297 * @brief Returns the bucket index of a given element. 1298 * @param __key A key instance. 1299 * @return The key bucket index. 1300 */ 1301 size_type 1302 bucket(const key_type& __key) const 1303 { return _M_h.bucket(__key); } 1304 1305 //@{ 1306 /** 1307 * @brief Returns a read-only (constant) iterator pointing to the first 1308 * bucket element. 1309 * @param __n The bucket index. 1310 * @return A read-only local iterator. 1311 */ 1312 local_iterator 1313 begin(size_type __n) 1314 { return _M_h.begin(__n); } 1315 1316 const_local_iterator 1317 begin(size_type __n) const 1318 { return _M_h.begin(__n); } 1319 1320 const_local_iterator 1321 cbegin(size_type __n) const 1322 { return _M_h.cbegin(__n); } 1323 //@} 1324 1325 //@{ 1326 /** 1327 * @brief Returns a read-only (constant) iterator pointing to one past 1328 * the last bucket elements. 1329 * @param __n The bucket index. 1330 * @return A read-only local iterator. 1331 */ 1332 local_iterator 1333 end(size_type __n) 1334 { return _M_h.end(__n); } 1335 1336 const_local_iterator 1337 end(size_type __n) const 1338 { return _M_h.end(__n); } 1339 1340 const_local_iterator 1341 cend(size_type __n) const 1342 { return _M_h.cend(__n); } 1343 //@} 1344 1345 // hash policy. 1346 1347 /// Returns the average number of elements per bucket. 1348 float 1349 load_factor() const noexcept 1350 { return _M_h.load_factor(); } 1351 1352 /// Returns a positive number that the %unordered_multiset tries to keep the 1353 /// load factor less than or equal to. 1354 float 1355 max_load_factor() const noexcept 1356 { return _M_h.max_load_factor(); } 1357 1358 /** 1359 * @brief Change the %unordered_multiset maximum load factor. 1360 * @param __z The new maximum load factor. 1361 */ 1362 void 1363 max_load_factor(float __z) 1364 { _M_h.max_load_factor(__z); } 1365 1366 /** 1367 * @brief May rehash the %unordered_multiset. 1368 * @param __n The new number of buckets. 1369 * 1370 * Rehash will occur only if the new number of buckets respect the 1371 * %unordered_multiset maximum load factor. 1372 */ 1373 void 1374 rehash(size_type __n) 1375 { _M_h.rehash(__n); } 1376 1377 /** 1378 * @brief Prepare the %unordered_multiset for a specified number of 1379 * elements. 1380 * @param __n Number of elements required. 1381 * 1382 * Same as rehash(ceil(n / max_load_factor())). 1383 */ 1384 void 1385 reserve(size_type __n) 1386 { _M_h.reserve(__n); } 1387 1388 template<typename _Value1, typename _Hash1, typename _Pred1, 1389 typename _Alloc1> 1390 friend bool 1391 operator==(const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&, 1392 const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&); 1393 }; 1394 1395 template<class _Value, class _Hash, class _Pred, class _Alloc> 1396 inline void 1397 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 1398 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 1399 noexcept(noexcept(__x.swap(__y))) 1400 { __x.swap(__y); } 1401 1402 template<class _Value, class _Hash, class _Pred, class _Alloc> 1403 inline void 1404 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1405 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1406 noexcept(noexcept(__x.swap(__y))) 1407 { __x.swap(__y); } 1408 1409 template<class _Value, class _Hash, class _Pred, class _Alloc> 1410 inline bool 1411 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 1412 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 1413 { return __x._M_h._M_equal(__y._M_h); } 1414 1415 template<class _Value, class _Hash, class _Pred, class _Alloc> 1416 inline bool 1417 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 1418 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 1419 { return !(__x == __y); } 1420 1421 template<class _Value, class _Hash, class _Pred, class _Alloc> 1422 inline bool 1423 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1424 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1425 { return __x._M_h._M_equal(__y._M_h); } 1426 1427 template<class _Value, class _Hash, class _Pred, class _Alloc> 1428 inline bool 1429 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1430 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1431 { return !(__x == __y); } 1432 1433 _GLIBCXX_END_NAMESPACE_CONTAINER 1434 } // namespace std 1435 1436 #endif /* _UNORDERED_SET_H */ 1437