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