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