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