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