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