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