1 // unordered_set implementation -*- C++ -*-
3 // Copyright (C) 2010-2018 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /** @file bits/unordered_set.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{unordered_set}
30 #ifndef _UNORDERED_SET_H
31 #define _UNORDERED_SET_H
33 namespace std
_GLIBCXX_VISIBILITY(default)
35 _GLIBCXX_BEGIN_NAMESPACE_VERSION
36 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
38 /// Base types for unordered_set.
40 using __uset_traits
= __detail::_Hashtable_traits
<_Cache
, true, true>;
42 template<typename _Value
,
43 typename _Hash
= hash
<_Value
>,
44 typename _Pred
= std::equal_to
<_Value
>,
45 typename _Alloc
= std::allocator
<_Value
>,
46 typename _Tr
= __uset_traits
<__cache_default
<_Value
, _Hash
>::value
>>
47 using __uset_hashtable
= _Hashtable
<_Value
, _Value
, _Alloc
,
48 __detail::_Identity
, _Pred
, _Hash
,
49 __detail::_Mod_range_hashing
,
50 __detail::_Default_ranged_hash
,
51 __detail::_Prime_rehash_policy
, _Tr
>;
53 /// Base types for unordered_multiset.
55 using __umset_traits
= __detail::_Hashtable_traits
<_Cache
, true, false>;
57 template<typename _Value
,
58 typename _Hash
= hash
<_Value
>,
59 typename _Pred
= std::equal_to
<_Value
>,
60 typename _Alloc
= std::allocator
<_Value
>,
61 typename _Tr
= __umset_traits
<__cache_default
<_Value
, _Hash
>::value
>>
62 using __umset_hashtable
= _Hashtable
<_Value
, _Value
, _Alloc
,
65 __detail::_Mod_range_hashing
,
66 __detail::_Default_ranged_hash
,
67 __detail::_Prime_rehash_policy
, _Tr
>;
69 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
70 class unordered_multiset
;
73 * @brief A standard container composed of unique keys (containing
74 * at most one of each key value) in which the elements' keys are
75 * the elements themselves.
77 * @ingroup unordered_associative_containers
79 * @tparam _Value Type of key objects.
80 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
82 * @tparam _Pred Predicate function object type, defaults to
85 * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
87 * Meets the requirements of a <a href="tables.html#65">container</a>, and
88 * <a href="tables.html#xx">unordered associative container</a>
90 * Base is _Hashtable, dispatched at compile time via template
91 * alias __uset_hashtable.
93 template<typename _Value
,
94 typename _Hash
= hash
<_Value
>,
95 typename _Pred
= equal_to
<_Value
>,
96 typename _Alloc
= allocator
<_Value
>>
99 typedef __uset_hashtable
<_Value
, _Hash
, _Pred
, _Alloc
> _Hashtable
;
106 typedef typename
_Hashtable::key_type key_type
;
107 typedef typename
_Hashtable::value_type value_type
;
108 typedef typename
_Hashtable::hasher hasher
;
109 typedef typename
_Hashtable::key_equal key_equal
;
110 typedef typename
_Hashtable::allocator_type allocator_type
;
114 /// Iterator-related typedefs.
115 typedef typename
_Hashtable::pointer pointer
;
116 typedef typename
_Hashtable::const_pointer const_pointer
;
117 typedef typename
_Hashtable::reference reference
;
118 typedef typename
_Hashtable::const_reference const_reference
;
119 typedef typename
_Hashtable::iterator iterator
;
120 typedef typename
_Hashtable::const_iterator const_iterator
;
121 typedef typename
_Hashtable::local_iterator local_iterator
;
122 typedef typename
_Hashtable::const_local_iterator const_local_iterator
;
123 typedef typename
_Hashtable::size_type size_type
;
124 typedef typename
_Hashtable::difference_type difference_type
;
127 #if __cplusplus > 201402L
128 using node_type
= typename
_Hashtable::node_type
;
129 using insert_return_type
= typename
_Hashtable::insert_return_type
;
132 // construct/destroy/copy
134 /// Default constructor.
135 unordered_set() = default;
138 * @brief Default constructor creates no elements.
139 * @param __n Minimal initial number of buckets.
140 * @param __hf A hash functor.
141 * @param __eql A key equality functor.
142 * @param __a An allocator object.
145 unordered_set(size_type __n
,
146 const hasher
& __hf
= hasher(),
147 const key_equal
& __eql
= key_equal(),
148 const allocator_type
& __a
= allocator_type())
149 : _M_h(__n
, __hf
, __eql
, __a
)
153 * @brief Builds an %unordered_set from a range.
154 * @param __first An input iterator.
155 * @param __last An input iterator.
156 * @param __n Minimal initial number of buckets.
157 * @param __hf A hash functor.
158 * @param __eql A key equality functor.
159 * @param __a An allocator object.
161 * Create an %unordered_set consisting of copies of the elements from
162 * [__first,__last). This is linear in N (where N is
163 * distance(__first,__last)).
165 template<typename _InputIterator
>
166 unordered_set(_InputIterator __first
, _InputIterator __last
,
168 const hasher
& __hf
= hasher(),
169 const key_equal
& __eql
= key_equal(),
170 const allocator_type
& __a
= allocator_type())
171 : _M_h(__first
, __last
, __n
, __hf
, __eql
, __a
)
174 /// Copy constructor.
175 unordered_set(const unordered_set
&) = default;
177 /// Move constructor.
178 unordered_set(unordered_set
&&) = default;
181 * @brief Creates an %unordered_set with no elements.
182 * @param __a An allocator object.
185 unordered_set(const allocator_type
& __a
)
190 * @brief Copy constructor with allocator argument.
191 * @param __uset Input %unordered_set to copy.
192 * @param __a An allocator object.
194 unordered_set(const unordered_set
& __uset
,
195 const allocator_type
& __a
)
196 : _M_h(__uset
._M_h
, __a
)
200 * @brief Move constructor with allocator argument.
201 * @param __uset Input %unordered_set to move.
202 * @param __a An allocator object.
204 unordered_set(unordered_set
&& __uset
,
205 const allocator_type
& __a
)
206 : _M_h(std::move(__uset
._M_h
), __a
)
210 * @brief Builds an %unordered_set from an initializer_list.
211 * @param __l An initializer_list.
212 * @param __n Minimal initial number of buckets.
213 * @param __hf A hash functor.
214 * @param __eql A key equality functor.
215 * @param __a An allocator object.
217 * Create an %unordered_set consisting of copies of the elements in the
218 * list. This is linear in N (where N is @a __l.size()).
220 unordered_set(initializer_list
<value_type
> __l
,
222 const hasher
& __hf
= hasher(),
223 const key_equal
& __eql
= key_equal(),
224 const allocator_type
& __a
= allocator_type())
225 : _M_h(__l
, __n
, __hf
, __eql
, __a
)
228 unordered_set(size_type __n
, const allocator_type
& __a
)
229 : unordered_set(__n
, hasher(), key_equal(), __a
)
232 unordered_set(size_type __n
, const hasher
& __hf
,
233 const allocator_type
& __a
)
234 : unordered_set(__n
, __hf
, key_equal(), __a
)
237 template<typename _InputIterator
>
238 unordered_set(_InputIterator __first
, _InputIterator __last
,
240 const allocator_type
& __a
)
241 : unordered_set(__first
, __last
, __n
, hasher(), key_equal(), __a
)
244 template<typename _InputIterator
>
245 unordered_set(_InputIterator __first
, _InputIterator __last
,
246 size_type __n
, const hasher
& __hf
,
247 const allocator_type
& __a
)
248 : unordered_set(__first
, __last
, __n
, __hf
, key_equal(), __a
)
251 unordered_set(initializer_list
<value_type
> __l
,
253 const allocator_type
& __a
)
254 : unordered_set(__l
, __n
, hasher(), key_equal(), __a
)
257 unordered_set(initializer_list
<value_type
> __l
,
258 size_type __n
, const hasher
& __hf
,
259 const allocator_type
& __a
)
260 : unordered_set(__l
, __n
, __hf
, key_equal(), __a
)
263 /// Copy assignment operator.
265 operator=(const unordered_set
&) = default;
267 /// Move assignment operator.
269 operator=(unordered_set
&&) = default;
272 * @brief %Unordered_set list assignment operator.
273 * @param __l An initializer_list.
275 * This function fills an %unordered_set with copies of the elements in
276 * the initializer list @a __l.
278 * Note that the assignment completely changes the %unordered_set and
279 * that the resulting %unordered_set's size is the same as the number
280 * of elements assigned.
283 operator=(initializer_list
<value_type
> __l
)
289 /// Returns the allocator object used by the %unordered_set.
291 get_allocator() const noexcept
292 { return _M_h
.get_allocator(); }
294 // size and capacity:
296 /// Returns true if the %unordered_set is empty.
298 empty() const noexcept
299 { return _M_h
.empty(); }
301 /// Returns the size of the %unordered_set.
303 size() const noexcept
304 { return _M_h
.size(); }
306 /// Returns the maximum size of the %unordered_set.
308 max_size() const noexcept
309 { return _M_h
.max_size(); }
315 * Returns a read-only (constant) iterator that points to the first
316 * element in the %unordered_set.
320 { return _M_h
.begin(); }
323 begin() const noexcept
324 { return _M_h
.begin(); }
329 * Returns a read-only (constant) iterator that points one past the last
330 * element in the %unordered_set.
334 { return _M_h
.end(); }
338 { return _M_h
.end(); }
342 * Returns a read-only (constant) iterator that points to the first
343 * element in the %unordered_set.
346 cbegin() const noexcept
347 { return _M_h
.begin(); }
350 * Returns a read-only (constant) iterator that points one past the last
351 * element in the %unordered_set.
354 cend() const noexcept
355 { return _M_h
.end(); }
360 * @brief Attempts to build and insert an element into the
362 * @param __args Arguments used to generate an element.
363 * @return A pair, of which the first element is an iterator that points
364 * to the possibly inserted element, and the second is a bool
365 * that is true if the element was actually inserted.
367 * This function attempts to build and insert an element into the
368 * %unordered_set. An %unordered_set relies on unique keys and thus an
369 * element is only inserted if it is not already present in the
372 * Insertion requires amortized constant time.
374 template<typename
... _Args
>
375 std::pair
<iterator
, bool>
376 emplace(_Args
&&... __args
)
377 { return _M_h
.emplace(std::forward
<_Args
>(__args
)...); }
380 * @brief Attempts to insert an element into the %unordered_set.
381 * @param __pos An iterator that serves as a hint as to where the
382 * element should be inserted.
383 * @param __args Arguments used to generate the element to be
385 * @return An iterator that points to the element with key equivalent to
386 * the one generated from @a __args (may or may not be the
389 * This function is not concerned about whether the insertion took place,
390 * and thus does not return a boolean like the single-argument emplace()
391 * does. Note that the first parameter is only a hint and can
392 * potentially improve the performance of the insertion process. A bad
393 * hint would cause no gains in efficiency.
395 * For more on @a hinting, see:
396 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
398 * Insertion requires amortized constant time.
400 template<typename
... _Args
>
402 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
403 { return _M_h
.emplace_hint(__pos
, std::forward
<_Args
>(__args
)...); }
407 * @brief Attempts to insert an element into the %unordered_set.
408 * @param __x Element to be inserted.
409 * @return A pair, of which the first element is an iterator that points
410 * to the possibly inserted element, and the second is a bool
411 * that is true if the element was actually inserted.
413 * This function attempts to insert an element into the %unordered_set.
414 * An %unordered_set relies on unique keys and thus an element is only
415 * inserted if it is not already present in the %unordered_set.
417 * Insertion requires amortized constant time.
419 std::pair
<iterator
, bool>
420 insert(const value_type
& __x
)
421 { return _M_h
.insert(__x
); }
423 std::pair
<iterator
, bool>
424 insert(value_type
&& __x
)
425 { return _M_h
.insert(std::move(__x
)); }
430 * @brief Attempts to insert an element into the %unordered_set.
431 * @param __hint An iterator that serves as a hint as to where the
432 * element should be inserted.
433 * @param __x Element to be inserted.
434 * @return An iterator that points to the element with key of
435 * @a __x (may or may not be the element passed in).
437 * This function is not concerned about whether the insertion took place,
438 * and thus does not return a boolean like the single-argument insert()
439 * does. Note that the first parameter is only a hint and can
440 * potentially improve the performance of the insertion process. A bad
441 * hint would cause no gains in efficiency.
443 * For more on @a hinting, see:
444 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
446 * Insertion requires amortized constant.
449 insert(const_iterator __hint
, const value_type
& __x
)
450 { return _M_h
.insert(__hint
, __x
); }
453 insert(const_iterator __hint
, value_type
&& __x
)
454 { return _M_h
.insert(__hint
, std::move(__x
)); }
458 * @brief A template function that attempts to insert a range of
460 * @param __first Iterator pointing to the start of the range to be
462 * @param __last Iterator pointing to the end of the range.
464 * Complexity similar to that of the range constructor.
466 template<typename _InputIterator
>
468 insert(_InputIterator __first
, _InputIterator __last
)
469 { _M_h
.insert(__first
, __last
); }
472 * @brief Attempts to insert a list of elements into the %unordered_set.
473 * @param __l A std::initializer_list<value_type> of elements
476 * Complexity similar to that of the range constructor.
479 insert(initializer_list
<value_type
> __l
)
480 { _M_h
.insert(__l
); }
482 #if __cplusplus > 201402L
485 extract(const_iterator __pos
)
487 __glibcxx_assert(__pos
!= end());
488 return _M_h
.extract(__pos
);
493 extract(const key_type
& __key
)
494 { return _M_h
.extract(__key
); }
496 /// Re-insert an extracted node.
498 insert(node_type
&& __nh
)
499 { return _M_h
._M_reinsert_node(std::move(__nh
)); }
501 /// Re-insert an extracted node.
503 insert(const_iterator
, node_type
&& __nh
)
504 { return _M_h
._M_reinsert_node(std::move(__nh
)).position
; }
509 * @brief Erases an element from an %unordered_set.
510 * @param __position An iterator pointing to the element to be erased.
511 * @return An iterator pointing to the element immediately following
512 * @a __position prior to the element being erased. If no such
513 * element exists, end() is returned.
515 * This function erases an element, pointed to by the given iterator,
516 * from an %unordered_set. Note that this function only erases the
517 * element, and that if the element is itself a pointer, the pointed-to
518 * memory is not touched in any way. Managing the pointer is the user's
522 erase(const_iterator __position
)
523 { return _M_h
.erase(__position
); }
527 erase(iterator __position
)
528 { return _M_h
.erase(__position
); }
532 * @brief Erases elements according to the provided key.
533 * @param __x Key of element to be erased.
534 * @return The number of elements erased.
536 * This function erases all the elements located by the given key from
537 * an %unordered_set. For an %unordered_set the result of this function
538 * can only be 0 (not present) or 1 (present).
539 * Note that this function only erases the element, and that if
540 * the element is itself a pointer, the pointed-to memory is not touched
541 * in any way. Managing the pointer is the user's responsibility.
544 erase(const key_type
& __x
)
545 { return _M_h
.erase(__x
); }
548 * @brief Erases a [__first,__last) range of elements from an
550 * @param __first Iterator pointing to the start of the range to be
552 * @param __last Iterator pointing to the end of the range to
554 * @return The iterator @a __last.
556 * This function erases a sequence of elements from an %unordered_set.
557 * Note that this function only erases the element, and that if
558 * the element is itself a pointer, the pointed-to memory is not touched
559 * in any way. Managing the pointer is the user's responsibility.
562 erase(const_iterator __first
, const_iterator __last
)
563 { return _M_h
.erase(__first
, __last
); }
566 * Erases all elements in an %unordered_set. Note that this function only
567 * erases the elements, and that if the elements themselves are pointers,
568 * the pointed-to memory is not touched in any way. Managing the pointer
569 * is the user's responsibility.
576 * @brief Swaps data with another %unordered_set.
577 * @param __x An %unordered_set of the same element and allocator
580 * This exchanges the elements between two sets in constant time.
581 * Note that the global std::swap() function is specialized such that
582 * std::swap(s1,s2) will feed to this function.
585 swap(unordered_set
& __x
)
586 noexcept( noexcept(_M_h
.swap(__x
._M_h
)) )
587 { _M_h
.swap(__x
._M_h
); }
589 #if __cplusplus > 201402L
590 template<typename
, typename
, typename
>
591 friend class std::_Hash_merge_helper
;
593 template<typename _H2
, typename _P2
>
595 merge(unordered_set
<_Value
, _H2
, _P2
, _Alloc
>& __source
)
597 using _Merge_helper
= _Hash_merge_helper
<unordered_set
, _H2
, _P2
>;
598 _M_h
._M_merge_unique(_Merge_helper::_S_get_table(__source
));
601 template<typename _H2
, typename _P2
>
603 merge(unordered_set
<_Value
, _H2
, _P2
, _Alloc
>&& __source
)
606 template<typename _H2
, typename _P2
>
608 merge(unordered_multiset
<_Value
, _H2
, _P2
, _Alloc
>& __source
)
610 using _Merge_helper
= _Hash_merge_helper
<unordered_set
, _H2
, _P2
>;
611 _M_h
._M_merge_unique(_Merge_helper::_S_get_table(__source
));
614 template<typename _H2
, typename _P2
>
616 merge(unordered_multiset
<_Value
, _H2
, _P2
, _Alloc
>&& __source
)
622 /// Returns the hash functor object with which the %unordered_set was
625 hash_function() const
626 { return _M_h
.hash_function(); }
628 /// Returns the key comparison object with which the %unordered_set was
632 { return _M_h
.key_eq(); }
638 * @brief Tries to locate an element in an %unordered_set.
639 * @param __x Element to be located.
640 * @return Iterator pointing to sought-after element, or end() if not
643 * This function takes a key and tries to locate the element with which
644 * the key matches. If successful the function returns an iterator
645 * pointing to the sought after element. If unsuccessful it returns the
646 * past-the-end ( @c end() ) iterator.
649 find(const key_type
& __x
)
650 { return _M_h
.find(__x
); }
653 find(const key_type
& __x
) const
654 { return _M_h
.find(__x
); }
658 * @brief Finds the number of elements.
659 * @param __x Element to located.
660 * @return Number of elements with specified key.
662 * This function only makes sense for unordered_multisets; for
663 * unordered_set the result will either be 0 (not present) or 1
667 count(const key_type
& __x
) const
668 { return _M_h
.count(__x
); }
672 * @brief Finds a subsequence matching given key.
673 * @param __x Key to be located.
674 * @return Pair of iterators that possibly points to the subsequence
675 * matching given key.
677 * This function probably only makes sense for multisets.
679 std::pair
<iterator
, iterator
>
680 equal_range(const key_type
& __x
)
681 { return _M_h
.equal_range(__x
); }
683 std::pair
<const_iterator
, const_iterator
>
684 equal_range(const key_type
& __x
) const
685 { return _M_h
.equal_range(__x
); }
690 /// Returns the number of buckets of the %unordered_set.
692 bucket_count() const noexcept
693 { return _M_h
.bucket_count(); }
695 /// Returns the maximum number of buckets of the %unordered_set.
697 max_bucket_count() const noexcept
698 { return _M_h
.max_bucket_count(); }
701 * @brief Returns the number of elements in a given bucket.
702 * @param __n A bucket index.
703 * @return The number of elements in the bucket.
706 bucket_size(size_type __n
) const
707 { return _M_h
.bucket_size(__n
); }
710 * @brief Returns the bucket index of a given element.
711 * @param __key A key instance.
712 * @return The key bucket index.
715 bucket(const key_type
& __key
) const
716 { return _M_h
.bucket(__key
); }
720 * @brief Returns a read-only (constant) iterator pointing to the first
722 * @param __n The bucket index.
723 * @return A read-only local iterator.
727 { return _M_h
.begin(__n
); }
730 begin(size_type __n
) const
731 { return _M_h
.begin(__n
); }
734 cbegin(size_type __n
) const
735 { return _M_h
.cbegin(__n
); }
740 * @brief Returns a read-only (constant) iterator pointing to one past
741 * the last bucket elements.
742 * @param __n The bucket index.
743 * @return A read-only local iterator.
747 { return _M_h
.end(__n
); }
750 end(size_type __n
) const
751 { return _M_h
.end(__n
); }
754 cend(size_type __n
) const
755 { return _M_h
.cend(__n
); }
760 /// Returns the average number of elements per bucket.
762 load_factor() const noexcept
763 { return _M_h
.load_factor(); }
765 /// Returns a positive number that the %unordered_set tries to keep the
766 /// load factor less than or equal to.
768 max_load_factor() const noexcept
769 { return _M_h
.max_load_factor(); }
772 * @brief Change the %unordered_set maximum load factor.
773 * @param __z The new maximum load factor.
776 max_load_factor(float __z
)
777 { _M_h
.max_load_factor(__z
); }
780 * @brief May rehash the %unordered_set.
781 * @param __n The new number of buckets.
783 * Rehash will occur only if the new number of buckets respect the
784 * %unordered_set maximum load factor.
787 rehash(size_type __n
)
788 { _M_h
.rehash(__n
); }
791 * @brief Prepare the %unordered_set for a specified number of
793 * @param __n Number of elements required.
795 * Same as rehash(ceil(n / max_load_factor())).
798 reserve(size_type __n
)
799 { _M_h
.reserve(__n
); }
801 template<typename _Value1
, typename _Hash1
, typename _Pred1
,
804 operator==(const unordered_set
<_Value1
, _Hash1
, _Pred1
, _Alloc1
>&,
805 const unordered_set
<_Value1
, _Hash1
, _Pred1
, _Alloc1
>&);
808 #if __cpp_deduction_guides >= 201606
810 template<typename _InputIterator
,
812 hash
<typename iterator_traits
<_InputIterator
>::value_type
>,
814 equal_to
<typename iterator_traits
<_InputIterator
>::value_type
>,
815 typename _Allocator
=
816 allocator
<typename iterator_traits
<_InputIterator
>::value_type
>,
817 typename
= _RequireInputIter
<_InputIterator
>,
818 typename
= _RequireAllocator
<_Allocator
>>
819 unordered_set(_InputIterator
, _InputIterator
,
820 unordered_set
<int>::size_type
= {},
821 _Hash
= _Hash(), _Pred
= _Pred(), _Allocator
= _Allocator())
822 -> unordered_set
<typename iterator_traits
<_InputIterator
>::value_type
,
823 _Hash
, _Pred
, _Allocator
>;
825 template<typename _Tp
, typename _Hash
= hash
<_Tp
>,
826 typename _Pred
= equal_to
<_Tp
>,
827 typename _Allocator
= allocator
<_Tp
>,
828 typename
= _RequireAllocator
<_Allocator
>>
829 unordered_set(initializer_list
<_Tp
>,
830 unordered_set
<int>::size_type
= {},
831 _Hash
= _Hash(), _Pred
= _Pred(), _Allocator
= _Allocator())
832 -> unordered_set
<_Tp
, _Hash
, _Pred
, _Allocator
>;
834 template<typename _InputIterator
, typename _Allocator
,
835 typename
= _RequireInputIter
<_InputIterator
>,
836 typename
= _RequireAllocator
<_Allocator
>>
837 unordered_set(_InputIterator
, _InputIterator
,
838 unordered_set
<int>::size_type
, _Allocator
)
839 -> unordered_set
<typename iterator_traits
<_InputIterator
>::value_type
,
841 typename iterator_traits
<_InputIterator
>::value_type
>,
843 typename iterator_traits
<_InputIterator
>::value_type
>,
846 template<typename _InputIterator
, typename _Hash
, typename _Allocator
,
847 typename
= _RequireInputIter
<_InputIterator
>,
848 typename
= _RequireAllocator
<_Allocator
>>
849 unordered_set(_InputIterator
, _InputIterator
,
850 unordered_set
<int>::size_type
,
852 -> unordered_set
<typename iterator_traits
<_InputIterator
>::value_type
,
855 typename iterator_traits
<_InputIterator
>::value_type
>,
858 template<typename _Tp
, typename _Allocator
,
859 typename
= _RequireAllocator
<_Allocator
>>
860 unordered_set(initializer_list
<_Tp
>,
861 unordered_set
<int>::size_type
, _Allocator
)
862 -> unordered_set
<_Tp
, hash
<_Tp
>, equal_to
<_Tp
>, _Allocator
>;
864 template<typename _Tp
, typename _Hash
, typename _Allocator
,
865 typename
= _RequireAllocator
<_Allocator
>>
866 unordered_set(initializer_list
<_Tp
>,
867 unordered_set
<int>::size_type
, _Hash
, _Allocator
)
868 -> unordered_set
<_Tp
, _Hash
, equal_to
<_Tp
>, _Allocator
>;
873 * @brief A standard container composed of equivalent keys
874 * (possibly containing multiple of each key value) in which the
875 * elements' keys are the elements themselves.
877 * @ingroup unordered_associative_containers
879 * @tparam _Value Type of key objects.
880 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
881 * @tparam _Pred Predicate function object type, defaults
882 * to equal_to<_Value>.
883 * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
885 * Meets the requirements of a <a href="tables.html#65">container</a>, and
886 * <a href="tables.html#xx">unordered associative container</a>
888 * Base is _Hashtable, dispatched at compile time via template
889 * alias __umset_hashtable.
891 template<typename _Value
,
892 typename _Hash
= hash
<_Value
>,
893 typename _Pred
= equal_to
<_Value
>,
894 typename _Alloc
= allocator
<_Value
>>
895 class unordered_multiset
897 typedef __umset_hashtable
<_Value
, _Hash
, _Pred
, _Alloc
> _Hashtable
;
904 typedef typename
_Hashtable::key_type key_type
;
905 typedef typename
_Hashtable::value_type value_type
;
906 typedef typename
_Hashtable::hasher hasher
;
907 typedef typename
_Hashtable::key_equal key_equal
;
908 typedef typename
_Hashtable::allocator_type allocator_type
;
912 /// Iterator-related typedefs.
913 typedef typename
_Hashtable::pointer pointer
;
914 typedef typename
_Hashtable::const_pointer const_pointer
;
915 typedef typename
_Hashtable::reference reference
;
916 typedef typename
_Hashtable::const_reference const_reference
;
917 typedef typename
_Hashtable::iterator iterator
;
918 typedef typename
_Hashtable::const_iterator const_iterator
;
919 typedef typename
_Hashtable::local_iterator local_iterator
;
920 typedef typename
_Hashtable::const_local_iterator const_local_iterator
;
921 typedef typename
_Hashtable::size_type size_type
;
922 typedef typename
_Hashtable::difference_type difference_type
;
925 #if __cplusplus > 201402L
926 using node_type
= typename
_Hashtable::node_type
;
929 // construct/destroy/copy
931 /// Default constructor.
932 unordered_multiset() = default;
935 * @brief Default constructor creates no elements.
936 * @param __n Minimal initial number of buckets.
937 * @param __hf A hash functor.
938 * @param __eql A key equality functor.
939 * @param __a An allocator object.
942 unordered_multiset(size_type __n
,
943 const hasher
& __hf
= hasher(),
944 const key_equal
& __eql
= key_equal(),
945 const allocator_type
& __a
= allocator_type())
946 : _M_h(__n
, __hf
, __eql
, __a
)
950 * @brief Builds an %unordered_multiset from a range.
951 * @param __first An input iterator.
952 * @param __last An input iterator.
953 * @param __n Minimal initial number of buckets.
954 * @param __hf A hash functor.
955 * @param __eql A key equality functor.
956 * @param __a An allocator object.
958 * Create an %unordered_multiset consisting of copies of the elements
959 * from [__first,__last). This is linear in N (where N is
960 * distance(__first,__last)).
962 template<typename _InputIterator
>
963 unordered_multiset(_InputIterator __first
, _InputIterator __last
,
965 const hasher
& __hf
= hasher(),
966 const key_equal
& __eql
= key_equal(),
967 const allocator_type
& __a
= allocator_type())
968 : _M_h(__first
, __last
, __n
, __hf
, __eql
, __a
)
971 /// Copy constructor.
972 unordered_multiset(const unordered_multiset
&) = default;
974 /// Move constructor.
975 unordered_multiset(unordered_multiset
&&) = default;
978 * @brief Builds an %unordered_multiset from an initializer_list.
979 * @param __l An initializer_list.
980 * @param __n Minimal initial number of buckets.
981 * @param __hf A hash functor.
982 * @param __eql A key equality functor.
983 * @param __a An allocator object.
985 * Create an %unordered_multiset consisting of copies of the elements in
986 * the list. This is linear in N (where N is @a __l.size()).
988 unordered_multiset(initializer_list
<value_type
> __l
,
990 const hasher
& __hf
= hasher(),
991 const key_equal
& __eql
= key_equal(),
992 const allocator_type
& __a
= allocator_type())
993 : _M_h(__l
, __n
, __hf
, __eql
, __a
)
996 /// Copy assignment operator.
998 operator=(const unordered_multiset
&) = default;
1000 /// Move assignment operator.
1002 operator=(unordered_multiset
&&) = default;
1005 * @brief Creates an %unordered_multiset with no elements.
1006 * @param __a An allocator object.
1009 unordered_multiset(const allocator_type
& __a
)
1014 * @brief Copy constructor with allocator argument.
1015 * @param __uset Input %unordered_multiset to copy.
1016 * @param __a An allocator object.
1018 unordered_multiset(const unordered_multiset
& __umset
,
1019 const allocator_type
& __a
)
1020 : _M_h(__umset
._M_h
, __a
)
1024 * @brief Move constructor with allocator argument.
1025 * @param __umset Input %unordered_multiset to move.
1026 * @param __a An allocator object.
1028 unordered_multiset(unordered_multiset
&& __umset
,
1029 const allocator_type
& __a
)
1030 : _M_h(std::move(__umset
._M_h
), __a
)
1033 unordered_multiset(size_type __n
, const allocator_type
& __a
)
1034 : unordered_multiset(__n
, hasher(), key_equal(), __a
)
1037 unordered_multiset(size_type __n
, const hasher
& __hf
,
1038 const allocator_type
& __a
)
1039 : unordered_multiset(__n
, __hf
, key_equal(), __a
)
1042 template<typename _InputIterator
>
1043 unordered_multiset(_InputIterator __first
, _InputIterator __last
,
1045 const allocator_type
& __a
)
1046 : unordered_multiset(__first
, __last
, __n
, hasher(), key_equal(), __a
)
1049 template<typename _InputIterator
>
1050 unordered_multiset(_InputIterator __first
, _InputIterator __last
,
1051 size_type __n
, const hasher
& __hf
,
1052 const allocator_type
& __a
)
1053 : unordered_multiset(__first
, __last
, __n
, __hf
, key_equal(), __a
)
1056 unordered_multiset(initializer_list
<value_type
> __l
,
1058 const allocator_type
& __a
)
1059 : unordered_multiset(__l
, __n
, hasher(), key_equal(), __a
)
1062 unordered_multiset(initializer_list
<value_type
> __l
,
1063 size_type __n
, const hasher
& __hf
,
1064 const allocator_type
& __a
)
1065 : unordered_multiset(__l
, __n
, __hf
, key_equal(), __a
)
1069 * @brief %Unordered_multiset list assignment operator.
1070 * @param __l An initializer_list.
1072 * This function fills an %unordered_multiset with copies of the elements
1073 * in the initializer list @a __l.
1075 * Note that the assignment completely changes the %unordered_multiset
1076 * and that the resulting %unordered_multiset's size is the same as the
1077 * number of elements assigned.
1080 operator=(initializer_list
<value_type
> __l
)
1086 /// Returns the allocator object used by the %unordered_multiset.
1088 get_allocator() const noexcept
1089 { return _M_h
.get_allocator(); }
1091 // size and capacity:
1093 /// Returns true if the %unordered_multiset is empty.
1095 empty() const noexcept
1096 { return _M_h
.empty(); }
1098 /// Returns the size of the %unordered_multiset.
1100 size() const noexcept
1101 { return _M_h
.size(); }
1103 /// Returns the maximum size of the %unordered_multiset.
1105 max_size() const noexcept
1106 { return _M_h
.max_size(); }
1112 * Returns a read-only (constant) iterator that points to the first
1113 * element in the %unordered_multiset.
1117 { return _M_h
.begin(); }
1120 begin() const noexcept
1121 { return _M_h
.begin(); }
1126 * Returns a read-only (constant) iterator that points one past the last
1127 * element in the %unordered_multiset.
1131 { return _M_h
.end(); }
1134 end() const noexcept
1135 { return _M_h
.end(); }
1139 * Returns a read-only (constant) iterator that points to the first
1140 * element in the %unordered_multiset.
1143 cbegin() const noexcept
1144 { return _M_h
.begin(); }
1147 * Returns a read-only (constant) iterator that points one past the last
1148 * element in the %unordered_multiset.
1151 cend() const noexcept
1152 { return _M_h
.end(); }
1157 * @brief Builds and insert an element into the %unordered_multiset.
1158 * @param __args Arguments used to generate an element.
1159 * @return An iterator that points to the inserted element.
1161 * Insertion requires amortized constant time.
1163 template<typename
... _Args
>
1165 emplace(_Args
&&... __args
)
1166 { return _M_h
.emplace(std::forward
<_Args
>(__args
)...); }
1169 * @brief Inserts an element into the %unordered_multiset.
1170 * @param __pos An iterator that serves as a hint as to where the
1171 * element should be inserted.
1172 * @param __args Arguments used to generate the element to be
1174 * @return An iterator that points to the inserted element.
1176 * Note that the first parameter is only a hint and can potentially
1177 * improve the performance of the insertion process. A bad hint would
1178 * cause no gains in efficiency.
1180 * For more on @a hinting, see:
1181 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1183 * Insertion requires amortized constant time.
1185 template<typename
... _Args
>
1187 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
1188 { return _M_h
.emplace_hint(__pos
, std::forward
<_Args
>(__args
)...); }
1192 * @brief Inserts an element into the %unordered_multiset.
1193 * @param __x Element to be inserted.
1194 * @return An iterator that points to the inserted element.
1196 * Insertion requires amortized constant time.
1199 insert(const value_type
& __x
)
1200 { return _M_h
.insert(__x
); }
1203 insert(value_type
&& __x
)
1204 { return _M_h
.insert(std::move(__x
)); }
1209 * @brief Inserts an element into the %unordered_multiset.
1210 * @param __hint An iterator that serves as a hint as to where the
1211 * element should be inserted.
1212 * @param __x Element to be inserted.
1213 * @return An iterator that points to the inserted element.
1215 * Note that the first parameter is only a hint and can potentially
1216 * improve the performance of the insertion process. A bad hint would
1217 * cause no gains in efficiency.
1219 * For more on @a hinting, see:
1220 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1222 * Insertion requires amortized constant.
1225 insert(const_iterator __hint
, const value_type
& __x
)
1226 { return _M_h
.insert(__hint
, __x
); }
1229 insert(const_iterator __hint
, value_type
&& __x
)
1230 { return _M_h
.insert(__hint
, std::move(__x
)); }
1234 * @brief A template function that inserts a range of elements.
1235 * @param __first Iterator pointing to the start of the range to be
1237 * @param __last Iterator pointing to the end of the range.
1239 * Complexity similar to that of the range constructor.
1241 template<typename _InputIterator
>
1243 insert(_InputIterator __first
, _InputIterator __last
)
1244 { _M_h
.insert(__first
, __last
); }
1247 * @brief Inserts a list of elements into the %unordered_multiset.
1248 * @param __l A std::initializer_list<value_type> of elements to be
1251 * Complexity similar to that of the range constructor.
1254 insert(initializer_list
<value_type
> __l
)
1255 { _M_h
.insert(__l
); }
1257 #if __cplusplus > 201402L
1260 extract(const_iterator __pos
)
1262 __glibcxx_assert(__pos
!= end());
1263 return _M_h
.extract(__pos
);
1268 extract(const key_type
& __key
)
1269 { return _M_h
.extract(__key
); }
1271 /// Re-insert an extracted node.
1273 insert(node_type
&& __nh
)
1274 { return _M_h
._M_reinsert_node_multi(cend(), std::move(__nh
)); }
1276 /// Re-insert an extracted node.
1278 insert(const_iterator __hint
, node_type
&& __nh
)
1279 { return _M_h
._M_reinsert_node_multi(__hint
, std::move(__nh
)); }
1284 * @brief Erases an element from an %unordered_multiset.
1285 * @param __position An iterator pointing to the element to be erased.
1286 * @return An iterator pointing to the element immediately following
1287 * @a __position prior to the element being erased. If no such
1288 * element exists, end() is returned.
1290 * This function erases an element, pointed to by the given iterator,
1291 * from an %unordered_multiset.
1293 * Note that this function only erases the element, and that if the
1294 * element is itself a pointer, the pointed-to memory is not touched in
1295 * any way. Managing the pointer is the user's responsibility.
1298 erase(const_iterator __position
)
1299 { return _M_h
.erase(__position
); }
1303 erase(iterator __position
)
1304 { return _M_h
.erase(__position
); }
1309 * @brief Erases elements according to the provided key.
1310 * @param __x Key of element to be erased.
1311 * @return The number of elements erased.
1313 * This function erases all the elements located by the given key from
1314 * an %unordered_multiset.
1316 * Note that this function only erases the element, and that if the
1317 * element is itself a pointer, the pointed-to memory is not touched in
1318 * any way. Managing the pointer is the user's responsibility.
1321 erase(const key_type
& __x
)
1322 { return _M_h
.erase(__x
); }
1325 * @brief Erases a [__first,__last) range of elements from an
1326 * %unordered_multiset.
1327 * @param __first Iterator pointing to the start of the range to be
1329 * @param __last Iterator pointing to the end of the range to
1331 * @return The iterator @a __last.
1333 * This function erases a sequence of elements from an
1334 * %unordered_multiset.
1336 * Note that this function only erases the element, and that if
1337 * the element is itself a pointer, the pointed-to memory is not touched
1338 * in any way. Managing the pointer is the user's responsibility.
1341 erase(const_iterator __first
, const_iterator __last
)
1342 { return _M_h
.erase(__first
, __last
); }
1345 * Erases all elements in an %unordered_multiset.
1347 * Note that this function only erases the elements, and that if the
1348 * elements themselves are pointers, the pointed-to memory is not touched
1349 * in any way. Managing the pointer is the user's responsibility.
1356 * @brief Swaps data with another %unordered_multiset.
1357 * @param __x An %unordered_multiset of the same element and allocator
1360 * This exchanges the elements between two sets in constant time.
1361 * Note that the global std::swap() function is specialized such that
1362 * std::swap(s1,s2) will feed to this function.
1365 swap(unordered_multiset
& __x
)
1366 noexcept( noexcept(_M_h
.swap(__x
._M_h
)) )
1367 { _M_h
.swap(__x
._M_h
); }
1369 #if __cplusplus > 201402L
1370 template<typename
, typename
, typename
>
1371 friend class std::_Hash_merge_helper
;
1373 template<typename _H2
, typename _P2
>
1375 merge(unordered_multiset
<_Value
, _H2
, _P2
, _Alloc
>& __source
)
1378 = _Hash_merge_helper
<unordered_multiset
, _H2
, _P2
>;
1379 _M_h
._M_merge_multi(_Merge_helper::_S_get_table(__source
));
1382 template<typename _H2
, typename _P2
>
1384 merge(unordered_multiset
<_Value
, _H2
, _P2
, _Alloc
>&& __source
)
1385 { merge(__source
); }
1387 template<typename _H2
, typename _P2
>
1389 merge(unordered_set
<_Value
, _H2
, _P2
, _Alloc
>& __source
)
1392 = _Hash_merge_helper
<unordered_multiset
, _H2
, _P2
>;
1393 _M_h
._M_merge_multi(_Merge_helper::_S_get_table(__source
));
1396 template<typename _H2
, typename _P2
>
1398 merge(unordered_set
<_Value
, _H2
, _P2
, _Alloc
>&& __source
)
1399 { merge(__source
); }
1404 /// Returns the hash functor object with which the %unordered_multiset
1405 /// was constructed.
1407 hash_function() const
1408 { return _M_h
.hash_function(); }
1410 /// Returns the key comparison object with which the %unordered_multiset
1411 /// was constructed.
1414 { return _M_h
.key_eq(); }
1420 * @brief Tries to locate an element in an %unordered_multiset.
1421 * @param __x Element to be located.
1422 * @return Iterator pointing to sought-after element, or end() if not
1425 * This function takes a key and tries to locate the element with which
1426 * the key matches. If successful the function returns an iterator
1427 * pointing to the sought after element. If unsuccessful it returns the
1428 * past-the-end ( @c end() ) iterator.
1431 find(const key_type
& __x
)
1432 { return _M_h
.find(__x
); }
1435 find(const key_type
& __x
) const
1436 { return _M_h
.find(__x
); }
1440 * @brief Finds the number of elements.
1441 * @param __x Element to located.
1442 * @return Number of elements with specified key.
1445 count(const key_type
& __x
) const
1446 { return _M_h
.count(__x
); }
1450 * @brief Finds a subsequence matching given key.
1451 * @param __x Key to be located.
1452 * @return Pair of iterators that possibly points to the subsequence
1453 * matching given key.
1455 std::pair
<iterator
, iterator
>
1456 equal_range(const key_type
& __x
)
1457 { return _M_h
.equal_range(__x
); }
1459 std::pair
<const_iterator
, const_iterator
>
1460 equal_range(const key_type
& __x
) const
1461 { return _M_h
.equal_range(__x
); }
1464 // bucket interface.
1466 /// Returns the number of buckets of the %unordered_multiset.
1468 bucket_count() const noexcept
1469 { return _M_h
.bucket_count(); }
1471 /// Returns the maximum number of buckets of the %unordered_multiset.
1473 max_bucket_count() const noexcept
1474 { return _M_h
.max_bucket_count(); }
1477 * @brief Returns the number of elements in a given bucket.
1478 * @param __n A bucket index.
1479 * @return The number of elements in the bucket.
1482 bucket_size(size_type __n
) const
1483 { return _M_h
.bucket_size(__n
); }
1486 * @brief Returns the bucket index of a given element.
1487 * @param __key A key instance.
1488 * @return The key bucket index.
1491 bucket(const key_type
& __key
) const
1492 { return _M_h
.bucket(__key
); }
1496 * @brief Returns a read-only (constant) iterator pointing to the first
1498 * @param __n The bucket index.
1499 * @return A read-only local iterator.
1502 begin(size_type __n
)
1503 { return _M_h
.begin(__n
); }
1505 const_local_iterator
1506 begin(size_type __n
) const
1507 { return _M_h
.begin(__n
); }
1509 const_local_iterator
1510 cbegin(size_type __n
) const
1511 { return _M_h
.cbegin(__n
); }
1516 * @brief Returns a read-only (constant) iterator pointing to one past
1517 * the last bucket elements.
1518 * @param __n The bucket index.
1519 * @return A read-only local iterator.
1523 { return _M_h
.end(__n
); }
1525 const_local_iterator
1526 end(size_type __n
) const
1527 { return _M_h
.end(__n
); }
1529 const_local_iterator
1530 cend(size_type __n
) const
1531 { return _M_h
.cend(__n
); }
1536 /// Returns the average number of elements per bucket.
1538 load_factor() const noexcept
1539 { return _M_h
.load_factor(); }
1541 /// Returns a positive number that the %unordered_multiset tries to keep the
1542 /// load factor less than or equal to.
1544 max_load_factor() const noexcept
1545 { return _M_h
.max_load_factor(); }
1548 * @brief Change the %unordered_multiset maximum load factor.
1549 * @param __z The new maximum load factor.
1552 max_load_factor(float __z
)
1553 { _M_h
.max_load_factor(__z
); }
1556 * @brief May rehash the %unordered_multiset.
1557 * @param __n The new number of buckets.
1559 * Rehash will occur only if the new number of buckets respect the
1560 * %unordered_multiset maximum load factor.
1563 rehash(size_type __n
)
1564 { _M_h
.rehash(__n
); }
1567 * @brief Prepare the %unordered_multiset for a specified number of
1569 * @param __n Number of elements required.
1571 * Same as rehash(ceil(n / max_load_factor())).
1574 reserve(size_type __n
)
1575 { _M_h
.reserve(__n
); }
1577 template<typename _Value1
, typename _Hash1
, typename _Pred1
,
1580 operator==(const unordered_multiset
<_Value1
, _Hash1
, _Pred1
, _Alloc1
>&,
1581 const unordered_multiset
<_Value1
, _Hash1
, _Pred1
, _Alloc1
>&);
1585 #if __cpp_deduction_guides >= 201606
1587 template<typename _InputIterator
,
1589 hash
<typename iterator_traits
<_InputIterator
>::value_type
>,
1591 equal_to
<typename iterator_traits
<_InputIterator
>::value_type
>,
1592 typename _Allocator
=
1593 allocator
<typename iterator_traits
<_InputIterator
>::value_type
>,
1594 typename
= _RequireInputIter
<_InputIterator
>,
1595 typename
= _RequireAllocator
<_Allocator
>>
1596 unordered_multiset(_InputIterator
, _InputIterator
,
1597 unordered_multiset
<int>::size_type
= {},
1598 _Hash
= _Hash(), _Pred
= _Pred(),
1599 _Allocator
= _Allocator())
1600 -> unordered_multiset
<typename iterator_traits
<_InputIterator
>::value_type
,
1601 _Hash
, _Pred
, _Allocator
>;
1603 template<typename _Tp
, typename _Hash
= hash
<_Tp
>,
1604 typename _Pred
= equal_to
<_Tp
>,
1605 typename _Allocator
= allocator
<_Tp
>,
1606 typename
= _RequireAllocator
<_Allocator
>>
1607 unordered_multiset(initializer_list
<_Tp
>,
1608 unordered_multiset
<int>::size_type
= {},
1609 _Hash
= _Hash(), _Pred
= _Pred(),
1610 _Allocator
= _Allocator())
1611 -> unordered_multiset
<_Tp
, _Hash
, _Pred
, _Allocator
>;
1613 template<typename _InputIterator
, typename _Allocator
,
1614 typename
= _RequireInputIter
<_InputIterator
>,
1615 typename
= _RequireAllocator
<_Allocator
>>
1616 unordered_multiset(_InputIterator
, _InputIterator
,
1617 unordered_multiset
<int>::size_type
, _Allocator
)
1618 -> unordered_multiset
<typename iterator_traits
<_InputIterator
>::value_type
,
1620 iterator_traits
<_InputIterator
>::value_type
>,
1622 iterator_traits
<_InputIterator
>::value_type
>,
1625 template<typename _InputIterator
, typename _Hash
, typename _Allocator
,
1626 typename
= _RequireInputIter
<_InputIterator
>,
1627 typename
= _RequireAllocator
<_Allocator
>>
1628 unordered_multiset(_InputIterator
, _InputIterator
,
1629 unordered_multiset
<int>::size_type
,
1631 -> unordered_multiset
<typename
1632 iterator_traits
<_InputIterator
>::value_type
,
1636 iterator_traits
<_InputIterator
>::value_type
>,
1639 template<typename _Tp
, typename _Allocator
,
1640 typename
= _RequireAllocator
<_Allocator
>>
1641 unordered_multiset(initializer_list
<_Tp
>,
1642 unordered_multiset
<int>::size_type
, _Allocator
)
1643 -> unordered_multiset
<_Tp
, hash
<_Tp
>, equal_to
<_Tp
>, _Allocator
>;
1645 template<typename _Tp
, typename _Hash
, typename _Allocator
,
1646 typename
= _RequireAllocator
<_Allocator
>>
1647 unordered_multiset(initializer_list
<_Tp
>,
1648 unordered_multiset
<int>::size_type
, _Hash
, _Allocator
)
1649 -> unordered_multiset
<_Tp
, _Hash
, equal_to
<_Tp
>, _Allocator
>;
1653 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
1655 swap(unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
1656 unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
1657 noexcept(noexcept(__x
.swap(__y
)))
1660 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
1662 swap(unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
1663 unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
1664 noexcept(noexcept(__x
.swap(__y
)))
1667 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
1669 operator==(const unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
1670 const unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
1671 { return __x
._M_h
._M_equal(__y
._M_h
); }
1673 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
1675 operator!=(const unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
1676 const unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
1677 { return !(__x
== __y
); }
1679 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
1681 operator==(const unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
1682 const unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
1683 { return __x
._M_h
._M_equal(__y
._M_h
); }
1685 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
1687 operator!=(const unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
1688 const unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
1689 { return !(__x
== __y
); }
1691 _GLIBCXX_END_NAMESPACE_CONTAINER
1693 #if __cplusplus > 201402L
1694 // Allow std::unordered_set access to internals of compatible sets.
1695 template<typename _Val
, typename _Hash1
, typename _Eq1
, typename _Alloc
,
1696 typename _Hash2
, typename _Eq2
>
1697 struct _Hash_merge_helper
<
1698 _GLIBCXX_STD_C::unordered_set
<_Val
, _Hash1
, _Eq1
, _Alloc
>, _Hash2
, _Eq2
>
1701 template<typename
... _Tp
>
1702 using unordered_set
= _GLIBCXX_STD_C::unordered_set
<_Tp
...>;
1703 template<typename
... _Tp
>
1704 using unordered_multiset
= _GLIBCXX_STD_C::unordered_multiset
<_Tp
...>;
1706 friend unordered_set
<_Val
, _Hash1
, _Eq1
, _Alloc
>;
1709 _S_get_table(unordered_set
<_Val
, _Hash2
, _Eq2
, _Alloc
>& __set
)
1710 { return __set
._M_h
; }
1713 _S_get_table(unordered_multiset
<_Val
, _Hash2
, _Eq2
, _Alloc
>& __set
)
1714 { return __set
._M_h
; }
1717 // Allow std::unordered_multiset access to internals of compatible sets.
1718 template<typename _Val
, typename _Hash1
, typename _Eq1
, typename _Alloc
,
1719 typename _Hash2
, typename _Eq2
>
1720 struct _Hash_merge_helper
<
1721 _GLIBCXX_STD_C::unordered_multiset
<_Val
, _Hash1
, _Eq1
, _Alloc
>,
1725 template<typename
... _Tp
>
1726 using unordered_set
= _GLIBCXX_STD_C::unordered_set
<_Tp
...>;
1727 template<typename
... _Tp
>
1728 using unordered_multiset
= _GLIBCXX_STD_C::unordered_multiset
<_Tp
...>;
1730 friend unordered_multiset
<_Val
, _Hash1
, _Eq1
, _Alloc
>;
1733 _S_get_table(unordered_set
<_Val
, _Hash2
, _Eq2
, _Alloc
>& __set
)
1734 { return __set
._M_h
; }
1737 _S_get_table(unordered_multiset
<_Val
, _Hash2
, _Eq2
, _Alloc
>& __set
)
1738 { return __set
._M_h
; }
1742 _GLIBCXX_END_NAMESPACE_VERSION
1745 #endif /* _UNORDERED_SET_H */