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