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