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