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