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