libstdc++
|
00001 // unordered_map implementation -*- C++ -*- 00002 00003 // Copyright (C) 2010-2018 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file bits/unordered_map.h 00026 * This is an internal header file, included by other library headers. 00027 * Do not attempt to use it directly. @headername{unordered_map} 00028 */ 00029 00030 #ifndef _UNORDERED_MAP_H 00031 #define _UNORDERED_MAP_H 00032 00033 namespace std _GLIBCXX_VISIBILITY(default) 00034 { 00035 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00036 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 00037 00038 /// Base types for unordered_map. 00039 template<bool _Cache> 00040 using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>; 00041 00042 template<typename _Key, 00043 typename _Tp, 00044 typename _Hash = hash<_Key>, 00045 typename _Pred = std::equal_to<_Key>, 00046 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >, 00047 typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>> 00048 using __umap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>, 00049 _Alloc, __detail::_Select1st, 00050 _Pred, _Hash, 00051 __detail::_Mod_range_hashing, 00052 __detail::_Default_ranged_hash, 00053 __detail::_Prime_rehash_policy, _Tr>; 00054 00055 /// Base types for unordered_multimap. 00056 template<bool _Cache> 00057 using __ummap_traits = __detail::_Hashtable_traits<_Cache, false, false>; 00058 00059 template<typename _Key, 00060 typename _Tp, 00061 typename _Hash = hash<_Key>, 00062 typename _Pred = std::equal_to<_Key>, 00063 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >, 00064 typename _Tr = __ummap_traits<__cache_default<_Key, _Hash>::value>> 00065 using __ummap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>, 00066 _Alloc, __detail::_Select1st, 00067 _Pred, _Hash, 00068 __detail::_Mod_range_hashing, 00069 __detail::_Default_ranged_hash, 00070 __detail::_Prime_rehash_policy, _Tr>; 00071 00072 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 00073 class unordered_multimap; 00074 00075 /** 00076 * @brief A standard container composed of unique keys (containing 00077 * at most one of each key value) that associates values of another type 00078 * with the keys. 00079 * 00080 * @ingroup unordered_associative_containers 00081 * 00082 * @tparam _Key Type of key objects. 00083 * @tparam _Tp Type of mapped objects. 00084 * @tparam _Hash Hashing function object type, defaults to hash<_Value>. 00085 * @tparam _Pred Predicate function object type, defaults 00086 * to equal_to<_Value>. 00087 * @tparam _Alloc Allocator type, defaults to 00088 * std::allocator<std::pair<const _Key, _Tp>>. 00089 * 00090 * Meets the requirements of a <a href="tables.html#65">container</a>, and 00091 * <a href="tables.html#xx">unordered associative container</a> 00092 * 00093 * The resulting value type of the container is std::pair<const _Key, _Tp>. 00094 * 00095 * Base is _Hashtable, dispatched at compile time via template 00096 * alias __umap_hashtable. 00097 */ 00098 template<typename _Key, typename _Tp, 00099 typename _Hash = hash<_Key>, 00100 typename _Pred = equal_to<_Key>, 00101 typename _Alloc = allocator<std::pair<const _Key, _Tp>>> 00102 class unordered_map 00103 { 00104 typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable; 00105 _Hashtable _M_h; 00106 00107 public: 00108 // typedefs: 00109 //@{ 00110 /// Public typedefs. 00111 typedef typename _Hashtable::key_type key_type; 00112 typedef typename _Hashtable::value_type value_type; 00113 typedef typename _Hashtable::mapped_type mapped_type; 00114 typedef typename _Hashtable::hasher hasher; 00115 typedef typename _Hashtable::key_equal key_equal; 00116 typedef typename _Hashtable::allocator_type allocator_type; 00117 //@} 00118 00119 //@{ 00120 /// Iterator-related typedefs. 00121 typedef typename _Hashtable::pointer pointer; 00122 typedef typename _Hashtable::const_pointer const_pointer; 00123 typedef typename _Hashtable::reference reference; 00124 typedef typename _Hashtable::const_reference const_reference; 00125 typedef typename _Hashtable::iterator iterator; 00126 typedef typename _Hashtable::const_iterator const_iterator; 00127 typedef typename _Hashtable::local_iterator local_iterator; 00128 typedef typename _Hashtable::const_local_iterator const_local_iterator; 00129 typedef typename _Hashtable::size_type size_type; 00130 typedef typename _Hashtable::difference_type difference_type; 00131 //@} 00132 00133 #if __cplusplus > 201402L 00134 using node_type = typename _Hashtable::node_type; 00135 using insert_return_type = typename _Hashtable::insert_return_type; 00136 #endif 00137 00138 //construct/destroy/copy 00139 00140 /// Default constructor. 00141 unordered_map() = default; 00142 00143 /** 00144 * @brief Default constructor creates no elements. 00145 * @param __n Minimal initial number of buckets. 00146 * @param __hf A hash functor. 00147 * @param __eql A key equality functor. 00148 * @param __a An allocator object. 00149 */ 00150 explicit 00151 unordered_map(size_type __n, 00152 const hasher& __hf = hasher(), 00153 const key_equal& __eql = key_equal(), 00154 const allocator_type& __a = allocator_type()) 00155 : _M_h(__n, __hf, __eql, __a) 00156 { } 00157 00158 /** 00159 * @brief Builds an %unordered_map from a range. 00160 * @param __first An input iterator. 00161 * @param __last An input iterator. 00162 * @param __n Minimal initial number of buckets. 00163 * @param __hf A hash functor. 00164 * @param __eql A key equality functor. 00165 * @param __a An allocator object. 00166 * 00167 * Create an %unordered_map consisting of copies of the elements from 00168 * [__first,__last). This is linear in N (where N is 00169 * distance(__first,__last)). 00170 */ 00171 template<typename _InputIterator> 00172 unordered_map(_InputIterator __first, _InputIterator __last, 00173 size_type __n = 0, 00174 const hasher& __hf = hasher(), 00175 const key_equal& __eql = key_equal(), 00176 const allocator_type& __a = allocator_type()) 00177 : _M_h(__first, __last, __n, __hf, __eql, __a) 00178 { } 00179 00180 /// Copy constructor. 00181 unordered_map(const unordered_map&) = default; 00182 00183 /// Move constructor. 00184 unordered_map(unordered_map&&) = default; 00185 00186 /** 00187 * @brief Creates an %unordered_map with no elements. 00188 * @param __a An allocator object. 00189 */ 00190 explicit 00191 unordered_map(const allocator_type& __a) 00192 : _M_h(__a) 00193 { } 00194 00195 /* 00196 * @brief Copy constructor with allocator argument. 00197 * @param __uset Input %unordered_map to copy. 00198 * @param __a An allocator object. 00199 */ 00200 unordered_map(const unordered_map& __umap, 00201 const allocator_type& __a) 00202 : _M_h(__umap._M_h, __a) 00203 { } 00204 00205 /* 00206 * @brief Move constructor with allocator argument. 00207 * @param __uset Input %unordered_map to move. 00208 * @param __a An allocator object. 00209 */ 00210 unordered_map(unordered_map&& __umap, 00211 const allocator_type& __a) 00212 : _M_h(std::move(__umap._M_h), __a) 00213 { } 00214 00215 /** 00216 * @brief Builds an %unordered_map from an initializer_list. 00217 * @param __l An initializer_list. 00218 * @param __n Minimal initial number of buckets. 00219 * @param __hf A hash functor. 00220 * @param __eql A key equality functor. 00221 * @param __a An allocator object. 00222 * 00223 * Create an %unordered_map consisting of copies of the elements in the 00224 * list. This is linear in N (where N is @a __l.size()). 00225 */ 00226 unordered_map(initializer_list<value_type> __l, 00227 size_type __n = 0, 00228 const hasher& __hf = hasher(), 00229 const key_equal& __eql = key_equal(), 00230 const allocator_type& __a = allocator_type()) 00231 : _M_h(__l, __n, __hf, __eql, __a) 00232 { } 00233 00234 unordered_map(size_type __n, const allocator_type& __a) 00235 : unordered_map(__n, hasher(), key_equal(), __a) 00236 { } 00237 00238 unordered_map(size_type __n, const hasher& __hf, 00239 const allocator_type& __a) 00240 : unordered_map(__n, __hf, key_equal(), __a) 00241 { } 00242 00243 template<typename _InputIterator> 00244 unordered_map(_InputIterator __first, _InputIterator __last, 00245 size_type __n, 00246 const allocator_type& __a) 00247 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a) 00248 { } 00249 00250 template<typename _InputIterator> 00251 unordered_map(_InputIterator __first, _InputIterator __last, 00252 size_type __n, const hasher& __hf, 00253 const allocator_type& __a) 00254 : unordered_map(__first, __last, __n, __hf, key_equal(), __a) 00255 { } 00256 00257 unordered_map(initializer_list<value_type> __l, 00258 size_type __n, 00259 const allocator_type& __a) 00260 : unordered_map(__l, __n, hasher(), key_equal(), __a) 00261 { } 00262 00263 unordered_map(initializer_list<value_type> __l, 00264 size_type __n, const hasher& __hf, 00265 const allocator_type& __a) 00266 : unordered_map(__l, __n, __hf, key_equal(), __a) 00267 { } 00268 00269 /// Copy assignment operator. 00270 unordered_map& 00271 operator=(const unordered_map&) = default; 00272 00273 /// Move assignment operator. 00274 unordered_map& 00275 operator=(unordered_map&&) = default; 00276 00277 /** 00278 * @brief %Unordered_map list assignment operator. 00279 * @param __l An initializer_list. 00280 * 00281 * This function fills an %unordered_map with copies of the elements in 00282 * the initializer list @a __l. 00283 * 00284 * Note that the assignment completely changes the %unordered_map and 00285 * that the resulting %unordered_map's size is the same as the number 00286 * of elements assigned. 00287 */ 00288 unordered_map& 00289 operator=(initializer_list<value_type> __l) 00290 { 00291 _M_h = __l; 00292 return *this; 00293 } 00294 00295 /// Returns the allocator object used by the %unordered_map. 00296 allocator_type 00297 get_allocator() const noexcept 00298 { return _M_h.get_allocator(); } 00299 00300 // size and capacity: 00301 00302 /// Returns true if the %unordered_map is empty. 00303 bool 00304 empty() const noexcept 00305 { return _M_h.empty(); } 00306 00307 /// Returns the size of the %unordered_map. 00308 size_type 00309 size() const noexcept 00310 { return _M_h.size(); } 00311 00312 /// Returns the maximum size of the %unordered_map. 00313 size_type 00314 max_size() const noexcept 00315 { return _M_h.max_size(); } 00316 00317 // iterators. 00318 00319 /** 00320 * Returns a read/write iterator that points to the first element in the 00321 * %unordered_map. 00322 */ 00323 iterator 00324 begin() noexcept 00325 { return _M_h.begin(); } 00326 00327 //@{ 00328 /** 00329 * Returns a read-only (constant) iterator that points to the first 00330 * element in the %unordered_map. 00331 */ 00332 const_iterator 00333 begin() const noexcept 00334 { return _M_h.begin(); } 00335 00336 const_iterator 00337 cbegin() const noexcept 00338 { return _M_h.begin(); } 00339 //@} 00340 00341 /** 00342 * Returns a read/write iterator that points one past the last element in 00343 * the %unordered_map. 00344 */ 00345 iterator 00346 end() noexcept 00347 { return _M_h.end(); } 00348 00349 //@{ 00350 /** 00351 * Returns a read-only (constant) iterator that points one past the last 00352 * element in the %unordered_map. 00353 */ 00354 const_iterator 00355 end() const noexcept 00356 { return _M_h.end(); } 00357 00358 const_iterator 00359 cend() const noexcept 00360 { return _M_h.end(); } 00361 //@} 00362 00363 // modifiers. 00364 00365 /** 00366 * @brief Attempts to build and insert a std::pair into the 00367 * %unordered_map. 00368 * 00369 * @param __args Arguments used to generate a new pair instance (see 00370 * std::piecewise_contruct for passing arguments to each 00371 * part of the pair constructor). 00372 * 00373 * @return A pair, of which the first element is an iterator that points 00374 * to the possibly inserted pair, and the second is a bool that 00375 * is true if the pair was actually inserted. 00376 * 00377 * This function attempts to build and insert a (key, value) %pair into 00378 * the %unordered_map. 00379 * An %unordered_map relies on unique keys and thus a %pair is only 00380 * inserted if its first element (the key) is not already present in the 00381 * %unordered_map. 00382 * 00383 * Insertion requires amortized constant time. 00384 */ 00385 template<typename... _Args> 00386 std::pair<iterator, bool> 00387 emplace(_Args&&... __args) 00388 { return _M_h.emplace(std::forward<_Args>(__args)...); } 00389 00390 /** 00391 * @brief Attempts to build and insert a std::pair into the 00392 * %unordered_map. 00393 * 00394 * @param __pos An iterator that serves as a hint as to where the pair 00395 * should be inserted. 00396 * @param __args Arguments used to generate a new pair instance (see 00397 * std::piecewise_contruct for passing arguments to each 00398 * part of the pair constructor). 00399 * @return An iterator that points to the element with key of the 00400 * std::pair built from @a __args (may or may not be that 00401 * std::pair). 00402 * 00403 * This function is not concerned about whether the insertion took place, 00404 * and thus does not return a boolean like the single-argument emplace() 00405 * does. 00406 * Note that the first parameter is only a hint and can potentially 00407 * improve the performance of the insertion process. A bad hint would 00408 * cause no gains in efficiency. 00409 * 00410 * See 00411 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 00412 * for more on @a hinting. 00413 * 00414 * Insertion requires amortized constant time. 00415 */ 00416 template<typename... _Args> 00417 iterator 00418 emplace_hint(const_iterator __pos, _Args&&... __args) 00419 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); } 00420 00421 #if __cplusplus > 201402L 00422 /// Extract a node. 00423 node_type 00424 extract(const_iterator __pos) 00425 { 00426 __glibcxx_assert(__pos != end()); 00427 return _M_h.extract(__pos); 00428 } 00429 00430 /// Extract a node. 00431 node_type 00432 extract(const key_type& __key) 00433 { return _M_h.extract(__key); } 00434 00435 /// Re-insert an extracted node. 00436 insert_return_type 00437 insert(node_type&& __nh) 00438 { return _M_h._M_reinsert_node(std::move(__nh)); } 00439 00440 /// Re-insert an extracted node. 00441 iterator 00442 insert(const_iterator, node_type&& __nh) 00443 { return _M_h._M_reinsert_node(std::move(__nh)).position; } 00444 00445 #define __cpp_lib_unordered_map_try_emplace 201411 00446 /** 00447 * @brief Attempts to build and insert a std::pair into the 00448 * %unordered_map. 00449 * 00450 * @param __k Key to use for finding a possibly existing pair in 00451 * the unordered_map. 00452 * @param __args Arguments used to generate the .second for a 00453 * new pair instance. 00454 * 00455 * @return A pair, of which the first element is an iterator that points 00456 * to the possibly inserted pair, and the second is a bool that 00457 * is true if the pair was actually inserted. 00458 * 00459 * This function attempts to build and insert a (key, value) %pair into 00460 * the %unordered_map. 00461 * An %unordered_map relies on unique keys and thus a %pair is only 00462 * inserted if its first element (the key) is not already present in the 00463 * %unordered_map. 00464 * If a %pair is not inserted, this function has no effect. 00465 * 00466 * Insertion requires amortized constant time. 00467 */ 00468 template <typename... _Args> 00469 pair<iterator, bool> 00470 try_emplace(const key_type& __k, _Args&&... __args) 00471 { 00472 iterator __i = find(__k); 00473 if (__i == end()) 00474 { 00475 __i = emplace(std::piecewise_construct, 00476 std::forward_as_tuple(__k), 00477 std::forward_as_tuple( 00478 std::forward<_Args>(__args)...)) 00479 .first; 00480 return {__i, true}; 00481 } 00482 return {__i, false}; 00483 } 00484 00485 // move-capable overload 00486 template <typename... _Args> 00487 pair<iterator, bool> 00488 try_emplace(key_type&& __k, _Args&&... __args) 00489 { 00490 iterator __i = find(__k); 00491 if (__i == end()) 00492 { 00493 __i = emplace(std::piecewise_construct, 00494 std::forward_as_tuple(std::move(__k)), 00495 std::forward_as_tuple( 00496 std::forward<_Args>(__args)...)) 00497 .first; 00498 return {__i, true}; 00499 } 00500 return {__i, false}; 00501 } 00502 00503 /** 00504 * @brief Attempts to build and insert a std::pair into the 00505 * %unordered_map. 00506 * 00507 * @param __hint An iterator that serves as a hint as to where the pair 00508 * should be inserted. 00509 * @param __k Key to use for finding a possibly existing pair in 00510 * the unordered_map. 00511 * @param __args Arguments used to generate the .second for a 00512 * new pair instance. 00513 * @return An iterator that points to the element with key of the 00514 * std::pair built from @a __args (may or may not be that 00515 * std::pair). 00516 * 00517 * This function is not concerned about whether the insertion took place, 00518 * and thus does not return a boolean like the single-argument emplace() 00519 * does. However, if insertion did not take place, 00520 * this function has no effect. 00521 * Note that the first parameter is only a hint and can potentially 00522 * improve the performance of the insertion process. A bad hint would 00523 * cause no gains in efficiency. 00524 * 00525 * See 00526 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 00527 * for more on @a hinting. 00528 * 00529 * Insertion requires amortized constant time. 00530 */ 00531 template <typename... _Args> 00532 iterator 00533 try_emplace(const_iterator __hint, const key_type& __k, 00534 _Args&&... __args) 00535 { 00536 iterator __i = find(__k); 00537 if (__i == end()) 00538 __i = emplace_hint(__hint, std::piecewise_construct, 00539 std::forward_as_tuple(__k), 00540 std::forward_as_tuple( 00541 std::forward<_Args>(__args)...)); 00542 return __i; 00543 } 00544 00545 // move-capable overload 00546 template <typename... _Args> 00547 iterator 00548 try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args) 00549 { 00550 iterator __i = find(__k); 00551 if (__i == end()) 00552 __i = emplace_hint(__hint, std::piecewise_construct, 00553 std::forward_as_tuple(std::move(__k)), 00554 std::forward_as_tuple( 00555 std::forward<_Args>(__args)...)); 00556 return __i; 00557 } 00558 #endif // C++17 00559 00560 //@{ 00561 /** 00562 * @brief Attempts to insert a std::pair into the %unordered_map. 00563 00564 * @param __x Pair to be inserted (see std::make_pair for easy 00565 * creation of pairs). 00566 * 00567 * @return A pair, of which the first element is an iterator that 00568 * points to the possibly inserted pair, and the second is 00569 * a bool that is true if the pair was actually inserted. 00570 * 00571 * This function attempts to insert a (key, value) %pair into the 00572 * %unordered_map. An %unordered_map relies on unique keys and thus a 00573 * %pair is only inserted if its first element (the key) is not already 00574 * present in the %unordered_map. 00575 * 00576 * Insertion requires amortized constant time. 00577 */ 00578 std::pair<iterator, bool> 00579 insert(const value_type& __x) 00580 { return _M_h.insert(__x); } 00581 00582 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00583 // 2354. Unnecessary copying when inserting into maps with braced-init 00584 std::pair<iterator, bool> 00585 insert(value_type&& __x) 00586 { return _M_h.insert(std::move(__x)); } 00587 00588 template<typename _Pair> 00589 __enable_if_t<is_constructible<value_type, _Pair&&>::value, 00590 pair<iterator, bool>> 00591 insert(_Pair&& __x) 00592 { return _M_h.emplace(std::forward<_Pair>(__x)); } 00593 //@} 00594 00595 //@{ 00596 /** 00597 * @brief Attempts to insert a std::pair into the %unordered_map. 00598 * @param __hint An iterator that serves as a hint as to where the 00599 * pair should be inserted. 00600 * @param __x Pair to be inserted (see std::make_pair for easy creation 00601 * of pairs). 00602 * @return An iterator that points to the element with key of 00603 * @a __x (may or may not be the %pair passed in). 00604 * 00605 * This function is not concerned about whether the insertion took place, 00606 * and thus does not return a boolean like the single-argument insert() 00607 * does. Note that the first parameter is only a hint and can 00608 * potentially improve the performance of the insertion process. A bad 00609 * hint would cause no gains in efficiency. 00610 * 00611 * See 00612 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 00613 * for more on @a hinting. 00614 * 00615 * Insertion requires amortized constant time. 00616 */ 00617 iterator 00618 insert(const_iterator __hint, const value_type& __x) 00619 { return _M_h.insert(__hint, __x); } 00620 00621 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00622 // 2354. Unnecessary copying when inserting into maps with braced-init 00623 iterator 00624 insert(const_iterator __hint, value_type&& __x) 00625 { return _M_h.insert(__hint, std::move(__x)); } 00626 00627 template<typename _Pair> 00628 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator> 00629 insert(const_iterator __hint, _Pair&& __x) 00630 { return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); } 00631 //@} 00632 00633 /** 00634 * @brief A template function that attempts to insert a range of 00635 * elements. 00636 * @param __first Iterator pointing to the start of the range to be 00637 * inserted. 00638 * @param __last Iterator pointing to the end of the range. 00639 * 00640 * Complexity similar to that of the range constructor. 00641 */ 00642 template<typename _InputIterator> 00643 void 00644 insert(_InputIterator __first, _InputIterator __last) 00645 { _M_h.insert(__first, __last); } 00646 00647 /** 00648 * @brief Attempts to insert a list of elements into the %unordered_map. 00649 * @param __l A std::initializer_list<value_type> of elements 00650 * to be inserted. 00651 * 00652 * Complexity similar to that of the range constructor. 00653 */ 00654 void 00655 insert(initializer_list<value_type> __l) 00656 { _M_h.insert(__l); } 00657 00658 00659 #if __cplusplus > 201402L 00660 #define __cpp_lib_unordered_map_insertion 201411 00661 /** 00662 * @brief Attempts to insert a std::pair into the %unordered_map. 00663 * @param __k Key to use for finding a possibly existing pair in 00664 * the map. 00665 * @param __obj Argument used to generate the .second for a pair 00666 * instance. 00667 * 00668 * @return A pair, of which the first element is an iterator that 00669 * points to the possibly inserted pair, and the second is 00670 * a bool that is true if the pair was actually inserted. 00671 * 00672 * This function attempts to insert a (key, value) %pair into the 00673 * %unordered_map. An %unordered_map relies on unique keys and thus a 00674 * %pair is only inserted if its first element (the key) is not already 00675 * present in the %unordered_map. 00676 * If the %pair was already in the %unordered_map, the .second of 00677 * the %pair is assigned from __obj. 00678 * 00679 * Insertion requires amortized constant time. 00680 */ 00681 template <typename _Obj> 00682 pair<iterator, bool> 00683 insert_or_assign(const key_type& __k, _Obj&& __obj) 00684 { 00685 iterator __i = find(__k); 00686 if (__i == end()) 00687 { 00688 __i = emplace(std::piecewise_construct, 00689 std::forward_as_tuple(__k), 00690 std::forward_as_tuple(std::forward<_Obj>(__obj))) 00691 .first; 00692 return {__i, true}; 00693 } 00694 (*__i).second = std::forward<_Obj>(__obj); 00695 return {__i, false}; 00696 } 00697 00698 // move-capable overload 00699 template <typename _Obj> 00700 pair<iterator, bool> 00701 insert_or_assign(key_type&& __k, _Obj&& __obj) 00702 { 00703 iterator __i = find(__k); 00704 if (__i == end()) 00705 { 00706 __i = emplace(std::piecewise_construct, 00707 std::forward_as_tuple(std::move(__k)), 00708 std::forward_as_tuple(std::forward<_Obj>(__obj))) 00709 .first; 00710 return {__i, true}; 00711 } 00712 (*__i).second = std::forward<_Obj>(__obj); 00713 return {__i, false}; 00714 } 00715 00716 /** 00717 * @brief Attempts to insert a std::pair into the %unordered_map. 00718 * @param __hint An iterator that serves as a hint as to where the 00719 * pair should be inserted. 00720 * @param __k Key to use for finding a possibly existing pair in 00721 * the unordered_map. 00722 * @param __obj Argument used to generate the .second for a pair 00723 * instance. 00724 * @return An iterator that points to the element with key of 00725 * @a __x (may or may not be the %pair passed in). 00726 * 00727 * This function is not concerned about whether the insertion took place, 00728 * and thus does not return a boolean like the single-argument insert() 00729 * does. 00730 * If the %pair was already in the %unordered map, the .second of 00731 * the %pair is assigned from __obj. 00732 * Note that the first parameter is only a hint and can 00733 * potentially improve the performance of the insertion process. A bad 00734 * hint would cause no gains in efficiency. 00735 * 00736 * See 00737 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 00738 * for more on @a hinting. 00739 * 00740 * Insertion requires amortized constant time. 00741 */ 00742 template <typename _Obj> 00743 iterator 00744 insert_or_assign(const_iterator __hint, const key_type& __k, 00745 _Obj&& __obj) 00746 { 00747 iterator __i = find(__k); 00748 if (__i == end()) 00749 { 00750 return emplace_hint(__hint, std::piecewise_construct, 00751 std::forward_as_tuple(__k), 00752 std::forward_as_tuple( 00753 std::forward<_Obj>(__obj))); 00754 } 00755 (*__i).second = std::forward<_Obj>(__obj); 00756 return __i; 00757 } 00758 00759 // move-capable overload 00760 template <typename _Obj> 00761 iterator 00762 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj) 00763 { 00764 iterator __i = find(__k); 00765 if (__i == end()) 00766 { 00767 return emplace_hint(__hint, std::piecewise_construct, 00768 std::forward_as_tuple(std::move(__k)), 00769 std::forward_as_tuple( 00770 std::forward<_Obj>(__obj))); 00771 } 00772 (*__i).second = std::forward<_Obj>(__obj); 00773 return __i; 00774 } 00775 #endif 00776 00777 //@{ 00778 /** 00779 * @brief Erases an element from an %unordered_map. 00780 * @param __position An iterator pointing to the element to be erased. 00781 * @return An iterator pointing to the element immediately following 00782 * @a __position prior to the element being erased. If no such 00783 * element exists, end() is returned. 00784 * 00785 * This function erases an element, pointed to by the given iterator, 00786 * from an %unordered_map. 00787 * Note that this function only erases the element, and that if the 00788 * element is itself a pointer, the pointed-to memory is not touched in 00789 * any way. Managing the pointer is the user's responsibility. 00790 */ 00791 iterator 00792 erase(const_iterator __position) 00793 { return _M_h.erase(__position); } 00794 00795 // LWG 2059. 00796 iterator 00797 erase(iterator __position) 00798 { return _M_h.erase(__position); } 00799 //@} 00800 00801 /** 00802 * @brief Erases elements according to the provided key. 00803 * @param __x Key of element to be erased. 00804 * @return The number of elements erased. 00805 * 00806 * This function erases all the elements located by the given key from 00807 * an %unordered_map. For an %unordered_map the result of this function 00808 * can only be 0 (not present) or 1 (present). 00809 * Note that this function only erases the element, and that if the 00810 * element is itself a pointer, the pointed-to memory is not touched in 00811 * any way. Managing the pointer is the user's responsibility. 00812 */ 00813 size_type 00814 erase(const key_type& __x) 00815 { return _M_h.erase(__x); } 00816 00817 /** 00818 * @brief Erases a [__first,__last) range of elements from an 00819 * %unordered_map. 00820 * @param __first Iterator pointing to the start of the range to be 00821 * erased. 00822 * @param __last Iterator pointing to the end of the range to 00823 * be erased. 00824 * @return The iterator @a __last. 00825 * 00826 * This function erases a sequence of elements from an %unordered_map. 00827 * Note that this function only erases the elements, and that if 00828 * the element is itself a pointer, the pointed-to memory is not touched 00829 * in any way. Managing the pointer is the user's responsibility. 00830 */ 00831 iterator 00832 erase(const_iterator __first, const_iterator __last) 00833 { return _M_h.erase(__first, __last); } 00834 00835 /** 00836 * Erases all elements in an %unordered_map. 00837 * Note that this function only erases the elements, and that if the 00838 * elements themselves are pointers, the pointed-to memory is not touched 00839 * in any way. Managing the pointer is the user's responsibility. 00840 */ 00841 void 00842 clear() noexcept 00843 { _M_h.clear(); } 00844 00845 /** 00846 * @brief Swaps data with another %unordered_map. 00847 * @param __x An %unordered_map of the same element and allocator 00848 * types. 00849 * 00850 * This exchanges the elements between two %unordered_map in constant 00851 * time. 00852 * Note that the global std::swap() function is specialized such that 00853 * std::swap(m1,m2) will feed to this function. 00854 */ 00855 void 00856 swap(unordered_map& __x) 00857 noexcept( noexcept(_M_h.swap(__x._M_h)) ) 00858 { _M_h.swap(__x._M_h); } 00859 00860 #if __cplusplus > 201402L 00861 template<typename, typename, typename> 00862 friend class std::_Hash_merge_helper; 00863 00864 template<typename _H2, typename _P2> 00865 void 00866 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source) 00867 { 00868 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>; 00869 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source)); 00870 } 00871 00872 template<typename _H2, typename _P2> 00873 void 00874 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source) 00875 { merge(__source); } 00876 00877 template<typename _H2, typename _P2> 00878 void 00879 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source) 00880 { 00881 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>; 00882 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source)); 00883 } 00884 00885 template<typename _H2, typename _P2> 00886 void 00887 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source) 00888 { merge(__source); } 00889 #endif // C++17 00890 00891 // observers. 00892 00893 /// Returns the hash functor object with which the %unordered_map was 00894 /// constructed. 00895 hasher 00896 hash_function() const 00897 { return _M_h.hash_function(); } 00898 00899 /// Returns the key comparison object with which the %unordered_map was 00900 /// constructed. 00901 key_equal 00902 key_eq() const 00903 { return _M_h.key_eq(); } 00904 00905 // lookup. 00906 00907 //@{ 00908 /** 00909 * @brief Tries to locate an element in an %unordered_map. 00910 * @param __x Key to be located. 00911 * @return Iterator pointing to sought-after element, or end() if not 00912 * found. 00913 * 00914 * This function takes a key and tries to locate the element with which 00915 * the key matches. If successful the function returns an iterator 00916 * pointing to the sought after element. If unsuccessful it returns the 00917 * past-the-end ( @c end() ) iterator. 00918 */ 00919 iterator 00920 find(const key_type& __x) 00921 { return _M_h.find(__x); } 00922 00923 const_iterator 00924 find(const key_type& __x) const 00925 { return _M_h.find(__x); } 00926 //@} 00927 00928 /** 00929 * @brief Finds the number of elements. 00930 * @param __x Key to count. 00931 * @return Number of elements with specified key. 00932 * 00933 * This function only makes sense for %unordered_multimap; for 00934 * %unordered_map the result will either be 0 (not present) or 1 00935 * (present). 00936 */ 00937 size_type 00938 count(const key_type& __x) const 00939 { return _M_h.count(__x); } 00940 00941 //@{ 00942 /** 00943 * @brief Finds a subsequence matching given key. 00944 * @param __x Key to be located. 00945 * @return Pair of iterators that possibly points to the subsequence 00946 * matching given key. 00947 * 00948 * This function probably only makes sense for %unordered_multimap. 00949 */ 00950 std::pair<iterator, iterator> 00951 equal_range(const key_type& __x) 00952 { return _M_h.equal_range(__x); } 00953 00954 std::pair<const_iterator, const_iterator> 00955 equal_range(const key_type& __x) const 00956 { return _M_h.equal_range(__x); } 00957 //@} 00958 00959 //@{ 00960 /** 00961 * @brief Subscript ( @c [] ) access to %unordered_map data. 00962 * @param __k The key for which data should be retrieved. 00963 * @return A reference to the data of the (key,data) %pair. 00964 * 00965 * Allows for easy lookup with the subscript ( @c [] )operator. Returns 00966 * data associated with the key specified in subscript. If the key does 00967 * not exist, a pair with that key is created using default values, which 00968 * is then returned. 00969 * 00970 * Lookup requires constant time. 00971 */ 00972 mapped_type& 00973 operator[](const key_type& __k) 00974 { return _M_h[__k]; } 00975 00976 mapped_type& 00977 operator[](key_type&& __k) 00978 { return _M_h[std::move(__k)]; } 00979 //@} 00980 00981 //@{ 00982 /** 00983 * @brief Access to %unordered_map data. 00984 * @param __k The key for which data should be retrieved. 00985 * @return A reference to the data whose key is equal to @a __k, if 00986 * such a data is present in the %unordered_map. 00987 * @throw std::out_of_range If no such data is present. 00988 */ 00989 mapped_type& 00990 at(const key_type& __k) 00991 { return _M_h.at(__k); } 00992 00993 const mapped_type& 00994 at(const key_type& __k) const 00995 { return _M_h.at(__k); } 00996 //@} 00997 00998 // bucket interface. 00999 01000 /// Returns the number of buckets of the %unordered_map. 01001 size_type 01002 bucket_count() const noexcept 01003 { return _M_h.bucket_count(); } 01004 01005 /// Returns the maximum number of buckets of the %unordered_map. 01006 size_type 01007 max_bucket_count() const noexcept 01008 { return _M_h.max_bucket_count(); } 01009 01010 /* 01011 * @brief Returns the number of elements in a given bucket. 01012 * @param __n A bucket index. 01013 * @return The number of elements in the bucket. 01014 */ 01015 size_type 01016 bucket_size(size_type __n) const 01017 { return _M_h.bucket_size(__n); } 01018 01019 /* 01020 * @brief Returns the bucket index of a given element. 01021 * @param __key A key instance. 01022 * @return The key bucket index. 01023 */ 01024 size_type 01025 bucket(const key_type& __key) const 01026 { return _M_h.bucket(__key); } 01027 01028 /** 01029 * @brief Returns a read/write iterator pointing to the first bucket 01030 * element. 01031 * @param __n The bucket index. 01032 * @return A read/write local iterator. 01033 */ 01034 local_iterator 01035 begin(size_type __n) 01036 { return _M_h.begin(__n); } 01037 01038 //@{ 01039 /** 01040 * @brief Returns a read-only (constant) iterator pointing to the first 01041 * bucket element. 01042 * @param __n The bucket index. 01043 * @return A read-only local iterator. 01044 */ 01045 const_local_iterator 01046 begin(size_type __n) const 01047 { return _M_h.begin(__n); } 01048 01049 const_local_iterator 01050 cbegin(size_type __n) const 01051 { return _M_h.cbegin(__n); } 01052 //@} 01053 01054 /** 01055 * @brief Returns a read/write iterator pointing to one past the last 01056 * bucket elements. 01057 * @param __n The bucket index. 01058 * @return A read/write local iterator. 01059 */ 01060 local_iterator 01061 end(size_type __n) 01062 { return _M_h.end(__n); } 01063 01064 //@{ 01065 /** 01066 * @brief Returns a read-only (constant) iterator pointing to one past 01067 * the last bucket elements. 01068 * @param __n The bucket index. 01069 * @return A read-only local iterator. 01070 */ 01071 const_local_iterator 01072 end(size_type __n) const 01073 { return _M_h.end(__n); } 01074 01075 const_local_iterator 01076 cend(size_type __n) const 01077 { return _M_h.cend(__n); } 01078 //@} 01079 01080 // hash policy. 01081 01082 /// Returns the average number of elements per bucket. 01083 float 01084 load_factor() const noexcept 01085 { return _M_h.load_factor(); } 01086 01087 /// Returns a positive number that the %unordered_map tries to keep the 01088 /// load factor less than or equal to. 01089 float 01090 max_load_factor() const noexcept 01091 { return _M_h.max_load_factor(); } 01092 01093 /** 01094 * @brief Change the %unordered_map maximum load factor. 01095 * @param __z The new maximum load factor. 01096 */ 01097 void 01098 max_load_factor(float __z) 01099 { _M_h.max_load_factor(__z); } 01100 01101 /** 01102 * @brief May rehash the %unordered_map. 01103 * @param __n The new number of buckets. 01104 * 01105 * Rehash will occur only if the new number of buckets respect the 01106 * %unordered_map maximum load factor. 01107 */ 01108 void 01109 rehash(size_type __n) 01110 { _M_h.rehash(__n); } 01111 01112 /** 01113 * @brief Prepare the %unordered_map for a specified number of 01114 * elements. 01115 * @param __n Number of elements required. 01116 * 01117 * Same as rehash(ceil(n / max_load_factor())). 01118 */ 01119 void 01120 reserve(size_type __n) 01121 { _M_h.reserve(__n); } 01122 01123 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1, 01124 typename _Alloc1> 01125 friend bool 01126 operator==(const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&, 01127 const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&); 01128 }; 01129 01130 #if __cpp_deduction_guides >= 201606 01131 01132 template<typename _InputIterator, 01133 typename _Hash = hash<__iter_key_t<_InputIterator>>, 01134 typename _Pred = equal_to<__iter_key_t<_InputIterator>>, 01135 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, 01136 typename = _RequireInputIter<_InputIterator>, 01137 typename = _RequireAllocator<_Allocator>> 01138 unordered_map(_InputIterator, _InputIterator, 01139 typename unordered_map<int, int>::size_type = {}, 01140 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 01141 -> unordered_map<__iter_key_t<_InputIterator>, 01142 __iter_val_t<_InputIterator>, 01143 _Hash, _Pred, _Allocator>; 01144 01145 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>, 01146 typename _Pred = equal_to<_Key>, 01147 typename _Allocator = allocator<pair<const _Key, _Tp>>, 01148 typename = _RequireAllocator<_Allocator>> 01149 unordered_map(initializer_list<pair<_Key, _Tp>>, 01150 typename unordered_map<int, int>::size_type = {}, 01151 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 01152 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>; 01153 01154 template<typename _InputIterator, typename _Allocator, 01155 typename = _RequireInputIter<_InputIterator>, 01156 typename = _RequireAllocator<_Allocator>> 01157 unordered_map(_InputIterator, _InputIterator, 01158 typename unordered_map<int, int>::size_type, _Allocator) 01159 -> unordered_map<__iter_key_t<_InputIterator>, 01160 __iter_val_t<_InputIterator>, 01161 hash<__iter_key_t<_InputIterator>>, 01162 equal_to<__iter_key_t<_InputIterator>>, 01163 _Allocator>; 01164 01165 template<typename _InputIterator, typename _Allocator, 01166 typename = _RequireInputIter<_InputIterator>, 01167 typename = _RequireAllocator<_Allocator>> 01168 unordered_map(_InputIterator, _InputIterator, _Allocator) 01169 -> unordered_map<__iter_key_t<_InputIterator>, 01170 __iter_val_t<_InputIterator>, 01171 hash<__iter_key_t<_InputIterator>>, 01172 equal_to<__iter_key_t<_InputIterator>>, 01173 _Allocator>; 01174 01175 template<typename _InputIterator, typename _Hash, typename _Allocator, 01176 typename = _RequireInputIter<_InputIterator>, 01177 typename = _RequireAllocator<_Allocator>> 01178 unordered_map(_InputIterator, _InputIterator, 01179 typename unordered_map<int, int>::size_type, 01180 _Hash, _Allocator) 01181 -> unordered_map<__iter_key_t<_InputIterator>, 01182 __iter_val_t<_InputIterator>, _Hash, 01183 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 01184 01185 template<typename _Key, typename _Tp, typename _Allocator, 01186 typename = _RequireAllocator<_Allocator>> 01187 unordered_map(initializer_list<pair<_Key, _Tp>>, 01188 typename unordered_map<int, int>::size_type, 01189 _Allocator) 01190 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 01191 01192 template<typename _Key, typename _Tp, typename _Allocator, 01193 typename = _RequireAllocator<_Allocator>> 01194 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator) 01195 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 01196 01197 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator, 01198 typename = _RequireAllocator<_Allocator>> 01199 unordered_map(initializer_list<pair<_Key, _Tp>>, 01200 typename unordered_map<int, int>::size_type, 01201 _Hash, _Allocator) 01202 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>; 01203 01204 #endif 01205 01206 /** 01207 * @brief A standard container composed of equivalent keys 01208 * (possibly containing multiple of each key value) that associates 01209 * values of another type with the keys. 01210 * 01211 * @ingroup unordered_associative_containers 01212 * 01213 * @tparam _Key Type of key objects. 01214 * @tparam _Tp Type of mapped objects. 01215 * @tparam _Hash Hashing function object type, defaults to hash<_Value>. 01216 * @tparam _Pred Predicate function object type, defaults 01217 * to equal_to<_Value>. 01218 * @tparam _Alloc Allocator type, defaults to 01219 * std::allocator<std::pair<const _Key, _Tp>>. 01220 * 01221 * Meets the requirements of a <a href="tables.html#65">container</a>, and 01222 * <a href="tables.html#xx">unordered associative container</a> 01223 * 01224 * The resulting value type of the container is std::pair<const _Key, _Tp>. 01225 * 01226 * Base is _Hashtable, dispatched at compile time via template 01227 * alias __ummap_hashtable. 01228 */ 01229 template<typename _Key, typename _Tp, 01230 typename _Hash = hash<_Key>, 01231 typename _Pred = equal_to<_Key>, 01232 typename _Alloc = allocator<std::pair<const _Key, _Tp>>> 01233 class unordered_multimap 01234 { 01235 typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable; 01236 _Hashtable _M_h; 01237 01238 public: 01239 // typedefs: 01240 //@{ 01241 /// Public typedefs. 01242 typedef typename _Hashtable::key_type key_type; 01243 typedef typename _Hashtable::value_type value_type; 01244 typedef typename _Hashtable::mapped_type mapped_type; 01245 typedef typename _Hashtable::hasher hasher; 01246 typedef typename _Hashtable::key_equal key_equal; 01247 typedef typename _Hashtable::allocator_type allocator_type; 01248 //@} 01249 01250 //@{ 01251 /// Iterator-related typedefs. 01252 typedef typename _Hashtable::pointer pointer; 01253 typedef typename _Hashtable::const_pointer const_pointer; 01254 typedef typename _Hashtable::reference reference; 01255 typedef typename _Hashtable::const_reference const_reference; 01256 typedef typename _Hashtable::iterator iterator; 01257 typedef typename _Hashtable::const_iterator const_iterator; 01258 typedef typename _Hashtable::local_iterator local_iterator; 01259 typedef typename _Hashtable::const_local_iterator const_local_iterator; 01260 typedef typename _Hashtable::size_type size_type; 01261 typedef typename _Hashtable::difference_type difference_type; 01262 //@} 01263 01264 #if __cplusplus > 201402L 01265 using node_type = typename _Hashtable::node_type; 01266 #endif 01267 01268 //construct/destroy/copy 01269 01270 /// Default constructor. 01271 unordered_multimap() = default; 01272 01273 /** 01274 * @brief Default constructor creates no elements. 01275 * @param __n Mnimal initial number of buckets. 01276 * @param __hf A hash functor. 01277 * @param __eql A key equality functor. 01278 * @param __a An allocator object. 01279 */ 01280 explicit 01281 unordered_multimap(size_type __n, 01282 const hasher& __hf = hasher(), 01283 const key_equal& __eql = key_equal(), 01284 const allocator_type& __a = allocator_type()) 01285 : _M_h(__n, __hf, __eql, __a) 01286 { } 01287 01288 /** 01289 * @brief Builds an %unordered_multimap from a range. 01290 * @param __first An input iterator. 01291 * @param __last An input iterator. 01292 * @param __n Minimal initial number of buckets. 01293 * @param __hf A hash functor. 01294 * @param __eql A key equality functor. 01295 * @param __a An allocator object. 01296 * 01297 * Create an %unordered_multimap consisting of copies of the elements 01298 * from [__first,__last). This is linear in N (where N is 01299 * distance(__first,__last)). 01300 */ 01301 template<typename _InputIterator> 01302 unordered_multimap(_InputIterator __first, _InputIterator __last, 01303 size_type __n = 0, 01304 const hasher& __hf = hasher(), 01305 const key_equal& __eql = key_equal(), 01306 const allocator_type& __a = allocator_type()) 01307 : _M_h(__first, __last, __n, __hf, __eql, __a) 01308 { } 01309 01310 /// Copy constructor. 01311 unordered_multimap(const unordered_multimap&) = default; 01312 01313 /// Move constructor. 01314 unordered_multimap(unordered_multimap&&) = default; 01315 01316 /** 01317 * @brief Creates an %unordered_multimap with no elements. 01318 * @param __a An allocator object. 01319 */ 01320 explicit 01321 unordered_multimap(const allocator_type& __a) 01322 : _M_h(__a) 01323 { } 01324 01325 /* 01326 * @brief Copy constructor with allocator argument. 01327 * @param __uset Input %unordered_multimap to copy. 01328 * @param __a An allocator object. 01329 */ 01330 unordered_multimap(const unordered_multimap& __ummap, 01331 const allocator_type& __a) 01332 : _M_h(__ummap._M_h, __a) 01333 { } 01334 01335 /* 01336 * @brief Move constructor with allocator argument. 01337 * @param __uset Input %unordered_multimap to move. 01338 * @param __a An allocator object. 01339 */ 01340 unordered_multimap(unordered_multimap&& __ummap, 01341 const allocator_type& __a) 01342 : _M_h(std::move(__ummap._M_h), __a) 01343 { } 01344 01345 /** 01346 * @brief Builds an %unordered_multimap from an initializer_list. 01347 * @param __l An initializer_list. 01348 * @param __n Minimal initial number of buckets. 01349 * @param __hf A hash functor. 01350 * @param __eql A key equality functor. 01351 * @param __a An allocator object. 01352 * 01353 * Create an %unordered_multimap consisting of copies of the elements in 01354 * the list. This is linear in N (where N is @a __l.size()). 01355 */ 01356 unordered_multimap(initializer_list<value_type> __l, 01357 size_type __n = 0, 01358 const hasher& __hf = hasher(), 01359 const key_equal& __eql = key_equal(), 01360 const allocator_type& __a = allocator_type()) 01361 : _M_h(__l, __n, __hf, __eql, __a) 01362 { } 01363 01364 unordered_multimap(size_type __n, const allocator_type& __a) 01365 : unordered_multimap(__n, hasher(), key_equal(), __a) 01366 { } 01367 01368 unordered_multimap(size_type __n, const hasher& __hf, 01369 const allocator_type& __a) 01370 : unordered_multimap(__n, __hf, key_equal(), __a) 01371 { } 01372 01373 template<typename _InputIterator> 01374 unordered_multimap(_InputIterator __first, _InputIterator __last, 01375 size_type __n, 01376 const allocator_type& __a) 01377 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) 01378 { } 01379 01380 template<typename _InputIterator> 01381 unordered_multimap(_InputIterator __first, _InputIterator __last, 01382 size_type __n, const hasher& __hf, 01383 const allocator_type& __a) 01384 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) 01385 { } 01386 01387 unordered_multimap(initializer_list<value_type> __l, 01388 size_type __n, 01389 const allocator_type& __a) 01390 : unordered_multimap(__l, __n, hasher(), key_equal(), __a) 01391 { } 01392 01393 unordered_multimap(initializer_list<value_type> __l, 01394 size_type __n, const hasher& __hf, 01395 const allocator_type& __a) 01396 : unordered_multimap(__l, __n, __hf, key_equal(), __a) 01397 { } 01398 01399 /// Copy assignment operator. 01400 unordered_multimap& 01401 operator=(const unordered_multimap&) = default; 01402 01403 /// Move assignment operator. 01404 unordered_multimap& 01405 operator=(unordered_multimap&&) = default; 01406 01407 /** 01408 * @brief %Unordered_multimap list assignment operator. 01409 * @param __l An initializer_list. 01410 * 01411 * This function fills an %unordered_multimap with copies of the 01412 * elements in the initializer list @a __l. 01413 * 01414 * Note that the assignment completely changes the %unordered_multimap 01415 * and that the resulting %unordered_multimap's size is the same as the 01416 * number of elements assigned. 01417 */ 01418 unordered_multimap& 01419 operator=(initializer_list<value_type> __l) 01420 { 01421 _M_h = __l; 01422 return *this; 01423 } 01424 01425 /// Returns the allocator object used by the %unordered_multimap. 01426 allocator_type 01427 get_allocator() const noexcept 01428 { return _M_h.get_allocator(); } 01429 01430 // size and capacity: 01431 01432 /// Returns true if the %unordered_multimap is empty. 01433 bool 01434 empty() const noexcept 01435 { return _M_h.empty(); } 01436 01437 /// Returns the size of the %unordered_multimap. 01438 size_type 01439 size() const noexcept 01440 { return _M_h.size(); } 01441 01442 /// Returns the maximum size of the %unordered_multimap. 01443 size_type 01444 max_size() const noexcept 01445 { return _M_h.max_size(); } 01446 01447 // iterators. 01448 01449 /** 01450 * Returns a read/write iterator that points to the first element in the 01451 * %unordered_multimap. 01452 */ 01453 iterator 01454 begin() noexcept 01455 { return _M_h.begin(); } 01456 01457 //@{ 01458 /** 01459 * Returns a read-only (constant) iterator that points to the first 01460 * element in the %unordered_multimap. 01461 */ 01462 const_iterator 01463 begin() const noexcept 01464 { return _M_h.begin(); } 01465 01466 const_iterator 01467 cbegin() const noexcept 01468 { return _M_h.begin(); } 01469 //@} 01470 01471 /** 01472 * Returns a read/write iterator that points one past the last element in 01473 * the %unordered_multimap. 01474 */ 01475 iterator 01476 end() noexcept 01477 { return _M_h.end(); } 01478 01479 //@{ 01480 /** 01481 * Returns a read-only (constant) iterator that points one past the last 01482 * element in the %unordered_multimap. 01483 */ 01484 const_iterator 01485 end() const noexcept 01486 { return _M_h.end(); } 01487 01488 const_iterator 01489 cend() const noexcept 01490 { return _M_h.end(); } 01491 //@} 01492 01493 // modifiers. 01494 01495 /** 01496 * @brief Attempts to build and insert a std::pair into the 01497 * %unordered_multimap. 01498 * 01499 * @param __args Arguments used to generate a new pair instance (see 01500 * std::piecewise_contruct for passing arguments to each 01501 * part of the pair constructor). 01502 * 01503 * @return An iterator that points to the inserted pair. 01504 * 01505 * This function attempts to build and insert a (key, value) %pair into 01506 * the %unordered_multimap. 01507 * 01508 * Insertion requires amortized constant time. 01509 */ 01510 template<typename... _Args> 01511 iterator 01512 emplace(_Args&&... __args) 01513 { return _M_h.emplace(std::forward<_Args>(__args)...); } 01514 01515 /** 01516 * @brief Attempts to build and insert a std::pair into the 01517 * %unordered_multimap. 01518 * 01519 * @param __pos An iterator that serves as a hint as to where the pair 01520 * should be inserted. 01521 * @param __args Arguments used to generate a new pair instance (see 01522 * std::piecewise_contruct for passing arguments to each 01523 * part of the pair constructor). 01524 * @return An iterator that points to the element with key of the 01525 * std::pair built from @a __args. 01526 * 01527 * Note that the first parameter is only a hint and can potentially 01528 * improve the performance of the insertion process. A bad hint would 01529 * cause no gains in efficiency. 01530 * 01531 * See 01532 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 01533 * for more on @a hinting. 01534 * 01535 * Insertion requires amortized constant time. 01536 */ 01537 template<typename... _Args> 01538 iterator 01539 emplace_hint(const_iterator __pos, _Args&&... __args) 01540 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); } 01541 01542 //@{ 01543 /** 01544 * @brief Inserts a std::pair into the %unordered_multimap. 01545 * @param __x Pair to be inserted (see std::make_pair for easy 01546 * creation of pairs). 01547 * 01548 * @return An iterator that points to the inserted pair. 01549 * 01550 * Insertion requires amortized constant time. 01551 */ 01552 iterator 01553 insert(const value_type& __x) 01554 { return _M_h.insert(__x); } 01555 01556 iterator 01557 insert(value_type&& __x) 01558 { return _M_h.insert(std::move(__x)); } 01559 01560 template<typename _Pair> 01561 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator> 01562 insert(_Pair&& __x) 01563 { return _M_h.emplace(std::forward<_Pair>(__x)); } 01564 //@} 01565 01566 //@{ 01567 /** 01568 * @brief Inserts a std::pair into the %unordered_multimap. 01569 * @param __hint An iterator that serves as a hint as to where the 01570 * pair should be inserted. 01571 * @param __x Pair to be inserted (see std::make_pair for easy creation 01572 * of pairs). 01573 * @return An iterator that points to the element with key of 01574 * @a __x (may or may not be the %pair passed in). 01575 * 01576 * Note that the first parameter is only a hint and can potentially 01577 * improve the performance of the insertion process. A bad hint would 01578 * cause no gains in efficiency. 01579 * 01580 * See 01581 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 01582 * for more on @a hinting. 01583 * 01584 * Insertion requires amortized constant time. 01585 */ 01586 iterator 01587 insert(const_iterator __hint, const value_type& __x) 01588 { return _M_h.insert(__hint, __x); } 01589 01590 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01591 // 2354. Unnecessary copying when inserting into maps with braced-init 01592 iterator 01593 insert(const_iterator __hint, value_type&& __x) 01594 { return _M_h.insert(__hint, std::move(__x)); } 01595 01596 template<typename _Pair> 01597 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator> 01598 insert(const_iterator __hint, _Pair&& __x) 01599 { return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); } 01600 //@} 01601 01602 /** 01603 * @brief A template function that attempts to insert a range of 01604 * elements. 01605 * @param __first Iterator pointing to the start of the range to be 01606 * inserted. 01607 * @param __last Iterator pointing to the end of the range. 01608 * 01609 * Complexity similar to that of the range constructor. 01610 */ 01611 template<typename _InputIterator> 01612 void 01613 insert(_InputIterator __first, _InputIterator __last) 01614 { _M_h.insert(__first, __last); } 01615 01616 /** 01617 * @brief Attempts to insert a list of elements into the 01618 * %unordered_multimap. 01619 * @param __l A std::initializer_list<value_type> of elements 01620 * to be inserted. 01621 * 01622 * Complexity similar to that of the range constructor. 01623 */ 01624 void 01625 insert(initializer_list<value_type> __l) 01626 { _M_h.insert(__l); } 01627 01628 #if __cplusplus > 201402L 01629 /// Extract a node. 01630 node_type 01631 extract(const_iterator __pos) 01632 { 01633 __glibcxx_assert(__pos != end()); 01634 return _M_h.extract(__pos); 01635 } 01636 01637 /// Extract a node. 01638 node_type 01639 extract(const key_type& __key) 01640 { return _M_h.extract(__key); } 01641 01642 /// Re-insert an extracted node. 01643 iterator 01644 insert(node_type&& __nh) 01645 { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); } 01646 01647 /// Re-insert an extracted node. 01648 iterator 01649 insert(const_iterator __hint, node_type&& __nh) 01650 { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); } 01651 #endif // C++17 01652 01653 //@{ 01654 /** 01655 * @brief Erases an element from an %unordered_multimap. 01656 * @param __position An iterator pointing to the element to be erased. 01657 * @return An iterator pointing to the element immediately following 01658 * @a __position prior to the element being erased. If no such 01659 * element exists, end() is returned. 01660 * 01661 * This function erases an element, pointed to by the given iterator, 01662 * from an %unordered_multimap. 01663 * Note that this function only erases the element, and that if the 01664 * element is itself a pointer, the pointed-to memory is not touched in 01665 * any way. Managing the pointer is the user's responsibility. 01666 */ 01667 iterator 01668 erase(const_iterator __position) 01669 { return _M_h.erase(__position); } 01670 01671 // LWG 2059. 01672 iterator 01673 erase(iterator __position) 01674 { return _M_h.erase(__position); } 01675 //@} 01676 01677 /** 01678 * @brief Erases elements according to the provided key. 01679 * @param __x Key of elements to be erased. 01680 * @return The number of elements erased. 01681 * 01682 * This function erases all the elements located by the given key from 01683 * an %unordered_multimap. 01684 * Note that this function only erases the element, and that if the 01685 * element is itself a pointer, the pointed-to memory is not touched in 01686 * any way. Managing the pointer is the user's responsibility. 01687 */ 01688 size_type 01689 erase(const key_type& __x) 01690 { return _M_h.erase(__x); } 01691 01692 /** 01693 * @brief Erases a [__first,__last) range of elements from an 01694 * %unordered_multimap. 01695 * @param __first Iterator pointing to the start of the range to be 01696 * erased. 01697 * @param __last Iterator pointing to the end of the range to 01698 * be erased. 01699 * @return The iterator @a __last. 01700 * 01701 * This function erases a sequence of elements from an 01702 * %unordered_multimap. 01703 * Note that this function only erases the elements, and that if 01704 * the element is itself a pointer, the pointed-to memory is not touched 01705 * in any way. Managing the pointer is the user's responsibility. 01706 */ 01707 iterator 01708 erase(const_iterator __first, const_iterator __last) 01709 { return _M_h.erase(__first, __last); } 01710 01711 /** 01712 * Erases all elements in an %unordered_multimap. 01713 * Note that this function only erases the elements, and that if the 01714 * elements themselves are pointers, the pointed-to memory is not touched 01715 * in any way. Managing the pointer is the user's responsibility. 01716 */ 01717 void 01718 clear() noexcept 01719 { _M_h.clear(); } 01720 01721 /** 01722 * @brief Swaps data with another %unordered_multimap. 01723 * @param __x An %unordered_multimap of the same element and allocator 01724 * types. 01725 * 01726 * This exchanges the elements between two %unordered_multimap in 01727 * constant time. 01728 * Note that the global std::swap() function is specialized such that 01729 * std::swap(m1,m2) will feed to this function. 01730 */ 01731 void 01732 swap(unordered_multimap& __x) 01733 noexcept( noexcept(_M_h.swap(__x._M_h)) ) 01734 { _M_h.swap(__x._M_h); } 01735 01736 #if __cplusplus > 201402L 01737 template<typename, typename, typename> 01738 friend class std::_Hash_merge_helper; 01739 01740 template<typename _H2, typename _P2> 01741 void 01742 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source) 01743 { 01744 using _Merge_helper 01745 = _Hash_merge_helper<unordered_multimap, _H2, _P2>; 01746 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); 01747 } 01748 01749 template<typename _H2, typename _P2> 01750 void 01751 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source) 01752 { merge(__source); } 01753 01754 template<typename _H2, typename _P2> 01755 void 01756 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source) 01757 { 01758 using _Merge_helper 01759 = _Hash_merge_helper<unordered_multimap, _H2, _P2>; 01760 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); 01761 } 01762 01763 template<typename _H2, typename _P2> 01764 void 01765 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source) 01766 { merge(__source); } 01767 #endif // C++17 01768 01769 // observers. 01770 01771 /// Returns the hash functor object with which the %unordered_multimap 01772 /// was constructed. 01773 hasher 01774 hash_function() const 01775 { return _M_h.hash_function(); } 01776 01777 /// Returns the key comparison object with which the %unordered_multimap 01778 /// was constructed. 01779 key_equal 01780 key_eq() const 01781 { return _M_h.key_eq(); } 01782 01783 // lookup. 01784 01785 //@{ 01786 /** 01787 * @brief Tries to locate an element in an %unordered_multimap. 01788 * @param __x Key to be located. 01789 * @return Iterator pointing to sought-after element, or end() if not 01790 * found. 01791 * 01792 * This function takes a key and tries to locate the element with which 01793 * the key matches. If successful the function returns an iterator 01794 * pointing to the sought after element. If unsuccessful it returns the 01795 * past-the-end ( @c end() ) iterator. 01796 */ 01797 iterator 01798 find(const key_type& __x) 01799 { return _M_h.find(__x); } 01800 01801 const_iterator 01802 find(const key_type& __x) const 01803 { return _M_h.find(__x); } 01804 //@} 01805 01806 /** 01807 * @brief Finds the number of elements. 01808 * @param __x Key to count. 01809 * @return Number of elements with specified key. 01810 */ 01811 size_type 01812 count(const key_type& __x) const 01813 { return _M_h.count(__x); } 01814 01815 //@{ 01816 /** 01817 * @brief Finds a subsequence matching given key. 01818 * @param __x Key to be located. 01819 * @return Pair of iterators that possibly points to the subsequence 01820 * matching given key. 01821 */ 01822 std::pair<iterator, iterator> 01823 equal_range(const key_type& __x) 01824 { return _M_h.equal_range(__x); } 01825 01826 std::pair<const_iterator, const_iterator> 01827 equal_range(const key_type& __x) const 01828 { return _M_h.equal_range(__x); } 01829 //@} 01830 01831 // bucket interface. 01832 01833 /// Returns the number of buckets of the %unordered_multimap. 01834 size_type 01835 bucket_count() const noexcept 01836 { return _M_h.bucket_count(); } 01837 01838 /// Returns the maximum number of buckets of the %unordered_multimap. 01839 size_type 01840 max_bucket_count() const noexcept 01841 { return _M_h.max_bucket_count(); } 01842 01843 /* 01844 * @brief Returns the number of elements in a given bucket. 01845 * @param __n A bucket index. 01846 * @return The number of elements in the bucket. 01847 */ 01848 size_type 01849 bucket_size(size_type __n) const 01850 { return _M_h.bucket_size(__n); } 01851 01852 /* 01853 * @brief Returns the bucket index of a given element. 01854 * @param __key A key instance. 01855 * @return The key bucket index. 01856 */ 01857 size_type 01858 bucket(const key_type& __key) const 01859 { return _M_h.bucket(__key); } 01860 01861 /** 01862 * @brief Returns a read/write iterator pointing to the first bucket 01863 * element. 01864 * @param __n The bucket index. 01865 * @return A read/write local iterator. 01866 */ 01867 local_iterator 01868 begin(size_type __n) 01869 { return _M_h.begin(__n); } 01870 01871 //@{ 01872 /** 01873 * @brief Returns a read-only (constant) iterator pointing to the first 01874 * bucket element. 01875 * @param __n The bucket index. 01876 * @return A read-only local iterator. 01877 */ 01878 const_local_iterator 01879 begin(size_type __n) const 01880 { return _M_h.begin(__n); } 01881 01882 const_local_iterator 01883 cbegin(size_type __n) const 01884 { return _M_h.cbegin(__n); } 01885 //@} 01886 01887 /** 01888 * @brief Returns a read/write iterator pointing to one past the last 01889 * bucket elements. 01890 * @param __n The bucket index. 01891 * @return A read/write local iterator. 01892 */ 01893 local_iterator 01894 end(size_type __n) 01895 { return _M_h.end(__n); } 01896 01897 //@{ 01898 /** 01899 * @brief Returns a read-only (constant) iterator pointing to one past 01900 * the last bucket elements. 01901 * @param __n The bucket index. 01902 * @return A read-only local iterator. 01903 */ 01904 const_local_iterator 01905 end(size_type __n) const 01906 { return _M_h.end(__n); } 01907 01908 const_local_iterator 01909 cend(size_type __n) const 01910 { return _M_h.cend(__n); } 01911 //@} 01912 01913 // hash policy. 01914 01915 /// Returns the average number of elements per bucket. 01916 float 01917 load_factor() const noexcept 01918 { return _M_h.load_factor(); } 01919 01920 /// Returns a positive number that the %unordered_multimap tries to keep 01921 /// the load factor less than or equal to. 01922 float 01923 max_load_factor() const noexcept 01924 { return _M_h.max_load_factor(); } 01925 01926 /** 01927 * @brief Change the %unordered_multimap maximum load factor. 01928 * @param __z The new maximum load factor. 01929 */ 01930 void 01931 max_load_factor(float __z) 01932 { _M_h.max_load_factor(__z); } 01933 01934 /** 01935 * @brief May rehash the %unordered_multimap. 01936 * @param __n The new number of buckets. 01937 * 01938 * Rehash will occur only if the new number of buckets respect the 01939 * %unordered_multimap maximum load factor. 01940 */ 01941 void 01942 rehash(size_type __n) 01943 { _M_h.rehash(__n); } 01944 01945 /** 01946 * @brief Prepare the %unordered_multimap for a specified number of 01947 * elements. 01948 * @param __n Number of elements required. 01949 * 01950 * Same as rehash(ceil(n / max_load_factor())). 01951 */ 01952 void 01953 reserve(size_type __n) 01954 { _M_h.reserve(__n); } 01955 01956 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1, 01957 typename _Alloc1> 01958 friend bool 01959 operator==(const unordered_multimap<_Key1, _Tp1, 01960 _Hash1, _Pred1, _Alloc1>&, 01961 const unordered_multimap<_Key1, _Tp1, 01962 _Hash1, _Pred1, _Alloc1>&); 01963 }; 01964 01965 #if __cpp_deduction_guides >= 201606 01966 01967 template<typename _InputIterator, 01968 typename _Hash = hash<__iter_key_t<_InputIterator>>, 01969 typename _Pred = equal_to<__iter_key_t<_InputIterator>>, 01970 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, 01971 typename = _RequireInputIter<_InputIterator>, 01972 typename = _RequireAllocator<_Allocator>> 01973 unordered_multimap(_InputIterator, _InputIterator, 01974 unordered_multimap<int, int>::size_type = {}, 01975 _Hash = _Hash(), _Pred = _Pred(), 01976 _Allocator = _Allocator()) 01977 -> unordered_multimap<__iter_key_t<_InputIterator>, 01978 __iter_val_t<_InputIterator>, _Hash, _Pred, 01979 _Allocator>; 01980 01981 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>, 01982 typename _Pred = equal_to<_Key>, 01983 typename _Allocator = allocator<pair<const _Key, _Tp>>, 01984 typename = _RequireAllocator<_Allocator>> 01985 unordered_multimap(initializer_list<pair<_Key, _Tp>>, 01986 unordered_multimap<int, int>::size_type = {}, 01987 _Hash = _Hash(), _Pred = _Pred(), 01988 _Allocator = _Allocator()) 01989 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>; 01990 01991 template<typename _InputIterator, typename _Allocator, 01992 typename = _RequireInputIter<_InputIterator>, 01993 typename = _RequireAllocator<_Allocator>> 01994 unordered_multimap(_InputIterator, _InputIterator, 01995 unordered_multimap<int, int>::size_type, _Allocator) 01996 -> unordered_multimap<__iter_key_t<_InputIterator>, 01997 __iter_val_t<_InputIterator>, 01998 hash<__iter_key_t<_InputIterator>>, 01999 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 02000 02001 template<typename _InputIterator, typename _Allocator, 02002 typename = _RequireInputIter<_InputIterator>, 02003 typename = _RequireAllocator<_Allocator>> 02004 unordered_multimap(_InputIterator, _InputIterator, _Allocator) 02005 -> unordered_multimap<__iter_key_t<_InputIterator>, 02006 __iter_val_t<_InputIterator>, 02007 hash<__iter_key_t<_InputIterator>>, 02008 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 02009 02010 template<typename _InputIterator, typename _Hash, typename _Allocator, 02011 typename = _RequireInputIter<_InputIterator>, 02012 typename = _RequireAllocator<_Allocator>> 02013 unordered_multimap(_InputIterator, _InputIterator, 02014 unordered_multimap<int, int>::size_type, _Hash, 02015 _Allocator) 02016 -> unordered_multimap<__iter_key_t<_InputIterator>, 02017 __iter_val_t<_InputIterator>, _Hash, 02018 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 02019 02020 template<typename _Key, typename _Tp, typename _Allocator, 02021 typename = _RequireAllocator<_Allocator>> 02022 unordered_multimap(initializer_list<pair<_Key, _Tp>>, 02023 unordered_multimap<int, int>::size_type, 02024 _Allocator) 02025 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 02026 02027 template<typename _Key, typename _Tp, typename _Allocator, 02028 typename = _RequireAllocator<_Allocator>> 02029 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) 02030 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 02031 02032 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator, 02033 typename = _RequireAllocator<_Allocator>> 02034 unordered_multimap(initializer_list<pair<_Key, _Tp>>, 02035 unordered_multimap<int, int>::size_type, 02036 _Hash, _Allocator) 02037 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>; 02038 02039 #endif 02040 02041 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 02042 inline void 02043 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 02044 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 02045 noexcept(noexcept(__x.swap(__y))) 02046 { __x.swap(__y); } 02047 02048 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 02049 inline void 02050 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 02051 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 02052 noexcept(noexcept(__x.swap(__y))) 02053 { __x.swap(__y); } 02054 02055 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 02056 inline bool 02057 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 02058 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 02059 { return __x._M_h._M_equal(__y._M_h); } 02060 02061 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 02062 inline bool 02063 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 02064 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 02065 { return !(__x == __y); } 02066 02067 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 02068 inline bool 02069 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 02070 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 02071 { return __x._M_h._M_equal(__y._M_h); } 02072 02073 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 02074 inline bool 02075 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 02076 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 02077 { return !(__x == __y); } 02078 02079 _GLIBCXX_END_NAMESPACE_CONTAINER 02080 02081 #if __cplusplus > 201402L 02082 // Allow std::unordered_map access to internals of compatible maps. 02083 template<typename _Key, typename _Val, typename _Hash1, typename _Eq1, 02084 typename _Alloc, typename _Hash2, typename _Eq2> 02085 struct _Hash_merge_helper< 02086 _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>, 02087 _Hash2, _Eq2> 02088 { 02089 private: 02090 template<typename... _Tp> 02091 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>; 02092 template<typename... _Tp> 02093 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>; 02094 02095 friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>; 02096 02097 static auto& 02098 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) 02099 { return __map._M_h; } 02100 02101 static auto& 02102 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) 02103 { return __map._M_h; } 02104 }; 02105 02106 // Allow std::unordered_multimap access to internals of compatible maps. 02107 template<typename _Key, typename _Val, typename _Hash1, typename _Eq1, 02108 typename _Alloc, typename _Hash2, typename _Eq2> 02109 struct _Hash_merge_helper< 02110 _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>, 02111 _Hash2, _Eq2> 02112 { 02113 private: 02114 template<typename... _Tp> 02115 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>; 02116 template<typename... _Tp> 02117 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>; 02118 02119 friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>; 02120 02121 static auto& 02122 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) 02123 { return __map._M_h; } 02124 02125 static auto& 02126 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) 02127 { return __map._M_h; } 02128 }; 02129 #endif // C++17 02130 02131 _GLIBCXX_END_NAMESPACE_VERSION 02132 } // namespace std 02133 02134 #endif /* _UNORDERED_MAP_H */