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, typename = typename 589 std::enable_if<std::is_constructible<value_type, 590 _Pair&&>::value>::type> 591 std::pair<iterator, bool> 592 insert(_Pair&& __x) 593 { return _M_h.insert(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, typename = typename 629 std::enable_if<std::is_constructible<value_type, 630 _Pair&&>::value>::type> 631 iterator 632 insert(const_iterator __hint, _Pair&& __x) 633 { return _M_h.insert(__hint, std::forward<_Pair>(__x)); } 634 //@} 635 636 /** 637 * @brief A template function that attempts to insert a range of 638 * elements. 639 * @param __first Iterator pointing to the start of the range to be 640 * inserted. 641 * @param __last Iterator pointing to the end of the range. 642 * 643 * Complexity similar to that of the range constructor. 644 */ 645 template<typename _InputIterator> 646 void 647 insert(_InputIterator __first, _InputIterator __last) 648 { _M_h.insert(__first, __last); } 649 650 /** 651 * @brief Attempts to insert a list of elements into the %unordered_map. 652 * @param __l A std::initializer_list<value_type> of elements 653 * to be inserted. 654 * 655 * Complexity similar to that of the range constructor. 656 */ 657 void 658 insert(initializer_list<value_type> __l) 659 { _M_h.insert(__l); } 660 661 662 #if __cplusplus > 201402L 663 #define __cpp_lib_unordered_map_insertion 201411 664 /** 665 * @brief Attempts to insert a std::pair into the %unordered_map. 666 * @param __k Key to use for finding a possibly existing pair in 667 * the map. 668 * @param __obj Argument used to generate the .second for a pair 669 * instance. 670 * 671 * @return A pair, of which the first element is an iterator that 672 * points to the possibly inserted pair, and the second is 673 * a bool that is true if the pair was actually inserted. 674 * 675 * This function attempts to insert a (key, value) %pair into the 676 * %unordered_map. An %unordered_map relies on unique keys and thus a 677 * %pair is only inserted if its first element (the key) is not already 678 * present in the %unordered_map. 679 * If the %pair was already in the %unordered_map, the .second of 680 * the %pair is assigned from __obj. 681 * 682 * Insertion requires amortized constant time. 683 */ 684 template <typename _Obj> 685 pair<iterator, bool> 686 insert_or_assign(const key_type& __k, _Obj&& __obj) 687 { 688 iterator __i = find(__k); 689 if (__i == end()) 690 { 691 __i = emplace(std::piecewise_construct, 692 std::forward_as_tuple(__k), 693 std::forward_as_tuple(std::forward<_Obj>(__obj))) 694 .first; 695 return {__i, true}; 696 } 697 (*__i).second = std::forward<_Obj>(__obj); 698 return {__i, false}; 699 } 700 701 // move-capable overload 702 template <typename _Obj> 703 pair<iterator, bool> 704 insert_or_assign(key_type&& __k, _Obj&& __obj) 705 { 706 iterator __i = find(__k); 707 if (__i == end()) 708 { 709 __i = emplace(std::piecewise_construct, 710 std::forward_as_tuple(std::move(__k)), 711 std::forward_as_tuple(std::forward<_Obj>(__obj))) 712 .first; 713 return {__i, true}; 714 } 715 (*__i).second = std::forward<_Obj>(__obj); 716 return {__i, false}; 717 } 718 719 /** 720 * @brief Attempts to insert a std::pair into the %unordered_map. 721 * @param __hint An iterator that serves as a hint as to where the 722 * pair should be inserted. 723 * @param __k Key to use for finding a possibly existing pair in 724 * the unordered_map. 725 * @param __obj Argument used to generate the .second for a pair 726 * instance. 727 * @return An iterator that points to the element with key of 728 * @a __x (may or may not be the %pair passed in). 729 * 730 * This function is not concerned about whether the insertion took place, 731 * and thus does not return a boolean like the single-argument insert() 732 * does. 733 * If the %pair was already in the %unordered map, the .second of 734 * the %pair is assigned from __obj. 735 * Note that the first parameter is only a hint and can 736 * potentially improve the performance of the insertion process. A bad 737 * hint would cause no gains in efficiency. 738 * 739 * See 740 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 741 * for more on @a hinting. 742 * 743 * Insertion requires amortized constant time. 744 */ 745 template <typename _Obj> 746 iterator 747 insert_or_assign(const_iterator __hint, const key_type& __k, 748 _Obj&& __obj) 749 { 750 iterator __i = find(__k); 751 if (__i == end()) 752 { 753 return emplace_hint(__hint, std::piecewise_construct, 754 std::forward_as_tuple(__k), 755 std::forward_as_tuple( 756 std::forward<_Obj>(__obj))); 757 } 758 (*__i).second = std::forward<_Obj>(__obj); 759 return __i; 760 } 761 762 // move-capable overload 763 template <typename _Obj> 764 iterator 765 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj) 766 { 767 iterator __i = find(__k); 768 if (__i == end()) 769 { 770 return emplace_hint(__hint, std::piecewise_construct, 771 std::forward_as_tuple(std::move(__k)), 772 std::forward_as_tuple( 773 std::forward<_Obj>(__obj))); 774 } 775 (*__i).second = std::forward<_Obj>(__obj); 776 return __i; 777 } 778 #endif 779 780 //@{ 781 /** 782 * @brief Erases an element from an %unordered_map. 783 * @param __position An iterator pointing to the element to be erased. 784 * @return An iterator pointing to the element immediately following 785 * @a __position prior to the element being erased. If no such 786 * element exists, end() is returned. 787 * 788 * This function erases an element, pointed to by the given iterator, 789 * from an %unordered_map. 790 * Note that this function only erases the element, and that if the 791 * element is itself a pointer, the pointed-to memory is not touched in 792 * any way. Managing the pointer is the user's responsibility. 793 */ 794 iterator 795 erase(const_iterator __position) 796 { return _M_h.erase(__position); } 797 798 // LWG 2059. 799 iterator 800 erase(iterator __position) 801 { return _M_h.erase(__position); } 802 //@} 803 804 /** 805 * @brief Erases elements according to the provided key. 806 * @param __x Key of element to be erased. 807 * @return The number of elements erased. 808 * 809 * This function erases all the elements located by the given key from 810 * an %unordered_map. For an %unordered_map the result of this function 811 * can only be 0 (not present) or 1 (present). 812 * Note that this function only erases the element, and that if the 813 * element is itself a pointer, the pointed-to memory is not touched in 814 * any way. Managing the pointer is the user's responsibility. 815 */ 816 size_type 817 erase(const key_type& __x) 818 { return _M_h.erase(__x); } 819 820 /** 821 * @brief Erases a [__first,__last) range of elements from an 822 * %unordered_map. 823 * @param __first Iterator pointing to the start of the range to be 824 * erased. 825 * @param __last Iterator pointing to the end of the range to 826 * be erased. 827 * @return The iterator @a __last. 828 * 829 * This function erases a sequence of elements from an %unordered_map. 830 * Note that this function only erases the elements, and that if 831 * the element is itself a pointer, the pointed-to memory is not touched 832 * in any way. Managing the pointer is the user's responsibility. 833 */ 834 iterator 835 erase(const_iterator __first, const_iterator __last) 836 { return _M_h.erase(__first, __last); } 837 838 /** 839 * Erases all elements in an %unordered_map. 840 * Note that this function only erases the elements, and that if the 841 * elements themselves are pointers, the pointed-to memory is not touched 842 * in any way. Managing the pointer is the user's responsibility. 843 */ 844 void 845 clear() noexcept 846 { _M_h.clear(); } 847 848 /** 849 * @brief Swaps data with another %unordered_map. 850 * @param __x An %unordered_map of the same element and allocator 851 * types. 852 * 853 * This exchanges the elements between two %unordered_map in constant 854 * time. 855 * Note that the global std::swap() function is specialized such that 856 * std::swap(m1,m2) will feed to this function. 857 */ 858 void 859 swap(unordered_map& __x) 860 noexcept( noexcept(_M_h.swap(__x._M_h)) ) 861 { _M_h.swap(__x._M_h); } 862 863 #if __cplusplus > 201402L 864 template<typename, typename, typename> 865 friend class std::_Hash_merge_helper; 866 867 template<typename _H2, typename _P2> 868 void 869 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source) 870 { 871 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>; 872 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source)); 873 } 874 875 template<typename _H2, typename _P2> 876 void 877 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source) 878 { merge(__source); } 879 880 template<typename _H2, typename _P2> 881 void 882 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source) 883 { 884 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>; 885 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source)); 886 } 887 888 template<typename _H2, typename _P2> 889 void 890 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source) 891 { merge(__source); } 892 #endif // C++17 893 894 // observers. 895 896 /// Returns the hash functor object with which the %unordered_map was 897 /// constructed. 898 hasher 899 hash_function() const 900 { return _M_h.hash_function(); } 901 902 /// Returns the key comparison object with which the %unordered_map was 903 /// constructed. 904 key_equal 905 key_eq() const 906 { return _M_h.key_eq(); } 907 908 // lookup. 909 910 //@{ 911 /** 912 * @brief Tries to locate an element in an %unordered_map. 913 * @param __x Key to be located. 914 * @return Iterator pointing to sought-after element, or end() if not 915 * found. 916 * 917 * This function takes a key and tries to locate the element with which 918 * the key matches. If successful the function returns an iterator 919 * pointing to the sought after element. If unsuccessful it returns the 920 * past-the-end ( @c end() ) iterator. 921 */ 922 iterator 923 find(const key_type& __x) 924 { return _M_h.find(__x); } 925 926 const_iterator 927 find(const key_type& __x) const 928 { return _M_h.find(__x); } 929 //@} 930 931 /** 932 * @brief Finds the number of elements. 933 * @param __x Key to count. 934 * @return Number of elements with specified key. 935 * 936 * This function only makes sense for %unordered_multimap; for 937 * %unordered_map the result will either be 0 (not present) or 1 938 * (present). 939 */ 940 size_type 941 count(const key_type& __x) const 942 { return _M_h.count(__x); } 943 944 //@{ 945 /** 946 * @brief Finds a subsequence matching given key. 947 * @param __x Key to be located. 948 * @return Pair of iterators that possibly points to the subsequence 949 * matching given key. 950 * 951 * This function probably only makes sense for %unordered_multimap. 952 */ 953 std::pair<iterator, iterator> 954 equal_range(const key_type& __x) 955 { return _M_h.equal_range(__x); } 956 957 std::pair<const_iterator, const_iterator> 958 equal_range(const key_type& __x) const 959 { return _M_h.equal_range(__x); } 960 //@} 961 962 //@{ 963 /** 964 * @brief Subscript ( @c [] ) access to %unordered_map data. 965 * @param __k The key for which data should be retrieved. 966 * @return A reference to the data of the (key,data) %pair. 967 * 968 * Allows for easy lookup with the subscript ( @c [] )operator. Returns 969 * data associated with the key specified in subscript. If the key does 970 * not exist, a pair with that key is created using default values, which 971 * is then returned. 972 * 973 * Lookup requires constant time. 974 */ 975 mapped_type& 976 operator[](const key_type& __k) 977 { return _M_h[__k]; } 978 979 mapped_type& 980 operator[](key_type&& __k) 981 { return _M_h[std::move(__k)]; } 982 //@} 983 984 //@{ 985 /** 986 * @brief Access to %unordered_map data. 987 * @param __k The key for which data should be retrieved. 988 * @return A reference to the data whose key is equal to @a __k, if 989 * such a data is present in the %unordered_map. 990 * @throw std::out_of_range If no such data is present. 991 */ 992 mapped_type& 993 at(const key_type& __k) 994 { return _M_h.at(__k); } 995 996 const mapped_type& 997 at(const key_type& __k) const 998 { return _M_h.at(__k); } 999 //@} 1000 1001 // bucket interface. 1002 1003 /// Returns the number of buckets of the %unordered_map. 1004 size_type 1005 bucket_count() const noexcept 1006 { return _M_h.bucket_count(); } 1007 1008 /// Returns the maximum number of buckets of the %unordered_map. 1009 size_type 1010 max_bucket_count() const noexcept 1011 { return _M_h.max_bucket_count(); } 1012 1013 /* 1014 * @brief Returns the number of elements in a given bucket. 1015 * @param __n A bucket index. 1016 * @return The number of elements in the bucket. 1017 */ 1018 size_type 1019 bucket_size(size_type __n) const 1020 { return _M_h.bucket_size(__n); } 1021 1022 /* 1023 * @brief Returns the bucket index of a given element. 1024 * @param __key A key instance. 1025 * @return The key bucket index. 1026 */ 1027 size_type 1028 bucket(const key_type& __key) const 1029 { return _M_h.bucket(__key); } 1030 1031 /** 1032 * @brief Returns a read/write iterator pointing to the first bucket 1033 * element. 1034 * @param __n The bucket index. 1035 * @return A read/write local iterator. 1036 */ 1037 local_iterator 1038 begin(size_type __n) 1039 { return _M_h.begin(__n); } 1040 1041 //@{ 1042 /** 1043 * @brief Returns a read-only (constant) iterator pointing to the first 1044 * bucket element. 1045 * @param __n The bucket index. 1046 * @return A read-only local iterator. 1047 */ 1048 const_local_iterator 1049 begin(size_type __n) const 1050 { return _M_h.begin(__n); } 1051 1052 const_local_iterator 1053 cbegin(size_type __n) const 1054 { return _M_h.cbegin(__n); } 1055 //@} 1056 1057 /** 1058 * @brief Returns a read/write iterator pointing to one past the last 1059 * bucket elements. 1060 * @param __n The bucket index. 1061 * @return A read/write local iterator. 1062 */ 1063 local_iterator 1064 end(size_type __n) 1065 { return _M_h.end(__n); } 1066 1067 //@{ 1068 /** 1069 * @brief Returns a read-only (constant) iterator pointing to one past 1070 * the last bucket elements. 1071 * @param __n The bucket index. 1072 * @return A read-only local iterator. 1073 */ 1074 const_local_iterator 1075 end(size_type __n) const 1076 { return _M_h.end(__n); } 1077 1078 const_local_iterator 1079 cend(size_type __n) const 1080 { return _M_h.cend(__n); } 1081 //@} 1082 1083 // hash policy. 1084 1085 /// Returns the average number of elements per bucket. 1086 float 1087 load_factor() const noexcept 1088 { return _M_h.load_factor(); } 1089 1090 /// Returns a positive number that the %unordered_map tries to keep the 1091 /// load factor less than or equal to. 1092 float 1093 max_load_factor() const noexcept 1094 { return _M_h.max_load_factor(); } 1095 1096 /** 1097 * @brief Change the %unordered_map maximum load factor. 1098 * @param __z The new maximum load factor. 1099 */ 1100 void 1101 max_load_factor(float __z) 1102 { _M_h.max_load_factor(__z); } 1103 1104 /** 1105 * @brief May rehash the %unordered_map. 1106 * @param __n The new number of buckets. 1107 * 1108 * Rehash will occur only if the new number of buckets respect the 1109 * %unordered_map maximum load factor. 1110 */ 1111 void 1112 rehash(size_type __n) 1113 { _M_h.rehash(__n); } 1114 1115 /** 1116 * @brief Prepare the %unordered_map for a specified number of 1117 * elements. 1118 * @param __n Number of elements required. 1119 * 1120 * Same as rehash(ceil(n / max_load_factor())). 1121 */ 1122 void 1123 reserve(size_type __n) 1124 { _M_h.reserve(__n); } 1125 1126 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1, 1127 typename _Alloc1> 1128 friend bool 1129 operator==(const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&, 1130 const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&); 1131 }; 1132 1133 #if __cpp_deduction_guides >= 201606 1134 1135 template<typename _InputIterator, 1136 typename _Hash = hash<__iter_key_t<_InputIterator>>, 1137 typename _Pred = equal_to<__iter_key_t<_InputIterator>>, 1138 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, 1139 typename = _RequireInputIter<_InputIterator>, 1140 typename = _RequireAllocator<_Allocator>> 1141 unordered_map(_InputIterator, _InputIterator, 1142 typename unordered_map<int, int>::size_type = {}, 1143 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 1144 -> unordered_map<__iter_key_t<_InputIterator>, 1145 __iter_val_t<_InputIterator>, 1146 _Hash, _Pred, _Allocator>; 1147 1148 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>, 1149 typename _Pred = equal_to<_Key>, 1150 typename _Allocator = allocator<pair<const _Key, _Tp>>, 1151 typename = _RequireAllocator<_Allocator>> 1152 unordered_map(initializer_list<pair<_Key, _Tp>>, 1153 typename unordered_map<int, int>::size_type = {}, 1154 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 1155 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>; 1156 1157 template<typename _InputIterator, typename _Allocator, 1158 typename = _RequireInputIter<_InputIterator>, 1159 typename = _RequireAllocator<_Allocator>> 1160 unordered_map(_InputIterator, _InputIterator, 1161 typename unordered_map<int, int>::size_type, _Allocator) 1162 -> unordered_map<__iter_key_t<_InputIterator>, 1163 __iter_val_t<_InputIterator>, 1164 hash<__iter_key_t<_InputIterator>>, 1165 equal_to<__iter_key_t<_InputIterator>>, 1166 _Allocator>; 1167 1168 template<typename _InputIterator, typename _Allocator, 1169 typename = _RequireInputIter<_InputIterator>, 1170 typename = _RequireAllocator<_Allocator>> 1171 unordered_map(_InputIterator, _InputIterator, _Allocator) 1172 -> unordered_map<__iter_key_t<_InputIterator>, 1173 __iter_val_t<_InputIterator>, 1174 hash<__iter_key_t<_InputIterator>>, 1175 equal_to<__iter_key_t<_InputIterator>>, 1176 _Allocator>; 1177 1178 template<typename _InputIterator, typename _Hash, typename _Allocator, 1179 typename = _RequireInputIter<_InputIterator>, 1180 typename = _RequireAllocator<_Allocator>> 1181 unordered_map(_InputIterator, _InputIterator, 1182 typename unordered_map<int, int>::size_type, 1183 _Hash, _Allocator) 1184 -> unordered_map<__iter_key_t<_InputIterator>, 1185 __iter_val_t<_InputIterator>, _Hash, 1186 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 1187 1188 template<typename _Key, typename _Tp, typename _Allocator, 1189 typename = _RequireAllocator<_Allocator>> 1190 unordered_map(initializer_list<pair<_Key, _Tp>>, 1191 typename unordered_map<int, int>::size_type, 1192 _Allocator) 1193 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 1194 1195 template<typename _Key, typename _Tp, typename _Allocator, 1196 typename = _RequireAllocator<_Allocator>> 1197 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator) 1198 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 1199 1200 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator, 1201 typename = _RequireAllocator<_Allocator>> 1202 unordered_map(initializer_list<pair<_Key, _Tp>>, 1203 typename unordered_map<int, int>::size_type, 1204 _Hash, _Allocator) 1205 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>; 1206 1207 #endif 1208 1209 /** 1210 * @brief A standard container composed of equivalent keys 1211 * (possibly containing multiple of each key value) that associates 1212 * values of another type with the keys. 1213 * 1214 * @ingroup unordered_associative_containers 1215 * 1216 * @tparam _Key Type of key objects. 1217 * @tparam _Tp Type of mapped objects. 1218 * @tparam _Hash Hashing function object type, defaults to hash<_Value>. 1219 * @tparam _Pred Predicate function object type, defaults 1220 * to equal_to<_Value>. 1221 * @tparam _Alloc Allocator type, defaults to 1222 * std::allocator<std::pair<const _Key, _Tp>>. 1223 * 1224 * Meets the requirements of a <a href="tables.html#65">container</a>, and 1225 * <a href="tables.html#xx">unordered associative container</a> 1226 * 1227 * The resulting value type of the container is std::pair<const _Key, _Tp>. 1228 * 1229 * Base is _Hashtable, dispatched at compile time via template 1230 * alias __ummap_hashtable. 1231 */ 1232 template<typename _Key, typename _Tp, 1233 typename _Hash = hash<_Key>, 1234 typename _Pred = equal_to<_Key>, 1235 typename _Alloc = allocator<std::pair<const _Key, _Tp>>> 1236 class unordered_multimap 1237 { 1238 typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable; 1239 _Hashtable _M_h; 1240 1241 public: 1242 // typedefs: 1243 //@{ 1244 /// Public typedefs. 1245 typedef typename _Hashtable::key_type key_type; 1246 typedef typename _Hashtable::value_type value_type; 1247 typedef typename _Hashtable::mapped_type mapped_type; 1248 typedef typename _Hashtable::hasher hasher; 1249 typedef typename _Hashtable::key_equal key_equal; 1250 typedef typename _Hashtable::allocator_type allocator_type; 1251 //@} 1252 1253 //@{ 1254 /// Iterator-related typedefs. 1255 typedef typename _Hashtable::pointer pointer; 1256 typedef typename _Hashtable::const_pointer const_pointer; 1257 typedef typename _Hashtable::reference reference; 1258 typedef typename _Hashtable::const_reference const_reference; 1259 typedef typename _Hashtable::iterator iterator; 1260 typedef typename _Hashtable::const_iterator const_iterator; 1261 typedef typename _Hashtable::local_iterator local_iterator; 1262 typedef typename _Hashtable::const_local_iterator const_local_iterator; 1263 typedef typename _Hashtable::size_type size_type; 1264 typedef typename _Hashtable::difference_type difference_type; 1265 //@} 1266 1267 #if __cplusplus > 201402L 1268 using node_type = typename _Hashtable::node_type; 1269 #endif 1270 1271 //construct/destroy/copy 1272 1273 /// Default constructor. 1274 unordered_multimap() = default; 1275 1276 /** 1277 * @brief Default constructor creates no elements. 1278 * @param __n Mnimal initial number of buckets. 1279 * @param __hf A hash functor. 1280 * @param __eql A key equality functor. 1281 * @param __a An allocator object. 1282 */ 1283 explicit 1284 unordered_multimap(size_type __n, 1285 const hasher& __hf = hasher(), 1286 const key_equal& __eql = key_equal(), 1287 const allocator_type& __a = allocator_type()) 1288 : _M_h(__n, __hf, __eql, __a) 1289 { } 1290 1291 /** 1292 * @brief Builds an %unordered_multimap from a range. 1293 * @param __first An input iterator. 1294 * @param __last An input iterator. 1295 * @param __n Minimal initial number of buckets. 1296 * @param __hf A hash functor. 1297 * @param __eql A key equality functor. 1298 * @param __a An allocator object. 1299 * 1300 * Create an %unordered_multimap consisting of copies of the elements 1301 * from [__first,__last). This is linear in N (where N is 1302 * distance(__first,__last)). 1303 */ 1304 template<typename _InputIterator> 1305 unordered_multimap(_InputIterator __first, _InputIterator __last, 1306 size_type __n = 0, 1307 const hasher& __hf = hasher(), 1308 const key_equal& __eql = key_equal(), 1309 const allocator_type& __a = allocator_type()) 1310 : _M_h(__first, __last, __n, __hf, __eql, __a) 1311 { } 1312 1313 /// Copy constructor. 1314 unordered_multimap(const unordered_multimap&) = default; 1315 1316 /// Move constructor. 1317 unordered_multimap(unordered_multimap&&) = default; 1318 1319 /** 1320 * @brief Creates an %unordered_multimap with no elements. 1321 * @param __a An allocator object. 1322 */ 1323 explicit 1324 unordered_multimap(const allocator_type& __a) 1325 : _M_h(__a) 1326 { } 1327 1328 /* 1329 * @brief Copy constructor with allocator argument. 1330 * @param __uset Input %unordered_multimap to copy. 1331 * @param __a An allocator object. 1332 */ 1333 unordered_multimap(const unordered_multimap& __ummap, 1334 const allocator_type& __a) 1335 : _M_h(__ummap._M_h, __a) 1336 { } 1337 1338 /* 1339 * @brief Move constructor with allocator argument. 1340 * @param __uset Input %unordered_multimap to move. 1341 * @param __a An allocator object. 1342 */ 1343 unordered_multimap(unordered_multimap&& __ummap, 1344 const allocator_type& __a) 1345 : _M_h(std::move(__ummap._M_h), __a) 1346 { } 1347 1348 /** 1349 * @brief Builds an %unordered_multimap from an initializer_list. 1350 * @param __l An initializer_list. 1351 * @param __n Minimal initial number of buckets. 1352 * @param __hf A hash functor. 1353 * @param __eql A key equality functor. 1354 * @param __a An allocator object. 1355 * 1356 * Create an %unordered_multimap consisting of copies of the elements in 1357 * the list. This is linear in N (where N is @a __l.size()). 1358 */ 1359 unordered_multimap(initializer_list<value_type> __l, 1360 size_type __n = 0, 1361 const hasher& __hf = hasher(), 1362 const key_equal& __eql = key_equal(), 1363 const allocator_type& __a = allocator_type()) 1364 : _M_h(__l, __n, __hf, __eql, __a) 1365 { } 1366 1367 unordered_multimap(size_type __n, const allocator_type& __a) 1368 : unordered_multimap(__n, hasher(), key_equal(), __a) 1369 { } 1370 1371 unordered_multimap(size_type __n, const hasher& __hf, 1372 const allocator_type& __a) 1373 : unordered_multimap(__n, __hf, key_equal(), __a) 1374 { } 1375 1376 template<typename _InputIterator> 1377 unordered_multimap(_InputIterator __first, _InputIterator __last, 1378 size_type __n, 1379 const allocator_type& __a) 1380 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) 1381 { } 1382 1383 template<typename _InputIterator> 1384 unordered_multimap(_InputIterator __first, _InputIterator __last, 1385 size_type __n, const hasher& __hf, 1386 const allocator_type& __a) 1387 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) 1388 { } 1389 1390 unordered_multimap(initializer_list<value_type> __l, 1391 size_type __n, 1392 const allocator_type& __a) 1393 : unordered_multimap(__l, __n, hasher(), key_equal(), __a) 1394 { } 1395 1396 unordered_multimap(initializer_list<value_type> __l, 1397 size_type __n, const hasher& __hf, 1398 const allocator_type& __a) 1399 : unordered_multimap(__l, __n, __hf, key_equal(), __a) 1400 { } 1401 1402 /// Copy assignment operator. 1403 unordered_multimap& 1404 operator=(const unordered_multimap&) = default; 1405 1406 /// Move assignment operator. 1407 unordered_multimap& 1408 operator=(unordered_multimap&&) = default; 1409 1410 /** 1411 * @brief %Unordered_multimap list assignment operator. 1412 * @param __l An initializer_list. 1413 * 1414 * This function fills an %unordered_multimap with copies of the 1415 * elements in the initializer list @a __l. 1416 * 1417 * Note that the assignment completely changes the %unordered_multimap 1418 * and that the resulting %unordered_multimap's size is the same as the 1419 * number of elements assigned. 1420 */ 1421 unordered_multimap& 1422 operator=(initializer_list<value_type> __l) 1423 { 1424 _M_h = __l; 1425 return *this; 1426 } 1427 1428 /// Returns the allocator object used by the %unordered_multimap. 1429 allocator_type 1430 get_allocator() const noexcept 1431 { return _M_h.get_allocator(); } 1432 1433 // size and capacity: 1434 1435 /// Returns true if the %unordered_multimap is empty. 1436 bool 1437 empty() const noexcept 1438 { return _M_h.empty(); } 1439 1440 /// Returns the size of the %unordered_multimap. 1441 size_type 1442 size() const noexcept 1443 { return _M_h.size(); } 1444 1445 /// Returns the maximum size of the %unordered_multimap. 1446 size_type 1447 max_size() const noexcept 1448 { return _M_h.max_size(); } 1449 1450 // iterators. 1451 1452 /** 1453 * Returns a read/write iterator that points to the first element in the 1454 * %unordered_multimap. 1455 */ 1456 iterator 1457 begin() noexcept 1458 { return _M_h.begin(); } 1459 1460 //@{ 1461 /** 1462 * Returns a read-only (constant) iterator that points to the first 1463 * element in the %unordered_multimap. 1464 */ 1465 const_iterator 1466 begin() const noexcept 1467 { return _M_h.begin(); } 1468 1469 const_iterator 1470 cbegin() const noexcept 1471 { return _M_h.begin(); } 1472 //@} 1473 1474 /** 1475 * Returns a read/write iterator that points one past the last element in 1476 * the %unordered_multimap. 1477 */ 1478 iterator 1479 end() noexcept 1480 { return _M_h.end(); } 1481 1482 //@{ 1483 /** 1484 * Returns a read-only (constant) iterator that points one past the last 1485 * element in the %unordered_multimap. 1486 */ 1487 const_iterator 1488 end() const noexcept 1489 { return _M_h.end(); } 1490 1491 const_iterator 1492 cend() const noexcept 1493 { return _M_h.end(); } 1494 //@} 1495 1496 // modifiers. 1497 1498 /** 1499 * @brief Attempts to build and insert a std::pair into the 1500 * %unordered_multimap. 1501 * 1502 * @param __args Arguments used to generate a new pair instance (see 1503 * std::piecewise_contruct for passing arguments to each 1504 * part of the pair constructor). 1505 * 1506 * @return An iterator that points to the inserted pair. 1507 * 1508 * This function attempts to build and insert a (key, value) %pair into 1509 * the %unordered_multimap. 1510 * 1511 * Insertion requires amortized constant time. 1512 */ 1513 template<typename... _Args> 1514 iterator 1515 emplace(_Args&&... __args) 1516 { return _M_h.emplace(std::forward<_Args>(__args)...); } 1517 1518 /** 1519 * @brief Attempts to build and insert a std::pair into the 1520 * %unordered_multimap. 1521 * 1522 * @param __pos An iterator that serves as a hint as to where the pair 1523 * should be inserted. 1524 * @param __args Arguments used to generate a new pair instance (see 1525 * std::piecewise_contruct for passing arguments to each 1526 * part of the pair constructor). 1527 * @return An iterator that points to the element with key of the 1528 * std::pair built from @a __args. 1529 * 1530 * Note that the first parameter is only a hint and can potentially 1531 * improve the performance of the insertion process. A bad hint would 1532 * cause no gains in efficiency. 1533 * 1534 * See 1535 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 1536 * for more on @a hinting. 1537 * 1538 * Insertion requires amortized constant time. 1539 */ 1540 template<typename... _Args> 1541 iterator 1542 emplace_hint(const_iterator __pos, _Args&&... __args) 1543 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); } 1544 1545 //@{ 1546 /** 1547 * @brief Inserts a std::pair into the %unordered_multimap. 1548 * @param __x Pair to be inserted (see std::make_pair for easy 1549 * creation of pairs). 1550 * 1551 * @return An iterator that points to the inserted pair. 1552 * 1553 * Insertion requires amortized constant time. 1554 */ 1555 iterator 1556 insert(const value_type& __x) 1557 { return _M_h.insert(__x); } 1558 1559 iterator 1560 insert(value_type&& __x) 1561 { return _M_h.insert(std::move(__x)); } 1562 1563 template<typename _Pair, typename = typename 1564 std::enable_if<std::is_constructible<value_type, 1565 _Pair&&>::value>::type> 1566 iterator 1567 insert(_Pair&& __x) 1568 { return _M_h.insert(std::forward<_Pair>(__x)); } 1569 //@} 1570 1571 //@{ 1572 /** 1573 * @brief Inserts a std::pair into the %unordered_multimap. 1574 * @param __hint An iterator that serves as a hint as to where the 1575 * pair should be inserted. 1576 * @param __x Pair to be inserted (see std::make_pair for easy creation 1577 * of pairs). 1578 * @return An iterator that points to the element with key of 1579 * @a __x (may or may not be the %pair passed in). 1580 * 1581 * Note that the first parameter is only a hint and can potentially 1582 * improve the performance of the insertion process. A bad hint would 1583 * cause no gains in efficiency. 1584 * 1585 * See 1586 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 1587 * for more on @a hinting. 1588 * 1589 * Insertion requires amortized constant time. 1590 */ 1591 iterator 1592 insert(const_iterator __hint, const value_type& __x) 1593 { return _M_h.insert(__hint, __x); } 1594 1595 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1596 // 2354. Unnecessary copying when inserting into maps with braced-init 1597 iterator 1598 insert(const_iterator __hint, value_type&& __x) 1599 { return _M_h.insert(__hint, std::move(__x)); } 1600 1601 template<typename _Pair, typename = typename 1602 std::enable_if<std::is_constructible<value_type, 1603 _Pair&&>::value>::type> 1604 iterator 1605 insert(const_iterator __hint, _Pair&& __x) 1606 { return _M_h.insert(__hint, std::forward<_Pair>(__x)); } 1607 //@} 1608 1609 /** 1610 * @brief A template function that attempts to insert a range of 1611 * elements. 1612 * @param __first Iterator pointing to the start of the range to be 1613 * inserted. 1614 * @param __last Iterator pointing to the end of the range. 1615 * 1616 * Complexity similar to that of the range constructor. 1617 */ 1618 template<typename _InputIterator> 1619 void 1620 insert(_InputIterator __first, _InputIterator __last) 1621 { _M_h.insert(__first, __last); } 1622 1623 /** 1624 * @brief Attempts to insert a list of elements into the 1625 * %unordered_multimap. 1626 * @param __l A std::initializer_list<value_type> of elements 1627 * to be inserted. 1628 * 1629 * Complexity similar to that of the range constructor. 1630 */ 1631 void 1632 insert(initializer_list<value_type> __l) 1633 { _M_h.insert(__l); } 1634 1635 #if __cplusplus > 201402L 1636 /// Extract a node. 1637 node_type 1638 extract(const_iterator __pos) 1639 { 1640 __glibcxx_assert(__pos != end()); 1641 return _M_h.extract(__pos); 1642 } 1643 1644 /// Extract a node. 1645 node_type 1646 extract(const key_type& __key) 1647 { return _M_h.extract(__key); } 1648 1649 /// Re-insert an extracted node. 1650 iterator 1651 insert(node_type&& __nh) 1652 { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); } 1653 1654 /// Re-insert an extracted node. 1655 iterator 1656 insert(const_iterator __hint, node_type&& __nh) 1657 { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); } 1658 #endif // C++17 1659 1660 //@{ 1661 /** 1662 * @brief Erases an element from an %unordered_multimap. 1663 * @param __position An iterator pointing to the element to be erased. 1664 * @return An iterator pointing to the element immediately following 1665 * @a __position prior to the element being erased. If no such 1666 * element exists, end() is returned. 1667 * 1668 * This function erases an element, pointed to by the given iterator, 1669 * from an %unordered_multimap. 1670 * Note that this function only erases the element, and that if the 1671 * element is itself a pointer, the pointed-to memory is not touched in 1672 * any way. Managing the pointer is the user's responsibility. 1673 */ 1674 iterator 1675 erase(const_iterator __position) 1676 { return _M_h.erase(__position); } 1677 1678 // LWG 2059. 1679 iterator 1680 erase(iterator __position) 1681 { return _M_h.erase(__position); } 1682 //@} 1683 1684 /** 1685 * @brief Erases elements according to the provided key. 1686 * @param __x Key of elements to be erased. 1687 * @return The number of elements erased. 1688 * 1689 * This function erases all the elements located by the given key from 1690 * an %unordered_multimap. 1691 * Note that this function only erases the element, and that if the 1692 * element is itself a pointer, the pointed-to memory is not touched in 1693 * any way. Managing the pointer is the user's responsibility. 1694 */ 1695 size_type 1696 erase(const key_type& __x) 1697 { return _M_h.erase(__x); } 1698 1699 /** 1700 * @brief Erases a [__first,__last) range of elements from an 1701 * %unordered_multimap. 1702 * @param __first Iterator pointing to the start of the range to be 1703 * erased. 1704 * @param __last Iterator pointing to the end of the range to 1705 * be erased. 1706 * @return The iterator @a __last. 1707 * 1708 * This function erases a sequence of elements from an 1709 * %unordered_multimap. 1710 * Note that this function only erases the elements, and that if 1711 * the element is itself a pointer, the pointed-to memory is not touched 1712 * in any way. Managing the pointer is the user's responsibility. 1713 */ 1714 iterator 1715 erase(const_iterator __first, const_iterator __last) 1716 { return _M_h.erase(__first, __last); } 1717 1718 /** 1719 * Erases all elements in an %unordered_multimap. 1720 * Note that this function only erases the elements, and that if the 1721 * elements themselves are pointers, the pointed-to memory is not touched 1722 * in any way. Managing the pointer is the user's responsibility. 1723 */ 1724 void 1725 clear() noexcept 1726 { _M_h.clear(); } 1727 1728 /** 1729 * @brief Swaps data with another %unordered_multimap. 1730 * @param __x An %unordered_multimap of the same element and allocator 1731 * types. 1732 * 1733 * This exchanges the elements between two %unordered_multimap in 1734 * constant time. 1735 * Note that the global std::swap() function is specialized such that 1736 * std::swap(m1,m2) will feed to this function. 1737 */ 1738 void 1739 swap(unordered_multimap& __x) 1740 noexcept( noexcept(_M_h.swap(__x._M_h)) ) 1741 { _M_h.swap(__x._M_h); } 1742 1743 #if __cplusplus > 201402L 1744 template<typename, typename, typename> 1745 friend class std::_Hash_merge_helper; 1746 1747 template<typename _H2, typename _P2> 1748 void 1749 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source) 1750 { 1751 using _Merge_helper 1752 = _Hash_merge_helper<unordered_multimap, _H2, _P2>; 1753 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); 1754 } 1755 1756 template<typename _H2, typename _P2> 1757 void 1758 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source) 1759 { merge(__source); } 1760 1761 template<typename _H2, typename _P2> 1762 void 1763 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source) 1764 { 1765 using _Merge_helper 1766 = _Hash_merge_helper<unordered_multimap, _H2, _P2>; 1767 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); 1768 } 1769 1770 template<typename _H2, typename _P2> 1771 void 1772 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source) 1773 { merge(__source); } 1774 #endif // C++17 1775 1776 // observers. 1777 1778 /// Returns the hash functor object with which the %unordered_multimap 1779 /// was constructed. 1780 hasher 1781 hash_function() const 1782 { return _M_h.hash_function(); } 1783 1784 /// Returns the key comparison object with which the %unordered_multimap 1785 /// was constructed. 1786 key_equal 1787 key_eq() const 1788 { return _M_h.key_eq(); } 1789 1790 // lookup. 1791 1792 //@{ 1793 /** 1794 * @brief Tries to locate an element in an %unordered_multimap. 1795 * @param __x Key to be located. 1796 * @return Iterator pointing to sought-after element, or end() if not 1797 * found. 1798 * 1799 * This function takes a key and tries to locate the element with which 1800 * the key matches. If successful the function returns an iterator 1801 * pointing to the sought after element. If unsuccessful it returns the 1802 * past-the-end ( @c end() ) iterator. 1803 */ 1804 iterator 1805 find(const key_type& __x) 1806 { return _M_h.find(__x); } 1807 1808 const_iterator 1809 find(const key_type& __x) const 1810 { return _M_h.find(__x); } 1811 //@} 1812 1813 /** 1814 * @brief Finds the number of elements. 1815 * @param __x Key to count. 1816 * @return Number of elements with specified key. 1817 */ 1818 size_type 1819 count(const key_type& __x) const 1820 { return _M_h.count(__x); } 1821 1822 //@{ 1823 /** 1824 * @brief Finds a subsequence matching given key. 1825 * @param __x Key to be located. 1826 * @return Pair of iterators that possibly points to the subsequence 1827 * matching given key. 1828 */ 1829 std::pair<iterator, iterator> 1830 equal_range(const key_type& __x) 1831 { return _M_h.equal_range(__x); } 1832 1833 std::pair<const_iterator, const_iterator> 1834 equal_range(const key_type& __x) const 1835 { return _M_h.equal_range(__x); } 1836 //@} 1837 1838 // bucket interface. 1839 1840 /// Returns the number of buckets of the %unordered_multimap. 1841 size_type 1842 bucket_count() const noexcept 1843 { return _M_h.bucket_count(); } 1844 1845 /// Returns the maximum number of buckets of the %unordered_multimap. 1846 size_type 1847 max_bucket_count() const noexcept 1848 { return _M_h.max_bucket_count(); } 1849 1850 /* 1851 * @brief Returns the number of elements in a given bucket. 1852 * @param __n A bucket index. 1853 * @return The number of elements in the bucket. 1854 */ 1855 size_type 1856 bucket_size(size_type __n) const 1857 { return _M_h.bucket_size(__n); } 1858 1859 /* 1860 * @brief Returns the bucket index of a given element. 1861 * @param __key A key instance. 1862 * @return The key bucket index. 1863 */ 1864 size_type 1865 bucket(const key_type& __key) const 1866 { return _M_h.bucket(__key); } 1867 1868 /** 1869 * @brief Returns a read/write iterator pointing to the first bucket 1870 * element. 1871 * @param __n The bucket index. 1872 * @return A read/write local iterator. 1873 */ 1874 local_iterator 1875 begin(size_type __n) 1876 { return _M_h.begin(__n); } 1877 1878 //@{ 1879 /** 1880 * @brief Returns a read-only (constant) iterator pointing to the first 1881 * bucket element. 1882 * @param __n The bucket index. 1883 * @return A read-only local iterator. 1884 */ 1885 const_local_iterator 1886 begin(size_type __n) const 1887 { return _M_h.begin(__n); } 1888 1889 const_local_iterator 1890 cbegin(size_type __n) const 1891 { return _M_h.cbegin(__n); } 1892 //@} 1893 1894 /** 1895 * @brief Returns a read/write iterator pointing to one past the last 1896 * bucket elements. 1897 * @param __n The bucket index. 1898 * @return A read/write local iterator. 1899 */ 1900 local_iterator 1901 end(size_type __n) 1902 { return _M_h.end(__n); } 1903 1904 //@{ 1905 /** 1906 * @brief Returns a read-only (constant) iterator pointing to one past 1907 * the last bucket elements. 1908 * @param __n The bucket index. 1909 * @return A read-only local iterator. 1910 */ 1911 const_local_iterator 1912 end(size_type __n) const 1913 { return _M_h.end(__n); } 1914 1915 const_local_iterator 1916 cend(size_type __n) const 1917 { return _M_h.cend(__n); } 1918 //@} 1919 1920 // hash policy. 1921 1922 /// Returns the average number of elements per bucket. 1923 float 1924 load_factor() const noexcept 1925 { return _M_h.load_factor(); } 1926 1927 /// Returns a positive number that the %unordered_multimap tries to keep 1928 /// the load factor less than or equal to. 1929 float 1930 max_load_factor() const noexcept 1931 { return _M_h.max_load_factor(); } 1932 1933 /** 1934 * @brief Change the %unordered_multimap maximum load factor. 1935 * @param __z The new maximum load factor. 1936 */ 1937 void 1938 max_load_factor(float __z) 1939 { _M_h.max_load_factor(__z); } 1940 1941 /** 1942 * @brief May rehash the %unordered_multimap. 1943 * @param __n The new number of buckets. 1944 * 1945 * Rehash will occur only if the new number of buckets respect the 1946 * %unordered_multimap maximum load factor. 1947 */ 1948 void 1949 rehash(size_type __n) 1950 { _M_h.rehash(__n); } 1951 1952 /** 1953 * @brief Prepare the %unordered_multimap for a specified number of 1954 * elements. 1955 * @param __n Number of elements required. 1956 * 1957 * Same as rehash(ceil(n / max_load_factor())). 1958 */ 1959 void 1960 reserve(size_type __n) 1961 { _M_h.reserve(__n); } 1962 1963 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1, 1964 typename _Alloc1> 1965 friend bool 1966 operator==(const unordered_multimap<_Key1, _Tp1, 1967 _Hash1, _Pred1, _Alloc1>&, 1968 const unordered_multimap<_Key1, _Tp1, 1969 _Hash1, _Pred1, _Alloc1>&); 1970 }; 1971 1972 #if __cpp_deduction_guides >= 201606 1973 1974 template<typename _InputIterator, 1975 typename _Hash = hash<__iter_key_t<_InputIterator>>, 1976 typename _Pred = equal_to<__iter_key_t<_InputIterator>>, 1977 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, 1978 typename = _RequireInputIter<_InputIterator>, 1979 typename = _RequireAllocator<_Allocator>> 1980 unordered_multimap(_InputIterator, _InputIterator, 1981 unordered_multimap<int, int>::size_type = {}, 1982 _Hash = _Hash(), _Pred = _Pred(), 1983 _Allocator = _Allocator()) 1984 -> unordered_multimap<__iter_key_t<_InputIterator>, 1985 __iter_val_t<_InputIterator>, _Hash, _Pred, 1986 _Allocator>; 1987 1988 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>, 1989 typename _Pred = equal_to<_Key>, 1990 typename _Allocator = allocator<pair<const _Key, _Tp>>, 1991 typename = _RequireAllocator<_Allocator>> 1992 unordered_multimap(initializer_list<pair<_Key, _Tp>>, 1993 unordered_multimap<int, int>::size_type = {}, 1994 _Hash = _Hash(), _Pred = _Pred(), 1995 _Allocator = _Allocator()) 1996 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>; 1997 1998 template<typename _InputIterator, typename _Allocator, 1999 typename = _RequireInputIter<_InputIterator>, 2000 typename = _RequireAllocator<_Allocator>> 2001 unordered_multimap(_InputIterator, _InputIterator, 2002 unordered_multimap<int, int>::size_type, _Allocator) 2003 -> unordered_multimap<__iter_key_t<_InputIterator>, 2004 __iter_val_t<_InputIterator>, 2005 hash<__iter_key_t<_InputIterator>>, 2006 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 2007 2008 template<typename _InputIterator, typename _Allocator, 2009 typename = _RequireInputIter<_InputIterator>, 2010 typename = _RequireAllocator<_Allocator>> 2011 unordered_multimap(_InputIterator, _InputIterator, _Allocator) 2012 -> unordered_multimap<__iter_key_t<_InputIterator>, 2013 __iter_val_t<_InputIterator>, 2014 hash<__iter_key_t<_InputIterator>>, 2015 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 2016 2017 template<typename _InputIterator, typename _Hash, typename _Allocator, 2018 typename = _RequireInputIter<_InputIterator>, 2019 typename = _RequireAllocator<_Allocator>> 2020 unordered_multimap(_InputIterator, _InputIterator, 2021 unordered_multimap<int, int>::size_type, _Hash, 2022 _Allocator) 2023 -> unordered_multimap<__iter_key_t<_InputIterator>, 2024 __iter_val_t<_InputIterator>, _Hash, 2025 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 2026 2027 template<typename _Key, typename _Tp, typename _Allocator, 2028 typename = _RequireAllocator<_Allocator>> 2029 unordered_multimap(initializer_list<pair<_Key, _Tp>>, 2030 unordered_multimap<int, int>::size_type, 2031 _Allocator) 2032 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 2033 2034 template<typename _Key, typename _Tp, typename _Allocator, 2035 typename = _RequireAllocator<_Allocator>> 2036 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) 2037 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 2038 2039 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator, 2040 typename = _RequireAllocator<_Allocator>> 2041 unordered_multimap(initializer_list<pair<_Key, _Tp>>, 2042 unordered_multimap<int, int>::size_type, 2043 _Hash, _Allocator) 2044 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>; 2045 2046 #endif 2047 2048 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2049 inline void 2050 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2051 unordered_map<_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 void 2057 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2058 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2059 noexcept(noexcept(__x.swap(__y))) 2060 { __x.swap(__y); } 2061 2062 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2063 inline bool 2064 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2065 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2066 { return __x._M_h._M_equal(__y._M_h); } 2067 2068 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2069 inline bool 2070 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2071 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2072 { return !(__x == __y); } 2073 2074 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2075 inline bool 2076 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2077 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2078 { return __x._M_h._M_equal(__y._M_h); } 2079 2080 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 2081 inline bool 2082 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 2083 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 2084 { return !(__x == __y); } 2085 2086 _GLIBCXX_END_NAMESPACE_CONTAINER 2087 2088 #if __cplusplus > 201402L 2089 // Allow std::unordered_map access to internals of compatible maps. 2090 template<typename _Key, typename _Val, typename _Hash1, typename _Eq1, 2091 typename _Alloc, typename _Hash2, typename _Eq2> 2092 struct _Hash_merge_helper< 2093 _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>, 2094 _Hash2, _Eq2> 2095 { 2096 private: 2097 template<typename... _Tp> 2098 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>; 2099 template<typename... _Tp> 2100 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>; 2101 2102 friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>; 2103 2104 static auto& 2105 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) 2106 { return __map._M_h; } 2107 2108 static auto& 2109 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) 2110 { return __map._M_h; } 2111 }; 2112 2113 // Allow std::unordered_multimap access to internals of compatible maps. 2114 template<typename _Key, typename _Val, typename _Hash1, typename _Eq1, 2115 typename _Alloc, typename _Hash2, typename _Eq2> 2116 struct _Hash_merge_helper< 2117 _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>, 2118 _Hash2, _Eq2> 2119 { 2120 private: 2121 template<typename... _Tp> 2122 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>; 2123 template<typename... _Tp> 2124 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>; 2125 2126 friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>; 2127 2128 static auto& 2129 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) 2130 { return __map._M_h; } 2131 2132 static auto& 2133 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) 2134 { return __map._M_h; } 2135 }; 2136 #endif // C++17 2137 2138 _GLIBCXX_END_NAMESPACE_VERSION 2139 } // namespace std 2140 2141 #endif /* _UNORDERED_MAP_H */ 2142