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