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