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