1 // unordered_map implementation -*- C++ -*- 2 3 // Copyright (C) 2010-2013 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 allocator<_Key>. 84 * 85 * Meets the requirements of a <a href="tables.html#65">container</a>, and 86 * <a href="tables.html#xx">unordered associative container</a> 87 * 88 * The resulting value type of the container is std::pair<const _Key, _Tp>. 89 * 90 * Base is _Hashtable, dispatched at compile time via template 91 * alias __umap_hashtable. 92 */ 93 template<class _Key, class _Tp, 94 class _Hash = hash<_Key>, 95 class _Pred = std::equal_to<_Key>, 96 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 97 class unordered_map : __check_copy_constructible<_Alloc> 98 { 99 typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable; 100 _Hashtable _M_h; 101 102 public: 103 // typedefs: 104 //@{ 105 /// Public typedefs. 106 typedef typename _Hashtable::key_type key_type; 107 typedef typename _Hashtable::value_type value_type; 108 typedef typename _Hashtable::mapped_type mapped_type; 109 typedef typename _Hashtable::hasher hasher; 110 typedef typename _Hashtable::key_equal key_equal; 111 typedef typename _Hashtable::allocator_type allocator_type; 112 //@} 113 114 //@{ 115 /// Iterator-related typedefs. 116 typedef typename allocator_type::pointer pointer; 117 typedef typename allocator_type::const_pointer const_pointer; 118 typedef typename allocator_type::reference reference; 119 typedef typename allocator_type::const_reference const_reference; 120 typedef typename _Hashtable::iterator iterator; 121 typedef typename _Hashtable::const_iterator const_iterator; 122 typedef typename _Hashtable::local_iterator local_iterator; 123 typedef typename _Hashtable::const_local_iterator const_local_iterator; 124 typedef typename _Hashtable::size_type size_type; 125 typedef typename _Hashtable::difference_type difference_type; 126 //@} 127 128 //construct/destroy/copy 129 130 /** 131 * @brief Default constructor creates no elements. 132 * @param __n Initial number of buckets. 133 * @param __hf A hash functor. 134 * @param __eql A key equality functor. 135 * @param __a An allocator object. 136 */ 137 explicit 138 unordered_map(size_type __n = 10, 139 const hasher& __hf = hasher(), 140 const key_equal& __eql = key_equal(), 141 const allocator_type& __a = allocator_type()) 142 : _M_h(__n, __hf, __eql, __a) 143 { } 144 145 /** 146 * @brief Builds an %unordered_map from a range. 147 * @param __first An input iterator. 148 * @param __last An input iterator. 149 * @param __n Minimal initial number of buckets. 150 * @param __hf A hash functor. 151 * @param __eql A key equality functor. 152 * @param __a An allocator object. 153 * 154 * Create an %unordered_map consisting of copies of the elements from 155 * [__first,__last). This is linear in N (where N is 156 * distance(__first,__last)). 157 */ 158 template<typename _InputIterator> 159 unordered_map(_InputIterator __f, _InputIterator __l, 160 size_type __n = 0, 161 const hasher& __hf = hasher(), 162 const key_equal& __eql = key_equal(), 163 const allocator_type& __a = allocator_type()) 164 : _M_h(__f, __l, __n, __hf, __eql, __a) 165 { } 166 167 /// Copy constructor. 168 unordered_map(const unordered_map&) = default; 169 170 /// Move constructor. 171 unordered_map(unordered_map&&) = default; 172 173 /** 174 * @brief Builds an %unordered_map from an initializer_list. 175 * @param __l An initializer_list. 176 * @param __n Minimal initial number of buckets. 177 * @param __hf A hash functor. 178 * @param __eql A key equality functor. 179 * @param __a An allocator object. 180 * 181 * Create an %unordered_map consisting of copies of the elements in the 182 * list. This is linear in N (where N is @a __l.size()). 183 */ 184 unordered_map(initializer_list<value_type> __l, 185 size_type __n = 0, 186 const hasher& __hf = hasher(), 187 const key_equal& __eql = key_equal(), 188 const allocator_type& __a = allocator_type()) 189 : _M_h(__l, __n, __hf, __eql, __a) 190 { } 191 192 /// Copy assignment operator. 193 unordered_map& 194 operator=(const unordered_map&) = default; 195 196 /// Move assignment operator. 197 unordered_map& 198 operator=(unordered_map&&) = default; 199 200 /** 201 * @brief %Unordered_map list assignment operator. 202 * @param __l An initializer_list. 203 * 204 * This function fills an %unordered_map with copies of the elements in 205 * the initializer list @a __l. 206 * 207 * Note that the assignment completely changes the %unordered_map and 208 * that the resulting %unordered_map's size is the same as the number 209 * of elements assigned. Old data may be lost. 210 */ 211 unordered_map& 212 operator=(initializer_list<value_type> __l) 213 { 214 _M_h = __l; 215 return *this; 216 } 217 218 /// Returns the allocator object with which the %unordered_map was 219 /// constructed. 220 allocator_type 221 get_allocator() const noexcept 222 { return _M_h.get_allocator(); } 223 224 // size and capacity: 225 226 /// Returns true if the %unordered_map is empty. 227 bool 228 empty() const noexcept 229 { return _M_h.empty(); } 230 231 /// Returns the size of the %unordered_map. 232 size_type 233 size() const noexcept 234 { return _M_h.size(); } 235 236 /// Returns the maximum size of the %unordered_map. 237 size_type 238 max_size() const noexcept 239 { return _M_h.max_size(); } 240 241 // iterators. 242 243 /** 244 * Returns a read/write iterator that points to the first element in the 245 * %unordered_map. 246 */ 247 iterator 248 begin() noexcept 249 { return _M_h.begin(); } 250 251 //@{ 252 /** 253 * Returns a read-only (constant) iterator that points to the first 254 * element in the %unordered_map. 255 */ 256 const_iterator 257 begin() const noexcept 258 { return _M_h.begin(); } 259 260 const_iterator 261 cbegin() const noexcept 262 { return _M_h.begin(); } 263 //@} 264 265 /** 266 * Returns a read/write iterator that points one past the last element in 267 * the %unordered_map. 268 */ 269 iterator 270 end() noexcept 271 { return _M_h.end(); } 272 273 //@{ 274 /** 275 * Returns a read-only (constant) iterator that points one past the last 276 * element in the %unordered_map. 277 */ 278 const_iterator 279 end() const noexcept 280 { return _M_h.end(); } 281 282 const_iterator 283 cend() const noexcept 284 { return _M_h.end(); } 285 //@} 286 287 // modifiers. 288 289 /** 290 * @brief Attempts to build and insert a std::pair into the %unordered_map. 291 * 292 * @param __args Arguments used to generate a new pair instance (see 293 * std::piecewise_contruct for passing arguments to each 294 * part of the pair constructor). 295 * 296 * @return A pair, of which the first element is an iterator that points 297 * to the possibly inserted pair, and the second is a bool that 298 * is true if the pair was actually inserted. 299 * 300 * This function attempts to build and insert a (key, value) %pair into 301 * the %unordered_map. 302 * An %unordered_map relies on unique keys and thus a %pair is only 303 * inserted if its first element (the key) is not already present in the 304 * %unordered_map. 305 * 306 * Insertion requires amortized constant time. 307 */ 308 template<typename... _Args> 309 std::pair<iterator, bool> 310 emplace(_Args&&... __args) 311 { return _M_h.emplace(std::forward<_Args>(__args)...); } 312 313 /** 314 * @brief Attempts to build and insert a std::pair into the %unordered_map. 315 * 316 * @param __pos An iterator that serves as a hint as to where the pair 317 * should be inserted. 318 * @param __args Arguments used to generate a new pair instance (see 319 * std::piecewise_contruct for passing arguments to each 320 * part of the pair constructor). 321 * @return An iterator that points to the element with key of the 322 * std::pair built from @a __args (may or may not be that 323 * std::pair). 324 * 325 * This function is not concerned about whether the insertion took place, 326 * and thus does not return a boolean like the single-argument emplace() 327 * does. 328 * Note that the first parameter is only a hint and can potentially 329 * improve the performance of the insertion process. A bad hint would 330 * cause no gains in efficiency. 331 * 332 * See 333 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html 334 * for more on @a hinting. 335 * 336 * Insertion requires amortized constant time. 337 */ 338 template<typename... _Args> 339 iterator 340 emplace_hint(const_iterator __pos, _Args&&... __args) 341 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); } 342 343 //@{ 344 /** 345 * @brief Attempts to insert a std::pair into the %unordered_map. 346 347 * @param __x Pair to be inserted (see std::make_pair for easy 348 * creation of pairs). 349 * 350 * @return A pair, of which the first element is an iterator that 351 * points to the possibly inserted pair, and the second is 352 * a bool that is true if the pair was actually inserted. 353 * 354 * This function attempts to insert a (key, value) %pair into the 355 * %unordered_map. An %unordered_map relies on unique keys and thus a 356 * %pair is only inserted if its first element (the key) is not already 357 * present in the %unordered_map. 358 * 359 * Insertion requires amortized constant time. 360 */ 361 std::pair<iterator, bool> 362 insert(const value_type& __x) 363 { return _M_h.insert(__x); } 364 365 template<typename _Pair, typename = typename 366 std::enable_if<std::is_constructible<value_type, 367 _Pair&&>::value>::type> 368 std::pair<iterator, bool> 369 insert(_Pair&& __x) 370 { return _M_h.insert(std::forward<_Pair>(__x)); } 371 //@} 372 373 //@{ 374 /** 375 * @brief Attempts to insert a std::pair into the %unordered_map. 376 * @param __hint An iterator that serves as a hint as to where the 377 * pair should be inserted. 378 * @param __x Pair to be inserted (see std::make_pair for easy creation 379 * of pairs). 380 * @return An iterator that points to the element with key of 381 * @a __x (may or may not be the %pair passed in). 382 * 383 * This function is not concerned about whether the insertion took place, 384 * and thus does not return a boolean like the single-argument insert() 385 * does. Note that the first parameter is only a hint and can 386 * potentially improve the performance of the insertion process. A bad 387 * hint would cause no gains in efficiency. 388 * 389 * See 390 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html 391 * for more on @a hinting. 392 * 393 * Insertion requires amortized constant time. 394 */ 395 iterator 396 insert(const_iterator __hint, const value_type& __x) 397 { return _M_h.insert(__hint, __x); } 398 399 template<typename _Pair, typename = typename 400 std::enable_if<std::is_constructible<value_type, 401 _Pair&&>::value>::type> 402 iterator 403 insert(const_iterator __hint, _Pair&& __x) 404 { return _M_h.insert(__hint, std::forward<_Pair>(__x)); } 405 //@} 406 407 /** 408 * @brief A template function that attempts to insert a range of 409 * elements. 410 * @param __first Iterator pointing to the start of the range to be 411 * inserted. 412 * @param __last Iterator pointing to the end of the range. 413 * 414 * Complexity similar to that of the range constructor. 415 */ 416 template<typename _InputIterator> 417 void 418 insert(_InputIterator __first, _InputIterator __last) 419 { _M_h.insert(__first, __last); } 420 421 /** 422 * @brief Attempts to insert a list of elements into the %unordered_map. 423 * @param __l A std::initializer_list<value_type> of elements 424 * to be inserted. 425 * 426 * Complexity similar to that of the range constructor. 427 */ 428 void 429 insert(initializer_list<value_type> __l) 430 { _M_h.insert(__l); } 431 432 //@{ 433 /** 434 * @brief Erases an element from an %unordered_map. 435 * @param __position An iterator pointing to the element to be erased. 436 * @return An iterator pointing to the element immediately following 437 * @a __position prior to the element being erased. If no such 438 * element exists, end() is returned. 439 * 440 * This function erases an element, pointed to by the given iterator, 441 * from an %unordered_map. 442 * Note that this function only erases the element, and that if the 443 * element is itself a pointer, the pointed-to memory is not touched in 444 * any way. Managing the pointer is the user's responsibility. 445 */ 446 iterator 447 erase(const_iterator __position) 448 { return _M_h.erase(__position); } 449 450 // LWG 2059. 451 iterator 452 erase(iterator __it) 453 { return _M_h.erase(__it); } 454 //@} 455 456 /** 457 * @brief Erases elements according to the provided key. 458 * @param __x Key of element to be erased. 459 * @return The number of elements erased. 460 * 461 * This function erases all the elements located by the given key from 462 * an %unordered_map. For an %unordered_map the result of this function 463 * can only be 0 (not present) or 1 (present). 464 * Note that this function only erases the element, and that if the 465 * element is itself a pointer, the pointed-to memory is not touched in 466 * any way. Managing the pointer is the user's responsibility. 467 */ 468 size_type 469 erase(const key_type& __x) 470 { return _M_h.erase(__x); } 471 472 /** 473 * @brief Erases a [__first,__last) range of elements from an 474 * %unordered_map. 475 * @param __first Iterator pointing to the start of the range to be 476 * erased. 477 * @param __last Iterator pointing to the end of the range to 478 * be erased. 479 * @return The iterator @a __last. 480 * 481 * This function erases a sequence of elements from an %unordered_map. 482 * Note that this function only erases the elements, and that if 483 * the element is itself a pointer, the pointed-to memory is not touched 484 * in any way. Managing the pointer is the user's responsibility. 485 */ 486 iterator 487 erase(const_iterator __first, const_iterator __last) 488 { return _M_h.erase(__first, __last); } 489 490 /** 491 * Erases all elements in an %unordered_map. 492 * Note that this function only erases the elements, and that if the 493 * elements themselves are pointers, the pointed-to memory is not touched 494 * in any way. Managing the pointer is the user's responsibility. 495 */ 496 void 497 clear() noexcept 498 { _M_h.clear(); } 499 500 /** 501 * @brief Swaps data with another %unordered_map. 502 * @param __x An %unordered_map of the same element and allocator 503 * types. 504 * 505 * This exchanges the elements between two %unordered_map in constant time. 506 * Note that the global std::swap() function is specialized such that 507 * std::swap(m1,m2) will feed to this function. 508 */ 509 void 510 swap(unordered_map& __x) 511 { _M_h.swap(__x._M_h); } 512 513 // observers. 514 515 /// Returns the hash functor object with which the %unordered_map was 516 /// constructed. 517 hasher 518 hash_function() const 519 { return _M_h.hash_function(); } 520 521 /// Returns the key comparison object with which the %unordered_map was 522 /// constructed. 523 key_equal 524 key_eq() const 525 { return _M_h.key_eq(); } 526 527 // lookup. 528 529 //@{ 530 /** 531 * @brief Tries to locate an element in an %unordered_map. 532 * @param __x Key to be located. 533 * @return Iterator pointing to sought-after element, or end() if not 534 * found. 535 * 536 * This function takes a key and tries to locate the element with which 537 * the key matches. If successful the function returns an iterator 538 * pointing to the sought after element. If unsuccessful it returns the 539 * past-the-end ( @c end() ) iterator. 540 */ 541 iterator 542 find(const key_type& __x) 543 { return _M_h.find(__x); } 544 545 const_iterator 546 find(const key_type& __x) const 547 { return _M_h.find(__x); } 548 //@} 549 550 /** 551 * @brief Finds the number of elements. 552 * @param __x Key to count. 553 * @return Number of elements with specified key. 554 * 555 * This function only makes sense for %unordered_multimap; for 556 * %unordered_map the result will either be 0 (not present) or 1 557 * (present). 558 */ 559 size_type 560 count(const key_type& __x) const 561 { return _M_h.count(__x); } 562 563 //@{ 564 /** 565 * @brief Finds a subsequence matching given key. 566 * @param __x Key to be located. 567 * @return Pair of iterators that possibly points to the subsequence 568 * matching given key. 569 * 570 * This function probably only makes sense for %unordered_multimap. 571 */ 572 std::pair<iterator, iterator> 573 equal_range(const key_type& __x) 574 { return _M_h.equal_range(__x); } 575 576 std::pair<const_iterator, const_iterator> 577 equal_range(const key_type& __x) const 578 { return _M_h.equal_range(__x); } 579 //@} 580 581 //@{ 582 /** 583 * @brief Subscript ( @c [] ) access to %unordered_map data. 584 * @param __k The key for which data should be retrieved. 585 * @return A reference to the data of the (key,data) %pair. 586 * 587 * Allows for easy lookup with the subscript ( @c [] )operator. Returns 588 * data associated with the key specified in subscript. If the key does 589 * not exist, a pair with that key is created using default values, which 590 * is then returned. 591 * 592 * Lookup requires constant time. 593 */ 594 mapped_type& 595 operator[](const key_type& __k) 596 { return _M_h[__k]; } 597 598 mapped_type& 599 operator[](key_type&& __k) 600 { return _M_h[std::move(__k)]; } 601 //@} 602 603 //@{ 604 /** 605 * @brief Access to %unordered_map data. 606 * @param __k The key for which data should be retrieved. 607 * @return A reference to the data whose key is equal to @a __k, if 608 * such a data is present in the %unordered_map. 609 * @throw std::out_of_range If no such data is present. 610 */ 611 mapped_type& 612 at(const key_type& __k) 613 { return _M_h.at(__k); } 614 615 const mapped_type& 616 at(const key_type& __k) const 617 { return _M_h.at(__k); } 618 //@} 619 620 // bucket interface. 621 622 /// Returns the number of buckets of the %unordered_map. 623 size_type 624 bucket_count() const noexcept 625 { return _M_h.bucket_count(); } 626 627 /// Returns the maximum number of buckets of the %unordered_map. 628 size_type 629 max_bucket_count() const noexcept 630 { return _M_h.max_bucket_count(); } 631 632 /* 633 * @brief Returns the number of elements in a given bucket. 634 * @param __n A bucket index. 635 * @return The number of elements in the bucket. 636 */ 637 size_type 638 bucket_size(size_type __n) const 639 { return _M_h.bucket_size(__n); } 640 641 /* 642 * @brief Returns the bucket index of a given element. 643 * @param __key A key instance. 644 * @return The key bucket index. 645 */ 646 size_type 647 bucket(const key_type& __key) const 648 { return _M_h.bucket(__key); } 649 650 /** 651 * @brief Returns a read/write iterator pointing to the first bucket 652 * element. 653 * @param __n The bucket index. 654 * @return A read/write local iterator. 655 */ 656 local_iterator 657 begin(size_type __n) 658 { return _M_h.begin(__n); } 659 660 //@{ 661 /** 662 * @brief Returns a read-only (constant) iterator pointing to the first 663 * bucket element. 664 * @param __n The bucket index. 665 * @return A read-only local iterator. 666 */ 667 const_local_iterator 668 begin(size_type __n) const 669 { return _M_h.begin(__n); } 670 671 const_local_iterator 672 cbegin(size_type __n) const 673 { return _M_h.cbegin(__n); } 674 //@} 675 676 /** 677 * @brief Returns a read/write iterator pointing to one past the last 678 * bucket elements. 679 * @param __n The bucket index. 680 * @return A read/write local iterator. 681 */ 682 local_iterator 683 end(size_type __n) 684 { return _M_h.end(__n); } 685 686 //@{ 687 /** 688 * @brief Returns a read-only (constant) iterator pointing to one past 689 * the last bucket elements. 690 * @param __n The bucket index. 691 * @return A read-only local iterator. 692 */ 693 const_local_iterator 694 end(size_type __n) const 695 { return _M_h.end(__n); } 696 697 const_local_iterator 698 cend(size_type __n) const 699 { return _M_h.cend(__n); } 700 //@} 701 702 // hash policy. 703 704 /// Returns the average number of elements per bucket. 705 float 706 load_factor() const noexcept 707 { return _M_h.load_factor(); } 708 709 /// Returns a positive number that the %unordered_map tries to keep the 710 /// load factor less than or equal to. 711 float 712 max_load_factor() const noexcept 713 { return _M_h.max_load_factor(); } 714 715 /** 716 * @brief Change the %unordered_map maximum load factor. 717 * @param __z The new maximum load factor. 718 */ 719 void 720 max_load_factor(float __z) 721 { _M_h.max_load_factor(__z); } 722 723 /** 724 * @brief May rehash the %unordered_map. 725 * @param __n The new number of buckets. 726 * 727 * Rehash will occur only if the new number of buckets respect the 728 * %unordered_map maximum load factor. 729 */ 730 void 731 rehash(size_type __n) 732 { _M_h.rehash(__n); } 733 734 /** 735 * @brief Prepare the %unordered_map for a specified number of 736 * elements. 737 * @param __n Number of elements required. 738 * 739 * Same as rehash(ceil(n / max_load_factor())). 740 */ 741 void 742 reserve(size_type __n) 743 { _M_h.reserve(__n); } 744 745 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1, 746 typename _Alloc1> 747 friend bool 748 operator==(const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&, 749 const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&); 750 }; 751 752 /** 753 * @brief A standard container composed of equivalent keys 754 * (possibly containing multiple of each key value) that associates 755 * values of another type with the keys. 756 * 757 * @ingroup unordered_associative_containers 758 * 759 * @tparam _Key Type of key objects. 760 * @tparam _Tp Type of mapped objects. 761 * @tparam _Hash Hashing function object type, defaults to hash<_Value>. 762 * @tparam _Pred Predicate function object type, defaults 763 * to equal_to<_Value>. 764 * @tparam _Alloc Allocator type, defaults to allocator<_Key>. 765 * 766 * Meets the requirements of a <a href="tables.html#65">container</a>, and 767 * <a href="tables.html#xx">unordered associative container</a> 768 * 769 * The resulting value type of the container is std::pair<const _Key, _Tp>. 770 * 771 * Base is _Hashtable, dispatched at compile time via template 772 * alias __ummap_hashtable. 773 */ 774 template<class _Key, class _Tp, 775 class _Hash = hash<_Key>, 776 class _Pred = std::equal_to<_Key>, 777 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 778 class unordered_multimap : __check_copy_constructible<_Alloc> 779 { 780 typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable; 781 _Hashtable _M_h; 782 783 public: 784 // typedefs: 785 //@{ 786 /// Public typedefs. 787 typedef typename _Hashtable::key_type key_type; 788 typedef typename _Hashtable::value_type value_type; 789 typedef typename _Hashtable::mapped_type mapped_type; 790 typedef typename _Hashtable::hasher hasher; 791 typedef typename _Hashtable::key_equal key_equal; 792 typedef typename _Hashtable::allocator_type allocator_type; 793 //@} 794 795 //@{ 796 /// Iterator-related typedefs. 797 typedef typename allocator_type::pointer pointer; 798 typedef typename allocator_type::const_pointer const_pointer; 799 typedef typename allocator_type::reference reference; 800 typedef typename allocator_type::const_reference const_reference; 801 typedef typename _Hashtable::iterator iterator; 802 typedef typename _Hashtable::const_iterator const_iterator; 803 typedef typename _Hashtable::local_iterator local_iterator; 804 typedef typename _Hashtable::const_local_iterator const_local_iterator; 805 typedef typename _Hashtable::size_type size_type; 806 typedef typename _Hashtable::difference_type difference_type; 807 //@} 808 809 //construct/destroy/copy 810 811 /** 812 * @brief Default constructor creates no elements. 813 * @param __n Initial number of buckets. 814 * @param __hf A hash functor. 815 * @param __eql A key equality functor. 816 * @param __a An allocator object. 817 */ 818 explicit 819 unordered_multimap(size_type __n = 10, 820 const hasher& __hf = hasher(), 821 const key_equal& __eql = key_equal(), 822 const allocator_type& __a = allocator_type()) 823 : _M_h(__n, __hf, __eql, __a) 824 { } 825 826 /** 827 * @brief Builds an %unordered_multimap from a range. 828 * @param __first An input iterator. 829 * @param __last An input iterator. 830 * @param __n Minimal initial number of buckets. 831 * @param __hf A hash functor. 832 * @param __eql A key equality functor. 833 * @param __a An allocator object. 834 * 835 * Create an %unordered_multimap consisting of copies of the elements 836 * from [__first,__last). This is linear in N (where N is 837 * distance(__first,__last)). 838 */ 839 template<typename _InputIterator> 840 unordered_multimap(_InputIterator __f, _InputIterator __l, 841 size_type __n = 0, 842 const hasher& __hf = hasher(), 843 const key_equal& __eql = key_equal(), 844 const allocator_type& __a = allocator_type()) 845 : _M_h(__f, __l, __n, __hf, __eql, __a) 846 { } 847 848 /// Copy constructor. 849 unordered_multimap(const unordered_multimap&) = default; 850 851 /// Move constructor. 852 unordered_multimap(unordered_multimap&&) = default; 853 854 /** 855 * @brief Builds an %unordered_multimap from an initializer_list. 856 * @param __l An initializer_list. 857 * @param __n Minimal initial number of buckets. 858 * @param __hf A hash functor. 859 * @param __eql A key equality functor. 860 * @param __a An allocator object. 861 * 862 * Create an %unordered_multimap consisting of copies of the elements in 863 * the list. This is linear in N (where N is @a __l.size()). 864 */ 865 unordered_multimap(initializer_list<value_type> __l, 866 size_type __n = 0, 867 const hasher& __hf = hasher(), 868 const key_equal& __eql = key_equal(), 869 const allocator_type& __a = allocator_type()) 870 : _M_h(__l, __n, __hf, __eql, __a) 871 { } 872 873 /// Copy assignment operator. 874 unordered_multimap& 875 operator=(const unordered_multimap&) = default; 876 877 /// Move assignment operator. 878 unordered_multimap& 879 operator=(unordered_multimap&&) = default; 880 881 /** 882 * @brief %Unordered_multimap list assignment operator. 883 * @param __l An initializer_list. 884 * 885 * This function fills an %unordered_multimap with copies of the elements 886 * in the initializer list @a __l. 887 * 888 * Note that the assignment completely changes the %unordered_multimap 889 * and that the resulting %unordered_multimap's size is the same as the 890 * number of elements assigned. Old data may be lost. 891 */ 892 unordered_multimap& 893 operator=(initializer_list<value_type> __l) 894 { 895 _M_h = __l; 896 return *this; 897 } 898 899 /// Returns the allocator object with which the %unordered_multimap was 900 /// constructed. 901 allocator_type 902 get_allocator() const noexcept 903 { return _M_h.get_allocator(); } 904 905 // size and capacity: 906 907 /// Returns true if the %unordered_multimap is empty. 908 bool 909 empty() const noexcept 910 { return _M_h.empty(); } 911 912 /// Returns the size of the %unordered_multimap. 913 size_type 914 size() const noexcept 915 { return _M_h.size(); } 916 917 /// Returns the maximum size of the %unordered_multimap. 918 size_type 919 max_size() const noexcept 920 { return _M_h.max_size(); } 921 922 // iterators. 923 924 /** 925 * Returns a read/write iterator that points to the first element in the 926 * %unordered_multimap. 927 */ 928 iterator 929 begin() noexcept 930 { return _M_h.begin(); } 931 932 //@{ 933 /** 934 * Returns a read-only (constant) iterator that points to the first 935 * element in the %unordered_multimap. 936 */ 937 const_iterator 938 begin() const noexcept 939 { return _M_h.begin(); } 940 941 const_iterator 942 cbegin() const noexcept 943 { return _M_h.begin(); } 944 //@} 945 946 /** 947 * Returns a read/write iterator that points one past the last element in 948 * the %unordered_multimap. 949 */ 950 iterator 951 end() noexcept 952 { return _M_h.end(); } 953 954 //@{ 955 /** 956 * Returns a read-only (constant) iterator that points one past the last 957 * element in the %unordered_multimap. 958 */ 959 const_iterator 960 end() const noexcept 961 { return _M_h.end(); } 962 963 const_iterator 964 cend() const noexcept 965 { return _M_h.end(); } 966 //@} 967 968 // modifiers. 969 970 /** 971 * @brief Attempts to build and insert a std::pair into the 972 * %unordered_multimap. 973 * 974 * @param __args Arguments used to generate a new pair instance (see 975 * std::piecewise_contruct for passing arguments to each 976 * part of the pair constructor). 977 * 978 * @return An iterator that points to the inserted pair. 979 * 980 * This function attempts to build and insert a (key, value) %pair into 981 * the %unordered_multimap. 982 * 983 * Insertion requires amortized constant time. 984 */ 985 template<typename... _Args> 986 iterator 987 emplace(_Args&&... __args) 988 { return _M_h.emplace(std::forward<_Args>(__args)...); } 989 990 /** 991 * @brief Attempts to build and insert a std::pair into the %unordered_multimap. 992 * 993 * @param __pos An iterator that serves as a hint as to where the pair 994 * should be inserted. 995 * @param __args Arguments used to generate a new pair instance (see 996 * std::piecewise_contruct for passing arguments to each 997 * part of the pair constructor). 998 * @return An iterator that points to the element with key of the 999 * std::pair built from @a __args. 1000 * 1001 * Note that the first parameter is only a hint and can potentially 1002 * improve the performance of the insertion process. A bad hint would 1003 * cause no gains in efficiency. 1004 * 1005 * See 1006 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html 1007 * for more on @a hinting. 1008 * 1009 * Insertion requires amortized constant time. 1010 */ 1011 template<typename... _Args> 1012 iterator 1013 emplace_hint(const_iterator __pos, _Args&&... __args) 1014 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); } 1015 1016 //@{ 1017 /** 1018 * @brief Inserts a std::pair into the %unordered_multimap. 1019 * @param __x Pair to be inserted (see std::make_pair for easy 1020 * creation of pairs). 1021 * 1022 * @return An iterator that points to the inserted pair. 1023 * 1024 * Insertion requires amortized constant time. 1025 */ 1026 iterator 1027 insert(const value_type& __x) 1028 { return _M_h.insert(__x); } 1029 1030 template<typename _Pair, typename = typename 1031 std::enable_if<std::is_constructible<value_type, 1032 _Pair&&>::value>::type> 1033 iterator 1034 insert(_Pair&& __x) 1035 { return _M_h.insert(std::forward<_Pair>(__x)); } 1036 //@} 1037 1038 //@{ 1039 /** 1040 * @brief Inserts a std::pair into the %unordered_multimap. 1041 * @param __hint An iterator that serves as a hint as to where the 1042 * pair should be inserted. 1043 * @param __x Pair to be inserted (see std::make_pair for easy creation 1044 * of pairs). 1045 * @return An iterator that points to the element with key of 1046 * @a __x (may or may not be the %pair passed in). 1047 * 1048 * Note that the first parameter is only a hint and can potentially 1049 * improve the performance of the insertion process. A bad hint would 1050 * cause no gains in efficiency. 1051 * 1052 * See 1053 * http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html 1054 * for more on @a hinting. 1055 * 1056 * Insertion requires amortized constant time. 1057 */ 1058 iterator 1059 insert(const_iterator __hint, const value_type& __x) 1060 { return _M_h.insert(__hint, __x); } 1061 1062 template<typename _Pair, typename = typename 1063 std::enable_if<std::is_constructible<value_type, 1064 _Pair&&>::value>::type> 1065 iterator 1066 insert(const_iterator __hint, _Pair&& __x) 1067 { return _M_h.insert(__hint, std::forward<_Pair>(__x)); } 1068 //@} 1069 1070 /** 1071 * @brief A template function that attempts to insert a range of 1072 * elements. 1073 * @param __first Iterator pointing to the start of the range to be 1074 * inserted. 1075 * @param __last Iterator pointing to the end of the range. 1076 * 1077 * Complexity similar to that of the range constructor. 1078 */ 1079 template<typename _InputIterator> 1080 void 1081 insert(_InputIterator __first, _InputIterator __last) 1082 { _M_h.insert(__first, __last); } 1083 1084 /** 1085 * @brief Attempts to insert a list of elements into the 1086 * %unordered_multimap. 1087 * @param __l A std::initializer_list<value_type> of elements 1088 * to be inserted. 1089 * 1090 * Complexity similar to that of the range constructor. 1091 */ 1092 void 1093 insert(initializer_list<value_type> __l) 1094 { _M_h.insert(__l); } 1095 1096 //@{ 1097 /** 1098 * @brief Erases an element from an %unordered_multimap. 1099 * @param __position An iterator pointing to the element to be erased. 1100 * @return An iterator pointing to the element immediately following 1101 * @a __position prior to the element being erased. If no such 1102 * element exists, end() is returned. 1103 * 1104 * This function erases an element, pointed to by the given iterator, 1105 * from an %unordered_multimap. 1106 * Note that this function only erases the element, and that if the 1107 * element is itself a pointer, the pointed-to memory is not touched in 1108 * any way. Managing the pointer is the user's responsibility. 1109 */ 1110 iterator 1111 erase(const_iterator __position) 1112 { return _M_h.erase(__position); } 1113 1114 // LWG 2059. 1115 iterator 1116 erase(iterator __it) 1117 { return _M_h.erase(__it); } 1118 //@} 1119 1120 /** 1121 * @brief Erases elements according to the provided key. 1122 * @param __x Key of elements to be erased. 1123 * @return The number of elements erased. 1124 * 1125 * This function erases all the elements located by the given key from 1126 * an %unordered_multimap. 1127 * Note that this function only erases the element, and that if the 1128 * element is itself a pointer, the pointed-to memory is not touched in 1129 * any way. Managing the pointer is the user's responsibility. 1130 */ 1131 size_type 1132 erase(const key_type& __x) 1133 { return _M_h.erase(__x); } 1134 1135 /** 1136 * @brief Erases a [__first,__last) range of elements from an 1137 * %unordered_multimap. 1138 * @param __first Iterator pointing to the start of the range to be 1139 * erased. 1140 * @param __last Iterator pointing to the end of the range to 1141 * be erased. 1142 * @return The iterator @a __last. 1143 * 1144 * This function erases a sequence of elements from an 1145 * %unordered_multimap. 1146 * Note that this function only erases the elements, and that if 1147 * the element is itself a pointer, the pointed-to memory is not touched 1148 * in any way. Managing the pointer is the user's responsibility. 1149 */ 1150 iterator 1151 erase(const_iterator __first, const_iterator __last) 1152 { return _M_h.erase(__first, __last); } 1153 1154 /** 1155 * Erases all elements in an %unordered_multimap. 1156 * Note that this function only erases the elements, and that if the 1157 * elements themselves are pointers, the pointed-to memory is not touched 1158 * in any way. Managing the pointer is the user's responsibility. 1159 */ 1160 void 1161 clear() noexcept 1162 { _M_h.clear(); } 1163 1164 /** 1165 * @brief Swaps data with another %unordered_multimap. 1166 * @param __x An %unordered_multimap of the same element and allocator 1167 * types. 1168 * 1169 * This exchanges the elements between two %unordered_multimap in 1170 * constant time. 1171 * Note that the global std::swap() function is specialized such that 1172 * std::swap(m1,m2) will feed to this function. 1173 */ 1174 void 1175 swap(unordered_multimap& __x) 1176 { _M_h.swap(__x._M_h); } 1177 1178 // observers. 1179 1180 /// Returns the hash functor object with which the %unordered_multimap 1181 /// was constructed. 1182 hasher 1183 hash_function() const 1184 { return _M_h.hash_function(); } 1185 1186 /// Returns the key comparison object with which the %unordered_multimap 1187 /// was constructed. 1188 key_equal 1189 key_eq() const 1190 { return _M_h.key_eq(); } 1191 1192 // lookup. 1193 1194 //@{ 1195 /** 1196 * @brief Tries to locate an element in an %unordered_multimap. 1197 * @param __x Key to be located. 1198 * @return Iterator pointing to sought-after element, or end() if not 1199 * found. 1200 * 1201 * This function takes a key and tries to locate the element with which 1202 * the key matches. If successful the function returns an iterator 1203 * pointing to the sought after element. If unsuccessful it returns the 1204 * past-the-end ( @c end() ) iterator. 1205 */ 1206 iterator 1207 find(const key_type& __x) 1208 { return _M_h.find(__x); } 1209 1210 const_iterator 1211 find(const key_type& __x) const 1212 { return _M_h.find(__x); } 1213 //@} 1214 1215 /** 1216 * @brief Finds the number of elements. 1217 * @param __x Key to count. 1218 * @return Number of elements with specified key. 1219 */ 1220 size_type 1221 count(const key_type& __x) const 1222 { return _M_h.count(__x); } 1223 1224 //@{ 1225 /** 1226 * @brief Finds a subsequence matching given key. 1227 * @param __x Key to be located. 1228 * @return Pair of iterators that possibly points to the subsequence 1229 * matching given key. 1230 */ 1231 std::pair<iterator, iterator> 1232 equal_range(const key_type& __x) 1233 { return _M_h.equal_range(__x); } 1234 1235 std::pair<const_iterator, const_iterator> 1236 equal_range(const key_type& __x) const 1237 { return _M_h.equal_range(__x); } 1238 //@} 1239 1240 // bucket interface. 1241 1242 /// Returns the number of buckets of the %unordered_multimap. 1243 size_type 1244 bucket_count() const noexcept 1245 { return _M_h.bucket_count(); } 1246 1247 /// Returns the maximum number of buckets of the %unordered_multimap. 1248 size_type 1249 max_bucket_count() const noexcept 1250 { return _M_h.max_bucket_count(); } 1251 1252 /* 1253 * @brief Returns the number of elements in a given bucket. 1254 * @param __n A bucket index. 1255 * @return The number of elements in the bucket. 1256 */ 1257 size_type 1258 bucket_size(size_type __n) const 1259 { return _M_h.bucket_size(__n); } 1260 1261 /* 1262 * @brief Returns the bucket index of a given element. 1263 * @param __key A key instance. 1264 * @return The key bucket index. 1265 */ 1266 size_type 1267 bucket(const key_type& __key) const 1268 { return _M_h.bucket(__key); } 1269 1270 /** 1271 * @brief Returns a read/write iterator pointing to the first bucket 1272 * element. 1273 * @param __n The bucket index. 1274 * @return A read/write local iterator. 1275 */ 1276 local_iterator 1277 begin(size_type __n) 1278 { return _M_h.begin(__n); } 1279 1280 //@{ 1281 /** 1282 * @brief Returns a read-only (constant) iterator pointing to the first 1283 * bucket element. 1284 * @param __n The bucket index. 1285 * @return A read-only local iterator. 1286 */ 1287 const_local_iterator 1288 begin(size_type __n) const 1289 { return _M_h.begin(__n); } 1290 1291 const_local_iterator 1292 cbegin(size_type __n) const 1293 { return _M_h.cbegin(__n); } 1294 //@} 1295 1296 /** 1297 * @brief Returns a read/write iterator pointing to one past the last 1298 * bucket elements. 1299 * @param __n The bucket index. 1300 * @return A read/write local iterator. 1301 */ 1302 local_iterator 1303 end(size_type __n) 1304 { return _M_h.end(__n); } 1305 1306 //@{ 1307 /** 1308 * @brief Returns a read-only (constant) iterator pointing to one past 1309 * the last bucket elements. 1310 * @param __n The bucket index. 1311 * @return A read-only local iterator. 1312 */ 1313 const_local_iterator 1314 end(size_type __n) const 1315 { return _M_h.end(__n); } 1316 1317 const_local_iterator 1318 cend(size_type __n) const 1319 { return _M_h.cend(__n); } 1320 //@} 1321 1322 // hash policy. 1323 1324 /// Returns the average number of elements per bucket. 1325 float 1326 load_factor() const noexcept 1327 { return _M_h.load_factor(); } 1328 1329 /// Returns a positive number that the %unordered_multimap tries to keep 1330 /// the load factor less than or equal to. 1331 float 1332 max_load_factor() const noexcept 1333 { return _M_h.max_load_factor(); } 1334 1335 /** 1336 * @brief Change the %unordered_multimap maximum load factor. 1337 * @param __z The new maximum load factor. 1338 */ 1339 void 1340 max_load_factor(float __z) 1341 { _M_h.max_load_factor(__z); } 1342 1343 /** 1344 * @brief May rehash the %unordered_multimap. 1345 * @param __n The new number of buckets. 1346 * 1347 * Rehash will occur only if the new number of buckets respect the 1348 * %unordered_multimap maximum load factor. 1349 */ 1350 void 1351 rehash(size_type __n) 1352 { _M_h.rehash(__n); } 1353 1354 /** 1355 * @brief Prepare the %unordered_multimap for a specified number of 1356 * elements. 1357 * @param __n Number of elements required. 1358 * 1359 * Same as rehash(ceil(n / max_load_factor())). 1360 */ 1361 void 1362 reserve(size_type __n) 1363 { _M_h.reserve(__n); } 1364 1365 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1, 1366 typename _Alloc1> 1367 friend bool 1368 operator==(const unordered_multimap<_Key1, _Tp1, 1369 _Hash1, _Pred1, _Alloc1>&, 1370 const unordered_multimap<_Key1, _Tp1, 1371 _Hash1, _Pred1, _Alloc1>&); 1372 }; 1373 1374 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1375 inline void 1376 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1377 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1378 { __x.swap(__y); } 1379 1380 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1381 inline void 1382 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1383 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1384 { __x.swap(__y); } 1385 1386 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1387 inline bool 1388 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1389 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1390 { return __x._M_h._M_equal(__y._M_h); } 1391 1392 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1393 inline bool 1394 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1395 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1396 { return !(__x == __y); } 1397 1398 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1399 inline bool 1400 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1401 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1402 { return __x._M_h._M_equal(__y._M_h); } 1403 1404 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 1405 inline bool 1406 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 1407 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 1408 { return !(__x == __y); } 1409 1410 _GLIBCXX_END_NAMESPACE_CONTAINER 1411 } // namespace std 1412 1413 #endif /* _UNORDERED_MAP_H */ 1414