libstdc++
|
00001 // unordered_map implementation -*- C++ -*- 00002 00003 // Copyright (C) 2010-2019 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 _GLIBCXX_NODISCARD 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 #if __cplusplus > 201703L 00942 /** 00943 * @brief Finds whether an element with the given key exists. 00944 * @param __x Key of elements to be located. 00945 * @return True if there is any element with the specified key. 00946 */ 00947 bool 00948 contains(const key_type& __x) const 00949 { return _M_h.find(__x) != _M_h.end(); } 00950 #endif 00951 00952 //@{ 00953 /** 00954 * @brief Finds a subsequence matching given key. 00955 * @param __x Key to be located. 00956 * @return Pair of iterators that possibly points to the subsequence 00957 * matching given key. 00958 * 00959 * This function probably only makes sense for %unordered_multimap. 00960 */ 00961 std::pair<iterator, iterator> 00962 equal_range(const key_type& __x) 00963 { return _M_h.equal_range(__x); } 00964 00965 std::pair<const_iterator, const_iterator> 00966 equal_range(const key_type& __x) const 00967 { return _M_h.equal_range(__x); } 00968 //@} 00969 00970 //@{ 00971 /** 00972 * @brief Subscript ( @c [] ) access to %unordered_map data. 00973 * @param __k The key for which data should be retrieved. 00974 * @return A reference to the data of the (key,data) %pair. 00975 * 00976 * Allows for easy lookup with the subscript ( @c [] )operator. Returns 00977 * data associated with the key specified in subscript. If the key does 00978 * not exist, a pair with that key is created using default values, which 00979 * is then returned. 00980 * 00981 * Lookup requires constant time. 00982 */ 00983 mapped_type& 00984 operator[](const key_type& __k) 00985 { return _M_h[__k]; } 00986 00987 mapped_type& 00988 operator[](key_type&& __k) 00989 { return _M_h[std::move(__k)]; } 00990 //@} 00991 00992 //@{ 00993 /** 00994 * @brief Access to %unordered_map data. 00995 * @param __k The key for which data should be retrieved. 00996 * @return A reference to the data whose key is equal to @a __k, if 00997 * such a data is present in the %unordered_map. 00998 * @throw std::out_of_range If no such data is present. 00999 */ 01000 mapped_type& 01001 at(const key_type& __k) 01002 { return _M_h.at(__k); } 01003 01004 const mapped_type& 01005 at(const key_type& __k) const 01006 { return _M_h.at(__k); } 01007 //@} 01008 01009 // bucket interface. 01010 01011 /// Returns the number of buckets of the %unordered_map. 01012 size_type 01013 bucket_count() const noexcept 01014 { return _M_h.bucket_count(); } 01015 01016 /// Returns the maximum number of buckets of the %unordered_map. 01017 size_type 01018 max_bucket_count() const noexcept 01019 { return _M_h.max_bucket_count(); } 01020 01021 /* 01022 * @brief Returns the number of elements in a given bucket. 01023 * @param __n A bucket index. 01024 * @return The number of elements in the bucket. 01025 */ 01026 size_type 01027 bucket_size(size_type __n) const 01028 { return _M_h.bucket_size(__n); } 01029 01030 /* 01031 * @brief Returns the bucket index of a given element. 01032 * @param __key A key instance. 01033 * @return The key bucket index. 01034 */ 01035 size_type 01036 bucket(const key_type& __key) const 01037 { return _M_h.bucket(__key); } 01038 01039 /** 01040 * @brief Returns a read/write iterator pointing to the first bucket 01041 * element. 01042 * @param __n The bucket index. 01043 * @return A read/write local iterator. 01044 */ 01045 local_iterator 01046 begin(size_type __n) 01047 { return _M_h.begin(__n); } 01048 01049 //@{ 01050 /** 01051 * @brief Returns a read-only (constant) iterator pointing to the first 01052 * bucket element. 01053 * @param __n The bucket index. 01054 * @return A read-only local iterator. 01055 */ 01056 const_local_iterator 01057 begin(size_type __n) const 01058 { return _M_h.begin(__n); } 01059 01060 const_local_iterator 01061 cbegin(size_type __n) const 01062 { return _M_h.cbegin(__n); } 01063 //@} 01064 01065 /** 01066 * @brief Returns a read/write iterator pointing to one past the last 01067 * bucket elements. 01068 * @param __n The bucket index. 01069 * @return A read/write local iterator. 01070 */ 01071 local_iterator 01072 end(size_type __n) 01073 { return _M_h.end(__n); } 01074 01075 //@{ 01076 /** 01077 * @brief Returns a read-only (constant) iterator pointing to one past 01078 * the last bucket elements. 01079 * @param __n The bucket index. 01080 * @return A read-only local iterator. 01081 */ 01082 const_local_iterator 01083 end(size_type __n) const 01084 { return _M_h.end(__n); } 01085 01086 const_local_iterator 01087 cend(size_type __n) const 01088 { return _M_h.cend(__n); } 01089 //@} 01090 01091 // hash policy. 01092 01093 /// Returns the average number of elements per bucket. 01094 float 01095 load_factor() const noexcept 01096 { return _M_h.load_factor(); } 01097 01098 /// Returns a positive number that the %unordered_map tries to keep the 01099 /// load factor less than or equal to. 01100 float 01101 max_load_factor() const noexcept 01102 { return _M_h.max_load_factor(); } 01103 01104 /** 01105 * @brief Change the %unordered_map maximum load factor. 01106 * @param __z The new maximum load factor. 01107 */ 01108 void 01109 max_load_factor(float __z) 01110 { _M_h.max_load_factor(__z); } 01111 01112 /** 01113 * @brief May rehash the %unordered_map. 01114 * @param __n The new number of buckets. 01115 * 01116 * Rehash will occur only if the new number of buckets respect the 01117 * %unordered_map maximum load factor. 01118 */ 01119 void 01120 rehash(size_type __n) 01121 { _M_h.rehash(__n); } 01122 01123 /** 01124 * @brief Prepare the %unordered_map for a specified number of 01125 * elements. 01126 * @param __n Number of elements required. 01127 * 01128 * Same as rehash(ceil(n / max_load_factor())). 01129 */ 01130 void 01131 reserve(size_type __n) 01132 { _M_h.reserve(__n); } 01133 01134 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1, 01135 typename _Alloc1> 01136 friend bool 01137 operator==(const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&, 01138 const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&); 01139 }; 01140 01141 #if __cpp_deduction_guides >= 201606 01142 01143 template<typename _InputIterator, 01144 typename _Hash = hash<__iter_key_t<_InputIterator>>, 01145 typename _Pred = equal_to<__iter_key_t<_InputIterator>>, 01146 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, 01147 typename = _RequireInputIter<_InputIterator>, 01148 typename = _RequireNotAllocatorOrIntegral<_Hash>, 01149 typename = _RequireNotAllocator<_Pred>, 01150 typename = _RequireAllocator<_Allocator>> 01151 unordered_map(_InputIterator, _InputIterator, 01152 typename unordered_map<int, int>::size_type = {}, 01153 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 01154 -> unordered_map<__iter_key_t<_InputIterator>, 01155 __iter_val_t<_InputIterator>, 01156 _Hash, _Pred, _Allocator>; 01157 01158 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>, 01159 typename _Pred = equal_to<_Key>, 01160 typename _Allocator = allocator<pair<const _Key, _Tp>>, 01161 typename = _RequireNotAllocatorOrIntegral<_Hash>, 01162 typename = _RequireNotAllocator<_Pred>, 01163 typename = _RequireAllocator<_Allocator>> 01164 unordered_map(initializer_list<pair<_Key, _Tp>>, 01165 typename unordered_map<int, int>::size_type = {}, 01166 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 01167 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>; 01168 01169 template<typename _InputIterator, typename _Allocator, 01170 typename = _RequireInputIter<_InputIterator>, 01171 typename = _RequireAllocator<_Allocator>> 01172 unordered_map(_InputIterator, _InputIterator, 01173 typename unordered_map<int, int>::size_type, _Allocator) 01174 -> unordered_map<__iter_key_t<_InputIterator>, 01175 __iter_val_t<_InputIterator>, 01176 hash<__iter_key_t<_InputIterator>>, 01177 equal_to<__iter_key_t<_InputIterator>>, 01178 _Allocator>; 01179 01180 template<typename _InputIterator, typename _Allocator, 01181 typename = _RequireInputIter<_InputIterator>, 01182 typename = _RequireAllocator<_Allocator>> 01183 unordered_map(_InputIterator, _InputIterator, _Allocator) 01184 -> unordered_map<__iter_key_t<_InputIterator>, 01185 __iter_val_t<_InputIterator>, 01186 hash<__iter_key_t<_InputIterator>>, 01187 equal_to<__iter_key_t<_InputIterator>>, 01188 _Allocator>; 01189 01190 template<typename _InputIterator, typename _Hash, typename _Allocator, 01191 typename = _RequireInputIter<_InputIterator>, 01192 typename = _RequireNotAllocatorOrIntegral<_Hash>, 01193 typename = _RequireAllocator<_Allocator>> 01194 unordered_map(_InputIterator, _InputIterator, 01195 typename unordered_map<int, int>::size_type, 01196 _Hash, _Allocator) 01197 -> unordered_map<__iter_key_t<_InputIterator>, 01198 __iter_val_t<_InputIterator>, _Hash, 01199 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 01200 01201 template<typename _Key, typename _Tp, typename _Allocator, 01202 typename = _RequireAllocator<_Allocator>> 01203 unordered_map(initializer_list<pair<_Key, _Tp>>, 01204 typename unordered_map<int, int>::size_type, 01205 _Allocator) 01206 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 01207 01208 template<typename _Key, typename _Tp, typename _Allocator, 01209 typename = _RequireAllocator<_Allocator>> 01210 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator) 01211 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 01212 01213 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator, 01214 typename = _RequireNotAllocatorOrIntegral<_Hash>, 01215 typename = _RequireAllocator<_Allocator>> 01216 unordered_map(initializer_list<pair<_Key, _Tp>>, 01217 typename unordered_map<int, int>::size_type, 01218 _Hash, _Allocator) 01219 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>; 01220 01221 #endif 01222 01223 /** 01224 * @brief A standard container composed of equivalent keys 01225 * (possibly containing multiple of each key value) that associates 01226 * values of another type with the keys. 01227 * 01228 * @ingroup unordered_associative_containers 01229 * 01230 * @tparam _Key Type of key objects. 01231 * @tparam _Tp Type of mapped objects. 01232 * @tparam _Hash Hashing function object type, defaults to hash<_Value>. 01233 * @tparam _Pred Predicate function object type, defaults 01234 * to equal_to<_Value>. 01235 * @tparam _Alloc Allocator type, defaults to 01236 * std::allocator<std::pair<const _Key, _Tp>>. 01237 * 01238 * Meets the requirements of a <a href="tables.html#65">container</a>, and 01239 * <a href="tables.html#xx">unordered associative container</a> 01240 * 01241 * The resulting value type of the container is std::pair<const _Key, _Tp>. 01242 * 01243 * Base is _Hashtable, dispatched at compile time via template 01244 * alias __ummap_hashtable. 01245 */ 01246 template<typename _Key, typename _Tp, 01247 typename _Hash = hash<_Key>, 01248 typename _Pred = equal_to<_Key>, 01249 typename _Alloc = allocator<std::pair<const _Key, _Tp>>> 01250 class unordered_multimap 01251 { 01252 typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable; 01253 _Hashtable _M_h; 01254 01255 public: 01256 // typedefs: 01257 //@{ 01258 /// Public typedefs. 01259 typedef typename _Hashtable::key_type key_type; 01260 typedef typename _Hashtable::value_type value_type; 01261 typedef typename _Hashtable::mapped_type mapped_type; 01262 typedef typename _Hashtable::hasher hasher; 01263 typedef typename _Hashtable::key_equal key_equal; 01264 typedef typename _Hashtable::allocator_type allocator_type; 01265 //@} 01266 01267 //@{ 01268 /// Iterator-related typedefs. 01269 typedef typename _Hashtable::pointer pointer; 01270 typedef typename _Hashtable::const_pointer const_pointer; 01271 typedef typename _Hashtable::reference reference; 01272 typedef typename _Hashtable::const_reference const_reference; 01273 typedef typename _Hashtable::iterator iterator; 01274 typedef typename _Hashtable::const_iterator const_iterator; 01275 typedef typename _Hashtable::local_iterator local_iterator; 01276 typedef typename _Hashtable::const_local_iterator const_local_iterator; 01277 typedef typename _Hashtable::size_type size_type; 01278 typedef typename _Hashtable::difference_type difference_type; 01279 //@} 01280 01281 #if __cplusplus > 201402L 01282 using node_type = typename _Hashtable::node_type; 01283 #endif 01284 01285 //construct/destroy/copy 01286 01287 /// Default constructor. 01288 unordered_multimap() = default; 01289 01290 /** 01291 * @brief Default constructor creates no elements. 01292 * @param __n Mnimal 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 explicit 01298 unordered_multimap(size_type __n, 01299 const hasher& __hf = hasher(), 01300 const key_equal& __eql = key_equal(), 01301 const allocator_type& __a = allocator_type()) 01302 : _M_h(__n, __hf, __eql, __a) 01303 { } 01304 01305 /** 01306 * @brief Builds an %unordered_multimap from a range. 01307 * @param __first An input iterator. 01308 * @param __last An input iterator. 01309 * @param __n Minimal initial number of buckets. 01310 * @param __hf A hash functor. 01311 * @param __eql A key equality functor. 01312 * @param __a An allocator object. 01313 * 01314 * Create an %unordered_multimap consisting of copies of the elements 01315 * from [__first,__last). This is linear in N (where N is 01316 * distance(__first,__last)). 01317 */ 01318 template<typename _InputIterator> 01319 unordered_multimap(_InputIterator __first, _InputIterator __last, 01320 size_type __n = 0, 01321 const hasher& __hf = hasher(), 01322 const key_equal& __eql = key_equal(), 01323 const allocator_type& __a = allocator_type()) 01324 : _M_h(__first, __last, __n, __hf, __eql, __a) 01325 { } 01326 01327 /// Copy constructor. 01328 unordered_multimap(const unordered_multimap&) = default; 01329 01330 /// Move constructor. 01331 unordered_multimap(unordered_multimap&&) = default; 01332 01333 /** 01334 * @brief Creates an %unordered_multimap with no elements. 01335 * @param __a An allocator object. 01336 */ 01337 explicit 01338 unordered_multimap(const allocator_type& __a) 01339 : _M_h(__a) 01340 { } 01341 01342 /* 01343 * @brief Copy constructor with allocator argument. 01344 * @param __uset Input %unordered_multimap to copy. 01345 * @param __a An allocator object. 01346 */ 01347 unordered_multimap(const unordered_multimap& __ummap, 01348 const allocator_type& __a) 01349 : _M_h(__ummap._M_h, __a) 01350 { } 01351 01352 /* 01353 * @brief Move constructor with allocator argument. 01354 * @param __uset Input %unordered_multimap to move. 01355 * @param __a An allocator object. 01356 */ 01357 unordered_multimap(unordered_multimap&& __ummap, 01358 const allocator_type& __a) 01359 : _M_h(std::move(__ummap._M_h), __a) 01360 { } 01361 01362 /** 01363 * @brief Builds an %unordered_multimap from an initializer_list. 01364 * @param __l An initializer_list. 01365 * @param __n Minimal initial number of buckets. 01366 * @param __hf A hash functor. 01367 * @param __eql A key equality functor. 01368 * @param __a An allocator object. 01369 * 01370 * Create an %unordered_multimap consisting of copies of the elements in 01371 * the list. This is linear in N (where N is @a __l.size()). 01372 */ 01373 unordered_multimap(initializer_list<value_type> __l, 01374 size_type __n = 0, 01375 const hasher& __hf = hasher(), 01376 const key_equal& __eql = key_equal(), 01377 const allocator_type& __a = allocator_type()) 01378 : _M_h(__l, __n, __hf, __eql, __a) 01379 { } 01380 01381 unordered_multimap(size_type __n, const allocator_type& __a) 01382 : unordered_multimap(__n, hasher(), key_equal(), __a) 01383 { } 01384 01385 unordered_multimap(size_type __n, const hasher& __hf, 01386 const allocator_type& __a) 01387 : unordered_multimap(__n, __hf, key_equal(), __a) 01388 { } 01389 01390 template<typename _InputIterator> 01391 unordered_multimap(_InputIterator __first, _InputIterator __last, 01392 size_type __n, 01393 const allocator_type& __a) 01394 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) 01395 { } 01396 01397 template<typename _InputIterator> 01398 unordered_multimap(_InputIterator __first, _InputIterator __last, 01399 size_type __n, const hasher& __hf, 01400 const allocator_type& __a) 01401 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) 01402 { } 01403 01404 unordered_multimap(initializer_list<value_type> __l, 01405 size_type __n, 01406 const allocator_type& __a) 01407 : unordered_multimap(__l, __n, hasher(), key_equal(), __a) 01408 { } 01409 01410 unordered_multimap(initializer_list<value_type> __l, 01411 size_type __n, const hasher& __hf, 01412 const allocator_type& __a) 01413 : unordered_multimap(__l, __n, __hf, key_equal(), __a) 01414 { } 01415 01416 /// Copy assignment operator. 01417 unordered_multimap& 01418 operator=(const unordered_multimap&) = default; 01419 01420 /// Move assignment operator. 01421 unordered_multimap& 01422 operator=(unordered_multimap&&) = default; 01423 01424 /** 01425 * @brief %Unordered_multimap list assignment operator. 01426 * @param __l An initializer_list. 01427 * 01428 * This function fills an %unordered_multimap with copies of the 01429 * elements in the initializer list @a __l. 01430 * 01431 * Note that the assignment completely changes the %unordered_multimap 01432 * and that the resulting %unordered_multimap's size is the same as the 01433 * number of elements assigned. 01434 */ 01435 unordered_multimap& 01436 operator=(initializer_list<value_type> __l) 01437 { 01438 _M_h = __l; 01439 return *this; 01440 } 01441 01442 /// Returns the allocator object used by the %unordered_multimap. 01443 allocator_type 01444 get_allocator() const noexcept 01445 { return _M_h.get_allocator(); } 01446 01447 // size and capacity: 01448 01449 /// Returns true if the %unordered_multimap is empty. 01450 _GLIBCXX_NODISCARD bool 01451 empty() const noexcept 01452 { return _M_h.empty(); } 01453 01454 /// Returns the size of the %unordered_multimap. 01455 size_type 01456 size() const noexcept 01457 { return _M_h.size(); } 01458 01459 /// Returns the maximum size of the %unordered_multimap. 01460 size_type 01461 max_size() const noexcept 01462 { return _M_h.max_size(); } 01463 01464 // iterators. 01465 01466 /** 01467 * Returns a read/write iterator that points to the first element in the 01468 * %unordered_multimap. 01469 */ 01470 iterator 01471 begin() noexcept 01472 { return _M_h.begin(); } 01473 01474 //@{ 01475 /** 01476 * Returns a read-only (constant) iterator that points to the first 01477 * element in the %unordered_multimap. 01478 */ 01479 const_iterator 01480 begin() const noexcept 01481 { return _M_h.begin(); } 01482 01483 const_iterator 01484 cbegin() const noexcept 01485 { return _M_h.begin(); } 01486 //@} 01487 01488 /** 01489 * Returns a read/write iterator that points one past the last element in 01490 * the %unordered_multimap. 01491 */ 01492 iterator 01493 end() noexcept 01494 { return _M_h.end(); } 01495 01496 //@{ 01497 /** 01498 * Returns a read-only (constant) iterator that points one past the last 01499 * element in the %unordered_multimap. 01500 */ 01501 const_iterator 01502 end() const noexcept 01503 { return _M_h.end(); } 01504 01505 const_iterator 01506 cend() const noexcept 01507 { return _M_h.end(); } 01508 //@} 01509 01510 // modifiers. 01511 01512 /** 01513 * @brief Attempts to build and insert a std::pair into the 01514 * %unordered_multimap. 01515 * 01516 * @param __args Arguments used to generate a new pair instance (see 01517 * std::piecewise_contruct for passing arguments to each 01518 * part of the pair constructor). 01519 * 01520 * @return An iterator that points to the inserted pair. 01521 * 01522 * This function attempts to build and insert a (key, value) %pair into 01523 * the %unordered_multimap. 01524 * 01525 * Insertion requires amortized constant time. 01526 */ 01527 template<typename... _Args> 01528 iterator 01529 emplace(_Args&&... __args) 01530 { return _M_h.emplace(std::forward<_Args>(__args)...); } 01531 01532 /** 01533 * @brief Attempts to build and insert a std::pair into the 01534 * %unordered_multimap. 01535 * 01536 * @param __pos An iterator that serves as a hint as to where the pair 01537 * should be inserted. 01538 * @param __args Arguments used to generate a new pair instance (see 01539 * std::piecewise_contruct for passing arguments to each 01540 * part of the pair constructor). 01541 * @return An iterator that points to the element with key of the 01542 * std::pair built from @a __args. 01543 * 01544 * Note that the first parameter is only a hint and can potentially 01545 * improve the performance of the insertion process. A bad hint would 01546 * cause no gains in efficiency. 01547 * 01548 * See 01549 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 01550 * for more on @a hinting. 01551 * 01552 * Insertion requires amortized constant time. 01553 */ 01554 template<typename... _Args> 01555 iterator 01556 emplace_hint(const_iterator __pos, _Args&&... __args) 01557 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); } 01558 01559 //@{ 01560 /** 01561 * @brief Inserts a std::pair into the %unordered_multimap. 01562 * @param __x Pair to be inserted (see std::make_pair for easy 01563 * creation of pairs). 01564 * 01565 * @return An iterator that points to the inserted pair. 01566 * 01567 * Insertion requires amortized constant time. 01568 */ 01569 iterator 01570 insert(const value_type& __x) 01571 { return _M_h.insert(__x); } 01572 01573 iterator 01574 insert(value_type&& __x) 01575 { return _M_h.insert(std::move(__x)); } 01576 01577 template<typename _Pair> 01578 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator> 01579 insert(_Pair&& __x) 01580 { return _M_h.emplace(std::forward<_Pair>(__x)); } 01581 //@} 01582 01583 //@{ 01584 /** 01585 * @brief Inserts a std::pair into the %unordered_multimap. 01586 * @param __hint An iterator that serves as a hint as to where the 01587 * pair should be inserted. 01588 * @param __x Pair to be inserted (see std::make_pair for easy creation 01589 * of pairs). 01590 * @return An iterator that points to the element with key of 01591 * @a __x (may or may not be the %pair passed in). 01592 * 01593 * Note that the first parameter is only a hint and can potentially 01594 * improve the performance of the insertion process. A bad hint would 01595 * cause no gains in efficiency. 01596 * 01597 * See 01598 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 01599 * for more on @a hinting. 01600 * 01601 * Insertion requires amortized constant time. 01602 */ 01603 iterator 01604 insert(const_iterator __hint, const value_type& __x) 01605 { return _M_h.insert(__hint, __x); } 01606 01607 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01608 // 2354. Unnecessary copying when inserting into maps with braced-init 01609 iterator 01610 insert(const_iterator __hint, value_type&& __x) 01611 { return _M_h.insert(__hint, std::move(__x)); } 01612 01613 template<typename _Pair> 01614 __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator> 01615 insert(const_iterator __hint, _Pair&& __x) 01616 { return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); } 01617 //@} 01618 01619 /** 01620 * @brief A template function that attempts to insert a range of 01621 * elements. 01622 * @param __first Iterator pointing to the start of the range to be 01623 * inserted. 01624 * @param __last Iterator pointing to the end of the range. 01625 * 01626 * Complexity similar to that of the range constructor. 01627 */ 01628 template<typename _InputIterator> 01629 void 01630 insert(_InputIterator __first, _InputIterator __last) 01631 { _M_h.insert(__first, __last); } 01632 01633 /** 01634 * @brief Attempts to insert a list of elements into the 01635 * %unordered_multimap. 01636 * @param __l A std::initializer_list<value_type> of elements 01637 * to be inserted. 01638 * 01639 * Complexity similar to that of the range constructor. 01640 */ 01641 void 01642 insert(initializer_list<value_type> __l) 01643 { _M_h.insert(__l); } 01644 01645 #if __cplusplus > 201402L 01646 /// Extract a node. 01647 node_type 01648 extract(const_iterator __pos) 01649 { 01650 __glibcxx_assert(__pos != end()); 01651 return _M_h.extract(__pos); 01652 } 01653 01654 /// Extract a node. 01655 node_type 01656 extract(const key_type& __key) 01657 { return _M_h.extract(__key); } 01658 01659 /// Re-insert an extracted node. 01660 iterator 01661 insert(node_type&& __nh) 01662 { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); } 01663 01664 /// Re-insert an extracted node. 01665 iterator 01666 insert(const_iterator __hint, node_type&& __nh) 01667 { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); } 01668 #endif // C++17 01669 01670 //@{ 01671 /** 01672 * @brief Erases an element from an %unordered_multimap. 01673 * @param __position An iterator pointing to the element to be erased. 01674 * @return An iterator pointing to the element immediately following 01675 * @a __position prior to the element being erased. If no such 01676 * element exists, end() is returned. 01677 * 01678 * This function erases an element, pointed to by the given iterator, 01679 * from an %unordered_multimap. 01680 * Note that this function only erases the element, and that if the 01681 * element is itself a pointer, the pointed-to memory is not touched in 01682 * any way. Managing the pointer is the user's responsibility. 01683 */ 01684 iterator 01685 erase(const_iterator __position) 01686 { return _M_h.erase(__position); } 01687 01688 // LWG 2059. 01689 iterator 01690 erase(iterator __position) 01691 { return _M_h.erase(__position); } 01692 //@} 01693 01694 /** 01695 * @brief Erases elements according to the provided key. 01696 * @param __x Key of elements to be erased. 01697 * @return The number of elements erased. 01698 * 01699 * This function erases all the elements located by the given key from 01700 * an %unordered_multimap. 01701 * Note that this function only erases the element, and that if the 01702 * element is itself a pointer, the pointed-to memory is not touched in 01703 * any way. Managing the pointer is the user's responsibility. 01704 */ 01705 size_type 01706 erase(const key_type& __x) 01707 { return _M_h.erase(__x); } 01708 01709 /** 01710 * @brief Erases a [__first,__last) range of elements from an 01711 * %unordered_multimap. 01712 * @param __first Iterator pointing to the start of the range to be 01713 * erased. 01714 * @param __last Iterator pointing to the end of the range to 01715 * be erased. 01716 * @return The iterator @a __last. 01717 * 01718 * This function erases a sequence of elements from an 01719 * %unordered_multimap. 01720 * Note that this function only erases the elements, and that if 01721 * the element is itself a pointer, the pointed-to memory is not touched 01722 * in any way. Managing the pointer is the user's responsibility. 01723 */ 01724 iterator 01725 erase(const_iterator __first, const_iterator __last) 01726 { return _M_h.erase(__first, __last); } 01727 01728 /** 01729 * Erases all elements in an %unordered_multimap. 01730 * Note that this function only erases the elements, and that if the 01731 * elements themselves are pointers, the pointed-to memory is not touched 01732 * in any way. Managing the pointer is the user's responsibility. 01733 */ 01734 void 01735 clear() noexcept 01736 { _M_h.clear(); } 01737 01738 /** 01739 * @brief Swaps data with another %unordered_multimap. 01740 * @param __x An %unordered_multimap of the same element and allocator 01741 * types. 01742 * 01743 * This exchanges the elements between two %unordered_multimap in 01744 * constant time. 01745 * Note that the global std::swap() function is specialized such that 01746 * std::swap(m1,m2) will feed to this function. 01747 */ 01748 void 01749 swap(unordered_multimap& __x) 01750 noexcept( noexcept(_M_h.swap(__x._M_h)) ) 01751 { _M_h.swap(__x._M_h); } 01752 01753 #if __cplusplus > 201402L 01754 template<typename, typename, typename> 01755 friend class std::_Hash_merge_helper; 01756 01757 template<typename _H2, typename _P2> 01758 void 01759 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source) 01760 { 01761 using _Merge_helper 01762 = _Hash_merge_helper<unordered_multimap, _H2, _P2>; 01763 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); 01764 } 01765 01766 template<typename _H2, typename _P2> 01767 void 01768 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source) 01769 { merge(__source); } 01770 01771 template<typename _H2, typename _P2> 01772 void 01773 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source) 01774 { 01775 using _Merge_helper 01776 = _Hash_merge_helper<unordered_multimap, _H2, _P2>; 01777 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); 01778 } 01779 01780 template<typename _H2, typename _P2> 01781 void 01782 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source) 01783 { merge(__source); } 01784 #endif // C++17 01785 01786 // observers. 01787 01788 /// Returns the hash functor object with which the %unordered_multimap 01789 /// was constructed. 01790 hasher 01791 hash_function() const 01792 { return _M_h.hash_function(); } 01793 01794 /// Returns the key comparison object with which the %unordered_multimap 01795 /// was constructed. 01796 key_equal 01797 key_eq() const 01798 { return _M_h.key_eq(); } 01799 01800 // lookup. 01801 01802 //@{ 01803 /** 01804 * @brief Tries to locate an element in an %unordered_multimap. 01805 * @param __x Key to be located. 01806 * @return Iterator pointing to sought-after element, or end() if not 01807 * found. 01808 * 01809 * This function takes a key and tries to locate the element with which 01810 * the key matches. If successful the function returns an iterator 01811 * pointing to the sought after element. If unsuccessful it returns the 01812 * past-the-end ( @c end() ) iterator. 01813 */ 01814 iterator 01815 find(const key_type& __x) 01816 { return _M_h.find(__x); } 01817 01818 const_iterator 01819 find(const key_type& __x) const 01820 { return _M_h.find(__x); } 01821 //@} 01822 01823 /** 01824 * @brief Finds the number of elements. 01825 * @param __x Key to count. 01826 * @return Number of elements with specified key. 01827 */ 01828 size_type 01829 count(const key_type& __x) const 01830 { return _M_h.count(__x); } 01831 01832 #if __cplusplus > 201703L 01833 /** 01834 * @brief Finds whether an element with the given key exists. 01835 * @param __x Key of elements to be located. 01836 * @return True if there is any element with the specified key. 01837 */ 01838 bool 01839 contains(const key_type& __x) const 01840 { return _M_h.find(__x) != _M_h.end(); } 01841 #endif 01842 01843 //@{ 01844 /** 01845 * @brief Finds a subsequence matching given key. 01846 * @param __x Key to be located. 01847 * @return Pair of iterators that possibly points to the subsequence 01848 * matching given key. 01849 */ 01850 std::pair<iterator, iterator> 01851 equal_range(const key_type& __x) 01852 { return _M_h.equal_range(__x); } 01853 01854 std::pair<const_iterator, const_iterator> 01855 equal_range(const key_type& __x) const 01856 { return _M_h.equal_range(__x); } 01857 //@} 01858 01859 // bucket interface. 01860 01861 /// Returns the number of buckets of the %unordered_multimap. 01862 size_type 01863 bucket_count() const noexcept 01864 { return _M_h.bucket_count(); } 01865 01866 /// Returns the maximum number of buckets of the %unordered_multimap. 01867 size_type 01868 max_bucket_count() const noexcept 01869 { return _M_h.max_bucket_count(); } 01870 01871 /* 01872 * @brief Returns the number of elements in a given bucket. 01873 * @param __n A bucket index. 01874 * @return The number of elements in the bucket. 01875 */ 01876 size_type 01877 bucket_size(size_type __n) const 01878 { return _M_h.bucket_size(__n); } 01879 01880 /* 01881 * @brief Returns the bucket index of a given element. 01882 * @param __key A key instance. 01883 * @return The key bucket index. 01884 */ 01885 size_type 01886 bucket(const key_type& __key) const 01887 { return _M_h.bucket(__key); } 01888 01889 /** 01890 * @brief Returns a read/write iterator pointing to the first bucket 01891 * element. 01892 * @param __n The bucket index. 01893 * @return A read/write local iterator. 01894 */ 01895 local_iterator 01896 begin(size_type __n) 01897 { return _M_h.begin(__n); } 01898 01899 //@{ 01900 /** 01901 * @brief Returns a read-only (constant) iterator pointing to the first 01902 * bucket element. 01903 * @param __n The bucket index. 01904 * @return A read-only local iterator. 01905 */ 01906 const_local_iterator 01907 begin(size_type __n) const 01908 { return _M_h.begin(__n); } 01909 01910 const_local_iterator 01911 cbegin(size_type __n) const 01912 { return _M_h.cbegin(__n); } 01913 //@} 01914 01915 /** 01916 * @brief Returns a read/write iterator pointing to one past the last 01917 * bucket elements. 01918 * @param __n The bucket index. 01919 * @return A read/write local iterator. 01920 */ 01921 local_iterator 01922 end(size_type __n) 01923 { return _M_h.end(__n); } 01924 01925 //@{ 01926 /** 01927 * @brief Returns a read-only (constant) iterator pointing to one past 01928 * the last bucket elements. 01929 * @param __n The bucket index. 01930 * @return A read-only local iterator. 01931 */ 01932 const_local_iterator 01933 end(size_type __n) const 01934 { return _M_h.end(__n); } 01935 01936 const_local_iterator 01937 cend(size_type __n) const 01938 { return _M_h.cend(__n); } 01939 //@} 01940 01941 // hash policy. 01942 01943 /// Returns the average number of elements per bucket. 01944 float 01945 load_factor() const noexcept 01946 { return _M_h.load_factor(); } 01947 01948 /// Returns a positive number that the %unordered_multimap tries to keep 01949 /// the load factor less than or equal to. 01950 float 01951 max_load_factor() const noexcept 01952 { return _M_h.max_load_factor(); } 01953 01954 /** 01955 * @brief Change the %unordered_multimap maximum load factor. 01956 * @param __z The new maximum load factor. 01957 */ 01958 void 01959 max_load_factor(float __z) 01960 { _M_h.max_load_factor(__z); } 01961 01962 /** 01963 * @brief May rehash the %unordered_multimap. 01964 * @param __n The new number of buckets. 01965 * 01966 * Rehash will occur only if the new number of buckets respect the 01967 * %unordered_multimap maximum load factor. 01968 */ 01969 void 01970 rehash(size_type __n) 01971 { _M_h.rehash(__n); } 01972 01973 /** 01974 * @brief Prepare the %unordered_multimap for a specified number of 01975 * elements. 01976 * @param __n Number of elements required. 01977 * 01978 * Same as rehash(ceil(n / max_load_factor())). 01979 */ 01980 void 01981 reserve(size_type __n) 01982 { _M_h.reserve(__n); } 01983 01984 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1, 01985 typename _Alloc1> 01986 friend bool 01987 operator==(const unordered_multimap<_Key1, _Tp1, 01988 _Hash1, _Pred1, _Alloc1>&, 01989 const unordered_multimap<_Key1, _Tp1, 01990 _Hash1, _Pred1, _Alloc1>&); 01991 }; 01992 01993 #if __cpp_deduction_guides >= 201606 01994 01995 template<typename _InputIterator, 01996 typename _Hash = hash<__iter_key_t<_InputIterator>>, 01997 typename _Pred = equal_to<__iter_key_t<_InputIterator>>, 01998 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, 01999 typename = _RequireInputIter<_InputIterator>, 02000 typename = _RequireNotAllocatorOrIntegral<_Hash>, 02001 typename = _RequireNotAllocator<_Pred>, 02002 typename = _RequireAllocator<_Allocator>> 02003 unordered_multimap(_InputIterator, _InputIterator, 02004 unordered_multimap<int, int>::size_type = {}, 02005 _Hash = _Hash(), _Pred = _Pred(), 02006 _Allocator = _Allocator()) 02007 -> unordered_multimap<__iter_key_t<_InputIterator>, 02008 __iter_val_t<_InputIterator>, _Hash, _Pred, 02009 _Allocator>; 02010 02011 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>, 02012 typename _Pred = equal_to<_Key>, 02013 typename _Allocator = allocator<pair<const _Key, _Tp>>, 02014 typename = _RequireNotAllocatorOrIntegral<_Hash>, 02015 typename = _RequireNotAllocator<_Pred>, 02016 typename = _RequireAllocator<_Allocator>> 02017 unordered_multimap(initializer_list<pair<_Key, _Tp>>, 02018 unordered_multimap<int, int>::size_type = {}, 02019 _Hash = _Hash(), _Pred = _Pred(), 02020 _Allocator = _Allocator()) 02021 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>; 02022 02023 template<typename _InputIterator, typename _Allocator, 02024 typename = _RequireInputIter<_InputIterator>, 02025 typename = _RequireAllocator<_Allocator>> 02026 unordered_multimap(_InputIterator, _InputIterator, 02027 unordered_multimap<int, int>::size_type, _Allocator) 02028 -> unordered_multimap<__iter_key_t<_InputIterator>, 02029 __iter_val_t<_InputIterator>, 02030 hash<__iter_key_t<_InputIterator>>, 02031 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 02032 02033 template<typename _InputIterator, typename _Allocator, 02034 typename = _RequireInputIter<_InputIterator>, 02035 typename = _RequireAllocator<_Allocator>> 02036 unordered_multimap(_InputIterator, _InputIterator, _Allocator) 02037 -> unordered_multimap<__iter_key_t<_InputIterator>, 02038 __iter_val_t<_InputIterator>, 02039 hash<__iter_key_t<_InputIterator>>, 02040 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 02041 02042 template<typename _InputIterator, typename _Hash, typename _Allocator, 02043 typename = _RequireInputIter<_InputIterator>, 02044 typename = _RequireNotAllocatorOrIntegral<_Hash>, 02045 typename = _RequireAllocator<_Allocator>> 02046 unordered_multimap(_InputIterator, _InputIterator, 02047 unordered_multimap<int, int>::size_type, _Hash, 02048 _Allocator) 02049 -> unordered_multimap<__iter_key_t<_InputIterator>, 02050 __iter_val_t<_InputIterator>, _Hash, 02051 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 02052 02053 template<typename _Key, typename _Tp, typename _Allocator, 02054 typename = _RequireAllocator<_Allocator>> 02055 unordered_multimap(initializer_list<pair<_Key, _Tp>>, 02056 unordered_multimap<int, int>::size_type, 02057 _Allocator) 02058 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 02059 02060 template<typename _Key, typename _Tp, typename _Allocator, 02061 typename = _RequireAllocator<_Allocator>> 02062 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) 02063 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 02064 02065 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator, 02066 typename = _RequireNotAllocatorOrIntegral<_Hash>, 02067 typename = _RequireAllocator<_Allocator>> 02068 unordered_multimap(initializer_list<pair<_Key, _Tp>>, 02069 unordered_multimap<int, int>::size_type, 02070 _Hash, _Allocator) 02071 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>; 02072 02073 #endif 02074 02075 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 02076 inline void 02077 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 02078 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 02079 noexcept(noexcept(__x.swap(__y))) 02080 { __x.swap(__y); } 02081 02082 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 02083 inline void 02084 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 02085 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 02086 noexcept(noexcept(__x.swap(__y))) 02087 { __x.swap(__y); } 02088 02089 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 02090 inline bool 02091 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 02092 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 02093 { return __x._M_h._M_equal(__y._M_h); } 02094 02095 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 02096 inline bool 02097 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 02098 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 02099 { return !(__x == __y); } 02100 02101 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 02102 inline bool 02103 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 02104 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 02105 { return __x._M_h._M_equal(__y._M_h); } 02106 02107 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 02108 inline bool 02109 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 02110 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 02111 { return !(__x == __y); } 02112 02113 _GLIBCXX_END_NAMESPACE_CONTAINER 02114 02115 #if __cplusplus > 201402L 02116 // Allow std::unordered_map access to internals of compatible maps. 02117 template<typename _Key, typename _Val, typename _Hash1, typename _Eq1, 02118 typename _Alloc, typename _Hash2, typename _Eq2> 02119 struct _Hash_merge_helper< 02120 _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>, 02121 _Hash2, _Eq2> 02122 { 02123 private: 02124 template<typename... _Tp> 02125 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>; 02126 template<typename... _Tp> 02127 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>; 02128 02129 friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>; 02130 02131 static auto& 02132 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) 02133 { return __map._M_h; } 02134 02135 static auto& 02136 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) 02137 { return __map._M_h; } 02138 }; 02139 02140 // Allow std::unordered_multimap access to internals of compatible maps. 02141 template<typename _Key, typename _Val, typename _Hash1, typename _Eq1, 02142 typename _Alloc, typename _Hash2, typename _Eq2> 02143 struct _Hash_merge_helper< 02144 _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>, 02145 _Hash2, _Eq2> 02146 { 02147 private: 02148 template<typename... _Tp> 02149 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>; 02150 template<typename... _Tp> 02151 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>; 02152 02153 friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>; 02154 02155 static auto& 02156 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) 02157 { return __map._M_h; } 02158 02159 static auto& 02160 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) 02161 { return __map._M_h; } 02162 }; 02163 #endif // C++17 02164 02165 _GLIBCXX_END_NAMESPACE_VERSION 02166 } // namespace std 02167 02168 #endif /* _UNORDERED_MAP_H */