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