1 // unordered_set implementation -*- C++ -*-
3 // Copyright (C) 2010-2014 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_CONTAINER
37 /// Base types for unordered_set.
39 using __uset_traits
= __detail::_Hashtable_traits
<_Cache
, true, true>;
41 template<typename _Value
,
42 typename _Hash
= hash
<_Value
>,
43 typename _Pred
= std::equal_to
<_Value
>,
44 typename _Alloc
= std::allocator
<_Value
>,
45 typename _Tr
= __uset_traits
<__cache_default
<_Value
, _Hash
>::value
>>
46 using __uset_hashtable
= _Hashtable
<_Value
, _Value
, _Alloc
,
47 __detail::_Identity
, _Pred
, _Hash
,
48 __detail::_Mod_range_hashing
,
49 __detail::_Default_ranged_hash
,
50 __detail::_Prime_rehash_policy
, _Tr
>;
52 /// Base types for unordered_multiset.
54 using __umset_traits
= __detail::_Hashtable_traits
<_Cache
, true, false>;
56 template<typename _Value
,
57 typename _Hash
= hash
<_Value
>,
58 typename _Pred
= std::equal_to
<_Value
>,
59 typename _Alloc
= std::allocator
<_Value
>,
60 typename _Tr
= __umset_traits
<__cache_default
<_Value
, _Hash
>::value
>>
61 using __umset_hashtable
= _Hashtable
<_Value
, _Value
, _Alloc
,
64 __detail::_Mod_range_hashing
,
65 __detail::_Default_ranged_hash
,
66 __detail::_Prime_rehash_policy
, _Tr
>;
69 * @brief A standard container composed of unique keys (containing
70 * at most one of each key value) in which the elements' keys are
71 * the elements themselves.
73 * @ingroup unordered_associative_containers
75 * @tparam _Value Type of key objects.
76 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
78 * @tparam _Pred Predicate function object type, defaults to
81 * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
83 * Meets the requirements of a <a href="tables.html#65">container</a>, and
84 * <a href="tables.html#xx">unordered associative container</a>
86 * Base is _Hashtable, dispatched at compile time via template
87 * alias __uset_hashtable.
89 template<class _Value
,
90 class _Hash
= hash
<_Value
>,
91 class _Pred
= std::equal_to
<_Value
>,
92 class _Alloc
= std::allocator
<_Value
> >
95 typedef __uset_hashtable
<_Value
, _Hash
, _Pred
, _Alloc
> _Hashtable
;
102 typedef typename
_Hashtable::key_type key_type
;
103 typedef typename
_Hashtable::value_type value_type
;
104 typedef typename
_Hashtable::hasher hasher
;
105 typedef typename
_Hashtable::key_equal key_equal
;
106 typedef typename
_Hashtable::allocator_type allocator_type
;
110 /// Iterator-related typedefs.
111 typedef typename
_Hashtable::pointer pointer
;
112 typedef typename
_Hashtable::const_pointer const_pointer
;
113 typedef typename
_Hashtable::reference reference
;
114 typedef typename
_Hashtable::const_reference const_reference
;
115 typedef typename
_Hashtable::iterator iterator
;
116 typedef typename
_Hashtable::const_iterator const_iterator
;
117 typedef typename
_Hashtable::local_iterator local_iterator
;
118 typedef typename
_Hashtable::const_local_iterator const_local_iterator
;
119 typedef typename
_Hashtable::size_type size_type
;
120 typedef typename
_Hashtable::difference_type difference_type
;
123 // construct/destroy/copy
125 /// Default constructor.
126 unordered_set() = default;
129 * @brief Default constructor creates no elements.
130 * @param __n Minimal initial number of buckets.
131 * @param __hf A hash functor.
132 * @param __eql A key equality functor.
133 * @param __a An allocator object.
136 unordered_set(size_type __n
,
137 const hasher
& __hf
= hasher(),
138 const key_equal
& __eql
= key_equal(),
139 const allocator_type
& __a
= allocator_type())
140 : _M_h(__n
, __hf
, __eql
, __a
)
144 * @brief Builds an %unordered_set from a range.
145 * @param __first An input iterator.
146 * @param __last An input iterator.
147 * @param __n Minimal initial number of buckets.
148 * @param __hf A hash functor.
149 * @param __eql A key equality functor.
150 * @param __a An allocator object.
152 * Create an %unordered_set consisting of copies of the elements from
153 * [__first,__last). This is linear in N (where N is
154 * distance(__first,__last)).
156 template<typename _InputIterator
>
157 unordered_set(_InputIterator __first
, _InputIterator __last
,
159 const hasher
& __hf
= hasher(),
160 const key_equal
& __eql
= key_equal(),
161 const allocator_type
& __a
= allocator_type())
162 : _M_h(__first
, __last
, __n
, __hf
, __eql
, __a
)
165 /// Copy constructor.
166 unordered_set(const unordered_set
&) = default;
168 /// Move constructor.
169 unordered_set(unordered_set
&&) = default;
172 * @brief Creates an %unordered_set with no elements.
173 * @param __a An allocator object.
176 unordered_set(const allocator_type
& __a
)
181 * @brief Copy constructor with allocator argument.
182 * @param __uset Input %unordered_set to copy.
183 * @param __a An allocator object.
185 unordered_set(const unordered_set
& __uset
,
186 const allocator_type
& __a
)
187 : _M_h(__uset
._M_h
, __a
)
191 * @brief Move constructor with allocator argument.
192 * @param __uset Input %unordered_set to move.
193 * @param __a An allocator object.
195 unordered_set(unordered_set
&& __uset
,
196 const allocator_type
& __a
)
197 : _M_h(std::move(__uset
._M_h
), __a
)
201 * @brief Builds an %unordered_set from an initializer_list.
202 * @param __l An initializer_list.
203 * @param __n Minimal initial number of buckets.
204 * @param __hf A hash functor.
205 * @param __eql A key equality functor.
206 * @param __a An allocator object.
208 * Create an %unordered_set consisting of copies of the elements in the
209 * list. This is linear in N (where N is @a __l.size()).
211 unordered_set(initializer_list
<value_type
> __l
,
213 const hasher
& __hf
= hasher(),
214 const key_equal
& __eql
= key_equal(),
215 const allocator_type
& __a
= allocator_type())
216 : _M_h(__l
, __n
, __hf
, __eql
, __a
)
219 /// Copy assignment operator.
221 operator=(const unordered_set
&) = default;
223 /// Move assignment operator.
225 operator=(unordered_set
&&) = default;
228 * @brief %Unordered_set list assignment operator.
229 * @param __l An initializer_list.
231 * This function fills an %unordered_set with copies of the elements in
232 * the initializer list @a __l.
234 * Note that the assignment completely changes the %unordered_set and
235 * that the resulting %unordered_set's size is the same as the number
236 * of elements assigned. Old data may be lost.
239 operator=(initializer_list
<value_type
> __l
)
245 /// Returns the allocator object with which the %unordered_set was
248 get_allocator() const noexcept
249 { return _M_h
.get_allocator(); }
251 // size and capacity:
253 /// Returns true if the %unordered_set is empty.
255 empty() const noexcept
256 { return _M_h
.empty(); }
258 /// Returns the size of the %unordered_set.
260 size() const noexcept
261 { return _M_h
.size(); }
263 /// Returns the maximum size of the %unordered_set.
265 max_size() const noexcept
266 { return _M_h
.max_size(); }
272 * Returns a read-only (constant) iterator that points to the first
273 * element in the %unordered_set.
277 { return _M_h
.begin(); }
280 begin() const noexcept
281 { return _M_h
.begin(); }
286 * Returns a read-only (constant) iterator that points one past the last
287 * element in the %unordered_set.
291 { return _M_h
.end(); }
295 { return _M_h
.end(); }
299 * Returns a read-only (constant) iterator that points to the first
300 * element in the %unordered_set.
303 cbegin() const noexcept
304 { return _M_h
.begin(); }
307 * Returns a read-only (constant) iterator that points one past the last
308 * element in the %unordered_set.
311 cend() const noexcept
312 { return _M_h
.end(); }
317 * @brief Attempts to build and insert an element into the
319 * @param __args Arguments used to generate an element.
320 * @return A pair, of which the first element is an iterator that points
321 * to the possibly inserted element, and the second is a bool
322 * that is true if the element was actually inserted.
324 * This function attempts to build and insert an element into the
325 * %unordered_set. An %unordered_set relies on unique keys and thus an
326 * element is only inserted if it is not already present in the
329 * Insertion requires amortized constant time.
331 template<typename
... _Args
>
332 std::pair
<iterator
, bool>
333 emplace(_Args
&&... __args
)
334 { return _M_h
.emplace(std::forward
<_Args
>(__args
)...); }
337 * @brief Attempts to insert an element into the %unordered_set.
338 * @param __pos An iterator that serves as a hint as to where the
339 * element should be inserted.
340 * @param __args Arguments used to generate the element to be
342 * @return An iterator that points to the element with key equivalent to
343 * the one generated from @a __args (may or may not be the
346 * This function is not concerned about whether the insertion took place,
347 * and thus does not return a boolean like the single-argument emplace()
348 * does. Note that the first parameter is only a hint and can
349 * potentially improve the performance of the insertion process. A bad
350 * hint would cause no gains in efficiency.
352 * For more on @a hinting, see:
353 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
355 * Insertion requires amortized constant time.
357 template<typename
... _Args
>
359 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
360 { return _M_h
.emplace_hint(__pos
, std::forward
<_Args
>(__args
)...); }
364 * @brief Attempts to insert an element into the %unordered_set.
365 * @param __x Element to be inserted.
366 * @return A pair, of which the first element is an iterator that points
367 * to the possibly inserted element, and the second is a bool
368 * that is true if the element was actually inserted.
370 * This function attempts to insert an element into the %unordered_set.
371 * An %unordered_set relies on unique keys and thus an element is only
372 * inserted if it is not already present in the %unordered_set.
374 * Insertion requires amortized constant time.
376 std::pair
<iterator
, bool>
377 insert(const value_type
& __x
)
378 { return _M_h
.insert(__x
); }
380 std::pair
<iterator
, bool>
381 insert(value_type
&& __x
)
382 { return _M_h
.insert(std::move(__x
)); }
387 * @brief Attempts to insert an element into the %unordered_set.
388 * @param __hint An iterator that serves as a hint as to where the
389 * element should be inserted.
390 * @param __x Element to be inserted.
391 * @return An iterator that points to the element with key of
392 * @a __x (may or may not be the element passed in).
394 * This function is not concerned about whether the insertion took place,
395 * and thus does not return a boolean like the single-argument insert()
396 * does. Note that the first parameter is only a hint and can
397 * potentially improve the performance of the insertion process. A bad
398 * hint would cause no gains in efficiency.
400 * For more on @a hinting, see:
401 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
403 * Insertion requires amortized constant.
406 insert(const_iterator __hint
, const value_type
& __x
)
407 { return _M_h
.insert(__hint
, __x
); }
410 insert(const_iterator __hint
, value_type
&& __x
)
411 { return _M_h
.insert(__hint
, std::move(__x
)); }
415 * @brief A template function that attempts to insert a range of
417 * @param __first Iterator pointing to the start of the range to be
419 * @param __last Iterator pointing to the end of the range.
421 * Complexity similar to that of the range constructor.
423 template<typename _InputIterator
>
425 insert(_InputIterator __first
, _InputIterator __last
)
426 { _M_h
.insert(__first
, __last
); }
429 * @brief Attempts to insert a list of elements into the %unordered_set.
430 * @param __l A std::initializer_list<value_type> of elements
433 * Complexity similar to that of the range constructor.
436 insert(initializer_list
<value_type
> __l
)
437 { _M_h
.insert(__l
); }
441 * @brief Erases an element from an %unordered_set.
442 * @param __position An iterator pointing to the element to be erased.
443 * @return An iterator pointing to the element immediately following
444 * @a __position prior to the element being erased. If no such
445 * element exists, end() is returned.
447 * This function erases an element, pointed to by the given iterator,
448 * from an %unordered_set. Note that this function only erases the
449 * element, and that if the element is itself a pointer, the pointed-to
450 * memory is not touched in any way. Managing the pointer is the user's
454 erase(const_iterator __position
)
455 { return _M_h
.erase(__position
); }
459 erase(iterator __position
)
460 { return _M_h
.erase(__position
); }
464 * @brief Erases elements according to the provided key.
465 * @param __x Key of element to be erased.
466 * @return The number of elements erased.
468 * This function erases all the elements located by the given key from
469 * an %unordered_set. For an %unordered_set the result of this function
470 * can only be 0 (not present) or 1 (present).
471 * Note that this function only erases the element, and that if
472 * the element is itself a pointer, the pointed-to memory is not touched
473 * in any way. Managing the pointer is the user's responsibility.
476 erase(const key_type
& __x
)
477 { return _M_h
.erase(__x
); }
480 * @brief Erases a [__first,__last) range of elements from an
482 * @param __first Iterator pointing to the start of the range to be
484 * @param __last Iterator pointing to the end of the range to
486 * @return The iterator @a __last.
488 * This function erases a sequence of elements from an %unordered_set.
489 * Note that this function only erases the element, and that if
490 * the element is itself a pointer, the pointed-to memory is not touched
491 * in any way. Managing the pointer is the user's responsibility.
494 erase(const_iterator __first
, const_iterator __last
)
495 { return _M_h
.erase(__first
, __last
); }
498 * Erases all elements in an %unordered_set. Note that this function only
499 * erases the elements, and that if the elements themselves are pointers,
500 * the pointed-to memory is not touched in any way. Managing the pointer
501 * is the user's responsibility.
508 * @brief Swaps data with another %unordered_set.
509 * @param __x An %unordered_set of the same element and allocator
512 * This exchanges the elements between two sets in constant time.
513 * Note that the global std::swap() function is specialized such that
514 * std::swap(s1,s2) will feed to this function.
517 swap(unordered_set
& __x
)
518 noexcept( noexcept(_M_h
.swap(__x
._M_h
)) )
519 { _M_h
.swap(__x
._M_h
); }
523 /// Returns the hash functor object with which the %unordered_set was
526 hash_function() const
527 { return _M_h
.hash_function(); }
529 /// Returns the key comparison object with which the %unordered_set was
533 { return _M_h
.key_eq(); }
539 * @brief Tries to locate an element in an %unordered_set.
540 * @param __x Element to be located.
541 * @return Iterator pointing to sought-after element, or end() if not
544 * This function takes a key and tries to locate the element with which
545 * the key matches. If successful the function returns an iterator
546 * pointing to the sought after element. If unsuccessful it returns the
547 * past-the-end ( @c end() ) iterator.
550 find(const key_type
& __x
)
551 { return _M_h
.find(__x
); }
554 find(const key_type
& __x
) const
555 { return _M_h
.find(__x
); }
559 * @brief Finds the number of elements.
560 * @param __x Element to located.
561 * @return Number of elements with specified key.
563 * This function only makes sense for unordered_multisets; for
564 * unordered_set the result will either be 0 (not present) or 1
568 count(const key_type
& __x
) const
569 { return _M_h
.count(__x
); }
573 * @brief Finds a subsequence matching given key.
574 * @param __x Key to be located.
575 * @return Pair of iterators that possibly points to the subsequence
576 * matching given key.
578 * This function probably only makes sense for multisets.
580 std::pair
<iterator
, iterator
>
581 equal_range(const key_type
& __x
)
582 { return _M_h
.equal_range(__x
); }
584 std::pair
<const_iterator
, const_iterator
>
585 equal_range(const key_type
& __x
) const
586 { return _M_h
.equal_range(__x
); }
591 /// Returns the number of buckets of the %unordered_set.
593 bucket_count() const noexcept
594 { return _M_h
.bucket_count(); }
596 /// Returns the maximum number of buckets of the %unordered_set.
598 max_bucket_count() const noexcept
599 { return _M_h
.max_bucket_count(); }
602 * @brief Returns the number of elements in a given bucket.
603 * @param __n A bucket index.
604 * @return The number of elements in the bucket.
607 bucket_size(size_type __n
) const
608 { return _M_h
.bucket_size(__n
); }
611 * @brief Returns the bucket index of a given element.
612 * @param __key A key instance.
613 * @return The key bucket index.
616 bucket(const key_type
& __key
) const
617 { return _M_h
.bucket(__key
); }
621 * @brief Returns a read-only (constant) iterator pointing to the first
623 * @param __n The bucket index.
624 * @return A read-only local iterator.
628 { return _M_h
.begin(__n
); }
631 begin(size_type __n
) const
632 { return _M_h
.begin(__n
); }
635 cbegin(size_type __n
) const
636 { return _M_h
.cbegin(__n
); }
641 * @brief Returns a read-only (constant) iterator pointing to one past
642 * the last bucket elements.
643 * @param __n The bucket index.
644 * @return A read-only local iterator.
648 { return _M_h
.end(__n
); }
651 end(size_type __n
) const
652 { return _M_h
.end(__n
); }
655 cend(size_type __n
) const
656 { return _M_h
.cend(__n
); }
661 /// Returns the average number of elements per bucket.
663 load_factor() const noexcept
664 { return _M_h
.load_factor(); }
666 /// Returns a positive number that the %unordered_set tries to keep the
667 /// load factor less than or equal to.
669 max_load_factor() const noexcept
670 { return _M_h
.max_load_factor(); }
673 * @brief Change the %unordered_set maximum load factor.
674 * @param __z The new maximum load factor.
677 max_load_factor(float __z
)
678 { _M_h
.max_load_factor(__z
); }
681 * @brief May rehash the %unordered_set.
682 * @param __n The new number of buckets.
684 * Rehash will occur only if the new number of buckets respect the
685 * %unordered_set maximum load factor.
688 rehash(size_type __n
)
689 { _M_h
.rehash(__n
); }
692 * @brief Prepare the %unordered_set for a specified number of
694 * @param __n Number of elements required.
696 * Same as rehash(ceil(n / max_load_factor())).
699 reserve(size_type __n
)
700 { _M_h
.reserve(__n
); }
702 template<typename _Value1
, typename _Hash1
, typename _Pred1
,
705 operator==(const unordered_set
<_Value1
, _Hash1
, _Pred1
, _Alloc1
>&,
706 const unordered_set
<_Value1
, _Hash1
, _Pred1
, _Alloc1
>&);
710 * @brief A standard container composed of equivalent keys
711 * (possibly containing multiple of each key value) in which the
712 * elements' keys are the elements themselves.
714 * @ingroup unordered_associative_containers
716 * @tparam _Value Type of key objects.
717 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
718 * @tparam _Pred Predicate function object type, defaults
719 * to equal_to<_Value>.
720 * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
722 * Meets the requirements of a <a href="tables.html#65">container</a>, and
723 * <a href="tables.html#xx">unordered associative container</a>
725 * Base is _Hashtable, dispatched at compile time via template
726 * alias __umset_hashtable.
728 template<class _Value
,
729 class _Hash
= hash
<_Value
>,
730 class _Pred
= std::equal_to
<_Value
>,
731 class _Alloc
= std::allocator
<_Value
> >
732 class unordered_multiset
734 typedef __umset_hashtable
<_Value
, _Hash
, _Pred
, _Alloc
> _Hashtable
;
741 typedef typename
_Hashtable::key_type key_type
;
742 typedef typename
_Hashtable::value_type value_type
;
743 typedef typename
_Hashtable::hasher hasher
;
744 typedef typename
_Hashtable::key_equal key_equal
;
745 typedef typename
_Hashtable::allocator_type allocator_type
;
749 /// Iterator-related typedefs.
750 typedef typename
_Hashtable::pointer pointer
;
751 typedef typename
_Hashtable::const_pointer const_pointer
;
752 typedef typename
_Hashtable::reference reference
;
753 typedef typename
_Hashtable::const_reference const_reference
;
754 typedef typename
_Hashtable::iterator iterator
;
755 typedef typename
_Hashtable::const_iterator const_iterator
;
756 typedef typename
_Hashtable::local_iterator local_iterator
;
757 typedef typename
_Hashtable::const_local_iterator const_local_iterator
;
758 typedef typename
_Hashtable::size_type size_type
;
759 typedef typename
_Hashtable::difference_type difference_type
;
762 // construct/destroy/copy
764 /// Default constructor.
765 unordered_multiset() = default;
768 * @brief Default constructor creates no elements.
769 * @param __n Minimal initial number of buckets.
770 * @param __hf A hash functor.
771 * @param __eql A key equality functor.
772 * @param __a An allocator object.
775 unordered_multiset(size_type __n
,
776 const hasher
& __hf
= hasher(),
777 const key_equal
& __eql
= key_equal(),
778 const allocator_type
& __a
= allocator_type())
779 : _M_h(__n
, __hf
, __eql
, __a
)
783 * @brief Builds an %unordered_multiset from a range.
784 * @param __first An input iterator.
785 * @param __last An input iterator.
786 * @param __n Minimal initial number of buckets.
787 * @param __hf A hash functor.
788 * @param __eql A key equality functor.
789 * @param __a An allocator object.
791 * Create an %unordered_multiset consisting of copies of the elements
792 * from [__first,__last). This is linear in N (where N is
793 * distance(__first,__last)).
795 template<typename _InputIterator
>
796 unordered_multiset(_InputIterator __first
, _InputIterator __last
,
798 const hasher
& __hf
= hasher(),
799 const key_equal
& __eql
= key_equal(),
800 const allocator_type
& __a
= allocator_type())
801 : _M_h(__first
, __last
, __n
, __hf
, __eql
, __a
)
804 /// Copy constructor.
805 unordered_multiset(const unordered_multiset
&) = default;
807 /// Move constructor.
808 unordered_multiset(unordered_multiset
&&) = default;
811 * @brief Builds an %unordered_multiset from an initializer_list.
812 * @param __l An initializer_list.
813 * @param __n Minimal initial number of buckets.
814 * @param __hf A hash functor.
815 * @param __eql A key equality functor.
816 * @param __a An allocator object.
818 * Create an %unordered_multiset consisting of copies of the elements in
819 * the list. This is linear in N (where N is @a __l.size()).
821 unordered_multiset(initializer_list
<value_type
> __l
,
823 const hasher
& __hf
= hasher(),
824 const key_equal
& __eql
= key_equal(),
825 const allocator_type
& __a
= allocator_type())
826 : _M_h(__l
, __n
, __hf
, __eql
, __a
)
829 /// Copy assignment operator.
831 operator=(const unordered_multiset
&) = default;
833 /// Move assignment operator.
835 operator=(unordered_multiset
&&) = default;
838 * @brief Creates an %unordered_multiset with no elements.
839 * @param __a An allocator object.
842 unordered_multiset(const allocator_type
& __a
)
847 * @brief Copy constructor with allocator argument.
848 * @param __uset Input %unordered_multiset to copy.
849 * @param __a An allocator object.
851 unordered_multiset(const unordered_multiset
& __umset
,
852 const allocator_type
& __a
)
853 : _M_h(__umset
._M_h
, __a
)
857 * @brief Move constructor with allocator argument.
858 * @param __umset Input %unordered_multiset to move.
859 * @param __a An allocator object.
861 unordered_multiset(unordered_multiset
&& __umset
,
862 const allocator_type
& __a
)
863 : _M_h(std::move(__umset
._M_h
), __a
)
867 * @brief %Unordered_multiset list assignment operator.
868 * @param __l An initializer_list.
870 * This function fills an %unordered_multiset with copies of the elements
871 * in the initializer list @a __l.
873 * Note that the assignment completely changes the %unordered_multiset
874 * and that the resulting %unordered_set's size is the same as the number
875 * of elements assigned. Old data may be lost.
878 operator=(initializer_list
<value_type
> __l
)
884 /// Returns the allocator object with which the %unordered_multiset was
887 get_allocator() const noexcept
888 { return _M_h
.get_allocator(); }
890 // size and capacity:
892 /// Returns true if the %unordered_multiset is empty.
894 empty() const noexcept
895 { return _M_h
.empty(); }
897 /// Returns the size of the %unordered_multiset.
899 size() const noexcept
900 { return _M_h
.size(); }
902 /// Returns the maximum size of the %unordered_multiset.
904 max_size() const noexcept
905 { return _M_h
.max_size(); }
911 * Returns a read-only (constant) iterator that points to the first
912 * element in the %unordered_multiset.
916 { return _M_h
.begin(); }
919 begin() const noexcept
920 { return _M_h
.begin(); }
925 * Returns a read-only (constant) iterator that points one past the last
926 * element in the %unordered_multiset.
930 { return _M_h
.end(); }
934 { return _M_h
.end(); }
938 * Returns a read-only (constant) iterator that points to the first
939 * element in the %unordered_multiset.
942 cbegin() const noexcept
943 { return _M_h
.begin(); }
946 * Returns a read-only (constant) iterator that points one past the last
947 * element in the %unordered_multiset.
950 cend() const noexcept
951 { return _M_h
.end(); }
956 * @brief Builds and insert an element into the %unordered_multiset.
957 * @param __args Arguments used to generate an element.
958 * @return An iterator that points to the inserted element.
960 * Insertion requires amortized constant time.
962 template<typename
... _Args
>
964 emplace(_Args
&&... __args
)
965 { return _M_h
.emplace(std::forward
<_Args
>(__args
)...); }
968 * @brief Inserts an element into the %unordered_multiset.
969 * @param __pos An iterator that serves as a hint as to where the
970 * element should be inserted.
971 * @param __args Arguments used to generate the element to be
973 * @return An iterator that points to the inserted element.
975 * Note that the first parameter is only a hint and can potentially
976 * improve the performance of the insertion process. A bad hint would
977 * cause no gains in efficiency.
979 * For more on @a hinting, see:
980 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
982 * Insertion requires amortized constant time.
984 template<typename
... _Args
>
986 emplace_hint(const_iterator __pos
, _Args
&&... __args
)
987 { return _M_h
.emplace_hint(__pos
, std::forward
<_Args
>(__args
)...); }
991 * @brief Inserts an element into the %unordered_multiset.
992 * @param __x Element to be inserted.
993 * @return An iterator that points to the inserted element.
995 * Insertion requires amortized constant time.
998 insert(const value_type
& __x
)
999 { return _M_h
.insert(__x
); }
1002 insert(value_type
&& __x
)
1003 { return _M_h
.insert(std::move(__x
)); }
1008 * @brief Inserts an element into the %unordered_multiset.
1009 * @param __hint An iterator that serves as a hint as to where the
1010 * element should be inserted.
1011 * @param __x Element to be inserted.
1012 * @return An iterator that points to the inserted element.
1014 * Note that the first parameter is only a hint and can potentially
1015 * improve the performance of the insertion process. A bad hint would
1016 * cause no gains in efficiency.
1018 * For more on @a hinting, see:
1019 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1021 * Insertion requires amortized constant.
1024 insert(const_iterator __hint
, const value_type
& __x
)
1025 { return _M_h
.insert(__hint
, __x
); }
1028 insert(const_iterator __hint
, value_type
&& __x
)
1029 { return _M_h
.insert(__hint
, std::move(__x
)); }
1033 * @brief A template function that inserts a range of elements.
1034 * @param __first Iterator pointing to the start of the range to be
1036 * @param __last Iterator pointing to the end of the range.
1038 * Complexity similar to that of the range constructor.
1040 template<typename _InputIterator
>
1042 insert(_InputIterator __first
, _InputIterator __last
)
1043 { _M_h
.insert(__first
, __last
); }
1046 * @brief Inserts a list of elements into the %unordered_multiset.
1047 * @param __l A std::initializer_list<value_type> of elements to be
1050 * Complexity similar to that of the range constructor.
1053 insert(initializer_list
<value_type
> __l
)
1054 { _M_h
.insert(__l
); }
1058 * @brief Erases an element from an %unordered_multiset.
1059 * @param __position An iterator pointing to the element to be erased.
1060 * @return An iterator pointing to the element immediately following
1061 * @a __position prior to the element being erased. If no such
1062 * element exists, end() is returned.
1064 * This function erases an element, pointed to by the given iterator,
1065 * from an %unordered_multiset.
1067 * Note that this function only erases the element, and that if the
1068 * element is itself a pointer, the pointed-to memory is not touched in
1069 * any way. Managing the pointer is the user's responsibility.
1072 erase(const_iterator __position
)
1073 { return _M_h
.erase(__position
); }
1077 erase(iterator __position
)
1078 { return _M_h
.erase(__position
); }
1083 * @brief Erases elements according to the provided key.
1084 * @param __x Key of element to be erased.
1085 * @return The number of elements erased.
1087 * This function erases all the elements located by the given key from
1088 * an %unordered_multiset.
1090 * Note that this function only erases the element, and that if the
1091 * element is itself a pointer, the pointed-to memory is not touched in
1092 * any way. Managing the pointer is the user's responsibility.
1095 erase(const key_type
& __x
)
1096 { return _M_h
.erase(__x
); }
1099 * @brief Erases a [__first,__last) range of elements from an
1100 * %unordered_multiset.
1101 * @param __first Iterator pointing to the start of the range to be
1103 * @param __last Iterator pointing to the end of the range to
1105 * @return The iterator @a __last.
1107 * This function erases a sequence of elements from an
1108 * %unordered_multiset.
1110 * Note that this function only erases the element, and that if
1111 * the element is itself a pointer, the pointed-to memory is not touched
1112 * in any way. Managing the pointer is the user's responsibility.
1115 erase(const_iterator __first
, const_iterator __last
)
1116 { return _M_h
.erase(__first
, __last
); }
1119 * Erases all elements in an %unordered_multiset.
1121 * Note that this function only erases the elements, and that if the
1122 * elements themselves are pointers, the pointed-to memory is not touched
1123 * in any way. Managing the pointer is the user's responsibility.
1130 * @brief Swaps data with another %unordered_multiset.
1131 * @param __x An %unordered_multiset of the same element and allocator
1134 * This exchanges the elements between two sets in constant time.
1135 * Note that the global std::swap() function is specialized such that
1136 * std::swap(s1,s2) will feed to this function.
1139 swap(unordered_multiset
& __x
)
1140 noexcept( noexcept(_M_h
.swap(__x
._M_h
)) )
1141 { _M_h
.swap(__x
._M_h
); }
1145 /// Returns the hash functor object with which the %unordered_multiset
1146 /// was constructed.
1148 hash_function() const
1149 { return _M_h
.hash_function(); }
1151 /// Returns the key comparison object with which the %unordered_multiset
1152 /// was constructed.
1155 { return _M_h
.key_eq(); }
1161 * @brief Tries to locate an element in an %unordered_multiset.
1162 * @param __x Element to be located.
1163 * @return Iterator pointing to sought-after element, or end() if not
1166 * This function takes a key and tries to locate the element with which
1167 * the key matches. If successful the function returns an iterator
1168 * pointing to the sought after element. If unsuccessful it returns the
1169 * past-the-end ( @c end() ) iterator.
1172 find(const key_type
& __x
)
1173 { return _M_h
.find(__x
); }
1176 find(const key_type
& __x
) const
1177 { return _M_h
.find(__x
); }
1181 * @brief Finds the number of elements.
1182 * @param __x Element to located.
1183 * @return Number of elements with specified key.
1186 count(const key_type
& __x
) const
1187 { return _M_h
.count(__x
); }
1191 * @brief Finds a subsequence matching given key.
1192 * @param __x Key to be located.
1193 * @return Pair of iterators that possibly points to the subsequence
1194 * matching given key.
1196 std::pair
<iterator
, iterator
>
1197 equal_range(const key_type
& __x
)
1198 { return _M_h
.equal_range(__x
); }
1200 std::pair
<const_iterator
, const_iterator
>
1201 equal_range(const key_type
& __x
) const
1202 { return _M_h
.equal_range(__x
); }
1205 // bucket interface.
1207 /// Returns the number of buckets of the %unordered_multiset.
1209 bucket_count() const noexcept
1210 { return _M_h
.bucket_count(); }
1212 /// Returns the maximum number of buckets of the %unordered_multiset.
1214 max_bucket_count() const noexcept
1215 { return _M_h
.max_bucket_count(); }
1218 * @brief Returns the number of elements in a given bucket.
1219 * @param __n A bucket index.
1220 * @return The number of elements in the bucket.
1223 bucket_size(size_type __n
) const
1224 { return _M_h
.bucket_size(__n
); }
1227 * @brief Returns the bucket index of a given element.
1228 * @param __key A key instance.
1229 * @return The key bucket index.
1232 bucket(const key_type
& __key
) const
1233 { return _M_h
.bucket(__key
); }
1237 * @brief Returns a read-only (constant) iterator pointing to the first
1239 * @param __n The bucket index.
1240 * @return A read-only local iterator.
1243 begin(size_type __n
)
1244 { return _M_h
.begin(__n
); }
1246 const_local_iterator
1247 begin(size_type __n
) const
1248 { return _M_h
.begin(__n
); }
1250 const_local_iterator
1251 cbegin(size_type __n
) const
1252 { return _M_h
.cbegin(__n
); }
1257 * @brief Returns a read-only (constant) iterator pointing to one past
1258 * the last bucket elements.
1259 * @param __n The bucket index.
1260 * @return A read-only local iterator.
1264 { return _M_h
.end(__n
); }
1266 const_local_iterator
1267 end(size_type __n
) const
1268 { return _M_h
.end(__n
); }
1270 const_local_iterator
1271 cend(size_type __n
) const
1272 { return _M_h
.cend(__n
); }
1277 /// Returns the average number of elements per bucket.
1279 load_factor() const noexcept
1280 { return _M_h
.load_factor(); }
1282 /// Returns a positive number that the %unordered_multiset tries to keep the
1283 /// load factor less than or equal to.
1285 max_load_factor() const noexcept
1286 { return _M_h
.max_load_factor(); }
1289 * @brief Change the %unordered_multiset maximum load factor.
1290 * @param __z The new maximum load factor.
1293 max_load_factor(float __z
)
1294 { _M_h
.max_load_factor(__z
); }
1297 * @brief May rehash the %unordered_multiset.
1298 * @param __n The new number of buckets.
1300 * Rehash will occur only if the new number of buckets respect the
1301 * %unordered_multiset maximum load factor.
1304 rehash(size_type __n
)
1305 { _M_h
.rehash(__n
); }
1308 * @brief Prepare the %unordered_multiset for a specified number of
1310 * @param __n Number of elements required.
1312 * Same as rehash(ceil(n / max_load_factor())).
1315 reserve(size_type __n
)
1316 { _M_h
.reserve(__n
); }
1318 template<typename _Value1
, typename _Hash1
, typename _Pred1
,
1321 operator==(const unordered_multiset
<_Value1
, _Hash1
, _Pred1
, _Alloc1
>&,
1322 const unordered_multiset
<_Value1
, _Hash1
, _Pred1
, _Alloc1
>&);
1325 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
1327 swap(unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
1328 unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
1331 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
1333 swap(unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
1334 unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
1337 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
1339 operator==(const unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
1340 const unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
1341 { return __x
._M_h
._M_equal(__y
._M_h
); }
1343 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
1345 operator!=(const unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
1346 const unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
1347 { return !(__x
== __y
); }
1349 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
1351 operator==(const unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
1352 const unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
1353 { return __x
._M_h
._M_equal(__y
._M_h
); }
1355 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
1357 operator!=(const unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
1358 const unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
1359 { return !(__x
== __y
); }
1361 _GLIBCXX_END_NAMESPACE_CONTAINER
1364 #endif /* _UNORDERED_SET_H */