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