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