libstdc++
|
00001 // unordered_set implementation -*- C++ -*- 00002 00003 // Copyright (C) 2010-2018 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 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 //@{ 00671 /** 00672 * @brief Finds a subsequence matching given key. 00673 * @param __x Key to be located. 00674 * @return Pair of iterators that possibly points to the subsequence 00675 * matching given key. 00676 * 00677 * This function probably only makes sense for multisets. 00678 */ 00679 std::pair<iterator, iterator> 00680 equal_range(const key_type& __x) 00681 { return _M_h.equal_range(__x); } 00682 00683 std::pair<const_iterator, const_iterator> 00684 equal_range(const key_type& __x) const 00685 { return _M_h.equal_range(__x); } 00686 //@} 00687 00688 // bucket interface. 00689 00690 /// Returns the number of buckets of the %unordered_set. 00691 size_type 00692 bucket_count() const noexcept 00693 { return _M_h.bucket_count(); } 00694 00695 /// Returns the maximum number of buckets of the %unordered_set. 00696 size_type 00697 max_bucket_count() const noexcept 00698 { return _M_h.max_bucket_count(); } 00699 00700 /* 00701 * @brief Returns the number of elements in a given bucket. 00702 * @param __n A bucket index. 00703 * @return The number of elements in the bucket. 00704 */ 00705 size_type 00706 bucket_size(size_type __n) const 00707 { return _M_h.bucket_size(__n); } 00708 00709 /* 00710 * @brief Returns the bucket index of a given element. 00711 * @param __key A key instance. 00712 * @return The key bucket index. 00713 */ 00714 size_type 00715 bucket(const key_type& __key) const 00716 { return _M_h.bucket(__key); } 00717 00718 //@{ 00719 /** 00720 * @brief Returns a read-only (constant) iterator pointing to the first 00721 * bucket element. 00722 * @param __n The bucket index. 00723 * @return A read-only local iterator. 00724 */ 00725 local_iterator 00726 begin(size_type __n) 00727 { return _M_h.begin(__n); } 00728 00729 const_local_iterator 00730 begin(size_type __n) const 00731 { return _M_h.begin(__n); } 00732 00733 const_local_iterator 00734 cbegin(size_type __n) const 00735 { return _M_h.cbegin(__n); } 00736 //@} 00737 00738 //@{ 00739 /** 00740 * @brief Returns a read-only (constant) iterator pointing to one past 00741 * the last bucket elements. 00742 * @param __n The bucket index. 00743 * @return A read-only local iterator. 00744 */ 00745 local_iterator 00746 end(size_type __n) 00747 { return _M_h.end(__n); } 00748 00749 const_local_iterator 00750 end(size_type __n) const 00751 { return _M_h.end(__n); } 00752 00753 const_local_iterator 00754 cend(size_type __n) const 00755 { return _M_h.cend(__n); } 00756 //@} 00757 00758 // hash policy. 00759 00760 /// Returns the average number of elements per bucket. 00761 float 00762 load_factor() const noexcept 00763 { return _M_h.load_factor(); } 00764 00765 /// Returns a positive number that the %unordered_set tries to keep the 00766 /// load factor less than or equal to. 00767 float 00768 max_load_factor() const noexcept 00769 { return _M_h.max_load_factor(); } 00770 00771 /** 00772 * @brief Change the %unordered_set maximum load factor. 00773 * @param __z The new maximum load factor. 00774 */ 00775 void 00776 max_load_factor(float __z) 00777 { _M_h.max_load_factor(__z); } 00778 00779 /** 00780 * @brief May rehash the %unordered_set. 00781 * @param __n The new number of buckets. 00782 * 00783 * Rehash will occur only if the new number of buckets respect the 00784 * %unordered_set maximum load factor. 00785 */ 00786 void 00787 rehash(size_type __n) 00788 { _M_h.rehash(__n); } 00789 00790 /** 00791 * @brief Prepare the %unordered_set for a specified number of 00792 * elements. 00793 * @param __n Number of elements required. 00794 * 00795 * Same as rehash(ceil(n / max_load_factor())). 00796 */ 00797 void 00798 reserve(size_type __n) 00799 { _M_h.reserve(__n); } 00800 00801 template<typename _Value1, typename _Hash1, typename _Pred1, 00802 typename _Alloc1> 00803 friend bool 00804 operator==(const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&, 00805 const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&); 00806 }; 00807 00808 #if __cpp_deduction_guides >= 201606 00809 00810 template<typename _InputIterator, 00811 typename _Hash = 00812 hash<typename iterator_traits<_InputIterator>::value_type>, 00813 typename _Pred = 00814 equal_to<typename iterator_traits<_InputIterator>::value_type>, 00815 typename _Allocator = 00816 allocator<typename iterator_traits<_InputIterator>::value_type>, 00817 typename = _RequireInputIter<_InputIterator>, 00818 typename = _RequireAllocator<_Allocator>> 00819 unordered_set(_InputIterator, _InputIterator, 00820 unordered_set<int>::size_type = {}, 00821 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 00822 -> unordered_set<typename iterator_traits<_InputIterator>::value_type, 00823 _Hash, _Pred, _Allocator>; 00824 00825 template<typename _Tp, typename _Hash = hash<_Tp>, 00826 typename _Pred = equal_to<_Tp>, 00827 typename _Allocator = allocator<_Tp>, 00828 typename = _RequireAllocator<_Allocator>> 00829 unordered_set(initializer_list<_Tp>, 00830 unordered_set<int>::size_type = {}, 00831 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) 00832 -> unordered_set<_Tp, _Hash, _Pred, _Allocator>; 00833 00834 template<typename _InputIterator, typename _Allocator, 00835 typename = _RequireInputIter<_InputIterator>, 00836 typename = _RequireAllocator<_Allocator>> 00837 unordered_set(_InputIterator, _InputIterator, 00838 unordered_set<int>::size_type, _Allocator) 00839 -> unordered_set<typename iterator_traits<_InputIterator>::value_type, 00840 hash< 00841 typename iterator_traits<_InputIterator>::value_type>, 00842 equal_to< 00843 typename iterator_traits<_InputIterator>::value_type>, 00844 _Allocator>; 00845 00846 template<typename _InputIterator, typename _Hash, typename _Allocator, 00847 typename = _RequireInputIter<_InputIterator>, 00848 typename = _RequireAllocator<_Allocator>> 00849 unordered_set(_InputIterator, _InputIterator, 00850 unordered_set<int>::size_type, 00851 _Hash, _Allocator) 00852 -> unordered_set<typename iterator_traits<_InputIterator>::value_type, 00853 _Hash, 00854 equal_to< 00855 typename iterator_traits<_InputIterator>::value_type>, 00856 _Allocator>; 00857 00858 template<typename _Tp, typename _Allocator, 00859 typename = _RequireAllocator<_Allocator>> 00860 unordered_set(initializer_list<_Tp>, 00861 unordered_set<int>::size_type, _Allocator) 00862 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 00863 00864 template<typename _Tp, typename _Hash, typename _Allocator, 00865 typename = _RequireAllocator<_Allocator>> 00866 unordered_set(initializer_list<_Tp>, 00867 unordered_set<int>::size_type, _Hash, _Allocator) 00868 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 00869 00870 #endif 00871 00872 /** 00873 * @brief A standard container composed of equivalent keys 00874 * (possibly containing multiple of each key value) in which the 00875 * elements' keys are the elements themselves. 00876 * 00877 * @ingroup unordered_associative_containers 00878 * 00879 * @tparam _Value Type of key objects. 00880 * @tparam _Hash Hashing function object type, defaults to hash<_Value>. 00881 * @tparam _Pred Predicate function object type, defaults 00882 * to equal_to<_Value>. 00883 * @tparam _Alloc Allocator type, defaults to allocator<_Key>. 00884 * 00885 * Meets the requirements of a <a href="tables.html#65">container</a>, and 00886 * <a href="tables.html#xx">unordered associative container</a> 00887 * 00888 * Base is _Hashtable, dispatched at compile time via template 00889 * alias __umset_hashtable. 00890 */ 00891 template<typename _Value, 00892 typename _Hash = hash<_Value>, 00893 typename _Pred = equal_to<_Value>, 00894 typename _Alloc = allocator<_Value>> 00895 class unordered_multiset 00896 { 00897 typedef __umset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable; 00898 _Hashtable _M_h; 00899 00900 public: 00901 // typedefs: 00902 //@{ 00903 /// Public typedefs. 00904 typedef typename _Hashtable::key_type key_type; 00905 typedef typename _Hashtable::value_type value_type; 00906 typedef typename _Hashtable::hasher hasher; 00907 typedef typename _Hashtable::key_equal key_equal; 00908 typedef typename _Hashtable::allocator_type allocator_type; 00909 //@} 00910 00911 //@{ 00912 /// Iterator-related typedefs. 00913 typedef typename _Hashtable::pointer pointer; 00914 typedef typename _Hashtable::const_pointer const_pointer; 00915 typedef typename _Hashtable::reference reference; 00916 typedef typename _Hashtable::const_reference const_reference; 00917 typedef typename _Hashtable::iterator iterator; 00918 typedef typename _Hashtable::const_iterator const_iterator; 00919 typedef typename _Hashtable::local_iterator local_iterator; 00920 typedef typename _Hashtable::const_local_iterator const_local_iterator; 00921 typedef typename _Hashtable::size_type size_type; 00922 typedef typename _Hashtable::difference_type difference_type; 00923 //@} 00924 00925 #if __cplusplus > 201402L 00926 using node_type = typename _Hashtable::node_type; 00927 #endif 00928 00929 // construct/destroy/copy 00930 00931 /// Default constructor. 00932 unordered_multiset() = default; 00933 00934 /** 00935 * @brief Default constructor creates no elements. 00936 * @param __n Minimal initial number of buckets. 00937 * @param __hf A hash functor. 00938 * @param __eql A key equality functor. 00939 * @param __a An allocator object. 00940 */ 00941 explicit 00942 unordered_multiset(size_type __n, 00943 const hasher& __hf = hasher(), 00944 const key_equal& __eql = key_equal(), 00945 const allocator_type& __a = allocator_type()) 00946 : _M_h(__n, __hf, __eql, __a) 00947 { } 00948 00949 /** 00950 * @brief Builds an %unordered_multiset from a range. 00951 * @param __first An input iterator. 00952 * @param __last An input iterator. 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 * Create an %unordered_multiset consisting of copies of the elements 00959 * from [__first,__last). This is linear in N (where N is 00960 * distance(__first,__last)). 00961 */ 00962 template<typename _InputIterator> 00963 unordered_multiset(_InputIterator __first, _InputIterator __last, 00964 size_type __n = 0, 00965 const hasher& __hf = hasher(), 00966 const key_equal& __eql = key_equal(), 00967 const allocator_type& __a = allocator_type()) 00968 : _M_h(__first, __last, __n, __hf, __eql, __a) 00969 { } 00970 00971 /// Copy constructor. 00972 unordered_multiset(const unordered_multiset&) = default; 00973 00974 /// Move constructor. 00975 unordered_multiset(unordered_multiset&&) = default; 00976 00977 /** 00978 * @brief Builds an %unordered_multiset from an initializer_list. 00979 * @param __l An initializer_list. 00980 * @param __n Minimal initial number of buckets. 00981 * @param __hf A hash functor. 00982 * @param __eql A key equality functor. 00983 * @param __a An allocator object. 00984 * 00985 * Create an %unordered_multiset consisting of copies of the elements in 00986 * the list. This is linear in N (where N is @a __l.size()). 00987 */ 00988 unordered_multiset(initializer_list<value_type> __l, 00989 size_type __n = 0, 00990 const hasher& __hf = hasher(), 00991 const key_equal& __eql = key_equal(), 00992 const allocator_type& __a = allocator_type()) 00993 : _M_h(__l, __n, __hf, __eql, __a) 00994 { } 00995 00996 /// Copy assignment operator. 00997 unordered_multiset& 00998 operator=(const unordered_multiset&) = default; 00999 01000 /// Move assignment operator. 01001 unordered_multiset& 01002 operator=(unordered_multiset&&) = default; 01003 01004 /** 01005 * @brief Creates an %unordered_multiset with no elements. 01006 * @param __a An allocator object. 01007 */ 01008 explicit 01009 unordered_multiset(const allocator_type& __a) 01010 : _M_h(__a) 01011 { } 01012 01013 /* 01014 * @brief Copy constructor with allocator argument. 01015 * @param __uset Input %unordered_multiset to copy. 01016 * @param __a An allocator object. 01017 */ 01018 unordered_multiset(const unordered_multiset& __umset, 01019 const allocator_type& __a) 01020 : _M_h(__umset._M_h, __a) 01021 { } 01022 01023 /* 01024 * @brief Move constructor with allocator argument. 01025 * @param __umset Input %unordered_multiset to move. 01026 * @param __a An allocator object. 01027 */ 01028 unordered_multiset(unordered_multiset&& __umset, 01029 const allocator_type& __a) 01030 : _M_h(std::move(__umset._M_h), __a) 01031 { } 01032 01033 unordered_multiset(size_type __n, const allocator_type& __a) 01034 : unordered_multiset(__n, hasher(), key_equal(), __a) 01035 { } 01036 01037 unordered_multiset(size_type __n, const hasher& __hf, 01038 const allocator_type& __a) 01039 : unordered_multiset(__n, __hf, key_equal(), __a) 01040 { } 01041 01042 template<typename _InputIterator> 01043 unordered_multiset(_InputIterator __first, _InputIterator __last, 01044 size_type __n, 01045 const allocator_type& __a) 01046 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) 01047 { } 01048 01049 template<typename _InputIterator> 01050 unordered_multiset(_InputIterator __first, _InputIterator __last, 01051 size_type __n, const hasher& __hf, 01052 const allocator_type& __a) 01053 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) 01054 { } 01055 01056 unordered_multiset(initializer_list<value_type> __l, 01057 size_type __n, 01058 const allocator_type& __a) 01059 : unordered_multiset(__l, __n, hasher(), key_equal(), __a) 01060 { } 01061 01062 unordered_multiset(initializer_list<value_type> __l, 01063 size_type __n, const hasher& __hf, 01064 const allocator_type& __a) 01065 : unordered_multiset(__l, __n, __hf, key_equal(), __a) 01066 { } 01067 01068 /** 01069 * @brief %Unordered_multiset list assignment operator. 01070 * @param __l An initializer_list. 01071 * 01072 * This function fills an %unordered_multiset with copies of the elements 01073 * in the initializer list @a __l. 01074 * 01075 * Note that the assignment completely changes the %unordered_multiset 01076 * and that the resulting %unordered_multiset's size is the same as the 01077 * number of elements assigned. 01078 */ 01079 unordered_multiset& 01080 operator=(initializer_list<value_type> __l) 01081 { 01082 _M_h = __l; 01083 return *this; 01084 } 01085 01086 /// Returns the allocator object used by the %unordered_multiset. 01087 allocator_type 01088 get_allocator() const noexcept 01089 { return _M_h.get_allocator(); } 01090 01091 // size and capacity: 01092 01093 /// Returns true if the %unordered_multiset is empty. 01094 bool 01095 empty() const noexcept 01096 { return _M_h.empty(); } 01097 01098 /// Returns the size of the %unordered_multiset. 01099 size_type 01100 size() const noexcept 01101 { return _M_h.size(); } 01102 01103 /// Returns the maximum size of the %unordered_multiset. 01104 size_type 01105 max_size() const noexcept 01106 { return _M_h.max_size(); } 01107 01108 // iterators. 01109 01110 //@{ 01111 /** 01112 * Returns a read-only (constant) iterator that points to the first 01113 * element in the %unordered_multiset. 01114 */ 01115 iterator 01116 begin() noexcept 01117 { return _M_h.begin(); } 01118 01119 const_iterator 01120 begin() const noexcept 01121 { return _M_h.begin(); } 01122 //@} 01123 01124 //@{ 01125 /** 01126 * Returns a read-only (constant) iterator that points one past the last 01127 * element in the %unordered_multiset. 01128 */ 01129 iterator 01130 end() noexcept 01131 { return _M_h.end(); } 01132 01133 const_iterator 01134 end() const noexcept 01135 { return _M_h.end(); } 01136 //@} 01137 01138 /** 01139 * Returns a read-only (constant) iterator that points to the first 01140 * element in the %unordered_multiset. 01141 */ 01142 const_iterator 01143 cbegin() const noexcept 01144 { return _M_h.begin(); } 01145 01146 /** 01147 * Returns a read-only (constant) iterator that points one past the last 01148 * element in the %unordered_multiset. 01149 */ 01150 const_iterator 01151 cend() const noexcept 01152 { return _M_h.end(); } 01153 01154 // modifiers. 01155 01156 /** 01157 * @brief Builds and insert an element into the %unordered_multiset. 01158 * @param __args Arguments used to generate an element. 01159 * @return An iterator that points to the inserted element. 01160 * 01161 * Insertion requires amortized constant time. 01162 */ 01163 template<typename... _Args> 01164 iterator 01165 emplace(_Args&&... __args) 01166 { return _M_h.emplace(std::forward<_Args>(__args)...); } 01167 01168 /** 01169 * @brief Inserts an element into the %unordered_multiset. 01170 * @param __pos An iterator that serves as a hint as to where the 01171 * element should be inserted. 01172 * @param __args Arguments used to generate the element to be 01173 * inserted. 01174 * @return An iterator that points to the inserted element. 01175 * 01176 * Note that the first parameter is only a hint and can potentially 01177 * improve the performance of the insertion process. A bad hint would 01178 * cause no gains in efficiency. 01179 * 01180 * For more on @a hinting, see: 01181 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 01182 * 01183 * Insertion requires amortized constant time. 01184 */ 01185 template<typename... _Args> 01186 iterator 01187 emplace_hint(const_iterator __pos, _Args&&... __args) 01188 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); } 01189 01190 //@{ 01191 /** 01192 * @brief Inserts an element into the %unordered_multiset. 01193 * @param __x Element to be inserted. 01194 * @return An iterator that points to the inserted element. 01195 * 01196 * Insertion requires amortized constant time. 01197 */ 01198 iterator 01199 insert(const value_type& __x) 01200 { return _M_h.insert(__x); } 01201 01202 iterator 01203 insert(value_type&& __x) 01204 { return _M_h.insert(std::move(__x)); } 01205 //@} 01206 01207 //@{ 01208 /** 01209 * @brief Inserts an element into the %unordered_multiset. 01210 * @param __hint An iterator that serves as a hint as to where the 01211 * element should be inserted. 01212 * @param __x Element to be inserted. 01213 * @return An iterator that points to the inserted element. 01214 * 01215 * Note that the first parameter is only a hint and can potentially 01216 * improve the performance of the insertion process. A bad hint would 01217 * cause no gains in efficiency. 01218 * 01219 * For more on @a hinting, see: 01220 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints 01221 * 01222 * Insertion requires amortized constant. 01223 */ 01224 iterator 01225 insert(const_iterator __hint, const value_type& __x) 01226 { return _M_h.insert(__hint, __x); } 01227 01228 iterator 01229 insert(const_iterator __hint, value_type&& __x) 01230 { return _M_h.insert(__hint, std::move(__x)); } 01231 //@} 01232 01233 /** 01234 * @brief A template function that inserts a range of elements. 01235 * @param __first Iterator pointing to the start of the range to be 01236 * inserted. 01237 * @param __last Iterator pointing to the end of the range. 01238 * 01239 * Complexity similar to that of the range constructor. 01240 */ 01241 template<typename _InputIterator> 01242 void 01243 insert(_InputIterator __first, _InputIterator __last) 01244 { _M_h.insert(__first, __last); } 01245 01246 /** 01247 * @brief Inserts a list of elements into the %unordered_multiset. 01248 * @param __l A std::initializer_list<value_type> of elements to be 01249 * inserted. 01250 * 01251 * Complexity similar to that of the range constructor. 01252 */ 01253 void 01254 insert(initializer_list<value_type> __l) 01255 { _M_h.insert(__l); } 01256 01257 #if __cplusplus > 201402L 01258 /// Extract a node. 01259 node_type 01260 extract(const_iterator __pos) 01261 { 01262 __glibcxx_assert(__pos != end()); 01263 return _M_h.extract(__pos); 01264 } 01265 01266 /// Extract a node. 01267 node_type 01268 extract(const key_type& __key) 01269 { return _M_h.extract(__key); } 01270 01271 /// Re-insert an extracted node. 01272 iterator 01273 insert(node_type&& __nh) 01274 { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); } 01275 01276 /// Re-insert an extracted node. 01277 iterator 01278 insert(const_iterator __hint, node_type&& __nh) 01279 { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); } 01280 #endif // C++17 01281 01282 //@{ 01283 /** 01284 * @brief Erases an element from an %unordered_multiset. 01285 * @param __position An iterator pointing to the element to be erased. 01286 * @return An iterator pointing to the element immediately following 01287 * @a __position prior to the element being erased. If no such 01288 * element exists, end() is returned. 01289 * 01290 * This function erases an element, pointed to by the given iterator, 01291 * from an %unordered_multiset. 01292 * 01293 * Note that this function only erases the element, and that if the 01294 * element is itself a pointer, the pointed-to memory is not touched in 01295 * any way. Managing the pointer is the user's responsibility. 01296 */ 01297 iterator 01298 erase(const_iterator __position) 01299 { return _M_h.erase(__position); } 01300 01301 // LWG 2059. 01302 iterator 01303 erase(iterator __position) 01304 { return _M_h.erase(__position); } 01305 //@} 01306 01307 01308 /** 01309 * @brief Erases elements according to the provided key. 01310 * @param __x Key of element to be erased. 01311 * @return The number of elements erased. 01312 * 01313 * This function erases all the elements located by the given key from 01314 * an %unordered_multiset. 01315 * 01316 * Note that this function only erases the element, and that if the 01317 * element is itself a pointer, the pointed-to memory is not touched in 01318 * any way. Managing the pointer is the user's responsibility. 01319 */ 01320 size_type 01321 erase(const key_type& __x) 01322 { return _M_h.erase(__x); } 01323 01324 /** 01325 * @brief Erases a [__first,__last) range of elements from an 01326 * %unordered_multiset. 01327 * @param __first Iterator pointing to the start of the range to be 01328 * erased. 01329 * @param __last Iterator pointing to the end of the range to 01330 * be erased. 01331 * @return The iterator @a __last. 01332 * 01333 * This function erases a sequence of elements from an 01334 * %unordered_multiset. 01335 * 01336 * Note that this function only erases the element, and that if 01337 * the element is itself a pointer, the pointed-to memory is not touched 01338 * in any way. Managing the pointer is the user's responsibility. 01339 */ 01340 iterator 01341 erase(const_iterator __first, const_iterator __last) 01342 { return _M_h.erase(__first, __last); } 01343 01344 /** 01345 * Erases all elements in an %unordered_multiset. 01346 * 01347 * Note that this function only erases the elements, and that if the 01348 * elements themselves are pointers, the pointed-to memory is not touched 01349 * in any way. Managing the pointer is the user's responsibility. 01350 */ 01351 void 01352 clear() noexcept 01353 { _M_h.clear(); } 01354 01355 /** 01356 * @brief Swaps data with another %unordered_multiset. 01357 * @param __x An %unordered_multiset of the same element and allocator 01358 * types. 01359 * 01360 * This exchanges the elements between two sets in constant time. 01361 * Note that the global std::swap() function is specialized such that 01362 * std::swap(s1,s2) will feed to this function. 01363 */ 01364 void 01365 swap(unordered_multiset& __x) 01366 noexcept( noexcept(_M_h.swap(__x._M_h)) ) 01367 { _M_h.swap(__x._M_h); } 01368 01369 #if __cplusplus > 201402L 01370 template<typename, typename, typename> 01371 friend class std::_Hash_merge_helper; 01372 01373 template<typename _H2, typename _P2> 01374 void 01375 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source) 01376 { 01377 using _Merge_helper 01378 = _Hash_merge_helper<unordered_multiset, _H2, _P2>; 01379 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); 01380 } 01381 01382 template<typename _H2, typename _P2> 01383 void 01384 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source) 01385 { merge(__source); } 01386 01387 template<typename _H2, typename _P2> 01388 void 01389 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source) 01390 { 01391 using _Merge_helper 01392 = _Hash_merge_helper<unordered_multiset, _H2, _P2>; 01393 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source)); 01394 } 01395 01396 template<typename _H2, typename _P2> 01397 void 01398 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source) 01399 { merge(__source); } 01400 #endif // C++17 01401 01402 // observers. 01403 01404 /// Returns the hash functor object with which the %unordered_multiset 01405 /// was constructed. 01406 hasher 01407 hash_function() const 01408 { return _M_h.hash_function(); } 01409 01410 /// Returns the key comparison object with which the %unordered_multiset 01411 /// was constructed. 01412 key_equal 01413 key_eq() const 01414 { return _M_h.key_eq(); } 01415 01416 // lookup. 01417 01418 //@{ 01419 /** 01420 * @brief Tries to locate an element in an %unordered_multiset. 01421 * @param __x Element to be located. 01422 * @return Iterator pointing to sought-after element, or end() if not 01423 * found. 01424 * 01425 * This function takes a key and tries to locate the element with which 01426 * the key matches. If successful the function returns an iterator 01427 * pointing to the sought after element. If unsuccessful it returns the 01428 * past-the-end ( @c end() ) iterator. 01429 */ 01430 iterator 01431 find(const key_type& __x) 01432 { return _M_h.find(__x); } 01433 01434 const_iterator 01435 find(const key_type& __x) const 01436 { return _M_h.find(__x); } 01437 //@} 01438 01439 /** 01440 * @brief Finds the number of elements. 01441 * @param __x Element to located. 01442 * @return Number of elements with specified key. 01443 */ 01444 size_type 01445 count(const key_type& __x) const 01446 { return _M_h.count(__x); } 01447 01448 //@{ 01449 /** 01450 * @brief Finds a subsequence matching given key. 01451 * @param __x Key to be located. 01452 * @return Pair of iterators that possibly points to the subsequence 01453 * matching given key. 01454 */ 01455 std::pair<iterator, iterator> 01456 equal_range(const key_type& __x) 01457 { return _M_h.equal_range(__x); } 01458 01459 std::pair<const_iterator, const_iterator> 01460 equal_range(const key_type& __x) const 01461 { return _M_h.equal_range(__x); } 01462 //@} 01463 01464 // bucket interface. 01465 01466 /// Returns the number of buckets of the %unordered_multiset. 01467 size_type 01468 bucket_count() const noexcept 01469 { return _M_h.bucket_count(); } 01470 01471 /// Returns the maximum number of buckets of the %unordered_multiset. 01472 size_type 01473 max_bucket_count() const noexcept 01474 { return _M_h.max_bucket_count(); } 01475 01476 /* 01477 * @brief Returns the number of elements in a given bucket. 01478 * @param __n A bucket index. 01479 * @return The number of elements in the bucket. 01480 */ 01481 size_type 01482 bucket_size(size_type __n) const 01483 { return _M_h.bucket_size(__n); } 01484 01485 /* 01486 * @brief Returns the bucket index of a given element. 01487 * @param __key A key instance. 01488 * @return The key bucket index. 01489 */ 01490 size_type 01491 bucket(const key_type& __key) const 01492 { return _M_h.bucket(__key); } 01493 01494 //@{ 01495 /** 01496 * @brief Returns a read-only (constant) iterator pointing to the first 01497 * bucket element. 01498 * @param __n The bucket index. 01499 * @return A read-only local iterator. 01500 */ 01501 local_iterator 01502 begin(size_type __n) 01503 { return _M_h.begin(__n); } 01504 01505 const_local_iterator 01506 begin(size_type __n) const 01507 { return _M_h.begin(__n); } 01508 01509 const_local_iterator 01510 cbegin(size_type __n) const 01511 { return _M_h.cbegin(__n); } 01512 //@} 01513 01514 //@{ 01515 /** 01516 * @brief Returns a read-only (constant) iterator pointing to one past 01517 * the last bucket elements. 01518 * @param __n The bucket index. 01519 * @return A read-only local iterator. 01520 */ 01521 local_iterator 01522 end(size_type __n) 01523 { return _M_h.end(__n); } 01524 01525 const_local_iterator 01526 end(size_type __n) const 01527 { return _M_h.end(__n); } 01528 01529 const_local_iterator 01530 cend(size_type __n) const 01531 { return _M_h.cend(__n); } 01532 //@} 01533 01534 // hash policy. 01535 01536 /// Returns the average number of elements per bucket. 01537 float 01538 load_factor() const noexcept 01539 { return _M_h.load_factor(); } 01540 01541 /// Returns a positive number that the %unordered_multiset tries to keep the 01542 /// load factor less than or equal to. 01543 float 01544 max_load_factor() const noexcept 01545 { return _M_h.max_load_factor(); } 01546 01547 /** 01548 * @brief Change the %unordered_multiset maximum load factor. 01549 * @param __z The new maximum load factor. 01550 */ 01551 void 01552 max_load_factor(float __z) 01553 { _M_h.max_load_factor(__z); } 01554 01555 /** 01556 * @brief May rehash the %unordered_multiset. 01557 * @param __n The new number of buckets. 01558 * 01559 * Rehash will occur only if the new number of buckets respect the 01560 * %unordered_multiset maximum load factor. 01561 */ 01562 void 01563 rehash(size_type __n) 01564 { _M_h.rehash(__n); } 01565 01566 /** 01567 * @brief Prepare the %unordered_multiset for a specified number of 01568 * elements. 01569 * @param __n Number of elements required. 01570 * 01571 * Same as rehash(ceil(n / max_load_factor())). 01572 */ 01573 void 01574 reserve(size_type __n) 01575 { _M_h.reserve(__n); } 01576 01577 template<typename _Value1, typename _Hash1, typename _Pred1, 01578 typename _Alloc1> 01579 friend bool 01580 operator==(const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&, 01581 const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&); 01582 }; 01583 01584 01585 #if __cpp_deduction_guides >= 201606 01586 01587 template<typename _InputIterator, 01588 typename _Hash = 01589 hash<typename iterator_traits<_InputIterator>::value_type>, 01590 typename _Pred = 01591 equal_to<typename iterator_traits<_InputIterator>::value_type>, 01592 typename _Allocator = 01593 allocator<typename iterator_traits<_InputIterator>::value_type>, 01594 typename = _RequireInputIter<_InputIterator>, 01595 typename = _RequireAllocator<_Allocator>> 01596 unordered_multiset(_InputIterator, _InputIterator, 01597 unordered_multiset<int>::size_type = {}, 01598 _Hash = _Hash(), _Pred = _Pred(), 01599 _Allocator = _Allocator()) 01600 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type, 01601 _Hash, _Pred, _Allocator>; 01602 01603 template<typename _Tp, typename _Hash = hash<_Tp>, 01604 typename _Pred = equal_to<_Tp>, 01605 typename _Allocator = allocator<_Tp>, 01606 typename = _RequireAllocator<_Allocator>> 01607 unordered_multiset(initializer_list<_Tp>, 01608 unordered_multiset<int>::size_type = {}, 01609 _Hash = _Hash(), _Pred = _Pred(), 01610 _Allocator = _Allocator()) 01611 -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>; 01612 01613 template<typename _InputIterator, typename _Allocator, 01614 typename = _RequireInputIter<_InputIterator>, 01615 typename = _RequireAllocator<_Allocator>> 01616 unordered_multiset(_InputIterator, _InputIterator, 01617 unordered_multiset<int>::size_type, _Allocator) 01618 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type, 01619 hash<typename 01620 iterator_traits<_InputIterator>::value_type>, 01621 equal_to<typename 01622 iterator_traits<_InputIterator>::value_type>, 01623 _Allocator>; 01624 01625 template<typename _InputIterator, typename _Hash, typename _Allocator, 01626 typename = _RequireInputIter<_InputIterator>, 01627 typename = _RequireAllocator<_Allocator>> 01628 unordered_multiset(_InputIterator, _InputIterator, 01629 unordered_multiset<int>::size_type, 01630 _Hash, _Allocator) 01631 -> unordered_multiset<typename 01632 iterator_traits<_InputIterator>::value_type, 01633 _Hash, 01634 equal_to< 01635 typename 01636 iterator_traits<_InputIterator>::value_type>, 01637 _Allocator>; 01638 01639 template<typename _Tp, typename _Allocator, 01640 typename = _RequireAllocator<_Allocator>> 01641 unordered_multiset(initializer_list<_Tp>, 01642 unordered_multiset<int>::size_type, _Allocator) 01643 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; 01644 01645 template<typename _Tp, typename _Hash, typename _Allocator, 01646 typename = _RequireAllocator<_Allocator>> 01647 unordered_multiset(initializer_list<_Tp>, 01648 unordered_multiset<int>::size_type, _Hash, _Allocator) 01649 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>; 01650 01651 #endif 01652 01653 template<class _Value, class _Hash, class _Pred, class _Alloc> 01654 inline void 01655 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 01656 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 01657 noexcept(noexcept(__x.swap(__y))) 01658 { __x.swap(__y); } 01659 01660 template<class _Value, class _Hash, class _Pred, class _Alloc> 01661 inline void 01662 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 01663 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 01664 noexcept(noexcept(__x.swap(__y))) 01665 { __x.swap(__y); } 01666 01667 template<class _Value, class _Hash, class _Pred, class _Alloc> 01668 inline bool 01669 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 01670 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 01671 { return __x._M_h._M_equal(__y._M_h); } 01672 01673 template<class _Value, class _Hash, class _Pred, class _Alloc> 01674 inline bool 01675 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, 01676 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) 01677 { return !(__x == __y); } 01678 01679 template<class _Value, class _Hash, class _Pred, class _Alloc> 01680 inline bool 01681 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 01682 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 01683 { return __x._M_h._M_equal(__y._M_h); } 01684 01685 template<class _Value, class _Hash, class _Pred, class _Alloc> 01686 inline bool 01687 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 01688 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 01689 { return !(__x == __y); } 01690 01691 _GLIBCXX_END_NAMESPACE_CONTAINER 01692 01693 #if __cplusplus > 201402L 01694 // Allow std::unordered_set access to internals of compatible sets. 01695 template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc, 01696 typename _Hash2, typename _Eq2> 01697 struct _Hash_merge_helper< 01698 _GLIBCXX_STD_C::unordered_set<_Val, _Hash1, _Eq1, _Alloc>, _Hash2, _Eq2> 01699 { 01700 private: 01701 template<typename... _Tp> 01702 using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>; 01703 template<typename... _Tp> 01704 using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>; 01705 01706 friend unordered_set<_Val, _Hash1, _Eq1, _Alloc>; 01707 01708 static auto& 01709 _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set) 01710 { return __set._M_h; } 01711 01712 static auto& 01713 _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set) 01714 { return __set._M_h; } 01715 }; 01716 01717 // Allow std::unordered_multiset access to internals of compatible sets. 01718 template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc, 01719 typename _Hash2, typename _Eq2> 01720 struct _Hash_merge_helper< 01721 _GLIBCXX_STD_C::unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>, 01722 _Hash2, _Eq2> 01723 { 01724 private: 01725 template<typename... _Tp> 01726 using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>; 01727 template<typename... _Tp> 01728 using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>; 01729 01730 friend unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>; 01731 01732 static auto& 01733 _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set) 01734 { return __set._M_h; } 01735 01736 static auto& 01737 _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set) 01738 { return __set._M_h; } 01739 }; 01740 #endif // C++17 01741 01742 _GLIBCXX_END_NAMESPACE_VERSION 01743 } // namespace std 01744 01745 #endif /* _UNORDERED_SET_H */