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