libstdc++
|
00001 // unordered_map implementation -*- C++ -*- 00002 00003 // Copyright (C) 2010-2015 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 /** 00415 * @brief Attempts to insert a std::pair into the %unordered_map. 00416 00417 * @param __x Pair to be inserted (see std::make_pair for easy 00418 * creation of pairs). 00419 * 00420 * @return A pair, of which the first element is an iterator that 00421 * points to the possibly inserted pair, and the second is 00422 * a bool that is true if the pair was actually inserted. 00423 * 00424 * This function attempts to insert a (key, value) %pair into the 00425 * %unordered_map. An %unordered_map relies on unique keys and thus a 00426 * %pair is only inserted if its first element (the key) is not already 00427 * present in the %unordered_map. 00428 * 00429 * Insertion requires amortized constant time. 00430 */ 00431 std::pair<iterator, bool> 00432 insert(const value_type& __x) 00433 { return _M_h.insert(__x); } 00434 00435 template<typename _Pair, typename = typename 00436 std::enable_if<std::is_constructible<value_type, 00437 _Pair&&>::value>::type> 00438 std::pair<iterator, bool> 00439 insert(_Pair&& __x) 00440 { return _M_h.insert(std::forward<_Pair>(__x)); } 00441 //@} 00442 00443 //@{ 00444 /** 00445 * @brief Attempts to insert a std::pair into the %unordered_map. 00446 * @param __hint An iterator that serves as a hint as to where the 00447 * pair should be inserted. 00448 * @param __x Pair to be inserted (see std::make_pair for easy creation 00449 * of pairs). 00450 * @return An iterator that points to the element with key of 00451 * @a __x (may or may not be the %pair passed in). 00452 * 00453 * This function is not concerned about whether the insertion took place, 00454 * and thus does not return a boolean like the single-argument insert() 00455 * does. Note that the first parameter is only a hint and can 00456 * potentially improve the performance of the insertion process. A bad 00457 * hint would cause no gains in efficiency. 00458 * 00459 * See 00460 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 00461 * for more on @a hinting. 00462 * 00463 * Insertion requires amortized constant time. 00464 */ 00465 iterator 00466 insert(const_iterator __hint, const value_type& __x) 00467 { return _M_h.insert(__hint, __x); } 00468 00469 template<typename _Pair, typename = typename 00470 std::enable_if<std::is_constructible<value_type, 00471 _Pair&&>::value>::type> 00472 iterator 00473 insert(const_iterator __hint, _Pair&& __x) 00474 { return _M_h.insert(__hint, std::forward<_Pair>(__x)); } 00475 //@} 00476 00477 /** 00478 * @brief A template function that attempts to insert a range of 00479 * elements. 00480 * @param __first Iterator pointing to the start of the range to be 00481 * inserted. 00482 * @param __last Iterator pointing to the end of the range. 00483 * 00484 * Complexity similar to that of the range constructor. 00485 */ 00486 template<typename _InputIterator> 00487 void 00488 insert(_InputIterator __first, _InputIterator __last) 00489 { _M_h.insert(__first, __last); } 00490 00491 /** 00492 * @brief Attempts to insert a list of elements into the %unordered_map. 00493 * @param __l A std::initializer_list<value_type> of elements 00494 * to be inserted. 00495 * 00496 * Complexity similar to that of the range constructor. 00497 */ 00498 void 00499 insert(initializer_list<value_type> __l) 00500 { _M_h.insert(__l); } 00501 00502 //@{ 00503 /** 00504 * @brief Erases an element from an %unordered_map. 00505 * @param __position An iterator pointing to the element to be erased. 00506 * @return An iterator pointing to the element immediately following 00507 * @a __position prior to the element being erased. If no such 00508 * element exists, end() is returned. 00509 * 00510 * This function erases an element, pointed to by the given iterator, 00511 * from an %unordered_map. 00512 * Note that this function only erases the element, and that if the 00513 * element is itself a pointer, the pointed-to memory is not touched in 00514 * any way. Managing the pointer is the user's responsibility. 00515 */ 00516 iterator 00517 erase(const_iterator __position) 00518 { return _M_h.erase(__position); } 00519 00520 // LWG 2059. 00521 iterator 00522 erase(iterator __position) 00523 { return _M_h.erase(__position); } 00524 //@} 00525 00526 /** 00527 * @brief Erases elements according to the provided key. 00528 * @param __x Key of element to be erased. 00529 * @return The number of elements erased. 00530 * 00531 * This function erases all the elements located by the given key from 00532 * an %unordered_map. For an %unordered_map the result of this function 00533 * can only be 0 (not present) or 1 (present). 00534 * Note that this function only erases the element, and that if the 00535 * element is itself a pointer, the pointed-to memory is not touched in 00536 * any way. Managing the pointer is the user's responsibility. 00537 */ 00538 size_type 00539 erase(const key_type& __x) 00540 { return _M_h.erase(__x); } 00541 00542 /** 00543 * @brief Erases a [__first,__last) range of elements from an 00544 * %unordered_map. 00545 * @param __first Iterator pointing to the start of the range to be 00546 * erased. 00547 * @param __last Iterator pointing to the end of the range to 00548 * be erased. 00549 * @return The iterator @a __last. 00550 * 00551 * This function erases a sequence of elements from an %unordered_map. 00552 * Note that this function only erases the elements, and that if 00553 * the element is itself a pointer, the pointed-to memory is not touched 00554 * in any way. Managing the pointer is the user's responsibility. 00555 */ 00556 iterator 00557 erase(const_iterator __first, const_iterator __last) 00558 { return _M_h.erase(__first, __last); } 00559 00560 /** 00561 * Erases all elements in an %unordered_map. 00562 * Note that this function only erases the elements, and that if the 00563 * elements themselves are pointers, the pointed-to memory is not touched 00564 * in any way. Managing the pointer is the user's responsibility. 00565 */ 00566 void 00567 clear() noexcept 00568 { _M_h.clear(); } 00569 00570 /** 00571 * @brief Swaps data with another %unordered_map. 00572 * @param __x An %unordered_map of the same element and allocator 00573 * types. 00574 * 00575 * This exchanges the elements between two %unordered_map in constant 00576 * time. 00577 * Note that the global std::swap() function is specialized such that 00578 * std::swap(m1,m2) will feed to this function. 00579 */ 00580 void 00581 swap(unordered_map& __x) 00582 noexcept( noexcept(_M_h.swap(__x._M_h)) ) 00583 { _M_h.swap(__x._M_h); } 00584 00585 // observers. 00586 00587 /// Returns the hash functor object with which the %unordered_map was 00588 /// constructed. 00589 hasher 00590 hash_function() const 00591 { return _M_h.hash_function(); } 00592 00593 /// Returns the key comparison object with which the %unordered_map was 00594 /// constructed. 00595 key_equal 00596 key_eq() const 00597 { return _M_h.key_eq(); } 00598 00599 // lookup. 00600 00601 //@{ 00602 /** 00603 * @brief Tries to locate an element in an %unordered_map. 00604 * @param __x Key to be located. 00605 * @return Iterator pointing to sought-after element, or end() if not 00606 * found. 00607 * 00608 * This function takes a key and tries to locate the element with which 00609 * the key matches. If successful the function returns an iterator 00610 * pointing to the sought after element. If unsuccessful it returns the 00611 * past-the-end ( @c end() ) iterator. 00612 */ 00613 iterator 00614 find(const key_type& __x) 00615 { return _M_h.find(__x); } 00616 00617 const_iterator 00618 find(const key_type& __x) const 00619 { return _M_h.find(__x); } 00620 //@} 00621 00622 /** 00623 * @brief Finds the number of elements. 00624 * @param __x Key to count. 00625 * @return Number of elements with specified key. 00626 * 00627 * This function only makes sense for %unordered_multimap; for 00628 * %unordered_map the result will either be 0 (not present) or 1 00629 * (present). 00630 */ 00631 size_type 00632 count(const key_type& __x) const 00633 { return _M_h.count(__x); } 00634 00635 //@{ 00636 /** 00637 * @brief Finds a subsequence matching given key. 00638 * @param __x Key to be located. 00639 * @return Pair of iterators that possibly points to the subsequence 00640 * matching given key. 00641 * 00642 * This function probably only makes sense for %unordered_multimap. 00643 */ 00644 std::pair<iterator, iterator> 00645 equal_range(const key_type& __x) 00646 { return _M_h.equal_range(__x); } 00647 00648 std::pair<const_iterator, const_iterator> 00649 equal_range(const key_type& __x) const 00650 { return _M_h.equal_range(__x); } 00651 //@} 00652 00653 //@{ 00654 /** 00655 * @brief Subscript ( @c [] ) access to %unordered_map data. 00656 * @param __k The key for which data should be retrieved. 00657 * @return A reference to the data of the (key,data) %pair. 00658 * 00659 * Allows for easy lookup with the subscript ( @c [] )operator. Returns 00660 * data associated with the key specified in subscript. If the key does 00661 * not exist, a pair with that key is created using default values, which 00662 * is then returned. 00663 * 00664 * Lookup requires constant time. 00665 */ 00666 mapped_type& 00667 operator[](const key_type& __k) 00668 { return _M_h[__k]; } 00669 00670 mapped_type& 00671 operator[](key_type&& __k) 00672 { return _M_h[std::move(__k)]; } 00673 //@} 00674 00675 //@{ 00676 /** 00677 * @brief Access to %unordered_map data. 00678 * @param __k The key for which data should be retrieved. 00679 * @return A reference to the data whose key is equal to @a __k, if 00680 * such a data is present in the %unordered_map. 00681 * @throw std::out_of_range If no such data is present. 00682 */ 00683 mapped_type& 00684 at(const key_type& __k) 00685 { return _M_h.at(__k); } 00686 00687 const mapped_type& 00688 at(const key_type& __k) const 00689 { return _M_h.at(__k); } 00690 //@} 00691 00692 // bucket interface. 00693 00694 /// Returns the number of buckets of the %unordered_map. 00695 size_type 00696 bucket_count() const noexcept 00697 { return _M_h.bucket_count(); } 00698 00699 /// Returns the maximum number of buckets of the %unordered_map. 00700 size_type 00701 max_bucket_count() const noexcept 00702 { return _M_h.max_bucket_count(); } 00703 00704 /* 00705 * @brief Returns the number of elements in a given bucket. 00706 * @param __n A bucket index. 00707 * @return The number of elements in the bucket. 00708 */ 00709 size_type 00710 bucket_size(size_type __n) const 00711 { return _M_h.bucket_size(__n); } 00712 00713 /* 00714 * @brief Returns the bucket index of a given element. 00715 * @param __key A key instance. 00716 * @return The key bucket index. 00717 */ 00718 size_type 00719 bucket(const key_type& __key) const 00720 { return _M_h.bucket(__key); } 00721 00722 /** 00723 * @brief Returns a read/write iterator pointing to the first bucket 00724 * element. 00725 * @param __n The bucket index. 00726 * @return A read/write local iterator. 00727 */ 00728 local_iterator 00729 begin(size_type __n) 00730 { return _M_h.begin(__n); } 00731 00732 //@{ 00733 /** 00734 * @brief Returns a read-only (constant) iterator pointing to the first 00735 * bucket element. 00736 * @param __n The bucket index. 00737 * @return A read-only local iterator. 00738 */ 00739 const_local_iterator 00740 begin(size_type __n) const 00741 { return _M_h.begin(__n); } 00742 00743 const_local_iterator 00744 cbegin(size_type __n) const 00745 { return _M_h.cbegin(__n); } 00746 //@} 00747 00748 /** 00749 * @brief Returns a read/write iterator pointing to one past the last 00750 * bucket elements. 00751 * @param __n The bucket index. 00752 * @return A read/write local iterator. 00753 */ 00754 local_iterator 00755 end(size_type __n) 00756 { return _M_h.end(__n); } 00757 00758 //@{ 00759 /** 00760 * @brief Returns a read-only (constant) iterator pointing to one past 00761 * the last bucket elements. 00762 * @param __n The bucket index. 00763 * @return A read-only local iterator. 00764 */ 00765 const_local_iterator 00766 end(size_type __n) const 00767 { return _M_h.end(__n); } 00768 00769 const_local_iterator 00770 cend(size_type __n) const 00771 { return _M_h.cend(__n); } 00772 //@} 00773 00774 // hash policy. 00775 00776 /// Returns the average number of elements per bucket. 00777 float 00778 load_factor() const noexcept 00779 { return _M_h.load_factor(); } 00780 00781 /// Returns a positive number that the %unordered_map tries to keep the 00782 /// load factor less than or equal to. 00783 float 00784 max_load_factor() const noexcept 00785 { return _M_h.max_load_factor(); } 00786 00787 /** 00788 * @brief Change the %unordered_map maximum load factor. 00789 * @param __z The new maximum load factor. 00790 */ 00791 void 00792 max_load_factor(float __z) 00793 { _M_h.max_load_factor(__z); } 00794 00795 /** 00796 * @brief May rehash the %unordered_map. 00797 * @param __n The new number of buckets. 00798 * 00799 * Rehash will occur only if the new number of buckets respect the 00800 * %unordered_map maximum load factor. 00801 */ 00802 void 00803 rehash(size_type __n) 00804 { _M_h.rehash(__n); } 00805 00806 /** 00807 * @brief Prepare the %unordered_map for a specified number of 00808 * elements. 00809 * @param __n Number of elements required. 00810 * 00811 * Same as rehash(ceil(n / max_load_factor())). 00812 */ 00813 void 00814 reserve(size_type __n) 00815 { _M_h.reserve(__n); } 00816 00817 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1, 00818 typename _Alloc1> 00819 friend bool 00820 operator==(const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&, 00821 const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&); 00822 }; 00823 00824 /** 00825 * @brief A standard container composed of equivalent keys 00826 * (possibly containing multiple of each key value) that associates 00827 * values of another type with the keys. 00828 * 00829 * @ingroup unordered_associative_containers 00830 * 00831 * @tparam _Key Type of key objects. 00832 * @tparam _Tp Type of mapped objects. 00833 * @tparam _Hash Hashing function object type, defaults to hash<_Value>. 00834 * @tparam _Pred Predicate function object type, defaults 00835 * to equal_to<_Value>. 00836 * @tparam _Alloc Allocator type, defaults to 00837 * std::allocator<std::pair<const _Key, _Tp>>. 00838 * 00839 * Meets the requirements of a <a href="tables.html#65">container</a>, and 00840 * <a href="tables.html#xx">unordered associative container</a> 00841 * 00842 * The resulting value type of the container is std::pair<const _Key, _Tp>. 00843 * 00844 * Base is _Hashtable, dispatched at compile time via template 00845 * alias __ummap_hashtable. 00846 */ 00847 template<class _Key, class _Tp, 00848 class _Hash = hash<_Key>, 00849 class _Pred = std::equal_to<_Key>, 00850 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > > 00851 class unordered_multimap 00852 { 00853 typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable; 00854 _Hashtable _M_h; 00855 00856 public: 00857 // typedefs: 00858 //@{ 00859 /// Public typedefs. 00860 typedef typename _Hashtable::key_type key_type; 00861 typedef typename _Hashtable::value_type value_type; 00862 typedef typename _Hashtable::mapped_type mapped_type; 00863 typedef typename _Hashtable::hasher hasher; 00864 typedef typename _Hashtable::key_equal key_equal; 00865 typedef typename _Hashtable::allocator_type allocator_type; 00866 //@} 00867 00868 //@{ 00869 /// Iterator-related typedefs. 00870 typedef typename _Hashtable::pointer pointer; 00871 typedef typename _Hashtable::const_pointer const_pointer; 00872 typedef typename _Hashtable::reference reference; 00873 typedef typename _Hashtable::const_reference const_reference; 00874 typedef typename _Hashtable::iterator iterator; 00875 typedef typename _Hashtable::const_iterator const_iterator; 00876 typedef typename _Hashtable::local_iterator local_iterator; 00877 typedef typename _Hashtable::const_local_iterator const_local_iterator; 00878 typedef typename _Hashtable::size_type size_type; 00879 typedef typename _Hashtable::difference_type difference_type; 00880 //@} 00881 00882 //construct/destroy/copy 00883 00884 /// Default constructor. 00885 unordered_multimap() = default; 00886 00887 /** 00888 * @brief Default constructor creates no elements. 00889 * @param __n Mnimal initial number of buckets. 00890 * @param __hf A hash functor. 00891 * @param __eql A key equality functor. 00892 * @param __a An allocator object. 00893 */ 00894 explicit 00895 unordered_multimap(size_type __n, 00896 const hasher& __hf = hasher(), 00897 const key_equal& __eql = key_equal(), 00898 const allocator_type& __a = allocator_type()) 00899 : _M_h(__n, __hf, __eql, __a) 00900 { } 00901 00902 /** 00903 * @brief Builds an %unordered_multimap from a range. 00904 * @param __first An input iterator. 00905 * @param __last An input iterator. 00906 * @param __n Minimal initial number of buckets. 00907 * @param __hf A hash functor. 00908 * @param __eql A key equality functor. 00909 * @param __a An allocator object. 00910 * 00911 * Create an %unordered_multimap consisting of copies of the elements 00912 * from [__first,__last). This is linear in N (where N is 00913 * distance(__first,__last)). 00914 */ 00915 template<typename _InputIterator> 00916 unordered_multimap(_InputIterator __first, _InputIterator __last, 00917 size_type __n = 0, 00918 const hasher& __hf = hasher(), 00919 const key_equal& __eql = key_equal(), 00920 const allocator_type& __a = allocator_type()) 00921 : _M_h(__first, __last, __n, __hf, __eql, __a) 00922 { } 00923 00924 /// Copy constructor. 00925 unordered_multimap(const unordered_multimap&) = default; 00926 00927 /// Move constructor. 00928 unordered_multimap(unordered_multimap&&) = default; 00929 00930 /** 00931 * @brief Creates an %unordered_multimap with no elements. 00932 * @param __a An allocator object. 00933 */ 00934 explicit 00935 unordered_multimap(const allocator_type& __a) 00936 : _M_h(__a) 00937 { } 00938 00939 /* 00940 * @brief Copy constructor with allocator argument. 00941 * @param __uset Input %unordered_multimap to copy. 00942 * @param __a An allocator object. 00943 */ 00944 unordered_multimap(const unordered_multimap& __ummap, 00945 const allocator_type& __a) 00946 : _M_h(__ummap._M_h, __a) 00947 { } 00948 00949 /* 00950 * @brief Move constructor with allocator argument. 00951 * @param __uset Input %unordered_multimap to move. 00952 * @param __a An allocator object. 00953 */ 00954 unordered_multimap(unordered_multimap&& __ummap, 00955 const allocator_type& __a) 00956 : _M_h(std::move(__ummap._M_h), __a) 00957 { } 00958 00959 /** 00960 * @brief Builds an %unordered_multimap from an initializer_list. 00961 * @param __l An initializer_list. 00962 * @param __n Minimal initial number of buckets. 00963 * @param __hf A hash functor. 00964 * @param __eql A key equality functor. 00965 * @param __a An allocator object. 00966 * 00967 * Create an %unordered_multimap consisting of copies of the elements in 00968 * the list. This is linear in N (where N is @a __l.size()). 00969 */ 00970 unordered_multimap(initializer_list<value_type> __l, 00971 size_type __n = 0, 00972 const hasher& __hf = hasher(), 00973 const key_equal& __eql = key_equal(), 00974 const allocator_type& __a = allocator_type()) 00975 : _M_h(__l, __n, __hf, __eql, __a) 00976 { } 00977 00978 unordered_multimap(size_type __n, const allocator_type& __a) 00979 : unordered_multimap(__n, hasher(), key_equal(), __a) 00980 { } 00981 00982 unordered_multimap(size_type __n, const hasher& __hf, 00983 const allocator_type& __a) 00984 : unordered_multimap(__n, __hf, key_equal(), __a) 00985 { } 00986 00987 template<typename _InputIterator> 00988 unordered_multimap(_InputIterator __first, _InputIterator __last, 00989 size_type __n, 00990 const allocator_type& __a) 00991 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a) 00992 { } 00993 00994 template<typename _InputIterator> 00995 unordered_multimap(_InputIterator __first, _InputIterator __last, 00996 size_type __n, const hasher& __hf, 00997 const allocator_type& __a) 00998 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a) 00999 { } 01000 01001 unordered_multimap(initializer_list<value_type> __l, 01002 size_type __n, 01003 const allocator_type& __a) 01004 : unordered_multimap(__l, __n, hasher(), key_equal(), __a) 01005 { } 01006 01007 unordered_multimap(initializer_list<value_type> __l, 01008 size_type __n, const hasher& __hf, 01009 const allocator_type& __a) 01010 : unordered_multimap(__l, __n, __hf, key_equal(), __a) 01011 { } 01012 01013 /// Copy assignment operator. 01014 unordered_multimap& 01015 operator=(const unordered_multimap&) = default; 01016 01017 /// Move assignment operator. 01018 unordered_multimap& 01019 operator=(unordered_multimap&&) = default; 01020 01021 /** 01022 * @brief %Unordered_multimap list assignment operator. 01023 * @param __l An initializer_list. 01024 * 01025 * This function fills an %unordered_multimap with copies of the elements 01026 * in the initializer list @a __l. 01027 * 01028 * Note that the assignment completely changes the %unordered_multimap 01029 * and that the resulting %unordered_multimap's size is the same as the 01030 * number of elements assigned. Old data may be lost. 01031 */ 01032 unordered_multimap& 01033 operator=(initializer_list<value_type> __l) 01034 { 01035 _M_h = __l; 01036 return *this; 01037 } 01038 01039 /// Returns the allocator object with which the %unordered_multimap was 01040 /// constructed. 01041 allocator_type 01042 get_allocator() const noexcept 01043 { return _M_h.get_allocator(); } 01044 01045 // size and capacity: 01046 01047 /// Returns true if the %unordered_multimap is empty. 01048 bool 01049 empty() const noexcept 01050 { return _M_h.empty(); } 01051 01052 /// Returns the size of the %unordered_multimap. 01053 size_type 01054 size() const noexcept 01055 { return _M_h.size(); } 01056 01057 /// Returns the maximum size of the %unordered_multimap. 01058 size_type 01059 max_size() const noexcept 01060 { return _M_h.max_size(); } 01061 01062 // iterators. 01063 01064 /** 01065 * Returns a read/write iterator that points to the first element in the 01066 * %unordered_multimap. 01067 */ 01068 iterator 01069 begin() noexcept 01070 { return _M_h.begin(); } 01071 01072 //@{ 01073 /** 01074 * Returns a read-only (constant) iterator that points to the first 01075 * element in the %unordered_multimap. 01076 */ 01077 const_iterator 01078 begin() const noexcept 01079 { return _M_h.begin(); } 01080 01081 const_iterator 01082 cbegin() const noexcept 01083 { return _M_h.begin(); } 01084 //@} 01085 01086 /** 01087 * Returns a read/write iterator that points one past the last element in 01088 * the %unordered_multimap. 01089 */ 01090 iterator 01091 end() noexcept 01092 { return _M_h.end(); } 01093 01094 //@{ 01095 /** 01096 * Returns a read-only (constant) iterator that points one past the last 01097 * element in the %unordered_multimap. 01098 */ 01099 const_iterator 01100 end() const noexcept 01101 { return _M_h.end(); } 01102 01103 const_iterator 01104 cend() const noexcept 01105 { return _M_h.end(); } 01106 //@} 01107 01108 // modifiers. 01109 01110 /** 01111 * @brief Attempts to build and insert a std::pair into the 01112 * %unordered_multimap. 01113 * 01114 * @param __args Arguments used to generate a new pair instance (see 01115 * std::piecewise_contruct for passing arguments to each 01116 * part of the pair constructor). 01117 * 01118 * @return An iterator that points to the inserted pair. 01119 * 01120 * This function attempts to build and insert a (key, value) %pair into 01121 * the %unordered_multimap. 01122 * 01123 * Insertion requires amortized constant time. 01124 */ 01125 template<typename... _Args> 01126 iterator 01127 emplace(_Args&&... __args) 01128 { return _M_h.emplace(std::forward<_Args>(__args)...); } 01129 01130 /** 01131 * @brief Attempts to build and insert a std::pair into the 01132 * %unordered_multimap. 01133 * 01134 * @param __pos An iterator that serves as a hint as to where the pair 01135 * should be inserted. 01136 * @param __args Arguments used to generate a new pair instance (see 01137 * std::piecewise_contruct for passing arguments to each 01138 * part of the pair constructor). 01139 * @return An iterator that points to the element with key of the 01140 * std::pair built from @a __args. 01141 * 01142 * Note that the first parameter is only a hint and can potentially 01143 * improve the performance of the insertion process. A bad hint would 01144 * cause no gains in efficiency. 01145 * 01146 * See 01147 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 01148 * for more on @a hinting. 01149 * 01150 * Insertion requires amortized constant time. 01151 */ 01152 template<typename... _Args> 01153 iterator 01154 emplace_hint(const_iterator __pos, _Args&&... __args) 01155 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); } 01156 01157 //@{ 01158 /** 01159 * @brief Inserts a std::pair into the %unordered_multimap. 01160 * @param __x Pair to be inserted (see std::make_pair for easy 01161 * creation of pairs). 01162 * 01163 * @return An iterator that points to the inserted pair. 01164 * 01165 * Insertion requires amortized constant time. 01166 */ 01167 iterator 01168 insert(const value_type& __x) 01169 { return _M_h.insert(__x); } 01170 01171 template<typename _Pair, typename = typename 01172 std::enable_if<std::is_constructible<value_type, 01173 _Pair&&>::value>::type> 01174 iterator 01175 insert(_Pair&& __x) 01176 { return _M_h.insert(std::forward<_Pair>(__x)); } 01177 //@} 01178 01179 //@{ 01180 /** 01181 * @brief Inserts a std::pair into the %unordered_multimap. 01182 * @param __hint An iterator that serves as a hint as to where the 01183 * pair should be inserted. 01184 * @param __x Pair to be inserted (see std::make_pair for easy creation 01185 * of pairs). 01186 * @return An iterator that points to the element with key of 01187 * @a __x (may or may not be the %pair passed in). 01188 * 01189 * Note that the first parameter is only a hint and can potentially 01190 * improve the performance of the insertion process. A bad hint would 01191 * cause no gains in efficiency. 01192 * 01193 * See 01194 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 01195 * for more on @a hinting. 01196 * 01197 * Insertion requires amortized constant time. 01198 */ 01199 iterator 01200 insert(const_iterator __hint, const value_type& __x) 01201 { return _M_h.insert(__hint, __x); } 01202 01203 template<typename _Pair, typename = typename 01204 std::enable_if<std::is_constructible<value_type, 01205 _Pair&&>::value>::type> 01206 iterator 01207 insert(const_iterator __hint, _Pair&& __x) 01208 { return _M_h.insert(__hint, std::forward<_Pair>(__x)); } 01209 //@} 01210 01211 /** 01212 * @brief A template function that attempts to insert a range of 01213 * elements. 01214 * @param __first Iterator pointing to the start of the range to be 01215 * inserted. 01216 * @param __last Iterator pointing to the end of the range. 01217 * 01218 * Complexity similar to that of the range constructor. 01219 */ 01220 template<typename _InputIterator> 01221 void 01222 insert(_InputIterator __first, _InputIterator __last) 01223 { _M_h.insert(__first, __last); } 01224 01225 /** 01226 * @brief Attempts to insert a list of elements into the 01227 * %unordered_multimap. 01228 * @param __l A std::initializer_list<value_type> of elements 01229 * to be inserted. 01230 * 01231 * Complexity similar to that of the range constructor. 01232 */ 01233 void 01234 insert(initializer_list<value_type> __l) 01235 { _M_h.insert(__l); } 01236 01237 //@{ 01238 /** 01239 * @brief Erases an element from an %unordered_multimap. 01240 * @param __position An iterator pointing to the element to be erased. 01241 * @return An iterator pointing to the element immediately following 01242 * @a __position prior to the element being erased. If no such 01243 * element exists, end() is returned. 01244 * 01245 * This function erases an element, pointed to by the given iterator, 01246 * from an %unordered_multimap. 01247 * Note that this function only erases the element, and that if the 01248 * element is itself a pointer, the pointed-to memory is not touched in 01249 * any way. Managing the pointer is the user's responsibility. 01250 */ 01251 iterator 01252 erase(const_iterator __position) 01253 { return _M_h.erase(__position); } 01254 01255 // LWG 2059. 01256 iterator 01257 erase(iterator __position) 01258 { return _M_h.erase(__position); } 01259 //@} 01260 01261 /** 01262 * @brief Erases elements according to the provided key. 01263 * @param __x Key of elements to be erased. 01264 * @return The number of elements erased. 01265 * 01266 * This function erases all the elements located by the given key from 01267 * an %unordered_multimap. 01268 * Note that this function only erases the element, and that if the 01269 * element is itself a pointer, the pointed-to memory is not touched in 01270 * any way. Managing the pointer is the user's responsibility. 01271 */ 01272 size_type 01273 erase(const key_type& __x) 01274 { return _M_h.erase(__x); } 01275 01276 /** 01277 * @brief Erases a [__first,__last) range of elements from an 01278 * %unordered_multimap. 01279 * @param __first Iterator pointing to the start of the range to be 01280 * erased. 01281 * @param __last Iterator pointing to the end of the range to 01282 * be erased. 01283 * @return The iterator @a __last. 01284 * 01285 * This function erases a sequence of elements from an 01286 * %unordered_multimap. 01287 * Note that this function only erases the elements, and that if 01288 * the element is itself a pointer, the pointed-to memory is not touched 01289 * in any way. Managing the pointer is the user's responsibility. 01290 */ 01291 iterator 01292 erase(const_iterator __first, const_iterator __last) 01293 { return _M_h.erase(__first, __last); } 01294 01295 /** 01296 * Erases all elements in an %unordered_multimap. 01297 * Note that this function only erases the elements, and that if the 01298 * elements themselves are pointers, the pointed-to memory is not touched 01299 * in any way. Managing the pointer is the user's responsibility. 01300 */ 01301 void 01302 clear() noexcept 01303 { _M_h.clear(); } 01304 01305 /** 01306 * @brief Swaps data with another %unordered_multimap. 01307 * @param __x An %unordered_multimap of the same element and allocator 01308 * types. 01309 * 01310 * This exchanges the elements between two %unordered_multimap in 01311 * constant time. 01312 * Note that the global std::swap() function is specialized such that 01313 * std::swap(m1,m2) will feed to this function. 01314 */ 01315 void 01316 swap(unordered_multimap& __x) 01317 noexcept( noexcept(_M_h.swap(__x._M_h)) ) 01318 { _M_h.swap(__x._M_h); } 01319 01320 // observers. 01321 01322 /// Returns the hash functor object with which the %unordered_multimap 01323 /// was constructed. 01324 hasher 01325 hash_function() const 01326 { return _M_h.hash_function(); } 01327 01328 /// Returns the key comparison object with which the %unordered_multimap 01329 /// was constructed. 01330 key_equal 01331 key_eq() const 01332 { return _M_h.key_eq(); } 01333 01334 // lookup. 01335 01336 //@{ 01337 /** 01338 * @brief Tries to locate an element in an %unordered_multimap. 01339 * @param __x Key to be located. 01340 * @return Iterator pointing to sought-after element, or end() if not 01341 * found. 01342 * 01343 * This function takes a key and tries to locate the element with which 01344 * the key matches. If successful the function returns an iterator 01345 * pointing to the sought after element. If unsuccessful it returns the 01346 * past-the-end ( @c end() ) iterator. 01347 */ 01348 iterator 01349 find(const key_type& __x) 01350 { return _M_h.find(__x); } 01351 01352 const_iterator 01353 find(const key_type& __x) const 01354 { return _M_h.find(__x); } 01355 //@} 01356 01357 /** 01358 * @brief Finds the number of elements. 01359 * @param __x Key to count. 01360 * @return Number of elements with specified key. 01361 */ 01362 size_type 01363 count(const key_type& __x) const 01364 { return _M_h.count(__x); } 01365 01366 //@{ 01367 /** 01368 * @brief Finds a subsequence matching given key. 01369 * @param __x Key to be located. 01370 * @return Pair of iterators that possibly points to the subsequence 01371 * matching given key. 01372 */ 01373 std::pair<iterator, iterator> 01374 equal_range(const key_type& __x) 01375 { return _M_h.equal_range(__x); } 01376 01377 std::pair<const_iterator, const_iterator> 01378 equal_range(const key_type& __x) const 01379 { return _M_h.equal_range(__x); } 01380 //@} 01381 01382 // bucket interface. 01383 01384 /// Returns the number of buckets of the %unordered_multimap. 01385 size_type 01386 bucket_count() const noexcept 01387 { return _M_h.bucket_count(); } 01388 01389 /// Returns the maximum number of buckets of the %unordered_multimap. 01390 size_type 01391 max_bucket_count() const noexcept 01392 { return _M_h.max_bucket_count(); } 01393 01394 /* 01395 * @brief Returns the number of elements in a given bucket. 01396 * @param __n A bucket index. 01397 * @return The number of elements in the bucket. 01398 */ 01399 size_type 01400 bucket_size(size_type __n) const 01401 { return _M_h.bucket_size(__n); } 01402 01403 /* 01404 * @brief Returns the bucket index of a given element. 01405 * @param __key A key instance. 01406 * @return The key bucket index. 01407 */ 01408 size_type 01409 bucket(const key_type& __key) const 01410 { return _M_h.bucket(__key); } 01411 01412 /** 01413 * @brief Returns a read/write iterator pointing to the first bucket 01414 * element. 01415 * @param __n The bucket index. 01416 * @return A read/write local iterator. 01417 */ 01418 local_iterator 01419 begin(size_type __n) 01420 { return _M_h.begin(__n); } 01421 01422 //@{ 01423 /** 01424 * @brief Returns a read-only (constant) iterator pointing to the first 01425 * bucket element. 01426 * @param __n The bucket index. 01427 * @return A read-only local iterator. 01428 */ 01429 const_local_iterator 01430 begin(size_type __n) const 01431 { return _M_h.begin(__n); } 01432 01433 const_local_iterator 01434 cbegin(size_type __n) const 01435 { return _M_h.cbegin(__n); } 01436 //@} 01437 01438 /** 01439 * @brief Returns a read/write iterator pointing to one past the last 01440 * bucket elements. 01441 * @param __n The bucket index. 01442 * @return A read/write local iterator. 01443 */ 01444 local_iterator 01445 end(size_type __n) 01446 { return _M_h.end(__n); } 01447 01448 //@{ 01449 /** 01450 * @brief Returns a read-only (constant) iterator pointing to one past 01451 * the last bucket elements. 01452 * @param __n The bucket index. 01453 * @return A read-only local iterator. 01454 */ 01455 const_local_iterator 01456 end(size_type __n) const 01457 { return _M_h.end(__n); } 01458 01459 const_local_iterator 01460 cend(size_type __n) const 01461 { return _M_h.cend(__n); } 01462 //@} 01463 01464 // hash policy. 01465 01466 /// Returns the average number of elements per bucket. 01467 float 01468 load_factor() const noexcept 01469 { return _M_h.load_factor(); } 01470 01471 /// Returns a positive number that the %unordered_multimap tries to keep 01472 /// the load factor less than or equal to. 01473 float 01474 max_load_factor() const noexcept 01475 { return _M_h.max_load_factor(); } 01476 01477 /** 01478 * @brief Change the %unordered_multimap maximum load factor. 01479 * @param __z The new maximum load factor. 01480 */ 01481 void 01482 max_load_factor(float __z) 01483 { _M_h.max_load_factor(__z); } 01484 01485 /** 01486 * @brief May rehash the %unordered_multimap. 01487 * @param __n The new number of buckets. 01488 * 01489 * Rehash will occur only if the new number of buckets respect the 01490 * %unordered_multimap maximum load factor. 01491 */ 01492 void 01493 rehash(size_type __n) 01494 { _M_h.rehash(__n); } 01495 01496 /** 01497 * @brief Prepare the %unordered_multimap for a specified number of 01498 * elements. 01499 * @param __n Number of elements required. 01500 * 01501 * Same as rehash(ceil(n / max_load_factor())). 01502 */ 01503 void 01504 reserve(size_type __n) 01505 { _M_h.reserve(__n); } 01506 01507 template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1, 01508 typename _Alloc1> 01509 friend bool 01510 operator==(const unordered_multimap<_Key1, _Tp1, 01511 _Hash1, _Pred1, _Alloc1>&, 01512 const unordered_multimap<_Key1, _Tp1, 01513 _Hash1, _Pred1, _Alloc1>&); 01514 }; 01515 01516 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 01517 inline void 01518 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 01519 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 01520 { __x.swap(__y); } 01521 01522 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 01523 inline void 01524 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 01525 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 01526 { __x.swap(__y); } 01527 01528 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 01529 inline bool 01530 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 01531 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 01532 { return __x._M_h._M_equal(__y._M_h); } 01533 01534 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 01535 inline bool 01536 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 01537 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 01538 { return !(__x == __y); } 01539 01540 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 01541 inline bool 01542 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 01543 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 01544 { return __x._M_h._M_equal(__y._M_h); } 01545 01546 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc> 01547 inline bool 01548 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x, 01549 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y) 01550 { return !(__x == __y); } 01551 01552 _GLIBCXX_END_NAMESPACE_CONTAINER 01553 } // namespace std 01554 01555 #endif /* _UNORDERED_MAP_H */