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