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