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, typename = typename 00589 std::enable_if<std::is_constructible<value_type, 00590 _Pair&&>::value>::type> 00591 std::pair<iterator, bool> 00592 insert(_Pair&& __x) 00593 { return _M_h.insert(std::forward<_Pair>(__x)); } 00594 //@} 00595 00596 //@{ 00597 /** 00598 * @brief Attempts to insert a std::pair into the %unordered_map. 00599 * @param __hint An iterator that serves as a hint as to where the 00600 * pair should be inserted. 00601 * @param __x Pair to be inserted (see std::make_pair for easy creation 00602 * of pairs). 00603 * @return An iterator that points to the element with key of 00604 * @a __x (may or may not be the %pair passed in). 00605 * 00606 * This function is not concerned about whether the insertion took place, 00607 * and thus does not return a boolean like the single-argument insert() 00608 * does. Note that the first parameter is only a hint and can 00609 * potentially improve the performance of the insertion process. A bad 00610 * hint would cause no gains in efficiency. 00611 * 00612 * See 00613 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 00614 * for more on @a hinting. 00615 * 00616 * Insertion requires amortized constant time. 00617 */ 00618 iterator 00619 insert(const_iterator __hint, const value_type& __x) 00620 { return _M_h.insert(__hint, __x); } 00621 00622 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00623 // 2354. Unnecessary copying when inserting into maps with braced-init 00624 iterator 00625 insert(const_iterator __hint, value_type&& __x) 00626 { return _M_h.insert(__hint, std::move(__x)); } 00627 00628 template<typename _Pair, typename = typename 00629 std::enable_if<std::is_constructible<value_type, 00630 _Pair&&>::value>::type> 00631 iterator 00632 insert(const_iterator __hint, _Pair&& __x) 00633 { return _M_h.insert(__hint, std::forward<_Pair>(__x)); } 00634 //@} 00635 00636 /** 00637 * @brief A template function that attempts to insert a range of 00638 * elements. 00639 * @param __first Iterator pointing to the start of the range to be 00640 * inserted. 00641 * @param __last Iterator pointing to the end of the range. 00642 * 00643 * Complexity similar to that of the range constructor. 00644 */ 00645 template<typename _InputIterator> 00646 void 00647 insert(_InputIterator __first, _InputIterator __last) 00648 { _M_h.insert(__first, __last); } 00649 00650 /** 00651 * @brief Attempts to insert a list of elements into the %unordered_map. 00652 * @param __l A std::initializer_list<value_type> of elements 00653 * to be inserted. 00654 * 00655 * Complexity similar to that of the range constructor. 00656 */ 00657 void 00658 insert(initializer_list<value_type> __l) 00659 { _M_h.insert(__l); } 00660 00661 00662 #if __cplusplus > 201402L 00663 #define __cpp_lib_unordered_map_insertion 201411 00664 /** 00665 * @brief Attempts to insert a std::pair into the %unordered_map. 00666 * @param __k Key to use for finding a possibly existing pair in 00667 * the map. 00668 * @param __obj Argument used to generate the .second for a pair 00669 * instance. 00670 * 00671 * @return A pair, of which the first element is an iterator that 00672 * points to the possibly inserted pair, and the second is 00673 * a bool that is true if the pair was actually inserted. 00674 * 00675 * This function attempts to insert a (key, value) %pair into the 00676 * %unordered_map. An %unordered_map relies on unique keys and thus a 00677 * %pair is only inserted if its first element (the key) is not already 00678 * present in the %unordered_map. 00679 * If the %pair was already in the %unordered_map, the .second of 00680 * the %pair is assigned from __obj. 00681 * 00682 * Insertion requires amortized constant time. 00683 */ 00684 template <typename _Obj> 00685 pair<iterator, bool> 00686 insert_or_assign(const key_type& __k, _Obj&& __obj) 00687 { 00688 iterator __i = find(__k); 00689 if (__i == end()) 00690 { 00691 __i = emplace(std::piecewise_construct, 00692 std::forward_as_tuple(__k), 00693 std::forward_as_tuple(std::forward<_Obj>(__obj))) 00694 .first; 00695 return {__i, true}; 00696 } 00697 (*__i).second = std::forward<_Obj>(__obj); 00698 return {__i, false}; 00699 } 00700 00701 // move-capable overload 00702 template <typename _Obj> 00703 pair<iterator, bool> 00704 insert_or_assign(key_type&& __k, _Obj&& __obj) 00705 { 00706 iterator __i = find(__k); 00707 if (__i == end()) 00708 { 00709 __i = emplace(std::piecewise_construct, 00710 std::forward_as_tuple(std::move(__k)), 00711 std::forward_as_tuple(std::forward<_Obj>(__obj))) 00712 .first; 00713 return {__i, true}; 00714 } 00715 (*__i).second = std::forward<_Obj>(__obj); 00716 return {__i, false}; 00717 } 00718 00719 /** 00720 * @brief Attempts to insert a std::pair into the %unordered_map. 00721 * @param __hint An iterator that serves as a hint as to where the 00722 * pair should be inserted. 00723 * @param __k Key to use for finding a possibly existing pair in 00724 * the unordered_map. 00725 * @param __obj Argument used to generate the .second for a pair 00726 * instance. 00727 * @return An iterator that points to the element with key of 00728 * @a __x (may or may not be the %pair passed in). 00729 * 00730 * This function is not concerned about whether the insertion took place, 00731 * and thus does not return a boolean like the single-argument insert() 00732 * does. 00733 * If the %pair was already in the %unordered map, the .second of 00734 * the %pair is assigned from __obj. 00735 * Note that the first parameter is only a hint and can 00736 * potentially improve the performance of the insertion process. A bad 00737 * hint would cause no gains in efficiency. 00738 * 00739 * See 00740 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 00741 * for more on @a hinting. 00742 * 00743 * Insertion requires amortized constant time. 00744 */ 00745 template <typename _Obj> 00746 iterator 00747 insert_or_assign(const_iterator __hint, const key_type& __k, 00748 _Obj&& __obj) 00749 { 00750 iterator __i = find(__k); 00751 if (__i == end()) 00752 { 00753 return emplace_hint(__hint, std::piecewise_construct, 00754 std::forward_as_tuple(__k), 00755 std::forward_as_tuple( 00756 std::forward<_Obj>(__obj))); 00757 } 00758 (*__i).second = std::forward<_Obj>(__obj); 00759 return __i; 00760 } 00761 00762 // move-capable overload 00763 template <typename _Obj> 00764 iterator 00765 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj) 00766 { 00767 iterator __i = find(__k); 00768 if (__i == end()) 00769 { 00770 return emplace_hint(__hint, std::piecewise_construct, 00771 std::forward_as_tuple(std::move(__k)), 00772 std::forward_as_tuple( 00773 std::forward<_Obj>(__obj))); 00774 } 00775 (*__i).second = std::forward<_Obj>(__obj); 00776 return __i; 00777 } 00778 #endif 00779 00780 //@{ 00781 /** 00782 * @brief Erases an element from an %unordered_map. 00783 * @param __position An iterator pointing to the element to be erased. 00784 * @return An iterator pointing to the element immediately following 00785 * @a __position prior to the element being erased. If no such 00786 * element exists, end() is returned. 00787 * 00788 * This function erases an element, pointed to by the given iterator, 00789 * from an %unordered_map. 00790 * Note that this function only erases the element, and that if the 00791 * element is itself a pointer, the pointed-to memory is not touched in 00792 * any way. Managing the pointer is the user's responsibility. 00793 */ 00794 iterator 00795 erase(const_iterator __position) 00796 { return _M_h.erase(__position); } 00797 00798 // LWG 2059. 00799 iterator 00800 erase(iterator __position) 00801 { return _M_h.erase(__position); } 00802 //@} 00803 00804 /** 00805 * @brief Erases elements according to the provided key. 00806 * @param __x Key of element to be erased. 00807 * @return The number of elements erased. 00808 * 00809 * This function erases all the elements located by the given key from 00810 * an %unordered_map. For an %unordered_map the result of this function 00811 * can only be 0 (not present) or 1 (present). 00812 * Note that this function only erases the element, and that if the 00813 * element is itself a pointer, the pointed-to memory is not touched in 00814 * any way. Managing the pointer is the user's responsibility. 00815 */ 00816 size_type 00817 erase(const key_type& __x) 00818 { return _M_h.erase(__x); } 00819 00820 /** 00821 * @brief Erases a [__first,__last) range of elements from an 00822 * %unordered_map. 00823 * @param __first Iterator pointing to the start of the range to be 00824 * erased. 00825 * @param __last Iterator pointing to the end of the range to 00826 * be erased. 00827 * @return The iterator @a __last. 00828 * 00829 * This function erases a sequence of elements from an %unordered_map. 00830 * Note that this function only erases the elements, and that if 00831 * the element is itself a pointer, the pointed-to memory is not touched 00832 * in any way. Managing the pointer is the user's responsibility. 00833 */ 00834 iterator 00835 erase(const_iterator __first, const_iterator __last) 00836 { return _M_h.erase(__first, __last); } 00837 00838 /** 00839 * Erases all elements in an %unordered_map. 00840 * Note that this function only erases the elements, and that if the 00841 * elements themselves are pointers, the pointed-to memory is not touched 00842 * in any way. Managing the pointer is the user's responsibility. 00843 */ 00844 void 00845 clear() noexcept 00846 { _M_h.clear(); } 00847 00848 /** 00849 * @brief Swaps data with another %unordered_map. 00850 * @param __x An %unordered_map of the same element and allocator 00851 * types. 00852 * 00853 * This exchanges the elements between two %unordered_map in constant 00854 * time. 00855 * Note that the global std::swap() function is specialized such that 00856 * std::swap(m1,m2) will feed to this function. 00857 */ 00858 void 00859 swap(unordered_map& __x) 00860 noexcept( noexcept(_M_h.swap(__x._M_h)) ) 00861 { _M_h.swap(__x._M_h); } 00862 00863 #if __cplusplus > 201402L 00864 template<typename, typename, typename> 00865 friend class std::_Hash_merge_helper; 00866 00867 template<typename _H2, typename _P2> 00868 void 00869 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source) 00870 { 00871 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>; 00872 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source)); 00873 } 00874 00875 template<typename _H2, typename _P2> 00876 void 00877 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source) 00878 { merge(__source); } 00879 00880 template<typename _H2, typename _P2> 00881 void 00882 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source) 00883 { 00884 using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>; 00885 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source)); 00886 } 00887 00888 template<typename _H2, typename _P2> 00889 void 00890 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source) 00891 { merge(__source); } 00892 #endif // C++17 00893 00894 // observers. 00895 00896 /// Returns the hash functor object with which the %unordered_map was 00897 /// constructed. 00898 hasher 00899 hash_function() const 00900 { return _M_h.hash_function(); } 00901 00902 /// Returns the key comparison object with which the %unordered_map was 00903 /// constructed. 00904 key_equal 00905 key_eq() const 00906 { return _M_h.key_eq(); } 00907 00908 // lookup. 00909 00910 //@{ 00911 /** 00912 * @brief Tries to locate an element in an %unordered_map. 00913 * @param __x Key to be located. 00914 * @return Iterator pointing to sought-after element, or end() if not 00915 * found. 00916 * 00917 * This function takes a key and tries to locate the element with which 00918 * the key matches. If successful the function returns an iterator 00919 * pointing to the sought after element. If unsuccessful it returns the 00920 * past-the-end ( @c end() ) iterator. 00921 */ 00922 iterator 00923 find(const key_type& __x) 00924 { return _M_h.find(__x); } 00925 00926 const_iterator 00927 find(const key_type& __x) const 00928 { return _M_h.find(__x); } 00929 //@} 00930 00931 /** 00932 * @brief Finds the number of elements. 00933 * @param __x Key to count. 00934 * @return Number of elements with specified key. 00935 * 00936 * This function only makes sense for %unordered_multimap; for 00937 * %unordered_map the result will either be 0 (not present) or 1 00938 * (present). 00939 */ 00940 size_type 00941 count(const key_type& __x) const 00942 { return _M_h.count(__x); } 00943 00944 //@{ 00945 /** 00946 * @brief Finds a subsequence matching given key. 00947 * @param __x Key to be located. 00948 * @return Pair of iterators that possibly points to the subsequence 00949 * matching given key. 00950 * 00951 * This function probably only makes sense for %unordered_multimap. 00952 */ 00953 std::pair<iterator, iterator> 00954 equal_range(const key_type& __x) 00955 { return _M_h.equal_range(__x); } 00956 00957 std::pair<const_iterator, const_iterator> 00958 equal_range(const key_type& __x) const 00959 { return _M_h.equal_range(__x); } 00960 //@} 00961 00962 //@{ 00963 /** 00964 * @brief Subscript ( @c [] ) access to %unordered_map data. 00965 * @param __k The key for which data should be retrieved. 00966 * @return A reference to the data of the (key,data) %pair. 00967 * 00968 * Allows for easy lookup with the subscript ( @c [] )operator. Returns 00969 * data associated with the key specified in subscript. If the key does 00970 * not exist, a pair with that key is created using default values, which 00971 * is then returned. 00972 * 00973 * Lookup requires constant time. 00974 */ 00975 mapped_type& 00976 operator[](const key_type& __k) 00977 { return _M_h[__k]; } 00978 00979 mapped_type& 00980 operator[](key_type&& __k) 00981 { return _M_h[std::move(__k)]; } 00982 //@} 00983 00984 //@{ 00985 /** 00986 * @brief Access to %unordered_map data. 00987 * @param __k The key for which data should be retrieved. 00988 * @return A reference to the data whose key is equal to @a __k, if 00989 * such a data is present in the %unordered_map. 00990 * @throw std::out_of_range If no such data is present. 00991 */ 00992 mapped_type& 00993 at(const key_type& __k) 00994 { return _M_h.at(__k); } 00995 00996 const mapped_type& 00997 at(const key_type& __k) const 00998 { return _M_h.at(__k); } 00999 //@} 01000 01001 // bucket interface. 01002 01003 /// Returns the number of buckets of the %unordered_map. 01004 size_type 01005 bucket_count() const noexcept 01006 { return _M_h.bucket_count(); } 01007 01008 /// Returns the maximum number of buckets of the %unordered_map. 01009 size_type 01010 max_bucket_count() const noexcept 01011 { return _M_h.max_bucket_count(); } 01012 01013 /* 01014 * @brief Returns the number of elements in a given bucket. 01015 * @param __n A bucket index. 01016 * @return The number of elements in the bucket. 01017 */ 01018 size_type 01019 bucket_size(size_type __n) const 01020 { return _M_h.bucket_size(__n); } 01021 01022 /* 01023 * @brief Returns the bucket index of a given element. 01024 * @param __key A key instance. 01025 * @return The key bucket index. 01026 */ 01027 size_type 01028 bucket(const key_type& __key) const 01029 { return _M_h.bucket(__key); } 01030 01031 /** 01032 * @brief Returns a read/write iterator pointing to the first bucket 01033 * element. 01034 * @param __n The bucket index. 01035 * @return A read/write local iterator. 01036 */ 01037 local_iterator 01038 begin(size_type __n) 01039 { return _M_h.begin(__n); } 01040 01041 //@{ 01042 /** 01043 * @brief Returns a read-only (constant) iterator pointing to the first 01044 * bucket element. 01045 * @param __n The bucket index. 01046 * @return A read-only local iterator. 01047 */ 01048 const_local_iterator 01049 begin(size_type __n) const 01050 { return _M_h.begin(__n); } 01051 01052 const_local_iterator 01053 cbegin(size_type __n) const 01054 { return _M_h.cbegin(__n); } 01055 //@} 01056 01057 /** 01058 * @brief Returns a read/write iterator pointing to one past the last 01059 * bucket elements. 01060 * @param __n The bucket index. 01061 * @return A read/write local iterator. 01062 */ 01063 local_iterator 01064 end(size_type __n) 01065 { return _M_h.end(__n); } 01066 01067 //@{ 01068 /** 01069 * @brief Returns a read-only (constant) iterator pointing to one past 01070 * the last bucket elements. 01071 * @param __n The bucket index. 01072 * @return A read-only local iterator. 01073 */ 01074 const_local_iterator 01075 end(size_type __n) const 01076 { return _M_h.end(__n); } 01077 01078 const_local_iterator 01079 cend(size_type __n) const 01080 { return _M_h.cend(__n); } 01081 //@} 01082 01083 // hash policy. 01084 01085 /// Returns the average number of elements per bucket. 01086 float 01087 load_factor() const noexcept 01088 { return _M_h.load_factor(); } 01089 01090 /// Returns a positive number that the %unordered_map tries to keep the 01091 /// load factor less than or equal to. 01092 float 01093 max_load_factor() const noexcept 01094 { return _M_h.max_load_factor(); } 01095 01096 /** 01097 * @brief Change the %unordered_map maximum load factor. 01098 * @param __z The new maximum load factor. 01099 */ 01100 void 01101 max_load_factor(float __z) 01102 { _M_h.max_load_factor(__z); } 01103 01104 /** 01105 * @brief May rehash the %unordered_map. 01106 * @param __n The new number of buckets. 01107 * 01108 * Rehash will occur only if the new number of buckets respect the 01109 * %unordered_map maximum load factor. 01110 */ 01111 void 01112 rehash(size_type __n) 01113 { _M_h.rehash(__n); } 01114 01115 /** 01116 * @brief Prepare the %unordered_map for a specified number of 01117 * elements. 01118 * @param __n Number of elements required. 01119 * 01120 * Same as rehash(ceil(n / max_load_factor())). 01121 */ 01122 void 01123 reserve(size_type __n) 01124 { _M_h.reserve(__n); } 01125 01126 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1, 01127 typename _Alloc1> 01128 friend bool 01129 operator==(const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&, 01130 const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&); 01131 }; 01132 01133 #if __cpp_deduction_guides >= 201606 01134 01135 template<typename _InputIterator, 01136 typename _Hash = hash<__iter_key_t<_InputIterator>>, 01137 typename _Pred = equal_to<__iter_key_t<_InputIterator>>, 01138 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, 01139 typename = _RequireInputIter<_InputIterator>, 01140 typename = _RequireAllocator<_Allocator>> 01141 unordered_map(_InputIterator, _InputIterator, 01142 typename unordered_map<int, int>::size_type = {}, 01143 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 01144 -> unordered_map<__iter_key_t<_InputIterator>, 01145 __iter_val_t<_InputIterator>, 01146 _Hash, _Pred, _Allocator>; 01147 01148 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>, 01149 typename _Pred = equal_to<_Key>, 01150 typename _Allocator = allocator<pair<const _Key, _Tp>>, 01151 typename = _RequireAllocator<_Allocator>> 01152 unordered_map(initializer_list<pair<_Key, _Tp>>, 01153 typename unordered_map<int, int>::size_type = {}, 01154 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 01155 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>; 01156 01157 template<typename _InputIterator, typename _Allocator, 01158 typename = _RequireInputIter<_InputIterator>, 01159 typename = _RequireAllocator<_Allocator>> 01160 unordered_map(_InputIterator, _InputIterator, 01161 typename unordered_map<int, int>::size_type, _Allocator) 01162 -> unordered_map<__iter_key_t<_InputIterator>, 01163 __iter_val_t<_InputIterator>, 01164 hash<__iter_key_t<_InputIterator>>, 01165 equal_to<__iter_key_t<_InputIterator>>, 01166 _Allocator>; 01167 01168 template<typename _InputIterator, typename _Allocator, 01169 typename = _RequireInputIter<_InputIterator>, 01170 typename = _RequireAllocator<_Allocator>> 01171 unordered_map(_InputIterator, _InputIterator, _Allocator) 01172 -> unordered_map<__iter_key_t<_InputIterator>, 01173 __iter_val_t<_InputIterator>, 01174 hash<__iter_key_t<_InputIterator>>, 01175 equal_to<__iter_key_t<_InputIterator>>, 01176 _Allocator>; 01177 01178 template<typename _InputIterator, typename _Hash, typename _Allocator, 01179 typename = _RequireInputIter<_InputIterator>, 01180 typename = _RequireAllocator<_Allocator>> 01181 unordered_map(_InputIterator, _InputIterator, 01182 typename unordered_map<int, int>::size_type, 01183 _Hash, _Allocator) 01184 -> unordered_map<__iter_key_t<_InputIterator>, 01185 __iter_val_t<_InputIterator>, _Hash, 01186 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 01187 01188 template<typename _Key, typename _Tp, typename _Allocator, 01189 typename = _RequireAllocator<_Allocator>> 01190 unordered_map(initializer_list<pair<_Key, _Tp>>, 01191 typename unordered_map<int, int>::size_type, 01192 _Allocator) 01193 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 01194 01195 template<typename _Key, typename _Tp, typename _Allocator, 01196 typename = _RequireAllocator<_Allocator>> 01197 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator) 01198 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 01199 01200 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator, 01201 typename = _RequireAllocator<_Allocator>> 01202 unordered_map(initializer_list<pair<_Key, _Tp>>, 01203 typename unordered_map<int, int>::size_type, 01204 _Hash, _Allocator) 01205 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>; 01206 01207 #endif 01208 01209 /** 01210 * @brief A standard container composed of equivalent keys 01211 * (possibly containing multiple of each key value) that associates 01212 * values of another type with the keys. 01213 * 01214 * @ingroup unordered_associative_containers 01215 * 01216 * @tparam _Key Type of key objects. 01217 * @tparam _Tp Type of mapped objects. 01218 * @tparam _Hash Hashing function object type, defaults to hash<_Value>. 01219 * @tparam _Pred Predicate function object type, defaults 01220 * to equal_to<_Value>. 01221 * @tparam _Alloc Allocator type, defaults to 01222 * std::allocator<std::pair<const _Key, _Tp>>. 01223 * 01224 * Meets the requirements of a <a href="tables.html#65">container</a>, and 01225 * <a href="tables.html#xx">unordered associative container</a> 01226 * 01227 * The resulting value type of the container is std::pair<const _Key, _Tp>. 01228 * 01229 * Base is _Hashtable, dispatched at compile time via template 01230 * alias __ummap_hashtable. 01231 */ 01232 template<typename _Key, typename _Tp, 01233 typename _Hash = hash<_Key>, 01234 typename _Pred = equal_to<_Key>, 01235 typename _Alloc = allocator<std::pair<const _Key, _Tp>>> 01236 class unordered_multimap 01237 { 01238 typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable; 01239 _Hashtable _M_h; 01240 01241 public: 01242 // typedefs: 01243 //@{ 01244 /// Public typedefs. 01245 typedef typename _Hashtable::key_type key_type; 01246 typedef typename _Hashtable::value_type value_type; 01247 typedef typename _Hashtable::mapped_type mapped_type; 01248 typedef typename _Hashtable::hasher hasher; 01249 typedef typename _Hashtable::key_equal key_equal; 01250 typedef typename _Hashtable::allocator_type allocator_type; 01251 //@} 01252 01253 //@{ 01254 /// Iterator-related typedefs. 01255 typedef typename _Hashtable::pointer pointer; 01256 typedef typename _Hashtable::const_pointer const_pointer; 01257 typedef typename _Hashtable::reference reference; 01258 typedef typename _Hashtable::const_reference const_reference; 01259 typedef typename _Hashtable::iterator iterator; 01260 typedef typename _Hashtable::const_iterator const_iterator; 01261 typedef typename _Hashtable::local_iterator local_iterator; 01262 typedef typename _Hashtable::const_local_iterator const_local_iterator; 01263 typedef typename _Hashtable::size_type size_type; 01264 typedef typename _Hashtable::difference_type difference_type; 01265 //@} 01266 01267 #if __cplusplus > 201402L 01268 using node_type = typename _Hashtable::node_type; 01269 #endif 01270 01271 //construct/destroy/copy 01272 01273 /// Default constructor. 01274 unordered_multimap() = default; 01275 01276 /** 01277 * @brief Default constructor creates no elements. 01278 * @param __n Mnimal initial number of buckets. 01279 * @param __hf A hash functor. 01280 * @param __eql A key equality functor. 01281 * @param __a An allocator object. 01282 */ 01283 explicit 01284 unordered_multimap(size_type __n, 01285 const hasher& __hf = hasher(), 01286 const key_equal& __eql = key_equal(), 01287 const allocator_type& __a = allocator_type()) 01288 : _M_h(__n, __hf, __eql, __a) 01289 { } 01290 01291 /** 01292 * @brief Builds an %unordered_multimap from a range. 01293 * @param __first An input iterator. 01294 * @param __last An input iterator. 01295 * @param __n Minimal initial number of buckets. 01296 * @param __hf A hash functor. 01297 * @param __eql A key equality functor. 01298 * @param __a An allocator object. 01299 * 01300 * Create an %unordered_multimap consisting of copies of the elements 01301 * from [__first,__last). This is linear in N (where N is 01302 * distance(__first,__last)). 01303 */ 01304 template<typename _InputIterator> 01305 unordered_multimap(_InputIterator __first, _InputIterator __last, 01306 size_type __n = 0, 01307 const hasher& __hf = hasher(), 01308 const key_equal& __eql = key_equal(), 01309 const allocator_type& __a = allocator_type()) 01310 : _M_h(__first, __last, __n, __hf, __eql, __a) 01311 { } 01312 01313 /// Copy constructor. 01314 unordered_multimap(const unordered_multimap&) = default; 01315 01316 /// Move constructor. 01317 unordered_multimap(unordered_multimap&&) = default; 01318 01319 /** 01320 * @brief Creates an %unordered_multimap with no elements. 01321 * @param __a An allocator object. 01322 */ 01323 explicit 01324 unordered_multimap(const allocator_type& __a) 01325 : _M_h(__a) 01326 { } 01327 01328 /* 01329 * @brief Copy constructor with allocator argument. 01330 * @param __uset Input %unordered_multimap to copy. 01331 * @param __a An allocator object. 01332 */ 01333 unordered_multimap(const unordered_multimap& __ummap, 01334 const allocator_type& __a) 01335 : _M_h(__ummap._M_h, __a) 01336 { } 01337 01338 /* 01339 * @brief Move constructor with allocator argument. 01340 * @param __uset Input %unordered_multimap to move. 01341 * @param __a An allocator object. 01342 */ 01343 unordered_multimap(unordered_multimap&& __ummap, 01344 const allocator_type& __a) 01345 : _M_h(std::move(__ummap._M_h), __a) 01346 { } 01347 01348 /** 01349 * @brief Builds an %unordered_multimap from an initializer_list. 01350 * @param __l An initializer_list. 01351 * @param __n Minimal initial number of buckets. 01352 * @param __hf A hash functor. 01353 * @param __eql A key equality functor. 01354 * @param __a An allocator object. 01355 * 01356 * Create an %unordered_multimap consisting of copies of the elements in 01357 * the list. This is linear in N (where N is @a __l.size()). 01358 */ 01359 unordered_multimap(initializer_list<value_type> __l, 01360 size_type __n = 0, 01361 const hasher& __hf = hasher(), 01362 const key_equal& __eql = key_equal(), 01363 const allocator_type& __a = allocator_type()) 01364 : _M_h(__l, __n, __hf, __eql, __a) 01365 { } 01366 01367 unordered_multimap(size_type __n, const allocator_type& __a) 01368 : unordered_multimap(__n, hasher(), key_equal(), __a) 01369 { } 01370 01371 unordered_multimap(size_type __n, const hasher& __hf, 01372 const allocator_type& __a) 01373 : unordered_multimap(__n, __hf, key_equal(), __a) 01374 { } 01375 01376 template<typename _InputIterator> 01377 unordered_multimap(_InputIterator __first, _InputIterator __last, 01378 size_type __n, 01379 const allocator_type& __a) 01380 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) 01381 { } 01382 01383 template<typename _InputIterator> 01384 unordered_multimap(_InputIterator __first, _InputIterator __last, 01385 size_type __n, const hasher& __hf, 01386 const allocator_type& __a) 01387 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) 01388 { } 01389 01390 unordered_multimap(initializer_list<value_type> __l, 01391 size_type __n, 01392 const allocator_type& __a) 01393 : unordered_multimap(__l, __n, hasher(), key_equal(), __a) 01394 { } 01395 01396 unordered_multimap(initializer_list<value_type> __l, 01397 size_type __n, const hasher& __hf, 01398 const allocator_type& __a) 01399 : unordered_multimap(__l, __n, __hf, key_equal(), __a) 01400 { } 01401 01402 /// Copy assignment operator. 01403 unordered_multimap& 01404 operator=(const unordered_multimap&) = default; 01405 01406 /// Move assignment operator. 01407 unordered_multimap& 01408 operator=(unordered_multimap&&) = default; 01409 01410 /** 01411 * @brief %Unordered_multimap list assignment operator. 01412 * @param __l An initializer_list. 01413 * 01414 * This function fills an %unordered_multimap with copies of the 01415 * elements in the initializer list @a __l. 01416 * 01417 * Note that the assignment completely changes the %unordered_multimap 01418 * and that the resulting %unordered_multimap's size is the same as the 01419 * number of elements assigned. 01420 */ 01421 unordered_multimap& 01422 operator=(initializer_list<value_type> __l) 01423 { 01424 _M_h = __l; 01425 return *this; 01426 } 01427 01428 /// Returns the allocator object used by the %unordered_multimap. 01429 allocator_type 01430 get_allocator() const noexcept 01431 { return _M_h.get_allocator(); } 01432 01433 // size and capacity: 01434 01435 /// Returns true if the %unordered_multimap is empty. 01436 bool 01437 empty() const noexcept 01438 { return _M_h.empty(); } 01439 01440 /// Returns the size of the %unordered_multimap. 01441 size_type 01442 size() const noexcept 01443 { return _M_h.size(); } 01444 01445 /// Returns the maximum size of the %unordered_multimap. 01446 size_type 01447 max_size() const noexcept 01448 { return _M_h.max_size(); } 01449 01450 // iterators. 01451 01452 /** 01453 * Returns a read/write iterator that points to the first element in the 01454 * %unordered_multimap. 01455 */ 01456 iterator 01457 begin() noexcept 01458 { return _M_h.begin(); } 01459 01460 //@{ 01461 /** 01462 * Returns a read-only (constant) iterator that points to the first 01463 * element in the %unordered_multimap. 01464 */ 01465 const_iterator 01466 begin() const noexcept 01467 { return _M_h.begin(); } 01468 01469 const_iterator 01470 cbegin() const noexcept 01471 { return _M_h.begin(); } 01472 //@} 01473 01474 /** 01475 * Returns a read/write iterator that points one past the last element in 01476 * the %unordered_multimap. 01477 */ 01478 iterator 01479 end() noexcept 01480 { return _M_h.end(); } 01481 01482 //@{ 01483 /** 01484 * Returns a read-only (constant) iterator that points one past the last 01485 * element in the %unordered_multimap. 01486 */ 01487 const_iterator 01488 end() const noexcept 01489 { return _M_h.end(); } 01490 01491 const_iterator 01492 cend() const noexcept 01493 { return _M_h.end(); } 01494 //@} 01495 01496 // modifiers. 01497 01498 /** 01499 * @brief Attempts to build and insert a std::pair into the 01500 * %unordered_multimap. 01501 * 01502 * @param __args Arguments used to generate a new pair instance (see 01503 * std::piecewise_contruct for passing arguments to each 01504 * part of the pair constructor). 01505 * 01506 * @return An iterator that points to the inserted pair. 01507 * 01508 * This function attempts to build and insert a (key, value) %pair into 01509 * the %unordered_multimap. 01510 * 01511 * Insertion requires amortized constant time. 01512 */ 01513 template<typename... _Args> 01514 iterator 01515 emplace(_Args&&... __args) 01516 { return _M_h.emplace(std::forward<_Args>(__args)...); } 01517 01518 /** 01519 * @brief Attempts to build and insert a std::pair into the 01520 * %unordered_multimap. 01521 * 01522 * @param __pos An iterator that serves as a hint as to where the pair 01523 * should be inserted. 01524 * @param __args Arguments used to generate a new pair instance (see 01525 * std::piecewise_contruct for passing arguments to each 01526 * part of the pair constructor). 01527 * @return An iterator that points to the element with key of the 01528 * std::pair built from @a __args. 01529 * 01530 * Note that the first parameter is only a hint and can potentially 01531 * improve the performance of the insertion process. A bad hint would 01532 * cause no gains in efficiency. 01533 * 01534 * See 01535 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 01536 * for more on @a hinting. 01537 * 01538 * Insertion requires amortized constant time. 01539 */ 01540 template<typename... _Args> 01541 iterator 01542 emplace_hint(const_iterator __pos, _Args&&... __args) 01543 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); } 01544 01545 //@{ 01546 /** 01547 * @brief Inserts a std::pair into the %unordered_multimap. 01548 * @param __x Pair to be inserted (see std::make_pair for easy 01549 * creation of pairs). 01550 * 01551 * @return An iterator that points to the inserted pair. 01552 * 01553 * Insertion requires amortized constant time. 01554 */ 01555 iterator 01556 insert(const value_type& __x) 01557 { return _M_h.insert(__x); } 01558 01559 iterator 01560 insert(value_type&& __x) 01561 { return _M_h.insert(std::move(__x)); } 01562 01563 template<typename _Pair, typename = typename 01564 std::enable_if<std::is_constructible<value_type, 01565 _Pair&&>::value>::type> 01566 iterator 01567 insert(_Pair&& __x) 01568 { return _M_h.insert(std::forward<_Pair>(__x)); } 01569 //@} 01570 01571 //@{ 01572 /** 01573 * @brief Inserts a std::pair into the %unordered_multimap. 01574 * @param __hint An iterator that serves as a hint as to where the 01575 * pair should be inserted. 01576 * @param __x Pair to be inserted (see std::make_pair for easy creation 01577 * of pairs). 01578 * @return An iterator that points to the element with key of 01579 * @a __x (may or may not be the %pair passed in). 01580 * 01581 * Note that the first parameter is only a hint and can potentially 01582 * improve the performance of the insertion process. A bad hint would 01583 * cause no gains in efficiency. 01584 * 01585 * See 01586 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 01587 * for more on @a hinting. 01588 * 01589 * Insertion requires amortized constant time. 01590 */ 01591 iterator 01592 insert(const_iterator __hint, const value_type& __x) 01593 { return _M_h.insert(__hint, __x); } 01594 01595 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01596 // 2354. Unnecessary copying when inserting into maps with braced-init 01597 iterator 01598 insert(const_iterator __hint, value_type&& __x) 01599 { return _M_h.insert(__hint, std::move(__x)); } 01600 01601 template<typename _Pair, typename = typename 01602 std::enable_if<std::is_constructible<value_type, 01603 _Pair&&>::value>::type> 01604 iterator 01605 insert(const_iterator __hint, _Pair&& __x) 01606 { return _M_h.insert(__hint, std::forward<_Pair>(__x)); } 01607 //@} 01608 01609 /** 01610 * @brief A template function that attempts to insert a range of 01611 * elements. 01612 * @param __first Iterator pointing to the start of the range to be 01613 * inserted. 01614 * @param __last Iterator pointing to the end of the range. 01615 * 01616 * Complexity similar to that of the range constructor. 01617 */ 01618 template<typename _InputIterator> 01619 void 01620 insert(_InputIterator __first, _InputIterator __last) 01621 { _M_h.insert(__first, __last); } 01622 01623 /** 01624 * @brief Attempts to insert a list of elements into the 01625 * %unordered_multimap. 01626 * @param __l A std::initializer_list<value_type> of elements 01627 * to be inserted. 01628 * 01629 * Complexity similar to that of the range constructor. 01630 */ 01631 void 01632 insert(initializer_list<value_type> __l) 01633 { _M_h.insert(__l); } 01634 01635 #if __cplusplus > 201402L 01636 /// Extract a node. 01637 node_type 01638 extract(const_iterator __pos) 01639 { 01640 __glibcxx_assert(__pos != end()); 01641 return _M_h.extract(__pos); 01642 } 01643 01644 /// Extract a node. 01645 node_type 01646 extract(const key_type& __key) 01647 { return _M_h.extract(__key); } 01648 01649 /// Re-insert an extracted node. 01650 iterator 01651 insert(node_type&& __nh) 01652 { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); } 01653 01654 /// Re-insert an extracted node. 01655 iterator 01656 insert(const_iterator __hint, node_type&& __nh) 01657 { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); } 01658 #endif // C++17 01659 01660 //@{ 01661 /** 01662 * @brief Erases an element from an %unordered_multimap. 01663 * @param __position An iterator pointing to the element to be erased. 01664 * @return An iterator pointing to the element immediately following 01665 * @a __position prior to the element being erased. If no such 01666 * element exists, end() is returned. 01667 * 01668 * This function erases an element, pointed to by the given iterator, 01669 * from an %unordered_multimap. 01670 * Note that this function only erases the element, and that if the 01671 * element is itself a pointer, the pointed-to memory is not touched in 01672 * any way. Managing the pointer is the user's responsibility. 01673 */ 01674 iterator 01675 erase(const_iterator __position) 01676 { return _M_h.erase(__position); } 01677 01678 // LWG 2059. 01679 iterator 01680 erase(iterator __position) 01681 { return _M_h.erase(__position); } 01682 //@} 01683 01684 /** 01685 * @brief Erases elements according to the provided key. 01686 * @param __x Key of elements to be erased. 01687 * @return The number of elements erased. 01688 * 01689 * This function erases all the elements located by the given key from 01690 * an %unordered_multimap. 01691 * Note that this function only erases the element, and that if the 01692 * element is itself a pointer, the pointed-to memory is not touched in 01693 * any way. Managing the pointer is the user's responsibility. 01694 */ 01695 size_type 01696 erase(const key_type& __x) 01697 { return _M_h.erase(__x); } 01698 01699 /** 01700 * @brief Erases a [__first,__last) range of elements from an 01701 * %unordered_multimap. 01702 * @param __first Iterator pointing to the start of the range to be 01703 * erased. 01704 * @param __last Iterator pointing to the end of the range to 01705 * be erased. 01706 * @return The iterator @a __last. 01707 * 01708 * This function erases a sequence of elements from an 01709 * %unordered_multimap. 01710 * Note that this function only erases the elements, and that if 01711 * the element is itself a pointer, the pointed-to memory is not touched 01712 * in any way. Managing the pointer is the user's responsibility. 01713 */ 01714 iterator 01715 erase(const_iterator __first, const_iterator __last) 01716 { return _M_h.erase(__first, __last); } 01717 01718 /** 01719 * Erases all elements in an %unordered_multimap. 01720 * Note that this function only erases the elements, and that if the 01721 * elements themselves are pointers, the pointed-to memory is not touched 01722 * in any way. Managing the pointer is the user's responsibility. 01723 */ 01724 void 01725 clear() noexcept 01726 { _M_h.clear(); } 01727 01728 /** 01729 * @brief Swaps data with another %unordered_multimap. 01730 * @param __x An %unordered_multimap of the same element and allocator 01731 * types. 01732 * 01733 * This exchanges the elements between two %unordered_multimap in 01734 * constant time. 01735 * Note that the global std::swap() function is specialized such that 01736 * std::swap(m1,m2) will feed to this function. 01737 */ 01738 void 01739 swap(unordered_multimap& __x) 01740 noexcept( noexcept(_M_h.swap(__x._M_h)) ) 01741 { _M_h.swap(__x._M_h); } 01742 01743 #if __cplusplus > 201402L 01744 template<typename, typename, typename> 01745 friend class std::_Hash_merge_helper; 01746 01747 template<typename _H2, typename _P2> 01748 void 01749 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source) 01750 { 01751 using _Merge_helper 01752 = _Hash_merge_helper<unordered_multimap, _H2, _P2>; 01753 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); 01754 } 01755 01756 template<typename _H2, typename _P2> 01757 void 01758 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source) 01759 { merge(__source); } 01760 01761 template<typename _H2, typename _P2> 01762 void 01763 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source) 01764 { 01765 using _Merge_helper 01766 = _Hash_merge_helper<unordered_multimap, _H2, _P2>; 01767 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); 01768 } 01769 01770 template<typename _H2, typename _P2> 01771 void 01772 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source) 01773 { merge(__source); } 01774 #endif // C++17 01775 01776 // observers. 01777 01778 /// Returns the hash functor object with which the %unordered_multimap 01779 /// was constructed. 01780 hasher 01781 hash_function() const 01782 { return _M_h.hash_function(); } 01783 01784 /// Returns the key comparison object with which the %unordered_multimap 01785 /// was constructed. 01786 key_equal 01787 key_eq() const 01788 { return _M_h.key_eq(); } 01789 01790 // lookup. 01791 01792 //@{ 01793 /** 01794 * @brief Tries to locate an element in an %unordered_multimap. 01795 * @param __x Key to be located. 01796 * @return Iterator pointing to sought-after element, or end() if not 01797 * found. 01798 * 01799 * This function takes a key and tries to locate the element with which 01800 * the key matches. If successful the function returns an iterator 01801 * pointing to the sought after element. If unsuccessful it returns the 01802 * past-the-end ( @c end() ) iterator. 01803 */ 01804 iterator 01805 find(const key_type& __x) 01806 { return _M_h.find(__x); } 01807 01808 const_iterator 01809 find(const key_type& __x) const 01810 { return _M_h.find(__x); } 01811 //@} 01812 01813 /** 01814 * @brief Finds the number of elements. 01815 * @param __x Key to count. 01816 * @return Number of elements with specified key. 01817 */ 01818 size_type 01819 count(const key_type& __x) const 01820 { return _M_h.count(__x); } 01821 01822 //@{ 01823 /** 01824 * @brief Finds a subsequence matching given key. 01825 * @param __x Key to be located. 01826 * @return Pair of iterators that possibly points to the subsequence 01827 * matching given key. 01828 */ 01829 std::pair<iterator, iterator> 01830 equal_range(const key_type& __x) 01831 { return _M_h.equal_range(__x); } 01832 01833 std::pair<const_iterator, const_iterator> 01834 equal_range(const key_type& __x) const 01835 { return _M_h.equal_range(__x); } 01836 //@} 01837 01838 // bucket interface. 01839 01840 /// Returns the number of buckets of the %unordered_multimap. 01841 size_type 01842 bucket_count() const noexcept 01843 { return _M_h.bucket_count(); } 01844 01845 /// Returns the maximum number of buckets of the %unordered_multimap. 01846 size_type 01847 max_bucket_count() const noexcept 01848 { return _M_h.max_bucket_count(); } 01849 01850 /* 01851 * @brief Returns the number of elements in a given bucket. 01852 * @param __n A bucket index. 01853 * @return The number of elements in the bucket. 01854 */ 01855 size_type 01856 bucket_size(size_type __n) const 01857 { return _M_h.bucket_size(__n); } 01858 01859 /* 01860 * @brief Returns the bucket index of a given element. 01861 * @param __key A key instance. 01862 * @return The key bucket index. 01863 */ 01864 size_type 01865 bucket(const key_type& __key) const 01866 { return _M_h.bucket(__key); } 01867 01868 /** 01869 * @brief Returns a read/write iterator pointing to the first bucket 01870 * element. 01871 * @param __n The bucket index. 01872 * @return A read/write local iterator. 01873 */ 01874 local_iterator 01875 begin(size_type __n) 01876 { return _M_h.begin(__n); } 01877 01878 //@{ 01879 /** 01880 * @brief Returns a read-only (constant) iterator pointing to the first 01881 * bucket element. 01882 * @param __n The bucket index. 01883 * @return A read-only local iterator. 01884 */ 01885 const_local_iterator 01886 begin(size_type __n) const 01887 { return _M_h.begin(__n); } 01888 01889 const_local_iterator 01890 cbegin(size_type __n) const 01891 { return _M_h.cbegin(__n); } 01892 //@} 01893 01894 /** 01895 * @brief Returns a read/write iterator pointing to one past the last 01896 * bucket elements. 01897 * @param __n The bucket index. 01898 * @return A read/write local iterator. 01899 */ 01900 local_iterator 01901 end(size_type __n) 01902 { return _M_h.end(__n); } 01903 01904 //@{ 01905 /** 01906 * @brief Returns a read-only (constant) iterator pointing to one past 01907 * the last bucket elements. 01908 * @param __n The bucket index. 01909 * @return A read-only local iterator. 01910 */ 01911 const_local_iterator 01912 end(size_type __n) const 01913 { return _M_h.end(__n); } 01914 01915 const_local_iterator 01916 cend(size_type __n) const 01917 { return _M_h.cend(__n); } 01918 //@} 01919 01920 // hash policy. 01921 01922 /// Returns the average number of elements per bucket. 01923 float 01924 load_factor() const noexcept 01925 { return _M_h.load_factor(); } 01926 01927 /// Returns a positive number that the %unordered_multimap tries to keep 01928 /// the load factor less than or equal to. 01929 float 01930 max_load_factor() const noexcept 01931 { return _M_h.max_load_factor(); } 01932 01933 /** 01934 * @brief Change the %unordered_multimap maximum load factor. 01935 * @param __z The new maximum load factor. 01936 */ 01937 void 01938 max_load_factor(float __z) 01939 { _M_h.max_load_factor(__z); } 01940 01941 /** 01942 * @brief May rehash the %unordered_multimap. 01943 * @param __n The new number of buckets. 01944 * 01945 * Rehash will occur only if the new number of buckets respect the 01946 * %unordered_multimap maximum load factor. 01947 */ 01948 void 01949 rehash(size_type __n) 01950 { _M_h.rehash(__n); } 01951 01952 /** 01953 * @brief Prepare the %unordered_multimap for a specified number of 01954 * elements. 01955 * @param __n Number of elements required. 01956 * 01957 * Same as rehash(ceil(n / max_load_factor())). 01958 */ 01959 void 01960 reserve(size_type __n) 01961 { _M_h.reserve(__n); } 01962 01963 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1, 01964 typename _Alloc1> 01965 friend bool 01966 operator==(const unordered_multimap<_Key1, _Tp1, 01967 _Hash1, _Pred1, _Alloc1>&, 01968 const unordered_multimap<_Key1, _Tp1, 01969 _Hash1, _Pred1, _Alloc1>&); 01970 }; 01971 01972 #if __cpp_deduction_guides >= 201606 01973 01974 template<typename _InputIterator, 01975 typename _Hash = hash<__iter_key_t<_InputIterator>>, 01976 typename _Pred = equal_to<__iter_key_t<_InputIterator>>, 01977 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, 01978 typename = _RequireInputIter<_InputIterator>, 01979 typename = _RequireAllocator<_Allocator>> 01980 unordered_multimap(_InputIterator, _InputIterator, 01981 unordered_multimap<int, int>::size_type = {}, 01982 _Hash = _Hash(), _Pred = _Pred(), 01983 _Allocator = _Allocator()) 01984 -> unordered_multimap<__iter_key_t<_InputIterator>, 01985 __iter_val_t<_InputIterator>, _Hash, _Pred, 01986 _Allocator>; 01987 01988 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>, 01989 typename _Pred = equal_to<_Key>, 01990 typename _Allocator = allocator<pair<const _Key, _Tp>>, 01991 typename = _RequireAllocator<_Allocator>> 01992 unordered_multimap(initializer_list<pair<_Key, _Tp>>, 01993 unordered_multimap<int, int>::size_type = {}, 01994 _Hash = _Hash(), _Pred = _Pred(), 01995 _Allocator = _Allocator()) 01996 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>; 01997 01998 template<typename _InputIterator, typename _Allocator, 01999 typename = _RequireInputIter<_InputIterator>, 02000 typename = _RequireAllocator<_Allocator>> 02001 unordered_multimap(_InputIterator, _InputIterator, 02002 unordered_multimap<int, int>::size_type, _Allocator) 02003 -> unordered_multimap<__iter_key_t<_InputIterator>, 02004 __iter_val_t<_InputIterator>, 02005 hash<__iter_key_t<_InputIterator>>, 02006 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 02007 02008 template<typename _InputIterator, typename _Allocator, 02009 typename = _RequireInputIter<_InputIterator>, 02010 typename = _RequireAllocator<_Allocator>> 02011 unordered_multimap(_InputIterator, _InputIterator, _Allocator) 02012 -> unordered_multimap<__iter_key_t<_InputIterator>, 02013 __iter_val_t<_InputIterator>, 02014 hash<__iter_key_t<_InputIterator>>, 02015 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 02016 02017 template<typename _InputIterator, typename _Hash, typename _Allocator, 02018 typename = _RequireInputIter<_InputIterator>, 02019 typename = _RequireAllocator<_Allocator>> 02020 unordered_multimap(_InputIterator, _InputIterator, 02021 unordered_multimap<int, int>::size_type, _Hash, 02022 _Allocator) 02023 -> unordered_multimap<__iter_key_t<_InputIterator>, 02024 __iter_val_t<_InputIterator>, _Hash, 02025 equal_to<__iter_key_t<_InputIterator>>, _Allocator>; 02026 02027 template<typename _Key, typename _Tp, typename _Allocator, 02028 typename = _RequireAllocator<_Allocator>> 02029 unordered_multimap(initializer_list<pair<_Key, _Tp>>, 02030 unordered_multimap<int, int>::size_type, 02031 _Allocator) 02032 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 02033 02034 template<typename _Key, typename _Tp, typename _Allocator, 02035 typename = _RequireAllocator<_Allocator>> 02036 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) 02037 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>; 02038 02039 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator, 02040 typename = _RequireAllocator<_Allocator>> 02041 unordered_multimap(initializer_list<pair<_Key, _Tp>>, 02042 unordered_multimap<int, int>::size_type, 02043 _Hash, _Allocator) 02044 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>; 02045 02046 #endif 02047 02048 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 02049 inline void 02050 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 02051 unordered_map<_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 void 02057 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 02058 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 02059 noexcept(noexcept(__x.swap(__y))) 02060 { __x.swap(__y); } 02061 02062 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 02063 inline bool 02064 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 02065 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 02066 { return __x._M_h._M_equal(__y._M_h); } 02067 02068 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 02069 inline bool 02070 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 02071 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 02072 { return !(__x == __y); } 02073 02074 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 02075 inline bool 02076 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 02077 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 02078 { return __x._M_h._M_equal(__y._M_h); } 02079 02080 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 02081 inline bool 02082 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 02083 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 02084 { return !(__x == __y); } 02085 02086 _GLIBCXX_END_NAMESPACE_CONTAINER 02087 02088 #if __cplusplus > 201402L 02089 // Allow std::unordered_map access to internals of compatible maps. 02090 template<typename _Key, typename _Val, typename _Hash1, typename _Eq1, 02091 typename _Alloc, typename _Hash2, typename _Eq2> 02092 struct _Hash_merge_helper< 02093 _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>, 02094 _Hash2, _Eq2> 02095 { 02096 private: 02097 template<typename... _Tp> 02098 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>; 02099 template<typename... _Tp> 02100 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>; 02101 02102 friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>; 02103 02104 static auto& 02105 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) 02106 { return __map._M_h; } 02107 02108 static auto& 02109 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) 02110 { return __map._M_h; } 02111 }; 02112 02113 // Allow std::unordered_multimap access to internals of compatible maps. 02114 template<typename _Key, typename _Val, typename _Hash1, typename _Eq1, 02115 typename _Alloc, typename _Hash2, typename _Eq2> 02116 struct _Hash_merge_helper< 02117 _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>, 02118 _Hash2, _Eq2> 02119 { 02120 private: 02121 template<typename... _Tp> 02122 using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>; 02123 template<typename... _Tp> 02124 using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>; 02125 02126 friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>; 02127 02128 static auto& 02129 _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) 02130 { return __map._M_h; } 02131 02132 static auto& 02133 _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map) 02134 { return __map._M_h; } 02135 }; 02136 #endif // C++17 02137 02138 _GLIBCXX_END_NAMESPACE_VERSION 02139 } // namespace std 02140 02141 #endif /* _UNORDERED_MAP_H */