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