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