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