1 // unordered_set implementation -*- C++ -*- 2 3 // Copyright (C) 2010-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 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_VERSION 36 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 37 38 /// Base types for unordered_set. 39 template<bool _Cache> 40 using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>; 41 42 template<typename _Value, 43 typename _Hash = hash<_Value>, 44 typename _Pred = std::equal_to<_Value>, 45 typename _Alloc = std::allocator<_Value>, 46 typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value>> 47 using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc, 48 __detail::_Identity, _Pred, _Hash, 49 __detail::_Mod_range_hashing, 50 __detail::_Default_ranged_hash, 51 __detail::_Prime_rehash_policy, _Tr>; 52 53 /// Base types for unordered_multiset. 54 template<bool _Cache> 55 using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>; 56 57 template<typename _Value, 58 typename _Hash = hash<_Value>, 59 typename _Pred = std::equal_to<_Value>, 60 typename _Alloc = std::allocator<_Value>, 61 typename _Tr = __umset_traits<__cache_default<_Value, _Hash>::value>> 62 using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc, 63 __detail::_Identity, 64 _Pred, _Hash, 65 __detail::_Mod_range_hashing, 66 __detail::_Default_ranged_hash, 67 __detail::_Prime_rehash_policy, _Tr>; 68 69 template<class _Value, class _Hash, class _Pred, class _Alloc> 70 class unordered_multiset; 71 72 /** 73 * @brief A standard container composed of unique keys (containing 74 * at most one of each key value) in which the elements' keys are 75 * the elements themselves. 76 * 77 * @ingroup unordered_associative_containers 78 * 79 * @tparam _Value Type of key objects. 80 * @tparam _Hash Hashing function object type, defaults to hash<_Value>. 81 82 * @tparam _Pred Predicate function object type, defaults to 83 * equal_to<_Value>. 84 * 85 * @tparam _Alloc Allocator type, defaults to allocator<_Key>. 86 * 87 * Meets the requirements of a <a href="tables.html#65">container</a>, and 88 * <a href="tables.html#xx">unordered associative container</a> 89 * 90 * Base is _Hashtable, dispatched at compile time via template 91 * alias __uset_hashtable. 92 */ 93 template<typename _Value, 94 typename _Hash = hash<_Value>, 95 typename _Pred = equal_to<_Value>, 96 typename _Alloc = allocator<_Value>> 97 class unordered_set 98 { 99 typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable; 100 _Hashtable _M_h; 101 102 public: 103 // typedefs: 104 ///@{ 105 /// Public typedefs. 106 typedef typename _Hashtable::key_type key_type; 107 typedef typename _Hashtable::value_type value_type; 108 typedef typename _Hashtable::hasher hasher; 109 typedef typename _Hashtable::key_equal key_equal; 110 typedef typename _Hashtable::allocator_type allocator_type; 111 ///@} 112 113 ///@{ 114 /// Iterator-related typedefs. 115 typedef typename _Hashtable::pointer pointer; 116 typedef typename _Hashtable::const_pointer const_pointer; 117 typedef typename _Hashtable::reference reference; 118 typedef typename _Hashtable::const_reference const_reference; 119 typedef typename _Hashtable::iterator iterator; 120 typedef typename _Hashtable::const_iterator const_iterator; 121 typedef typename _Hashtable::local_iterator local_iterator; 122 typedef typename _Hashtable::const_local_iterator const_local_iterator; 123 typedef typename _Hashtable::size_type size_type; 124 typedef typename _Hashtable::difference_type difference_type; 125 ///@} 126 127 #if __cplusplus > 201402L 128 using node_type = typename _Hashtable::node_type; 129 using insert_return_type = typename _Hashtable::insert_return_type; 130 #endif 131 132 // construct/destroy/copy 133 134 /// Default constructor. 135 unordered_set() = default; 136 137 /** 138 * @brief Default constructor creates no elements. 139 * @param __n Minimal initial number of buckets. 140 * @param __hf A hash functor. 141 * @param __eql A key equality functor. 142 * @param __a An allocator object. 143 */ 144 explicit 145 unordered_set(size_type __n, 146 const hasher& __hf = hasher(), 147 const key_equal& __eql = key_equal(), 148 const allocator_type& __a = allocator_type()) 149 : _M_h(__n, __hf, __eql, __a) 150 { } 151 152 /** 153 * @brief Builds an %unordered_set from a range. 154 * @param __first An input iterator. 155 * @param __last An input iterator. 156 * @param __n Minimal initial number of buckets. 157 * @param __hf A hash functor. 158 * @param __eql A key equality functor. 159 * @param __a An allocator object. 160 * 161 * Create an %unordered_set consisting of copies of the elements from 162 * [__first,__last). This is linear in N (where N is 163 * distance(__first,__last)). 164 */ 165 template<typename _InputIterator> 166 unordered_set(_InputIterator __first, _InputIterator __last, 167 size_type __n = 0, 168 const hasher& __hf = hasher(), 169 const key_equal& __eql = key_equal(), 170 const allocator_type& __a = allocator_type()) 171 : _M_h(__first, __last, __n, __hf, __eql, __a) 172 { } 173 174 /// Copy constructor. 175 unordered_set(const unordered_set&) = default; 176 177 /// Move constructor. 178 unordered_set(unordered_set&&) = default; 179 180 /** 181 * @brief Creates an %unordered_set with no elements. 182 * @param __a An allocator object. 183 */ 184 explicit 185 unordered_set(const allocator_type& __a) 186 : _M_h(__a) 187 { } 188 189 /* 190 * @brief Copy constructor with allocator argument. 191 * @param __uset Input %unordered_set to copy. 192 * @param __a An allocator object. 193 */ 194 unordered_set(const unordered_set& __uset, 195 const allocator_type& __a) 196 : _M_h(__uset._M_h, __a) 197 { } 198 199 /* 200 * @brief Move constructor with allocator argument. 201 * @param __uset Input %unordered_set to move. 202 * @param __a An allocator object. 203 */ 204 unordered_set(unordered_set&& __uset, 205 const allocator_type& __a) 206 noexcept( noexcept(_Hashtable(std::move(__uset._M_h), __a)) ) 207 : _M_h(std::move(__uset._M_h), __a) 208 { } 209 210 /** 211 * @brief Builds an %unordered_set from an initializer_list. 212 * @param __l An initializer_list. 213 * @param __n Minimal initial number of buckets. 214 * @param __hf A hash functor. 215 * @param __eql A key equality functor. 216 * @param __a An allocator object. 217 * 218 * Create an %unordered_set consisting of copies of the elements in the 219 * list. This is linear in N (where N is @a __l.size()). 220 */ 221 unordered_set(initializer_list<value_type> __l, 222 size_type __n = 0, 223 const hasher& __hf = hasher(), 224 const key_equal& __eql = key_equal(), 225 const allocator_type& __a = allocator_type()) 226 : _M_h(__l, __n, __hf, __eql, __a) 227 { } 228 229 unordered_set(size_type __n, const allocator_type& __a) 230 : unordered_set(__n, hasher(), key_equal(), __a) 231 { } 232 233 unordered_set(size_type __n, const hasher& __hf, 234 const allocator_type& __a) 235 : unordered_set(__n, __hf, key_equal(), __a) 236 { } 237 238 template<typename _InputIterator> 239 unordered_set(_InputIterator __first, _InputIterator __last, 240 size_type __n, 241 const allocator_type& __a) 242 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) 243 { } 244 245 template<typename _InputIterator> 246 unordered_set(_InputIterator __first, _InputIterator __last, 247 size_type __n, const hasher& __hf, 248 const allocator_type& __a) 249 : unordered_set(__first, __last, __n, __hf, key_equal(), __a) 250 { } 251 252 unordered_set(initializer_list<value_type> __l, 253 size_type __n, 254 const allocator_type& __a) 255 : unordered_set(__l, __n, hasher(), key_equal(), __a) 256 { } 257 258 unordered_set(initializer_list<value_type> __l, 259 size_type __n, const hasher& __hf, 260 const allocator_type& __a) 261 : unordered_set(__l, __n, __hf, key_equal(), __a) 262 { } 263 264 /// Copy assignment operator. 265 unordered_set& 266 operator=(const unordered_set&) = default; 267 268 /// Move assignment operator. 269 unordered_set& 270 operator=(unordered_set&&) = default; 271 272 /** 273 * @brief %Unordered_set list assignment operator. 274 * @param __l An initializer_list. 275 * 276 * This function fills an %unordered_set with copies of the elements in 277 * the initializer list @a __l. 278 * 279 * Note that the assignment completely changes the %unordered_set and 280 * that the resulting %unordered_set's size is the same as the number 281 * of elements assigned. 282 */ 283 unordered_set& 284 operator=(initializer_list<value_type> __l) 285 { 286 _M_h = __l; 287 return *this; 288 } 289 290 /// Returns the allocator object used by the %unordered_set. 291 allocator_type 292 get_allocator() const noexcept 293 { return _M_h.get_allocator(); } 294 295 // size and capacity: 296 297 /// Returns true if the %unordered_set is empty. 298 _GLIBCXX_NODISCARD bool 299 empty() const noexcept 300 { return _M_h.empty(); } 301 302 /// Returns the size of the %unordered_set. 303 size_type 304 size() const noexcept 305 { return _M_h.size(); } 306 307 /// Returns the maximum size of the %unordered_set. 308 size_type 309 max_size() const noexcept 310 { return _M_h.max_size(); } 311 312 // iterators. 313 314 ///@{ 315 /** 316 * Returns a read-only (constant) iterator that points to the first 317 * element in the %unordered_set. 318 */ 319 iterator 320 begin() noexcept 321 { return _M_h.begin(); } 322 323 const_iterator 324 begin() const noexcept 325 { return _M_h.begin(); } 326 ///@} 327 328 ///@{ 329 /** 330 * Returns a read-only (constant) iterator that points one past the last 331 * element in the %unordered_set. 332 */ 333 iterator 334 end() noexcept 335 { return _M_h.end(); } 336 337 const_iterator 338 end() const noexcept 339 { return _M_h.end(); } 340 ///@} 341 342 /** 343 * Returns a read-only (constant) iterator that points to the first 344 * element in the %unordered_set. 345 */ 346 const_iterator 347 cbegin() const noexcept 348 { return _M_h.begin(); } 349 350 /** 351 * Returns a read-only (constant) iterator that points one past the last 352 * element in the %unordered_set. 353 */ 354 const_iterator 355 cend() const noexcept 356 { return _M_h.end(); } 357 358 // modifiers. 359 360 /** 361 * @brief Attempts to build and insert an element into the 362 * %unordered_set. 363 * @param __args Arguments used to generate an element. 364 * @return A pair, of which the first element is an iterator that points 365 * to the possibly inserted element, and the second is a bool 366 * that is true if the element was actually inserted. 367 * 368 * This function attempts to build and insert an element into the 369 * %unordered_set. An %unordered_set relies on unique keys and thus an 370 * element is only inserted if it is not already present in the 371 * %unordered_set. 372 * 373 * Insertion requires amortized constant time. 374 */ 375 template<typename... _Args> 376 std::pair<iterator, bool> 377 emplace(_Args&&... __args) 378 { return _M_h.emplace(std::forward<_Args>(__args)...); } 379 380 /** 381 * @brief Attempts to insert an element into the %unordered_set. 382 * @param __pos An iterator that serves as a hint as to where the 383 * element should be inserted. 384 * @param __args Arguments used to generate the element to be 385 * inserted. 386 * @return An iterator that points to the element with key equivalent to 387 * the one generated from @a __args (may or may not be the 388 * element itself). 389 * 390 * This function is not concerned about whether the insertion took place, 391 * and thus does not return a boolean like the single-argument emplace() 392 * does. Note that the first parameter is only a hint and can 393 * potentially improve the performance of the insertion process. A bad 394 * hint would cause no gains in efficiency. 395 * 396 * For more on @a hinting, see: 397 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 398 * 399 * Insertion requires amortized constant time. 400 */ 401 template<typename... _Args> 402 iterator 403 emplace_hint(const_iterator __pos, _Args&&... __args) 404 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); } 405 406 ///@{ 407 /** 408 * @brief Attempts to insert an element into the %unordered_set. 409 * @param __x Element to be inserted. 410 * @return A pair, of which the first element is an iterator that points 411 * to the possibly inserted element, and the second is a bool 412 * that is true if the element was actually inserted. 413 * 414 * This function attempts to insert an element into the %unordered_set. 415 * An %unordered_set relies on unique keys and thus an element is only 416 * inserted if it is not already present in the %unordered_set. 417 * 418 * Insertion requires amortized constant time. 419 */ 420 std::pair<iterator, bool> 421 insert(const value_type& __x) 422 { return _M_h.insert(__x); } 423 424 std::pair<iterator, bool> 425 insert(value_type&& __x) 426 { return _M_h.insert(std::move(__x)); } 427 ///@} 428 429 ///@{ 430 /** 431 * @brief Attempts to insert an element into the %unordered_set. 432 * @param __hint An iterator that serves as a hint as to where the 433 * element should be inserted. 434 * @param __x Element to be inserted. 435 * @return An iterator that points to the element with key of 436 * @a __x (may or may not be the element passed in). 437 * 438 * This function is not concerned about whether the insertion took place, 439 * and thus does not return a boolean like the single-argument insert() 440 * does. Note that the first parameter is only a hint and can 441 * potentially improve the performance of the insertion process. A bad 442 * hint would cause no gains in efficiency. 443 * 444 * For more on @a hinting, see: 445 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 446 * 447 * Insertion requires amortized constant. 448 */ 449 iterator 450 insert(const_iterator __hint, const value_type& __x) 451 { return _M_h.insert(__hint, __x); } 452 453 iterator 454 insert(const_iterator __hint, value_type&& __x) 455 { return _M_h.insert(__hint, std::move(__x)); } 456 ///@} 457 458 /** 459 * @brief A template function that attempts to insert a range of 460 * elements. 461 * @param __first Iterator pointing to the start of the range to be 462 * inserted. 463 * @param __last Iterator pointing to the end of the range. 464 * 465 * Complexity similar to that of the range constructor. 466 */ 467 template<typename _InputIterator> 468 void 469 insert(_InputIterator __first, _InputIterator __last) 470 { _M_h.insert(__first, __last); } 471 472 /** 473 * @brief Attempts to insert a list of elements into the %unordered_set. 474 * @param __l A std::initializer_list<value_type> of elements 475 * to be inserted. 476 * 477 * Complexity similar to that of the range constructor. 478 */ 479 void 480 insert(initializer_list<value_type> __l) 481 { _M_h.insert(__l); } 482 483 #if __cplusplus > 201402L 484 /// Extract a node. 485 node_type 486 extract(const_iterator __pos) 487 { 488 __glibcxx_assert(__pos != end()); 489 return _M_h.extract(__pos); 490 } 491 492 /// Extract a node. 493 node_type 494 extract(const key_type& __key) 495 { return _M_h.extract(__key); } 496 497 /// Re-insert an extracted node. 498 insert_return_type 499 insert(node_type&& __nh) 500 { return _M_h._M_reinsert_node(std::move(__nh)); } 501 502 /// Re-insert an extracted node. 503 iterator 504 insert(const_iterator, node_type&& __nh) 505 { return _M_h._M_reinsert_node(std::move(__nh)).position; } 506 #endif // C++17 507 508 ///@{ 509 /** 510 * @brief Erases an element from an %unordered_set. 511 * @param __position An iterator pointing to the element to be erased. 512 * @return An iterator pointing to the element immediately following 513 * @a __position prior to the element being erased. If no such 514 * element exists, end() is returned. 515 * 516 * This function erases an element, pointed to by the given iterator, 517 * from an %unordered_set. Note that this function only erases the 518 * element, and that if the element is itself a pointer, the pointed-to 519 * memory is not touched in any way. Managing the pointer is the user's 520 * responsibility. 521 */ 522 iterator 523 erase(const_iterator __position) 524 { return _M_h.erase(__position); } 525 526 // LWG 2059. 527 iterator 528 erase(iterator __position) 529 { return _M_h.erase(__position); } 530 ///@} 531 532 /** 533 * @brief Erases elements according to the provided key. 534 * @param __x Key of element to be erased. 535 * @return The number of elements erased. 536 * 537 * This function erases all the elements located by the given key from 538 * an %unordered_set. For an %unordered_set the result of this function 539 * can only be 0 (not present) or 1 (present). 540 * Note that this function only erases the element, and that if 541 * the element is itself a pointer, the pointed-to memory is not touched 542 * in any way. Managing the pointer is the user's responsibility. 543 */ 544 size_type 545 erase(const key_type& __x) 546 { return _M_h.erase(__x); } 547 548 /** 549 * @brief Erases a [__first,__last) range of elements from an 550 * %unordered_set. 551 * @param __first Iterator pointing to the start of the range to be 552 * erased. 553 * @param __last Iterator pointing to the end of the range to 554 * be erased. 555 * @return The iterator @a __last. 556 * 557 * This function erases a sequence of elements from an %unordered_set. 558 * Note that this function only erases the element, and that if 559 * the element is itself a pointer, the pointed-to memory is not touched 560 * in any way. Managing the pointer is the user's responsibility. 561 */ 562 iterator 563 erase(const_iterator __first, const_iterator __last) 564 { return _M_h.erase(__first, __last); } 565 566 /** 567 * Erases all elements in an %unordered_set. Note that this function only 568 * erases the elements, and that if the elements themselves are pointers, 569 * the pointed-to memory is not touched in any way. Managing the pointer 570 * is the user's responsibility. 571 */ 572 void 573 clear() noexcept 574 { _M_h.clear(); } 575 576 /** 577 * @brief Swaps data with another %unordered_set. 578 * @param __x An %unordered_set of the same element and allocator 579 * types. 580 * 581 * This exchanges the elements between two sets in constant time. 582 * Note that the global std::swap() function is specialized such that 583 * std::swap(s1,s2) will feed to this function. 584 */ 585 void 586 swap(unordered_set& __x) 587 noexcept( noexcept(_M_h.swap(__x._M_h)) ) 588 { _M_h.swap(__x._M_h); } 589 590 #if __cplusplus > 201402L 591 template<typename, typename, typename> 592 friend class std::_Hash_merge_helper; 593 594 template<typename _H2, typename _P2> 595 void 596 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source) 597 { 598 using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>; 599 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source)); 600 } 601 602 template<typename _H2, typename _P2> 603 void 604 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source) 605 { merge(__source); } 606 607 template<typename _H2, typename _P2> 608 void 609 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source) 610 { 611 using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>; 612 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source)); 613 } 614 615 template<typename _H2, typename _P2> 616 void 617 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source) 618 { merge(__source); } 619 #endif // C++17 620 621 // observers. 622 623 /// Returns the hash functor object with which the %unordered_set was 624 /// constructed. 625 hasher 626 hash_function() const 627 { return _M_h.hash_function(); } 628 629 /// Returns the key comparison object with which the %unordered_set was 630 /// constructed. 631 key_equal 632 key_eq() const 633 { return _M_h.key_eq(); } 634 635 // lookup. 636 637 ///@{ 638 /** 639 * @brief Tries to locate an element in an %unordered_set. 640 * @param __x Element to be located. 641 * @return Iterator pointing to sought-after element, or end() if not 642 * found. 643 * 644 * This function takes a key and tries to locate the element with which 645 * the key matches. If successful the function returns an iterator 646 * pointing to the sought after element. If unsuccessful it returns the 647 * past-the-end ( @c end() ) iterator. 648 */ 649 iterator 650 find(const key_type& __x) 651 { return _M_h.find(__x); } 652 653 #if __cplusplus > 201703L 654 template<typename _Kt> 655 auto 656 find(const _Kt& __k) 657 -> decltype(_M_h._M_find_tr(__k)) 658 { return _M_h._M_find_tr(__k); } 659 #endif 660 661 const_iterator 662 find(const key_type& __x) const 663 { return _M_h.find(__x); } 664 665 #if __cplusplus > 201703L 666 template<typename _Kt> 667 auto 668 find(const _Kt& __k) const 669 -> decltype(_M_h._M_find_tr(__k)) 670 { return _M_h._M_find_tr(__k); } 671 #endif 672 ///@} 673 674 ///@{ 675 /** 676 * @brief Finds the number of elements. 677 * @param __x Element to located. 678 * @return Number of elements with specified key. 679 * 680 * This function only makes sense for unordered_multisets; for 681 * unordered_set the result will either be 0 (not present) or 1 682 * (present). 683 */ 684 size_type 685 count(const key_type& __x) const 686 { return _M_h.count(__x); } 687 688 #if __cplusplus > 201703L 689 template<typename _Kt> 690 auto 691 count(const _Kt& __k) const 692 -> decltype(_M_h._M_count_tr(__k)) 693 { return _M_h._M_count_tr(__k); } 694 #endif 695 ///@} 696 697 #if __cplusplus > 201703L 698 ///@{ 699 /** 700 * @brief Finds whether an element with the given key exists. 701 * @param __x Key of elements to be located. 702 * @return True if there is any element with the specified key. 703 */ 704 bool 705 contains(const key_type& __x) const 706 { return _M_h.find(__x) != _M_h.end(); } 707 708 template<typename _Kt> 709 auto 710 contains(const _Kt& __k) const 711 -> decltype(_M_h._M_find_tr(__k), void(), true) 712 { return _M_h._M_find_tr(__k) != _M_h.end(); } 713 ///@} 714 #endif 715 716 ///@{ 717 /** 718 * @brief Finds a subsequence matching given key. 719 * @param __x Key to be located. 720 * @return Pair of iterators that possibly points to the subsequence 721 * matching given key. 722 * 723 * This function probably only makes sense for multisets. 724 */ 725 std::pair<iterator, iterator> 726 equal_range(const key_type& __x) 727 { return _M_h.equal_range(__x); } 728 729 #if __cplusplus > 201703L 730 template<typename _Kt> 731 auto 732 equal_range(const _Kt& __k) 733 -> decltype(_M_h._M_equal_range_tr(__k)) 734 { return _M_h._M_equal_range_tr(__k); } 735 #endif 736 737 std::pair<const_iterator, const_iterator> 738 equal_range(const key_type& __x) const 739 { return _M_h.equal_range(__x); } 740 741 #if __cplusplus > 201703L 742 template<typename _Kt> 743 auto 744 equal_range(const _Kt& __k) const 745 -> decltype(_M_h._M_equal_range_tr(__k)) 746 { return _M_h._M_equal_range_tr(__k); } 747 #endif 748 ///@} 749 750 // bucket interface. 751 752 /// Returns the number of buckets of the %unordered_set. 753 size_type 754 bucket_count() const noexcept 755 { return _M_h.bucket_count(); } 756 757 /// Returns the maximum number of buckets of the %unordered_set. 758 size_type 759 max_bucket_count() const noexcept 760 { return _M_h.max_bucket_count(); } 761 762 /* 763 * @brief Returns the number of elements in a given bucket. 764 * @param __n A bucket index. 765 * @return The number of elements in the bucket. 766 */ 767 size_type 768 bucket_size(size_type __n) const 769 { return _M_h.bucket_size(__n); } 770 771 /* 772 * @brief Returns the bucket index of a given element. 773 * @param __key A key instance. 774 * @return The key bucket index. 775 */ 776 size_type 777 bucket(const key_type& __key) const 778 { return _M_h.bucket(__key); } 779 780 ///@{ 781 /** 782 * @brief Returns a read-only (constant) iterator pointing to the first 783 * bucket element. 784 * @param __n The bucket index. 785 * @return A read-only local iterator. 786 */ 787 local_iterator 788 begin(size_type __n) 789 { return _M_h.begin(__n); } 790 791 const_local_iterator 792 begin(size_type __n) const 793 { return _M_h.begin(__n); } 794 795 const_local_iterator 796 cbegin(size_type __n) const 797 { return _M_h.cbegin(__n); } 798 ///@} 799 800 ///@{ 801 /** 802 * @brief Returns a read-only (constant) iterator pointing to one past 803 * the last bucket elements. 804 * @param __n The bucket index. 805 * @return A read-only local iterator. 806 */ 807 local_iterator 808 end(size_type __n) 809 { return _M_h.end(__n); } 810 811 const_local_iterator 812 end(size_type __n) const 813 { return _M_h.end(__n); } 814 815 const_local_iterator 816 cend(size_type __n) const 817 { return _M_h.cend(__n); } 818 ///@} 819 820 // hash policy. 821 822 /// Returns the average number of elements per bucket. 823 float 824 load_factor() const noexcept 825 { return _M_h.load_factor(); } 826 827 /// Returns a positive number that the %unordered_set tries to keep the 828 /// load factor less than or equal to. 829 float 830 max_load_factor() const noexcept 831 { return _M_h.max_load_factor(); } 832 833 /** 834 * @brief Change the %unordered_set maximum load factor. 835 * @param __z The new maximum load factor. 836 */ 837 void 838 max_load_factor(float __z) 839 { _M_h.max_load_factor(__z); } 840 841 /** 842 * @brief May rehash the %unordered_set. 843 * @param __n The new number of buckets. 844 * 845 * Rehash will occur only if the new number of buckets respect the 846 * %unordered_set maximum load factor. 847 */ 848 void 849 rehash(size_type __n) 850 { _M_h.rehash(__n); } 851 852 /** 853 * @brief Prepare the %unordered_set for a specified number of 854 * elements. 855 * @param __n Number of elements required. 856 * 857 * Same as rehash(ceil(n / max_load_factor())). 858 */ 859 void 860 reserve(size_type __n) 861 { _M_h.reserve(__n); } 862 863 template<typename _Value1, typename _Hash1, typename _Pred1, 864 typename _Alloc1> 865 friend bool 866 operator==(const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&, 867 const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&); 868 }; 869 870 #if __cpp_deduction_guides >= 201606 871 872 template<typename _InputIterator, 873 typename _Hash = 874 hash<typename iterator_traits<_InputIterator>::value_type>, 875 typename _Pred = 876 equal_to<typename iterator_traits<_InputIterator>::value_type>, 877 typename _Allocator = 878 allocator<typename iterator_traits<_InputIterator>::value_type>, 879 typename = _RequireInputIter<_InputIterator>, 880 typename = _RequireNotAllocatorOrIntegral<_Hash>, 881 typename = _RequireNotAllocator<_Pred>, 882 typename = _RequireAllocator<_Allocator>> 883 unordered_set(_InputIterator, _InputIterator, 884 unordered_set<int>::size_type = {}, 885 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 886 -> unordered_set<typename iterator_traits<_InputIterator>::value_type, 887 _Hash, _Pred, _Allocator>; 888 889 template<typename _Tp, typename _Hash = hash<_Tp>, 890 typename _Pred = equal_to<_Tp>, 891 typename _Allocator = allocator<_Tp>, 892 typename = _RequireNotAllocatorOrIntegral<_Hash>, 893 typename = _RequireNotAllocator<_Pred>, 894 typename = _RequireAllocator<_Allocator>> 895 unordered_set(initializer_list<_Tp>, 896 unordered_set<int>::size_type = {}, 897 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 898 -> unordered_set<_Tp, _Hash, _Pred, _Allocator>; 899 900 template<typename _InputIterator, typename _Allocator, 901 typename = _RequireInputIter<_InputIterator>, 902 typename = _RequireAllocator<_Allocator>> 903 unordered_set(_InputIterator, _InputIterator, 904 unordered_set<int>::size_type, _Allocator) 905 -> unordered_set<typename iterator_traits<_InputIterator>::value_type, 906 hash< 907 typename iterator_traits<_InputIterator>::value_type>, 908 equal_to< 909 typename iterator_traits<_InputIterator>::value_type>, 910 _Allocator>; 911 912 template<typename _InputIterator, typename _Hash, typename _Allocator, 913 typename = _RequireInputIter<_InputIterator>, 914 typename = _RequireNotAllocatorOrIntegral<_Hash>, 915 typename = _RequireAllocator<_Allocator>> 916 unordered_set(_InputIterator, _InputIterator, 917 unordered_set<int>::size_type, 918 _Hash, _Allocator) 919 -> unordered_set<typename iterator_traits<_InputIterator>::value_type, 920 _Hash, 921 equal_to< 922 typename iterator_traits<_InputIterator>::value_type>, 923 _Allocator>; 924 925 template<typename _Tp, typename _Allocator, 926 typename = _RequireAllocator<_Allocator>> 927 unordered_set(initializer_list<_Tp>, 928 unordered_set<int>::size_type, _Allocator) 929 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 930 931 template<typename _Tp, typename _Hash, typename _Allocator, 932 typename = _RequireNotAllocatorOrIntegral<_Hash>, 933 typename = _RequireAllocator<_Allocator>> 934 unordered_set(initializer_list<_Tp>, 935 unordered_set<int>::size_type, _Hash, _Allocator) 936 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 937 938 #endif 939 940 /** 941 * @brief A standard container composed of equivalent keys 942 * (possibly containing multiple of each key value) in which the 943 * elements' keys are the elements themselves. 944 * 945 * @ingroup unordered_associative_containers 946 * 947 * @tparam _Value Type of key objects. 948 * @tparam _Hash Hashing function object type, defaults to hash<_Value>. 949 * @tparam _Pred Predicate function object type, defaults 950 * to equal_to<_Value>. 951 * @tparam _Alloc Allocator type, defaults to allocator<_Key>. 952 * 953 * Meets the requirements of a <a href="tables.html#65">container</a>, and 954 * <a href="tables.html#xx">unordered associative container</a> 955 * 956 * Base is _Hashtable, dispatched at compile time via template 957 * alias __umset_hashtable. 958 */ 959 template<typename _Value, 960 typename _Hash = hash<_Value>, 961 typename _Pred = equal_to<_Value>, 962 typename _Alloc = allocator<_Value>> 963 class unordered_multiset 964 { 965 typedef __umset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable; 966 _Hashtable _M_h; 967 968 public: 969 // typedefs: 970 ///@{ 971 /// Public typedefs. 972 typedef typename _Hashtable::key_type key_type; 973 typedef typename _Hashtable::value_type value_type; 974 typedef typename _Hashtable::hasher hasher; 975 typedef typename _Hashtable::key_equal key_equal; 976 typedef typename _Hashtable::allocator_type allocator_type; 977 ///@} 978 979 ///@{ 980 /// Iterator-related typedefs. 981 typedef typename _Hashtable::pointer pointer; 982 typedef typename _Hashtable::const_pointer const_pointer; 983 typedef typename _Hashtable::reference reference; 984 typedef typename _Hashtable::const_reference const_reference; 985 typedef typename _Hashtable::iterator iterator; 986 typedef typename _Hashtable::const_iterator const_iterator; 987 typedef typename _Hashtable::local_iterator local_iterator; 988 typedef typename _Hashtable::const_local_iterator const_local_iterator; 989 typedef typename _Hashtable::size_type size_type; 990 typedef typename _Hashtable::difference_type difference_type; 991 ///@} 992 993 #if __cplusplus > 201402L 994 using node_type = typename _Hashtable::node_type; 995 #endif 996 997 // construct/destroy/copy 998 999 /// Default constructor. 1000 unordered_multiset() = default; 1001 1002 /** 1003 * @brief Default constructor creates no elements. 1004 * @param __n Minimal initial number of buckets. 1005 * @param __hf A hash functor. 1006 * @param __eql A key equality functor. 1007 * @param __a An allocator object. 1008 */ 1009 explicit 1010 unordered_multiset(size_type __n, 1011 const hasher& __hf = hasher(), 1012 const key_equal& __eql = key_equal(), 1013 const allocator_type& __a = allocator_type()) 1014 : _M_h(__n, __hf, __eql, __a) 1015 { } 1016 1017 /** 1018 * @brief Builds an %unordered_multiset from a range. 1019 * @param __first An input iterator. 1020 * @param __last An input iterator. 1021 * @param __n Minimal initial number of buckets. 1022 * @param __hf A hash functor. 1023 * @param __eql A key equality functor. 1024 * @param __a An allocator object. 1025 * 1026 * Create an %unordered_multiset consisting of copies of the elements 1027 * from [__first,__last). This is linear in N (where N is 1028 * distance(__first,__last)). 1029 */ 1030 template<typename _InputIterator> 1031 unordered_multiset(_InputIterator __first, _InputIterator __last, 1032 size_type __n = 0, 1033 const hasher& __hf = hasher(), 1034 const key_equal& __eql = key_equal(), 1035 const allocator_type& __a = allocator_type()) 1036 : _M_h(__first, __last, __n, __hf, __eql, __a) 1037 { } 1038 1039 /// Copy constructor. 1040 unordered_multiset(const unordered_multiset&) = default; 1041 1042 /// Move constructor. 1043 unordered_multiset(unordered_multiset&&) = default; 1044 1045 /** 1046 * @brief Builds an %unordered_multiset from an initializer_list. 1047 * @param __l An initializer_list. 1048 * @param __n Minimal initial number of buckets. 1049 * @param __hf A hash functor. 1050 * @param __eql A key equality functor. 1051 * @param __a An allocator object. 1052 * 1053 * Create an %unordered_multiset consisting of copies of the elements in 1054 * the list. This is linear in N (where N is @a __l.size()). 1055 */ 1056 unordered_multiset(initializer_list<value_type> __l, 1057 size_type __n = 0, 1058 const hasher& __hf = hasher(), 1059 const key_equal& __eql = key_equal(), 1060 const allocator_type& __a = allocator_type()) 1061 : _M_h(__l, __n, __hf, __eql, __a) 1062 { } 1063 1064 /// Copy assignment operator. 1065 unordered_multiset& 1066 operator=(const unordered_multiset&) = default; 1067 1068 /// Move assignment operator. 1069 unordered_multiset& 1070 operator=(unordered_multiset&&) = default; 1071 1072 /** 1073 * @brief Creates an %unordered_multiset with no elements. 1074 * @param __a An allocator object. 1075 */ 1076 explicit 1077 unordered_multiset(const allocator_type& __a) 1078 : _M_h(__a) 1079 { } 1080 1081 /* 1082 * @brief Copy constructor with allocator argument. 1083 * @param __uset Input %unordered_multiset to copy. 1084 * @param __a An allocator object. 1085 */ 1086 unordered_multiset(const unordered_multiset& __umset, 1087 const allocator_type& __a) 1088 : _M_h(__umset._M_h, __a) 1089 { } 1090 1091 /* 1092 * @brief Move constructor with allocator argument. 1093 * @param __umset Input %unordered_multiset to move. 1094 * @param __a An allocator object. 1095 */ 1096 unordered_multiset(unordered_multiset&& __umset, 1097 const allocator_type& __a) 1098 noexcept( noexcept(_Hashtable(std::move(__umset._M_h), __a)) ) 1099 : _M_h(std::move(__umset._M_h), __a) 1100 { } 1101 1102 unordered_multiset(size_type __n, const allocator_type& __a) 1103 : unordered_multiset(__n, hasher(), key_equal(), __a) 1104 { } 1105 1106 unordered_multiset(size_type __n, const hasher& __hf, 1107 const allocator_type& __a) 1108 : unordered_multiset(__n, __hf, key_equal(), __a) 1109 { } 1110 1111 template<typename _InputIterator> 1112 unordered_multiset(_InputIterator __first, _InputIterator __last, 1113 size_type __n, 1114 const allocator_type& __a) 1115 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) 1116 { } 1117 1118 template<typename _InputIterator> 1119 unordered_multiset(_InputIterator __first, _InputIterator __last, 1120 size_type __n, const hasher& __hf, 1121 const allocator_type& __a) 1122 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) 1123 { } 1124 1125 unordered_multiset(initializer_list<value_type> __l, 1126 size_type __n, 1127 const allocator_type& __a) 1128 : unordered_multiset(__l, __n, hasher(), key_equal(), __a) 1129 { } 1130 1131 unordered_multiset(initializer_list<value_type> __l, 1132 size_type __n, const hasher& __hf, 1133 const allocator_type& __a) 1134 : unordered_multiset(__l, __n, __hf, key_equal(), __a) 1135 { } 1136 1137 /** 1138 * @brief %Unordered_multiset list assignment operator. 1139 * @param __l An initializer_list. 1140 * 1141 * This function fills an %unordered_multiset with copies of the elements 1142 * in the initializer list @a __l. 1143 * 1144 * Note that the assignment completely changes the %unordered_multiset 1145 * and that the resulting %unordered_multiset's size is the same as the 1146 * number of elements assigned. 1147 */ 1148 unordered_multiset& 1149 operator=(initializer_list<value_type> __l) 1150 { 1151 _M_h = __l; 1152 return *this; 1153 } 1154 1155 /// Returns the allocator object used by the %unordered_multiset. 1156 allocator_type 1157 get_allocator() const noexcept 1158 { return _M_h.get_allocator(); } 1159 1160 // size and capacity: 1161 1162 /// Returns true if the %unordered_multiset is empty. 1163 _GLIBCXX_NODISCARD bool 1164 empty() const noexcept 1165 { return _M_h.empty(); } 1166 1167 /// Returns the size of the %unordered_multiset. 1168 size_type 1169 size() const noexcept 1170 { return _M_h.size(); } 1171 1172 /// Returns the maximum size of the %unordered_multiset. 1173 size_type 1174 max_size() const noexcept 1175 { return _M_h.max_size(); } 1176 1177 // iterators. 1178 1179 ///@{ 1180 /** 1181 * Returns a read-only (constant) iterator that points to the first 1182 * element in the %unordered_multiset. 1183 */ 1184 iterator 1185 begin() noexcept 1186 { return _M_h.begin(); } 1187 1188 const_iterator 1189 begin() const noexcept 1190 { return _M_h.begin(); } 1191 ///@} 1192 1193 ///@{ 1194 /** 1195 * Returns a read-only (constant) iterator that points one past the last 1196 * element in the %unordered_multiset. 1197 */ 1198 iterator 1199 end() noexcept 1200 { return _M_h.end(); } 1201 1202 const_iterator 1203 end() const noexcept 1204 { return _M_h.end(); } 1205 ///@} 1206 1207 /** 1208 * Returns a read-only (constant) iterator that points to the first 1209 * element in the %unordered_multiset. 1210 */ 1211 const_iterator 1212 cbegin() const noexcept 1213 { return _M_h.begin(); } 1214 1215 /** 1216 * Returns a read-only (constant) iterator that points one past the last 1217 * element in the %unordered_multiset. 1218 */ 1219 const_iterator 1220 cend() const noexcept 1221 { return _M_h.end(); } 1222 1223 // modifiers. 1224 1225 /** 1226 * @brief Builds and insert an element into the %unordered_multiset. 1227 * @param __args Arguments used to generate an element. 1228 * @return An iterator that points to the inserted element. 1229 * 1230 * Insertion requires amortized constant time. 1231 */ 1232 template<typename... _Args> 1233 iterator 1234 emplace(_Args&&... __args) 1235 { return _M_h.emplace(std::forward<_Args>(__args)...); } 1236 1237 /** 1238 * @brief Inserts an element into the %unordered_multiset. 1239 * @param __pos An iterator that serves as a hint as to where the 1240 * element should be inserted. 1241 * @param __args Arguments used to generate the element to be 1242 * inserted. 1243 * @return An iterator that points to the inserted element. 1244 * 1245 * Note that the first parameter is only a hint and can potentially 1246 * improve the performance of the insertion process. A bad hint would 1247 * cause no gains in efficiency. 1248 * 1249 * For more on @a hinting, see: 1250 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 1251 * 1252 * Insertion requires amortized constant time. 1253 */ 1254 template<typename... _Args> 1255 iterator 1256 emplace_hint(const_iterator __pos, _Args&&... __args) 1257 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); } 1258 1259 ///@{ 1260 /** 1261 * @brief Inserts an element into the %unordered_multiset. 1262 * @param __x Element to be inserted. 1263 * @return An iterator that points to the inserted element. 1264 * 1265 * Insertion requires amortized constant time. 1266 */ 1267 iterator 1268 insert(const value_type& __x) 1269 { return _M_h.insert(__x); } 1270 1271 iterator 1272 insert(value_type&& __x) 1273 { return _M_h.insert(std::move(__x)); } 1274 ///@} 1275 1276 ///@{ 1277 /** 1278 * @brief Inserts an element into the %unordered_multiset. 1279 * @param __hint An iterator that serves as a hint as to where the 1280 * element should be inserted. 1281 * @param __x Element to be inserted. 1282 * @return An iterator that points to the inserted element. 1283 * 1284 * Note that the first parameter is only a hint and can potentially 1285 * improve the performance of the insertion process. A bad hint would 1286 * cause no gains in efficiency. 1287 * 1288 * For more on @a hinting, see: 1289 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 1290 * 1291 * Insertion requires amortized constant. 1292 */ 1293 iterator 1294 insert(const_iterator __hint, const value_type& __x) 1295 { return _M_h.insert(__hint, __x); } 1296 1297 iterator 1298 insert(const_iterator __hint, value_type&& __x) 1299 { return _M_h.insert(__hint, std::move(__x)); } 1300 ///@} 1301 1302 /** 1303 * @brief A template function that inserts a range of elements. 1304 * @param __first Iterator pointing to the start of the range to be 1305 * inserted. 1306 * @param __last Iterator pointing to the end of the range. 1307 * 1308 * Complexity similar to that of the range constructor. 1309 */ 1310 template<typename _InputIterator> 1311 void 1312 insert(_InputIterator __first, _InputIterator __last) 1313 { _M_h.insert(__first, __last); } 1314 1315 /** 1316 * @brief Inserts a list of elements into the %unordered_multiset. 1317 * @param __l A std::initializer_list<value_type> of elements to be 1318 * inserted. 1319 * 1320 * Complexity similar to that of the range constructor. 1321 */ 1322 void 1323 insert(initializer_list<value_type> __l) 1324 { _M_h.insert(__l); } 1325 1326 #if __cplusplus > 201402L 1327 /// Extract a node. 1328 node_type 1329 extract(const_iterator __pos) 1330 { 1331 __glibcxx_assert(__pos != end()); 1332 return _M_h.extract(__pos); 1333 } 1334 1335 /// Extract a node. 1336 node_type 1337 extract(const key_type& __key) 1338 { return _M_h.extract(__key); } 1339 1340 /// Re-insert an extracted node. 1341 iterator 1342 insert(node_type&& __nh) 1343 { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); } 1344 1345 /// Re-insert an extracted node. 1346 iterator 1347 insert(const_iterator __hint, node_type&& __nh) 1348 { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); } 1349 #endif // C++17 1350 1351 ///@{ 1352 /** 1353 * @brief Erases an element from an %unordered_multiset. 1354 * @param __position An iterator pointing to the element to be erased. 1355 * @return An iterator pointing to the element immediately following 1356 * @a __position prior to the element being erased. If no such 1357 * element exists, end() is returned. 1358 * 1359 * This function erases an element, pointed to by the given iterator, 1360 * from an %unordered_multiset. 1361 * 1362 * Note that this function only erases the element, and that if the 1363 * element is itself a pointer, the pointed-to memory is not touched in 1364 * any way. Managing the pointer is the user's responsibility. 1365 */ 1366 iterator 1367 erase(const_iterator __position) 1368 { return _M_h.erase(__position); } 1369 1370 // LWG 2059. 1371 iterator 1372 erase(iterator __position) 1373 { return _M_h.erase(__position); } 1374 ///@} 1375 1376 1377 /** 1378 * @brief Erases elements according to the provided key. 1379 * @param __x Key of element to be erased. 1380 * @return The number of elements erased. 1381 * 1382 * This function erases all the elements located by the given key from 1383 * an %unordered_multiset. 1384 * 1385 * Note that this function only erases the element, and that if the 1386 * element is itself a pointer, the pointed-to memory is not touched in 1387 * any way. Managing the pointer is the user's responsibility. 1388 */ 1389 size_type 1390 erase(const key_type& __x) 1391 { return _M_h.erase(__x); } 1392 1393 /** 1394 * @brief Erases a [__first,__last) range of elements from an 1395 * %unordered_multiset. 1396 * @param __first Iterator pointing to the start of the range to be 1397 * erased. 1398 * @param __last Iterator pointing to the end of the range to 1399 * be erased. 1400 * @return The iterator @a __last. 1401 * 1402 * This function erases a sequence of elements from an 1403 * %unordered_multiset. 1404 * 1405 * Note that this function only erases the element, and that if 1406 * the element is itself a pointer, the pointed-to memory is not touched 1407 * in any way. Managing the pointer is the user's responsibility. 1408 */ 1409 iterator 1410 erase(const_iterator __first, const_iterator __last) 1411 { return _M_h.erase(__first, __last); } 1412 1413 /** 1414 * Erases all elements in an %unordered_multiset. 1415 * 1416 * Note that this function only erases the elements, and that if the 1417 * elements themselves are pointers, the pointed-to memory is not touched 1418 * in any way. Managing the pointer is the user's responsibility. 1419 */ 1420 void 1421 clear() noexcept 1422 { _M_h.clear(); } 1423 1424 /** 1425 * @brief Swaps data with another %unordered_multiset. 1426 * @param __x An %unordered_multiset of the same element and allocator 1427 * types. 1428 * 1429 * This exchanges the elements between two sets in constant time. 1430 * Note that the global std::swap() function is specialized such that 1431 * std::swap(s1,s2) will feed to this function. 1432 */ 1433 void 1434 swap(unordered_multiset& __x) 1435 noexcept( noexcept(_M_h.swap(__x._M_h)) ) 1436 { _M_h.swap(__x._M_h); } 1437 1438 #if __cplusplus > 201402L 1439 template<typename, typename, typename> 1440 friend class std::_Hash_merge_helper; 1441 1442 template<typename _H2, typename _P2> 1443 void 1444 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source) 1445 { 1446 using _Merge_helper 1447 = _Hash_merge_helper<unordered_multiset, _H2, _P2>; 1448 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); 1449 } 1450 1451 template<typename _H2, typename _P2> 1452 void 1453 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source) 1454 { merge(__source); } 1455 1456 template<typename _H2, typename _P2> 1457 void 1458 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source) 1459 { 1460 using _Merge_helper 1461 = _Hash_merge_helper<unordered_multiset, _H2, _P2>; 1462 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); 1463 } 1464 1465 template<typename _H2, typename _P2> 1466 void 1467 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source) 1468 { merge(__source); } 1469 #endif // C++17 1470 1471 // observers. 1472 1473 /// Returns the hash functor object with which the %unordered_multiset 1474 /// was constructed. 1475 hasher 1476 hash_function() const 1477 { return _M_h.hash_function(); } 1478 1479 /// Returns the key comparison object with which the %unordered_multiset 1480 /// was constructed. 1481 key_equal 1482 key_eq() const 1483 { return _M_h.key_eq(); } 1484 1485 // lookup. 1486 1487 ///@{ 1488 /** 1489 * @brief Tries to locate an element in an %unordered_multiset. 1490 * @param __x Element to be located. 1491 * @return Iterator pointing to sought-after element, or end() if not 1492 * found. 1493 * 1494 * This function takes a key and tries to locate the element with which 1495 * the key matches. If successful the function returns an iterator 1496 * pointing to the sought after element. If unsuccessful it returns the 1497 * past-the-end ( @c end() ) iterator. 1498 */ 1499 iterator 1500 find(const key_type& __x) 1501 { return _M_h.find(__x); } 1502 1503 #if __cplusplus > 201703L 1504 template<typename _Kt> 1505 auto 1506 find(const _Kt& __x) 1507 -> decltype(_M_h._M_find_tr(__x)) 1508 { return _M_h._M_find_tr(__x); } 1509 #endif 1510 1511 const_iterator 1512 find(const key_type& __x) const 1513 { return _M_h.find(__x); } 1514 1515 #if __cplusplus > 201703L 1516 template<typename _Kt> 1517 auto 1518 find(const _Kt& __x) const 1519 -> decltype(_M_h._M_find_tr(__x)) 1520 { return _M_h._M_find_tr(__x); } 1521 #endif 1522 ///@} 1523 1524 ///@{ 1525 /** 1526 * @brief Finds the number of elements. 1527 * @param __x Element to located. 1528 * @return Number of elements with specified key. 1529 */ 1530 size_type 1531 count(const key_type& __x) const 1532 { return _M_h.count(__x); } 1533 1534 #if __cplusplus > 201703L 1535 template<typename _Kt> 1536 auto 1537 count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x)) 1538 { return _M_h._M_count_tr(__x); } 1539 #endif 1540 ///@} 1541 1542 #if __cplusplus > 201703L 1543 ///@{ 1544 /** 1545 * @brief Finds whether an element with the given key exists. 1546 * @param __x Key of elements to be located. 1547 * @return True if there is any element with the specified key. 1548 */ 1549 bool 1550 contains(const key_type& __x) const 1551 { return _M_h.find(__x) != _M_h.end(); } 1552 1553 template<typename _Kt> 1554 auto 1555 contains(const _Kt& __x) const 1556 -> decltype(_M_h._M_find_tr(__x), void(), true) 1557 { return _M_h._M_find_tr(__x) != _M_h.end(); } 1558 ///@} 1559 #endif 1560 1561 ///@{ 1562 /** 1563 * @brief Finds a subsequence matching given key. 1564 * @param __x Key to be located. 1565 * @return Pair of iterators that possibly points to the subsequence 1566 * matching given key. 1567 */ 1568 std::pair<iterator, iterator> 1569 equal_range(const key_type& __x) 1570 { return _M_h.equal_range(__x); } 1571 1572 #if __cplusplus > 201703L 1573 template<typename _Kt> 1574 auto 1575 equal_range(const _Kt& __x) 1576 -> decltype(_M_h._M_equal_range_tr(__x)) 1577 { return _M_h._M_equal_range_tr(__x); } 1578 #endif 1579 1580 std::pair<const_iterator, const_iterator> 1581 equal_range(const key_type& __x) const 1582 { return _M_h.equal_range(__x); } 1583 1584 #if __cplusplus > 201703L 1585 template<typename _Kt> 1586 auto 1587 equal_range(const _Kt& __x) const 1588 -> decltype(_M_h._M_equal_range_tr(__x)) 1589 { return _M_h._M_equal_range_tr(__x); } 1590 #endif 1591 ///@} 1592 1593 // bucket interface. 1594 1595 /// Returns the number of buckets of the %unordered_multiset. 1596 size_type 1597 bucket_count() const noexcept 1598 { return _M_h.bucket_count(); } 1599 1600 /// Returns the maximum number of buckets of the %unordered_multiset. 1601 size_type 1602 max_bucket_count() const noexcept 1603 { return _M_h.max_bucket_count(); } 1604 1605 /* 1606 * @brief Returns the number of elements in a given bucket. 1607 * @param __n A bucket index. 1608 * @return The number of elements in the bucket. 1609 */ 1610 size_type 1611 bucket_size(size_type __n) const 1612 { return _M_h.bucket_size(__n); } 1613 1614 /* 1615 * @brief Returns the bucket index of a given element. 1616 * @param __key A key instance. 1617 * @return The key bucket index. 1618 */ 1619 size_type 1620 bucket(const key_type& __key) const 1621 { return _M_h.bucket(__key); } 1622 1623 ///@{ 1624 /** 1625 * @brief Returns a read-only (constant) iterator pointing to the first 1626 * bucket element. 1627 * @param __n The bucket index. 1628 * @return A read-only local iterator. 1629 */ 1630 local_iterator 1631 begin(size_type __n) 1632 { return _M_h.begin(__n); } 1633 1634 const_local_iterator 1635 begin(size_type __n) const 1636 { return _M_h.begin(__n); } 1637 1638 const_local_iterator 1639 cbegin(size_type __n) const 1640 { return _M_h.cbegin(__n); } 1641 ///@} 1642 1643 ///@{ 1644 /** 1645 * @brief Returns a read-only (constant) iterator pointing to one past 1646 * the last bucket elements. 1647 * @param __n The bucket index. 1648 * @return A read-only local iterator. 1649 */ 1650 local_iterator 1651 end(size_type __n) 1652 { return _M_h.end(__n); } 1653 1654 const_local_iterator 1655 end(size_type __n) const 1656 { return _M_h.end(__n); } 1657 1658 const_local_iterator 1659 cend(size_type __n) const 1660 { return _M_h.cend(__n); } 1661 ///@} 1662 1663 // hash policy. 1664 1665 /// Returns the average number of elements per bucket. 1666 float 1667 load_factor() const noexcept 1668 { return _M_h.load_factor(); } 1669 1670 /// Returns a positive number that the %unordered_multiset tries to keep the 1671 /// load factor less than or equal to. 1672 float 1673 max_load_factor() const noexcept 1674 { return _M_h.max_load_factor(); } 1675 1676 /** 1677 * @brief Change the %unordered_multiset maximum load factor. 1678 * @param __z The new maximum load factor. 1679 */ 1680 void 1681 max_load_factor(float __z) 1682 { _M_h.max_load_factor(__z); } 1683 1684 /** 1685 * @brief May rehash the %unordered_multiset. 1686 * @param __n The new number of buckets. 1687 * 1688 * Rehash will occur only if the new number of buckets respect the 1689 * %unordered_multiset maximum load factor. 1690 */ 1691 void 1692 rehash(size_type __n) 1693 { _M_h.rehash(__n); } 1694 1695 /** 1696 * @brief Prepare the %unordered_multiset for a specified number of 1697 * elements. 1698 * @param __n Number of elements required. 1699 * 1700 * Same as rehash(ceil(n / max_load_factor())). 1701 */ 1702 void 1703 reserve(size_type __n) 1704 { _M_h.reserve(__n); } 1705 1706 template<typename _Value1, typename _Hash1, typename _Pred1, 1707 typename _Alloc1> 1708 friend bool 1709 operator==(const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&, 1710 const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&); 1711 }; 1712 1713 1714 #if __cpp_deduction_guides >= 201606 1715 1716 template<typename _InputIterator, 1717 typename _Hash = 1718 hash<typename iterator_traits<_InputIterator>::value_type>, 1719 typename _Pred = 1720 equal_to<typename iterator_traits<_InputIterator>::value_type>, 1721 typename _Allocator = 1722 allocator<typename iterator_traits<_InputIterator>::value_type>, 1723 typename = _RequireInputIter<_InputIterator>, 1724 typename = _RequireNotAllocatorOrIntegral<_Hash>, 1725 typename = _RequireNotAllocator<_Pred>, 1726 typename = _RequireAllocator<_Allocator>> 1727 unordered_multiset(_InputIterator, _InputIterator, 1728 unordered_multiset<int>::size_type = {}, 1729 _Hash = _Hash(), _Pred = _Pred(), 1730 _Allocator = _Allocator()) 1731 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type, 1732 _Hash, _Pred, _Allocator>; 1733 1734 template<typename _Tp, typename _Hash = hash<_Tp>, 1735 typename _Pred = equal_to<_Tp>, 1736 typename _Allocator = allocator<_Tp>, 1737 typename = _RequireNotAllocatorOrIntegral<_Hash>, 1738 typename = _RequireNotAllocator<_Pred>, 1739 typename = _RequireAllocator<_Allocator>> 1740 unordered_multiset(initializer_list<_Tp>, 1741 unordered_multiset<int>::size_type = {}, 1742 _Hash = _Hash(), _Pred = _Pred(), 1743 _Allocator = _Allocator()) 1744 -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>; 1745 1746 template<typename _InputIterator, typename _Allocator, 1747 typename = _RequireInputIter<_InputIterator>, 1748 typename = _RequireAllocator<_Allocator>> 1749 unordered_multiset(_InputIterator, _InputIterator, 1750 unordered_multiset<int>::size_type, _Allocator) 1751 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type, 1752 hash<typename 1753 iterator_traits<_InputIterator>::value_type>, 1754 equal_to<typename 1755 iterator_traits<_InputIterator>::value_type>, 1756 _Allocator>; 1757 1758 template<typename _InputIterator, typename _Hash, typename _Allocator, 1759 typename = _RequireInputIter<_InputIterator>, 1760 typename = _RequireNotAllocatorOrIntegral<_Hash>, 1761 typename = _RequireAllocator<_Allocator>> 1762 unordered_multiset(_InputIterator, _InputIterator, 1763 unordered_multiset<int>::size_type, 1764 _Hash, _Allocator) 1765 -> unordered_multiset<typename 1766 iterator_traits<_InputIterator>::value_type, 1767 _Hash, 1768 equal_to< 1769 typename 1770 iterator_traits<_InputIterator>::value_type>, 1771 _Allocator>; 1772 1773 template<typename _Tp, typename _Allocator, 1774 typename = _RequireAllocator<_Allocator>> 1775 unordered_multiset(initializer_list<_Tp>, 1776 unordered_multiset<int>::size_type, _Allocator) 1777 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 1778 1779 template<typename _Tp, typename _Hash, typename _Allocator, 1780 typename = _RequireNotAllocatorOrIntegral<_Hash>, 1781 typename = _RequireAllocator<_Allocator>> 1782 unordered_multiset(initializer_list<_Tp>, 1783 unordered_multiset<int>::size_type, _Hash, _Allocator) 1784 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 1785 1786 #endif 1787 1788 template<class _Value, class _Hash, class _Pred, class _Alloc> 1789 inline void 1790 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 1791 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 1792 noexcept(noexcept(__x.swap(__y))) 1793 { __x.swap(__y); } 1794 1795 template<class _Value, class _Hash, class _Pred, class _Alloc> 1796 inline void 1797 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1798 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1799 noexcept(noexcept(__x.swap(__y))) 1800 { __x.swap(__y); } 1801 1802 template<class _Value, class _Hash, class _Pred, class _Alloc> 1803 inline bool 1804 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 1805 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 1806 { return __x._M_h._M_equal(__y._M_h); } 1807 1808 #if __cpp_impl_three_way_comparison < 201907L 1809 template<class _Value, class _Hash, class _Pred, class _Alloc> 1810 inline bool 1811 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 1812 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 1813 { return !(__x == __y); } 1814 #endif 1815 1816 template<class _Value, class _Hash, class _Pred, class _Alloc> 1817 inline bool 1818 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1819 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1820 { return __x._M_h._M_equal(__y._M_h); } 1821 1822 #if __cpp_impl_three_way_comparison < 201907L 1823 template<class _Value, class _Hash, class _Pred, class _Alloc> 1824 inline bool 1825 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 1826 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 1827 { return !(__x == __y); } 1828 #endif 1829 1830 _GLIBCXX_END_NAMESPACE_CONTAINER 1831 1832 #if __cplusplus > 201402L 1833 // Allow std::unordered_set access to internals of compatible sets. 1834 template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc, 1835 typename _Hash2, typename _Eq2> 1836 struct _Hash_merge_helper< 1837 _GLIBCXX_STD_C::unordered_set<_Val, _Hash1, _Eq1, _Alloc>, _Hash2, _Eq2> 1838 { 1839 private: 1840 template<typename... _Tp> 1841 using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>; 1842 template<typename... _Tp> 1843 using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>; 1844 1845 friend unordered_set<_Val, _Hash1, _Eq1, _Alloc>; 1846 1847 static auto& 1848 _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set) 1849 { return __set._M_h; } 1850 1851 static auto& 1852 _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set) 1853 { return __set._M_h; } 1854 }; 1855 1856 // Allow std::unordered_multiset access to internals of compatible sets. 1857 template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc, 1858 typename _Hash2, typename _Eq2> 1859 struct _Hash_merge_helper< 1860 _GLIBCXX_STD_C::unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>, 1861 _Hash2, _Eq2> 1862 { 1863 private: 1864 template<typename... _Tp> 1865 using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>; 1866 template<typename... _Tp> 1867 using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>; 1868 1869 friend unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>; 1870 1871 static auto& 1872 _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set) 1873 { return __set._M_h; } 1874 1875 static auto& 1876 _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set) 1877 { return __set._M_h; } 1878 }; 1879 #endif // C++17 1880 1881 _GLIBCXX_END_NAMESPACE_VERSION 1882 } // namespace std 1883 1884 #endif /* _UNORDERED_SET_H */ 1885