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