libstdc++
unordered_set.h
Go to the documentation of this file.
1// unordered_set implementation -*- C++ -*-
2
3// Copyright (C) 2010-2025 Free Software Foundation, Inc.
4//
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)
9// any later version.
10
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.
15
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.
19
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/>.
24
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}
28 */
29
30#ifndef _UNORDERED_SET_H
31#define _UNORDERED_SET_H
32
33#include <bits/hashtable.h>
34#include <bits/allocator.h>
35#include <bits/functional_hash.h> // hash
36#include <bits/stl_function.h> // equal_to
37
38namespace std _GLIBCXX_VISIBILITY(default)
39{
40_GLIBCXX_BEGIN_NAMESPACE_VERSION
41_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
42
43 /// Base types for unordered_set.
44 template<bool _Cache>
45 using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>;
46
47 template<typename _Value,
48 typename _Hash = hash<_Value>,
49 typename _Pred = std::equal_to<_Value>,
50 typename _Alloc = std::allocator<_Value>,
52 using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc,
53 __detail::_Identity, _Pred, _Hash,
54 __detail::_Mod_range_hashing,
55 __detail::_Default_ranged_hash,
56 __detail::_Prime_rehash_policy, _Tr>;
57
58 /// Base types for unordered_multiset.
59 template<bool _Cache>
60 using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>;
61
62 template<typename _Value,
63 typename _Hash = hash<_Value>,
64 typename _Pred = std::equal_to<_Value>,
65 typename _Alloc = std::allocator<_Value>,
67 using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc,
68 __detail::_Identity,
69 _Pred, _Hash,
70 __detail::_Mod_range_hashing,
71 __detail::_Default_ranged_hash,
72 __detail::_Prime_rehash_policy, _Tr>;
73
74 template<class _Value, class _Hash, class _Pred, class _Alloc>
76
77 /**
78 * @brief A standard container composed of unique keys (containing
79 * at most one of each key value) in which the elements' keys are
80 * the elements themselves.
81 *
82 * @ingroup unordered_associative_containers
83 * @headerfile unordered_set
84 * @since C++11
85 *
86 * @tparam _Value Type of key objects.
87 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
88
89 * @tparam _Pred Predicate function object type, defaults to
90 * equal_to<_Value>.
91 *
92 * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
93 *
94 * Meets the requirements of a <a href="tables.html#65">container</a>, and
95 * <a href="tables.html#xx">unordered associative container</a>
96 *
97 * Base is _Hashtable, dispatched at compile time via template
98 * alias __uset_hashtable.
99 */
100 template<typename _Value,
101 typename _Hash = hash<_Value>,
102 typename _Pred = equal_to<_Value>,
103 typename _Alloc = allocator<_Value>>
105 {
106 typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
107 _Hashtable _M_h;
108
109 public:
110 // typedefs:
111 ///@{
112 /// Public typedefs.
113 typedef typename _Hashtable::key_type key_type;
114 typedef typename _Hashtable::value_type value_type;
115 typedef typename _Hashtable::hasher hasher;
116 typedef typename _Hashtable::key_equal key_equal;
117 typedef typename _Hashtable::allocator_type allocator_type;
118 ///@}
119
120 ///@{
121 /// Iterator-related typedefs.
122 typedef typename _Hashtable::pointer pointer;
123 typedef typename _Hashtable::const_pointer const_pointer;
124 typedef typename _Hashtable::reference reference;
125 typedef typename _Hashtable::const_reference const_reference;
126 typedef typename _Hashtable::iterator iterator;
127 typedef typename _Hashtable::const_iterator const_iterator;
128 typedef typename _Hashtable::local_iterator local_iterator;
129 typedef typename _Hashtable::const_local_iterator const_local_iterator;
130 typedef typename _Hashtable::size_type size_type;
131 typedef typename _Hashtable::difference_type difference_type;
132 ///@}
133
134#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
135 using node_type = typename _Hashtable::node_type;
136 using insert_return_type = typename _Hashtable::insert_return_type;
137#endif
138
139 // construct/destroy/copy
140
141 /// Default constructor.
142 unordered_set() = default;
143
144 /**
145 * @brief Default constructor creates no elements.
146 * @param __n Minimal initial number of buckets.
147 * @param __hf A hash functor.
148 * @param __eql A key equality functor.
149 * @param __a An allocator object.
150 */
151 explicit
153 const hasher& __hf = hasher(),
154 const key_equal& __eql = key_equal(),
155 const allocator_type& __a = allocator_type())
156 : _M_h(__n, __hf, __eql, __a)
157 { }
158
159 /**
160 * @brief Builds an %unordered_set from a range.
161 * @param __first An input iterator.
162 * @param __last An input iterator.
163 * @param __n Minimal initial number of buckets.
164 * @param __hf A hash functor.
165 * @param __eql A key equality functor.
166 * @param __a An allocator object.
167 *
168 * Create an %unordered_set consisting of copies of the elements from
169 * [__first,__last). This is linear in N (where N is
170 * distance(__first,__last)).
171 */
172 template<typename _InputIterator>
173 unordered_set(_InputIterator __first, _InputIterator __last,
174 size_type __n = 0,
175 const hasher& __hf = hasher(),
176 const key_equal& __eql = key_equal(),
177 const allocator_type& __a = allocator_type())
178 : _M_h(__first, __last, __n, __hf, __eql, __a)
179 { }
180
181 /// Copy constructor.
182 unordered_set(const unordered_set&) = default;
183
184 /// Move constructor.
186
187 /**
188 * @brief Creates an %unordered_set with no elements.
189 * @param __a An allocator object.
190 */
191 explicit
193 : _M_h(__a)
194 { }
195
196 /*
197 * @brief Copy constructor with allocator argument.
198 * @param __uset Input %unordered_set to copy.
199 * @param __a An allocator object.
200 */
201 unordered_set(const unordered_set& __uset,
202 const allocator_type& __a)
203 : _M_h(__uset._M_h, __a)
204 { }
205
206 /*
207 * @brief Move constructor with allocator argument.
208 * @param __uset Input %unordered_set to move.
209 * @param __a An allocator object.
210 */
211 unordered_set(unordered_set&& __uset,
212 const allocator_type& __a)
213 noexcept( noexcept(_Hashtable(std::move(__uset._M_h), __a)) )
214 : _M_h(std::move(__uset._M_h), __a)
215 { }
216
217 /**
218 * @brief Builds an %unordered_set from an initializer_list.
219 * @param __l An initializer_list.
220 * @param __n Minimal initial number of buckets.
221 * @param __hf A hash functor.
222 * @param __eql A key equality functor.
223 * @param __a An allocator object.
224 *
225 * Create an %unordered_set consisting of copies of the elements in the
226 * list. This is linear in N (where N is @a __l.size()).
227 */
229 size_type __n = 0,
230 const hasher& __hf = hasher(),
231 const key_equal& __eql = key_equal(),
232 const allocator_type& __a = allocator_type())
233 : _M_h(__l, __n, __hf, __eql, __a)
234 { }
235
236 unordered_set(size_type __n, const allocator_type& __a)
237 : unordered_set(__n, hasher(), key_equal(), __a)
238 { }
239
240 unordered_set(size_type __n, const hasher& __hf,
241 const allocator_type& __a)
242 : unordered_set(__n, __hf, key_equal(), __a)
243 { }
244
245 template<typename _InputIterator>
246 unordered_set(_InputIterator __first, _InputIterator __last,
247 size_type __n,
248 const allocator_type& __a)
249 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
250 { }
251
252 template<typename _InputIterator>
253 unordered_set(_InputIterator __first, _InputIterator __last,
254 size_type __n, const hasher& __hf,
255 const allocator_type& __a)
256 : unordered_set(__first, __last, __n, __hf, key_equal(), __a)
257 { }
258
259 unordered_set(initializer_list<value_type> __l,
260 size_type __n,
261 const allocator_type& __a)
262 : unordered_set(__l, __n, hasher(), key_equal(), __a)
263 { }
264
265 unordered_set(initializer_list<value_type> __l,
266 size_type __n, const hasher& __hf,
267 const allocator_type& __a)
268 : unordered_set(__l, __n, __hf, key_equal(), __a)
269 { }
270
271 /// Copy assignment operator.
273 operator=(const unordered_set&) = default;
274
275 /// Move assignment operator.
278
279 /**
280 * @brief %Unordered_set list assignment operator.
281 * @param __l An initializer_list.
282 *
283 * This function fills an %unordered_set with copies of the elements in
284 * the initializer list @a __l.
285 *
286 * Note that the assignment completely changes the %unordered_set and
287 * that the resulting %unordered_set's size is the same as the number
288 * of elements assigned.
289 */
292 {
293 _M_h = __l;
294 return *this;
295 }
296
297 /// Returns the allocator object used by the %unordered_set.
298 allocator_type
299 get_allocator() const noexcept
300 { return _M_h.get_allocator(); }
301
302 // size and capacity:
303
304 /// Returns true if the %unordered_set is empty.
305 _GLIBCXX_NODISCARD bool
306 empty() const noexcept
307 { return _M_h.empty(); }
308
309 /// Returns the size of the %unordered_set.
311 size() const noexcept
312 { return _M_h.size(); }
313
314 /// Returns the maximum size of the %unordered_set.
316 max_size() const noexcept
317 { return _M_h.max_size(); }
318
319 // iterators.
320
321 ///@{
322 /**
323 * Returns a read-only (constant) iterator that points to the first
324 * element in the %unordered_set.
325 */
327 begin() noexcept
328 { return _M_h.begin(); }
329
330 const_iterator
331 begin() const noexcept
332 { return _M_h.begin(); }
333 ///@}
334
335 ///@{
336 /**
337 * Returns a read-only (constant) iterator that points one past the last
338 * element in the %unordered_set.
339 */
341 end() noexcept
342 { return _M_h.end(); }
343
344 const_iterator
345 end() const noexcept
346 { return _M_h.end(); }
347 ///@}
348
349 /**
350 * Returns a read-only (constant) iterator that points to the first
351 * element in the %unordered_set.
352 */
353 const_iterator
354 cbegin() const noexcept
355 { return _M_h.begin(); }
356
357 /**
358 * Returns a read-only (constant) iterator that points one past the last
359 * element in the %unordered_set.
360 */
361 const_iterator
362 cend() const noexcept
363 { return _M_h.end(); }
364
365 // modifiers.
366
367 /**
368 * @brief Attempts to build and insert an element into the
369 * %unordered_set.
370 * @param __args Arguments used to generate an element.
371 * @return A pair, of which the first element is an iterator that points
372 * to the possibly inserted element, and the second is a bool
373 * that is true if the element was actually inserted.
374 *
375 * This function attempts to build and insert an element into the
376 * %unordered_set. An %unordered_set relies on unique keys and thus an
377 * element is only inserted if it is not already present in the
378 * %unordered_set.
379 *
380 * Insertion requires amortized constant time.
381 */
382 template<typename... _Args>
384 emplace(_Args&&... __args)
385 { return _M_h.emplace(std::forward<_Args>(__args)...); }
386
387 /**
388 * @brief Attempts to insert an element into the %unordered_set.
389 * @param __pos An iterator that serves as a hint as to where the
390 * element should be inserted.
391 * @param __args Arguments used to generate the element to be
392 * inserted.
393 * @return An iterator that points to the element with key equivalent to
394 * the one generated from @a __args (may or may not be the
395 * element itself).
396 *
397 * This function is not concerned about whether the insertion took place,
398 * and thus does not return a boolean like the single-argument emplace()
399 * does. Note that the first parameter is only a hint and can
400 * potentially improve the performance of the insertion process. A bad
401 * hint would cause no gains in efficiency.
402 *
403 * For more on @a hinting, see:
404 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
405 *
406 * Insertion requires amortized constant time.
407 */
408 template<typename... _Args>
410 emplace_hint(const_iterator __pos, _Args&&... __args)
411 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
412
413 ///@{
414 /**
415 * @brief Attempts to insert an element into the %unordered_set.
416 * @param __x Element to be inserted.
417 * @return A pair, of which the first element is an iterator that points
418 * to the possibly inserted element, and the second is a bool
419 * that is true if the element was actually inserted.
420 *
421 * This function attempts to insert an element into the %unordered_set.
422 * An %unordered_set relies on unique keys and thus an element is only
423 * inserted if it is not already present in the %unordered_set.
424 *
425 * Insertion requires amortized constant time.
426 */
428 insert(const value_type& __x)
429 { return _M_h.insert(__x); }
430
433 { return _M_h.insert(std::move(__x)); }
434 ///@}
435
436 ///@{
437 /**
438 * @brief Attempts to insert an element into the %unordered_set.
439 * @param __hint An iterator that serves as a hint as to where the
440 * element should be inserted.
441 * @param __x Element to be inserted.
442 * @return An iterator that points to the element with key of
443 * @a __x (may or may not be the element passed in).
444 *
445 * This function is not concerned about whether the insertion took place,
446 * and thus does not return a boolean like the single-argument insert()
447 * does. Note that the first parameter is only a hint and can
448 * potentially improve the performance of the insertion process. A bad
449 * hint would cause no gains in efficiency.
450 *
451 * For more on @a hinting, see:
452 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
453 *
454 * Insertion requires amortized constant.
455 */
457 insert(const_iterator __hint, const value_type& __x)
458 { return _M_h.insert(__hint, __x); }
459
462 { return _M_h.insert(__hint, std::move(__x)); }
463 ///@}
464
465 /**
466 * @brief A template function that attempts to insert a range of
467 * elements.
468 * @param __first Iterator pointing to the start of the range to be
469 * inserted.
470 * @param __last Iterator pointing to the end of the range.
471 *
472 * Complexity similar to that of the range constructor.
473 */
474 template<typename _InputIterator>
475 void
476 insert(_InputIterator __first, _InputIterator __last)
477 { _M_h.insert(__first, __last); }
478
479 /**
480 * @brief Attempts to insert a list of elements into the %unordered_set.
481 * @param __l A std::initializer_list<value_type> of elements
482 * to be inserted.
483 *
484 * Complexity similar to that of the range constructor.
485 */
486 void
488 { _M_h.insert(__l); }
489
490#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
491 /// Extract a node.
492 node_type
493 extract(const_iterator __pos)
494 {
495 __glibcxx_assert(__pos != end());
496 return _M_h.extract(__pos);
497 }
498
499 /// Extract a node.
500 node_type
501 extract(const key_type& __key)
502 { return _M_h.extract(__key); }
503
504 /// Re-insert an extracted node.
505 insert_return_type
506 insert(node_type&& __nh)
507 { return _M_h._M_reinsert_node(std::move(__nh)); }
508
509 /// Re-insert an extracted node.
511 insert(const_iterator, node_type&& __nh)
512 { return _M_h._M_reinsert_node(std::move(__nh)).position; }
513#endif // node_extract
514
515 ///@{
516 /**
517 * @brief Erases an element from an %unordered_set.
518 * @param __position An iterator pointing to the element to be erased.
519 * @return An iterator pointing to the element immediately following
520 * @a __position prior to the element being erased. If no such
521 * element exists, end() is returned.
522 *
523 * This function erases an element, pointed to by the given iterator,
524 * from an %unordered_set. Note that this function only erases the
525 * element, and that if the element is itself a pointer, the pointed-to
526 * memory is not touched in any way. Managing the pointer is the user's
527 * responsibility.
528 */
531 { return _M_h.erase(__position); }
532
533 // LWG 2059.
535 erase(iterator __position)
536 { return _M_h.erase(__position); }
537 ///@}
538
539 /**
540 * @brief Erases elements according to the provided key.
541 * @param __x Key of element to be erased.
542 * @return The number of elements erased.
543 *
544 * This function erases all the elements located by the given key from
545 * an %unordered_set. For an %unordered_set the result of this function
546 * can only be 0 (not present) or 1 (present).
547 * Note that this function only erases the element, and that if
548 * the element is itself a pointer, the pointed-to memory is not touched
549 * in any way. Managing the pointer is the user's responsibility.
550 */
552 erase(const key_type& __x)
553 { return _M_h.erase(__x); }
554
555 /**
556 * @brief Erases a [__first,__last) range of elements from an
557 * %unordered_set.
558 * @param __first Iterator pointing to the start of the range to be
559 * erased.
560 * @param __last Iterator pointing to the end of the range to
561 * be erased.
562 * @return The iterator @a __last.
563 *
564 * This function erases a sequence of elements from an %unordered_set.
565 * Note that this function only erases the element, and that if
566 * the element is itself a pointer, the pointed-to memory is not touched
567 * in any way. Managing the pointer is the user's responsibility.
568 */
571 { return _M_h.erase(__first, __last); }
572
573 /**
574 * Erases all elements in an %unordered_set. Note that this function only
575 * erases the elements, and that if the elements themselves are pointers,
576 * the pointed-to memory is not touched in any way. Managing the pointer
577 * is the user's responsibility.
578 */
579 void
580 clear() noexcept
581 { _M_h.clear(); }
582
583 /**
584 * @brief Swaps data with another %unordered_set.
585 * @param __x An %unordered_set of the same element and allocator
586 * types.
587 *
588 * This exchanges the elements between two sets in constant time.
589 * Note that the global std::swap() function is specialized such that
590 * std::swap(s1,s2) will feed to this function.
591 */
592 void
594 noexcept( noexcept(_M_h.swap(__x._M_h)) )
595 { _M_h.swap(__x._M_h); }
596
597#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
598 template<typename, typename, typename>
599 friend class std::_Hash_merge_helper;
600
601 template<typename _H2, typename _P2>
602 void
604 {
605 if constexpr (is_same_v<_H2, _Hash> && is_same_v<_P2, _Pred>)
606 if (std::__addressof(__source) == this) [[__unlikely__]]
607 return;
608
609 using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
610 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
611 }
612
613 template<typename _H2, typename _P2>
614 void
615 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
616 {
617 using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
618 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
619 }
620
621 template<typename _H2, typename _P2>
622 void
623 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
624 {
625 using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
626 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
627 }
628
629 template<typename _H2, typename _P2>
630 void
631 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
632 { merge(__source); }
633#endif // node_extract
634
635 // observers.
636
637 /// Returns the hash functor object with which the %unordered_set was
638 /// constructed.
639 hasher
641 { return _M_h.hash_function(); }
642
643 /// Returns the key comparison object with which the %unordered_set was
644 /// constructed.
646 key_eq() const
647 { return _M_h.key_eq(); }
648
649 // lookup.
650
651 ///@{
652 /**
653 * @brief Tries to locate an element in an %unordered_set.
654 * @param __x Element to be located.
655 * @return Iterator pointing to sought-after element, or end() if not
656 * found.
657 *
658 * This function takes a key and tries to locate the element with which
659 * the key matches. If successful the function returns an iterator
660 * pointing to the sought after element. If unsuccessful it returns the
661 * past-the-end ( @c end() ) iterator.
662 */
664 find(const key_type& __x)
665 { return _M_h.find(__x); }
666
667#if __cplusplus > 201703L
668 template<typename _Kt>
669 auto
670 find(const _Kt& __k)
671 -> decltype(_M_h._M_find_tr(__k))
672 { return _M_h._M_find_tr(__k); }
673#endif
674
675 const_iterator
676 find(const key_type& __x) const
677 { return _M_h.find(__x); }
678
679#if __cplusplus > 201703L
680 template<typename _Kt>
681 auto
682 find(const _Kt& __k) const
683 -> decltype(_M_h._M_find_tr(__k))
684 { return _M_h._M_find_tr(__k); }
685#endif
686 ///@}
687
688 ///@{
689 /**
690 * @brief Finds the number of elements.
691 * @param __x Element to located.
692 * @return Number of elements with specified key.
693 *
694 * This function only makes sense for unordered_multisets; for
695 * unordered_set the result will either be 0 (not present) or 1
696 * (present).
697 */
699 count(const key_type& __x) const
700 { return _M_h.count(__x); }
701
702#if __cplusplus > 201703L
703 template<typename _Kt>
704 auto
705 count(const _Kt& __k) const
706 -> decltype(_M_h._M_count_tr(__k))
707 { return _M_h._M_count_tr(__k); }
708#endif
709 ///@}
710
711#if __cplusplus > 201703L
712 ///@{
713 /**
714 * @brief Finds whether an element with the given key exists.
715 * @param __x Key of elements to be located.
716 * @return True if there is any element with the specified key.
717 */
718 bool
719 contains(const key_type& __x) const
720 { return _M_h.find(__x) != _M_h.end(); }
721
722 template<typename _Kt>
723 auto
724 contains(const _Kt& __k) const
725 -> decltype(_M_h._M_find_tr(__k), void(), true)
726 { return _M_h._M_find_tr(__k) != _M_h.end(); }
727 ///@}
728#endif
729
730 ///@{
731 /**
732 * @brief Finds a subsequence matching given key.
733 * @param __x Key to be located.
734 * @return Pair of iterators that possibly points to the subsequence
735 * matching given key.
736 *
737 * This function probably only makes sense for multisets.
738 */
741 { return _M_h.equal_range(__x); }
742
743#if __cplusplus > 201703L
744 template<typename _Kt>
745 auto
746 equal_range(const _Kt& __k)
747 -> decltype(_M_h._M_equal_range_tr(__k))
748 { return _M_h._M_equal_range_tr(__k); }
749#endif
750
752 equal_range(const key_type& __x) const
753 { return _M_h.equal_range(__x); }
754
755#if __cplusplus > 201703L
756 template<typename _Kt>
757 auto
758 equal_range(const _Kt& __k) const
759 -> decltype(_M_h._M_equal_range_tr(__k))
760 { return _M_h._M_equal_range_tr(__k); }
761#endif
762 ///@}
763
764 // bucket interface.
765
766 /// Returns the number of buckets of the %unordered_set.
768 bucket_count() const noexcept
769 { return _M_h.bucket_count(); }
770
771 /// Returns the maximum number of buckets of the %unordered_set.
773 max_bucket_count() const noexcept
774 { return _M_h.max_bucket_count(); }
775
776 /*
777 * @brief Returns the number of elements in a given bucket.
778 * @param __n A bucket index.
779 * @return The number of elements in the bucket.
780 */
782 bucket_size(size_type __n) const
783 { return _M_h.bucket_size(__n); }
784
785 /*
786 * @brief Returns the bucket index of a given element.
787 * @param __key A key instance.
788 * @return The key bucket index.
789 */
790 size_type
791 bucket(const key_type& __key) const
792 { return _M_h.bucket(__key); }
793
794 ///@{
795 /**
796 * @brief Returns a read-only (constant) iterator pointing to the first
797 * bucket element.
798 * @param __n The bucket index.
799 * @return A read-only local iterator.
800 */
803 { return _M_h.begin(__n); }
804
806 begin(size_type __n) const
807 { return _M_h.begin(__n); }
808
810 cbegin(size_type __n) const
811 { return _M_h.cbegin(__n); }
812 ///@}
813
814 ///@{
815 /**
816 * @brief Returns a read-only (constant) iterator pointing to one past
817 * the last bucket elements.
818 * @param __n The bucket index.
819 * @return A read-only local iterator.
820 */
823 { return _M_h.end(__n); }
824
826 end(size_type __n) const
827 { return _M_h.end(__n); }
828
830 cend(size_type __n) const
831 { return _M_h.cend(__n); }
832 ///@}
833
834 // hash policy.
835
836 /// Returns the average number of elements per bucket.
837 float
838 load_factor() const noexcept
839 { return _M_h.load_factor(); }
840
841 /// Returns a positive number that the %unordered_set tries to keep the
842 /// load factor less than or equal to.
843 float
844 max_load_factor() const noexcept
845 { return _M_h.max_load_factor(); }
846
847 /**
848 * @brief Change the %unordered_set maximum load factor.
849 * @param __z The new maximum load factor.
850 */
851 void
853 { _M_h.max_load_factor(__z); }
854
855 /**
856 * @brief May rehash the %unordered_set.
857 * @param __n The new number of buckets.
858 *
859 * Rehash will occur only if the new number of buckets respect the
860 * %unordered_set maximum load factor.
861 */
862 void
864 { _M_h.rehash(__n); }
865
866 /**
867 * @brief Prepare the %unordered_set for a specified number of
868 * elements.
869 * @param __n Number of elements required.
870 *
871 * Same as rehash(ceil(n / max_load_factor())).
872 */
873 void
875 { _M_h.reserve(__n); }
876
877 template<typename _Value1, typename _Hash1, typename _Pred1,
878 typename _Alloc1>
879 friend bool
882 };
883
884#if __cpp_deduction_guides >= 201606
885
886 template<typename _InputIterator,
887 typename _Hash =
888 hash<typename iterator_traits<_InputIterator>::value_type>,
889 typename _Pred =
890 equal_to<typename iterator_traits<_InputIterator>::value_type>,
891 typename _Allocator =
892 allocator<typename iterator_traits<_InputIterator>::value_type>,
893 typename = _RequireInputIter<_InputIterator>,
894 typename = _RequireNotAllocatorOrIntegral<_Hash>,
895 typename = _RequireNotAllocator<_Pred>,
896 typename = _RequireAllocator<_Allocator>>
897 unordered_set(_InputIterator, _InputIterator,
898 unordered_set<int>::size_type = {},
899 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
901 _Hash, _Pred, _Allocator>;
902
903 template<typename _Tp, typename _Hash = hash<_Tp>,
904 typename _Pred = equal_to<_Tp>,
905 typename _Allocator = allocator<_Tp>,
906 typename = _RequireNotAllocatorOrIntegral<_Hash>,
907 typename = _RequireNotAllocator<_Pred>,
908 typename = _RequireAllocator<_Allocator>>
911 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
913
914 template<typename _InputIterator, typename _Allocator,
915 typename = _RequireInputIter<_InputIterator>,
916 typename = _RequireAllocator<_Allocator>>
917 unordered_set(_InputIterator, _InputIterator,
920 hash<
922 equal_to<
924 _Allocator>;
925
926 template<typename _InputIterator, typename _Hash, typename _Allocator,
927 typename = _RequireInputIter<_InputIterator>,
928 typename = _RequireNotAllocatorOrIntegral<_Hash>,
929 typename = _RequireAllocator<_Allocator>>
930 unordered_set(_InputIterator, _InputIterator,
932 _Hash, _Allocator)
934 _Hash,
935 equal_to<
937 _Allocator>;
938
939 template<typename _Tp, typename _Allocator,
940 typename = _RequireAllocator<_Allocator>>
944
945 template<typename _Tp, typename _Hash, typename _Allocator,
946 typename = _RequireNotAllocatorOrIntegral<_Hash>,
947 typename = _RequireAllocator<_Allocator>>
949 unordered_set<int>::size_type, _Hash, _Allocator)
951
952#endif
953
954 /**
955 * @brief A standard container composed of equivalent keys
956 * (possibly containing multiple of each key value) in which the
957 * elements' keys are the elements themselves.
958 *
959 * @ingroup unordered_associative_containers
960 * @headerfile unordered_set
961 * @since C++11
962 *
963 * @tparam _Value Type of key objects.
964 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
965 * @tparam _Pred Predicate function object type, defaults
966 * to equal_to<_Value>.
967 * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
968 *
969 * Meets the requirements of a <a href="tables.html#65">container</a>, and
970 * <a href="tables.html#xx">unordered associative container</a>
971 *
972 * Base is _Hashtable, dispatched at compile time via template
973 * alias __umset_hashtable.
974 */
975 template<typename _Value,
976 typename _Hash = hash<_Value>,
977 typename _Pred = equal_to<_Value>,
978 typename _Alloc = allocator<_Value>>
980 {
981 typedef __umset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
982 _Hashtable _M_h;
983
984 public:
985 // typedefs:
986 ///@{
987 /// Public typedefs.
988 typedef typename _Hashtable::key_type key_type;
989 typedef typename _Hashtable::value_type value_type;
990 typedef typename _Hashtable::hasher hasher;
991 typedef typename _Hashtable::key_equal key_equal;
992 typedef typename _Hashtable::allocator_type allocator_type;
993 ///@}
994
995 ///@{
996 /// Iterator-related typedefs.
997 typedef typename _Hashtable::pointer pointer;
998 typedef typename _Hashtable::const_pointer const_pointer;
999 typedef typename _Hashtable::reference reference;
1000 typedef typename _Hashtable::const_reference const_reference;
1001 typedef typename _Hashtable::iterator iterator;
1002 typedef typename _Hashtable::const_iterator const_iterator;
1003 typedef typename _Hashtable::local_iterator local_iterator;
1004 typedef typename _Hashtable::const_local_iterator const_local_iterator;
1005 typedef typename _Hashtable::size_type size_type;
1006 typedef typename _Hashtable::difference_type difference_type;
1007 ///@}
1008
1009#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1010 using node_type = typename _Hashtable::node_type;
1011#endif
1012
1013 // construct/destroy/copy
1014
1015 /// Default constructor.
1017
1018 /**
1019 * @brief Default constructor creates no elements.
1020 * @param __n Minimal initial number of buckets.
1021 * @param __hf A hash functor.
1022 * @param __eql A key equality functor.
1023 * @param __a An allocator object.
1024 */
1025 explicit
1027 const hasher& __hf = hasher(),
1028 const key_equal& __eql = key_equal(),
1029 const allocator_type& __a = allocator_type())
1030 : _M_h(__n, __hf, __eql, __a)
1031 { }
1032
1033 /**
1034 * @brief Builds an %unordered_multiset from a range.
1035 * @param __first An input iterator.
1036 * @param __last An input iterator.
1037 * @param __n Minimal initial number of buckets.
1038 * @param __hf A hash functor.
1039 * @param __eql A key equality functor.
1040 * @param __a An allocator object.
1041 *
1042 * Create an %unordered_multiset consisting of copies of the elements
1043 * from [__first,__last). This is linear in N (where N is
1044 * distance(__first,__last)).
1045 */
1046 template<typename _InputIterator>
1047 unordered_multiset(_InputIterator __first, _InputIterator __last,
1048 size_type __n = 0,
1049 const hasher& __hf = hasher(),
1050 const key_equal& __eql = key_equal(),
1051 const allocator_type& __a = allocator_type())
1052 : _M_h(__first, __last, __n, __hf, __eql, __a)
1053 { }
1054
1055 /// Copy constructor.
1057
1058 /// Move constructor.
1060
1061 /**
1062 * @brief Builds an %unordered_multiset from an initializer_list.
1063 * @param __l An initializer_list.
1064 * @param __n Minimal initial number of buckets.
1065 * @param __hf A hash functor.
1066 * @param __eql A key equality functor.
1067 * @param __a An allocator object.
1068 *
1069 * Create an %unordered_multiset consisting of copies of the elements in
1070 * the list. This is linear in N (where N is @a __l.size()).
1071 */
1073 size_type __n = 0,
1074 const hasher& __hf = hasher(),
1075 const key_equal& __eql = key_equal(),
1076 const allocator_type& __a = allocator_type())
1077 : _M_h(__l, __n, __hf, __eql, __a)
1078 { }
1079
1080 /// Copy assignment operator.
1083
1084 /// Move assignment operator.
1087
1088 /**
1089 * @brief Creates an %unordered_multiset with no elements.
1090 * @param __a An allocator object.
1091 */
1092 explicit
1094 : _M_h(__a)
1095 { }
1096
1097 /*
1098 * @brief Copy constructor with allocator argument.
1099 * @param __uset Input %unordered_multiset to copy.
1100 * @param __a An allocator object.
1101 */
1103 const allocator_type& __a)
1104 : _M_h(__umset._M_h, __a)
1105 { }
1106
1107 /*
1108 * @brief Move constructor with allocator argument.
1109 * @param __umset Input %unordered_multiset to move.
1110 * @param __a An allocator object.
1111 */
1112 unordered_multiset(unordered_multiset&& __umset,
1113 const allocator_type& __a)
1114 noexcept( noexcept(_Hashtable(std::move(__umset._M_h), __a)) )
1115 : _M_h(std::move(__umset._M_h), __a)
1116 { }
1117
1119 : unordered_multiset(__n, hasher(), key_equal(), __a)
1120 { }
1121
1122 unordered_multiset(size_type __n, const hasher& __hf,
1123 const allocator_type& __a)
1124 : unordered_multiset(__n, __hf, key_equal(), __a)
1125 { }
1126
1127 template<typename _InputIterator>
1128 unordered_multiset(_InputIterator __first, _InputIterator __last,
1129 size_type __n,
1130 const allocator_type& __a)
1131 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
1132 { }
1133
1134 template<typename _InputIterator>
1135 unordered_multiset(_InputIterator __first, _InputIterator __last,
1136 size_type __n, const hasher& __hf,
1137 const allocator_type& __a)
1138 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
1139 { }
1140
1141 unordered_multiset(initializer_list<value_type> __l,
1142 size_type __n,
1143 const allocator_type& __a)
1144 : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
1145 { }
1146
1147 unordered_multiset(initializer_list<value_type> __l,
1148 size_type __n, const hasher& __hf,
1149 const allocator_type& __a)
1150 : unordered_multiset(__l, __n, __hf, key_equal(), __a)
1151 { }
1152
1153 /**
1154 * @brief %Unordered_multiset list assignment operator.
1155 * @param __l An initializer_list.
1156 *
1157 * This function fills an %unordered_multiset with copies of the elements
1158 * in the initializer list @a __l.
1159 *
1160 * Note that the assignment completely changes the %unordered_multiset
1161 * and that the resulting %unordered_multiset's size is the same as the
1162 * number of elements assigned.
1163 */
1166 {
1167 _M_h = __l;
1168 return *this;
1169 }
1170
1171 /// Returns the allocator object used by the %unordered_multiset.
1172 allocator_type
1173 get_allocator() const noexcept
1174 { return _M_h.get_allocator(); }
1175
1176 // size and capacity:
1177
1178 /// Returns true if the %unordered_multiset is empty.
1179 _GLIBCXX_NODISCARD bool
1180 empty() const noexcept
1181 { return _M_h.empty(); }
1182
1183 /// Returns the size of the %unordered_multiset.
1184 size_type
1185 size() const noexcept
1186 { return _M_h.size(); }
1187
1188 /// Returns the maximum size of the %unordered_multiset.
1189 size_type
1190 max_size() const noexcept
1191 { return _M_h.max_size(); }
1192
1193 // iterators.
1194
1195 ///@{
1196 /**
1197 * Returns a read-only (constant) iterator that points to the first
1198 * element in the %unordered_multiset.
1199 */
1200 iterator
1201 begin() noexcept
1202 { return _M_h.begin(); }
1203
1204 const_iterator
1205 begin() const noexcept
1206 { return _M_h.begin(); }
1207 ///@}
1208
1209 ///@{
1210 /**
1211 * Returns a read-only (constant) iterator that points one past the last
1212 * element in the %unordered_multiset.
1213 */
1214 iterator
1215 end() noexcept
1216 { return _M_h.end(); }
1217
1218 const_iterator
1219 end() const noexcept
1220 { return _M_h.end(); }
1221 ///@}
1222
1223 /**
1224 * Returns a read-only (constant) iterator that points to the first
1225 * element in the %unordered_multiset.
1226 */
1227 const_iterator
1228 cbegin() const noexcept
1229 { return _M_h.begin(); }
1230
1231 /**
1232 * Returns a read-only (constant) iterator that points one past the last
1233 * element in the %unordered_multiset.
1234 */
1235 const_iterator
1236 cend() const noexcept
1237 { return _M_h.end(); }
1238
1239 // modifiers.
1240
1241 /**
1242 * @brief Builds and insert an element into the %unordered_multiset.
1243 * @param __args Arguments used to generate an element.
1244 * @return An iterator that points to the inserted element.
1245 *
1246 * Insertion requires amortized constant time.
1247 */
1248 template<typename... _Args>
1249 iterator
1250 emplace(_Args&&... __args)
1251 { return _M_h.emplace(std::forward<_Args>(__args)...); }
1252
1253 /**
1254 * @brief Inserts an element into the %unordered_multiset.
1255 * @param __pos An iterator that serves as a hint as to where the
1256 * element should be inserted.
1257 * @param __args Arguments used to generate the element to be
1258 * inserted.
1259 * @return An iterator that points to the inserted element.
1260 *
1261 * Note that the first parameter is only a hint and can potentially
1262 * improve the performance of the insertion process. A bad hint would
1263 * cause no gains in efficiency.
1264 *
1265 * For more on @a hinting, see:
1266 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1267 *
1268 * Insertion requires amortized constant time.
1269 */
1270 template<typename... _Args>
1271 iterator
1272 emplace_hint(const_iterator __pos, _Args&&... __args)
1273 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1274
1275 ///@{
1276 /**
1277 * @brief Inserts an element into the %unordered_multiset.
1278 * @param __x Element to be inserted.
1279 * @return An iterator that points to the inserted element.
1280 *
1281 * Insertion requires amortized constant time.
1282 */
1283 iterator
1284 insert(const value_type& __x)
1285 { return _M_h.insert(__x); }
1286
1287 iterator
1289 { return _M_h.insert(std::move(__x)); }
1290 ///@}
1291
1292 ///@{
1293 /**
1294 * @brief Inserts an element into the %unordered_multiset.
1295 * @param __hint An iterator that serves as a hint as to where the
1296 * element should be inserted.
1297 * @param __x Element to be inserted.
1298 * @return An iterator that points to the inserted element.
1299 *
1300 * Note that the first parameter is only a hint and can potentially
1301 * improve the performance of the insertion process. A bad hint would
1302 * cause no gains in efficiency.
1303 *
1304 * For more on @a hinting, see:
1305 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1306 *
1307 * Insertion requires amortized constant.
1308 */
1309 iterator
1311 { return _M_h.insert(__hint, __x); }
1312
1313 iterator
1315 { return _M_h.insert(__hint, std::move(__x)); }
1316 ///@}
1317
1318 /**
1319 * @brief A template function that inserts a range of elements.
1320 * @param __first Iterator pointing to the start of the range to be
1321 * inserted.
1322 * @param __last Iterator pointing to the end of the range.
1323 *
1324 * Complexity similar to that of the range constructor.
1325 */
1326 template<typename _InputIterator>
1327 void
1328 insert(_InputIterator __first, _InputIterator __last)
1329 { _M_h.insert(__first, __last); }
1330
1331 /**
1332 * @brief Inserts a list of elements into the %unordered_multiset.
1333 * @param __l A std::initializer_list<value_type> of elements to be
1334 * inserted.
1335 *
1336 * Complexity similar to that of the range constructor.
1337 */
1338 void
1340 { _M_h.insert(__l); }
1341
1342#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1343 /// Extract a node.
1344 node_type
1345 extract(const_iterator __pos)
1346 {
1347 __glibcxx_assert(__pos != end());
1348 return _M_h.extract(__pos);
1349 }
1350
1351 /// Extract a node.
1352 node_type
1353 extract(const key_type& __key)
1354 { return _M_h.extract(__key); }
1355
1356 /// Re-insert an extracted node.
1357 iterator
1358 insert(node_type&& __nh)
1359 { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
1360
1361 /// Re-insert an extracted node.
1362 iterator
1363 insert(const_iterator __hint, node_type&& __nh)
1364 { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
1365#endif // node_extract
1366
1367 ///@{
1368 /**
1369 * @brief Erases an element from an %unordered_multiset.
1370 * @param __position An iterator pointing to the element to be erased.
1371 * @return An iterator pointing to the element immediately following
1372 * @a __position prior to the element being erased. If no such
1373 * element exists, end() is returned.
1374 *
1375 * This function erases an element, pointed to by the given iterator,
1376 * from an %unordered_multiset.
1377 *
1378 * Note that this function only erases the element, and that if the
1379 * element is itself a pointer, the pointed-to memory is not touched in
1380 * any way. Managing the pointer is the user's responsibility.
1381 */
1382 iterator
1384 { return _M_h.erase(__position); }
1385
1386 // LWG 2059.
1387 iterator
1388 erase(iterator __position)
1389 { return _M_h.erase(__position); }
1390 ///@}
1391
1392
1393 /**
1394 * @brief Erases elements according to the provided key.
1395 * @param __x Key of element to be erased.
1396 * @return The number of elements erased.
1397 *
1398 * This function erases all the elements located by the given key from
1399 * an %unordered_multiset.
1400 *
1401 * Note that this function only erases the element, and that if the
1402 * element is itself a pointer, the pointed-to memory is not touched in
1403 * any way. Managing the pointer is the user's responsibility.
1404 */
1405 size_type
1406 erase(const key_type& __x)
1407 { return _M_h.erase(__x); }
1408
1409 /**
1410 * @brief Erases a [__first,__last) range of elements from an
1411 * %unordered_multiset.
1412 * @param __first Iterator pointing to the start of the range to be
1413 * erased.
1414 * @param __last Iterator pointing to the end of the range to
1415 * be erased.
1416 * @return The iterator @a __last.
1417 *
1418 * This function erases a sequence of elements from an
1419 * %unordered_multiset.
1420 *
1421 * Note that this function only erases the element, and that if
1422 * the element is itself a pointer, the pointed-to memory is not touched
1423 * in any way. Managing the pointer is the user's responsibility.
1424 */
1425 iterator
1427 { return _M_h.erase(__first, __last); }
1428
1429 /**
1430 * Erases all elements in an %unordered_multiset.
1431 *
1432 * Note that this function only erases the elements, and that if the
1433 * elements themselves are pointers, the pointed-to memory is not touched
1434 * in any way. Managing the pointer is the user's responsibility.
1435 */
1436 void
1437 clear() noexcept
1438 { _M_h.clear(); }
1439
1440 /**
1441 * @brief Swaps data with another %unordered_multiset.
1442 * @param __x An %unordered_multiset of the same element and allocator
1443 * types.
1444 *
1445 * This exchanges the elements between two sets in constant time.
1446 * Note that the global std::swap() function is specialized such that
1447 * std::swap(s1,s2) will feed to this function.
1448 */
1449 void
1451 noexcept( noexcept(_M_h.swap(__x._M_h)) )
1452 { _M_h.swap(__x._M_h); }
1453
1454#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1455 template<typename, typename, typename>
1456 friend class std::_Hash_merge_helper;
1457
1458 template<typename _H2, typename _P2>
1459 void
1461 {
1462 if constexpr (is_same_v<_H2, _Hash> && is_same_v<_P2, _Pred>)
1463 if (std::__addressof(__source) == this) [[__unlikely__]]
1464 return;
1465
1466 using _Merge_helper
1467 = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1468 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1469 }
1470
1471 template<typename _H2, typename _P2>
1472 void
1473 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
1474 {
1475 using _Merge_helper
1476 = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1477 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1478 }
1479
1480 template<typename _H2, typename _P2>
1481 void
1482 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
1483 {
1484 using _Merge_helper
1485 = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1486 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1487 }
1488
1489 template<typename _H2, typename _P2>
1490 void
1491 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
1492 { merge(__source); }
1493#endif // node_extract
1494
1495 // observers.
1496
1497 /// Returns the hash functor object with which the %unordered_multiset
1498 /// was constructed.
1499 hasher
1501 { return _M_h.hash_function(); }
1502
1503 /// Returns the key comparison object with which the %unordered_multiset
1504 /// was constructed.
1505 key_equal
1506 key_eq() const
1507 { return _M_h.key_eq(); }
1508
1509 // lookup.
1510
1511 ///@{
1512 /**
1513 * @brief Tries to locate an element in an %unordered_multiset.
1514 * @param __x Element to be located.
1515 * @return Iterator pointing to sought-after element, or end() if not
1516 * found.
1517 *
1518 * This function takes a key and tries to locate the element with which
1519 * the key matches. If successful the function returns an iterator
1520 * pointing to the sought after element. If unsuccessful it returns the
1521 * past-the-end ( @c end() ) iterator.
1522 */
1523 iterator
1524 find(const key_type& __x)
1525 { return _M_h.find(__x); }
1526
1527#if __cplusplus > 201703L
1528 template<typename _Kt>
1529 auto
1530 find(const _Kt& __x)
1531 -> decltype(_M_h._M_find_tr(__x))
1532 { return _M_h._M_find_tr(__x); }
1533#endif
1534
1535 const_iterator
1536 find(const key_type& __x) const
1537 { return _M_h.find(__x); }
1538
1539#if __cplusplus > 201703L
1540 template<typename _Kt>
1541 auto
1542 find(const _Kt& __x) const
1543 -> decltype(_M_h._M_find_tr(__x))
1544 { return _M_h._M_find_tr(__x); }
1545#endif
1546 ///@}
1547
1548 ///@{
1549 /**
1550 * @brief Finds the number of elements.
1551 * @param __x Element to located.
1552 * @return Number of elements with specified key.
1553 */
1554 size_type
1555 count(const key_type& __x) const
1556 { return _M_h.count(__x); }
1557
1558#if __cplusplus > 201703L
1559 template<typename _Kt>
1560 auto
1561 count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x))
1562 { return _M_h._M_count_tr(__x); }
1563#endif
1564 ///@}
1565
1566#if __cplusplus > 201703L
1567 ///@{
1568 /**
1569 * @brief Finds whether an element with the given key exists.
1570 * @param __x Key of elements to be located.
1571 * @return True if there is any element with the specified key.
1572 */
1573 bool
1574 contains(const key_type& __x) const
1575 { return _M_h.find(__x) != _M_h.end(); }
1576
1577 template<typename _Kt>
1578 auto
1579 contains(const _Kt& __x) const
1580 -> decltype(_M_h._M_find_tr(__x), void(), true)
1581 { return _M_h._M_find_tr(__x) != _M_h.end(); }
1582 ///@}
1583#endif
1584
1585 ///@{
1586 /**
1587 * @brief Finds a subsequence matching given key.
1588 * @param __x Key to be located.
1589 * @return Pair of iterators that possibly points to the subsequence
1590 * matching given key.
1591 */
1594 { return _M_h.equal_range(__x); }
1595
1596#if __cplusplus > 201703L
1597 template<typename _Kt>
1598 auto
1599 equal_range(const _Kt& __x)
1600 -> decltype(_M_h._M_equal_range_tr(__x))
1601 { return _M_h._M_equal_range_tr(__x); }
1602#endif
1603
1605 equal_range(const key_type& __x) const
1606 { return _M_h.equal_range(__x); }
1607
1608#if __cplusplus > 201703L
1609 template<typename _Kt>
1610 auto
1611 equal_range(const _Kt& __x) const
1612 -> decltype(_M_h._M_equal_range_tr(__x))
1613 { return _M_h._M_equal_range_tr(__x); }
1614#endif
1615 ///@}
1616
1617 // bucket interface.
1618
1619 /// Returns the number of buckets of the %unordered_multiset.
1620 size_type
1621 bucket_count() const noexcept
1622 { return _M_h.bucket_count(); }
1623
1624 /// Returns the maximum number of buckets of the %unordered_multiset.
1625 size_type
1626 max_bucket_count() const noexcept
1627 { return _M_h.max_bucket_count(); }
1628
1629 /*
1630 * @brief Returns the number of elements in a given bucket.
1631 * @param __n A bucket index.
1632 * @return The number of elements in the bucket.
1633 */
1634 size_type
1635 bucket_size(size_type __n) const
1636 { return _M_h.bucket_size(__n); }
1637
1638 /*
1639 * @brief Returns the bucket index of a given element.
1640 * @param __key A key instance.
1641 * @return The key bucket index.
1642 */
1643 size_type
1644 bucket(const key_type& __key) const
1645 { return _M_h.bucket(__key); }
1646
1647 ///@{
1648 /**
1649 * @brief Returns a read-only (constant) iterator pointing to the first
1650 * bucket element.
1651 * @param __n The bucket index.
1652 * @return A read-only local iterator.
1653 */
1656 { return _M_h.begin(__n); }
1657
1659 begin(size_type __n) const
1660 { return _M_h.begin(__n); }
1661
1664 { return _M_h.cbegin(__n); }
1665 ///@}
1666
1667 ///@{
1668 /**
1669 * @brief Returns a read-only (constant) iterator pointing to one past
1670 * the last bucket elements.
1671 * @param __n The bucket index.
1672 * @return A read-only local iterator.
1673 */
1676 { return _M_h.end(__n); }
1677
1679 end(size_type __n) const
1680 { return _M_h.end(__n); }
1681
1683 cend(size_type __n) const
1684 { return _M_h.cend(__n); }
1685 ///@}
1686
1687 // hash policy.
1688
1689 /// Returns the average number of elements per bucket.
1690 float
1691 load_factor() const noexcept
1692 { return _M_h.load_factor(); }
1693
1694 /// Returns a positive number that the %unordered_multiset tries to keep the
1695 /// load factor less than or equal to.
1696 float
1697 max_load_factor() const noexcept
1698 { return _M_h.max_load_factor(); }
1699
1700 /**
1701 * @brief Change the %unordered_multiset maximum load factor.
1702 * @param __z The new maximum load factor.
1703 */
1704 void
1706 { _M_h.max_load_factor(__z); }
1707
1708 /**
1709 * @brief May rehash the %unordered_multiset.
1710 * @param __n The new number of buckets.
1711 *
1712 * Rehash will occur only if the new number of buckets respect the
1713 * %unordered_multiset maximum load factor.
1714 */
1715 void
1717 { _M_h.rehash(__n); }
1718
1719 /**
1720 * @brief Prepare the %unordered_multiset for a specified number of
1721 * elements.
1722 * @param __n Number of elements required.
1723 *
1724 * Same as rehash(ceil(n / max_load_factor())).
1725 */
1726 void
1728 { _M_h.reserve(__n); }
1729
1730 template<typename _Value1, typename _Hash1, typename _Pred1,
1731 typename _Alloc1>
1732 friend bool
1735 };
1736
1737
1738#if __cpp_deduction_guides >= 201606
1739
1740 template<typename _InputIterator,
1741 typename _Hash =
1742 hash<typename iterator_traits<_InputIterator>::value_type>,
1743 typename _Pred =
1744 equal_to<typename iterator_traits<_InputIterator>::value_type>,
1745 typename _Allocator =
1746 allocator<typename iterator_traits<_InputIterator>::value_type>,
1747 typename = _RequireInputIter<_InputIterator>,
1748 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1749 typename = _RequireNotAllocator<_Pred>,
1750 typename = _RequireAllocator<_Allocator>>
1751 unordered_multiset(_InputIterator, _InputIterator,
1752 unordered_multiset<int>::size_type = {},
1753 _Hash = _Hash(), _Pred = _Pred(),
1754 _Allocator = _Allocator())
1756 _Hash, _Pred, _Allocator>;
1757
1758 template<typename _Tp, typename _Hash = hash<_Tp>,
1759 typename _Pred = equal_to<_Tp>,
1760 typename _Allocator = allocator<_Tp>,
1761 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1762 typename = _RequireNotAllocator<_Pred>,
1763 typename = _RequireAllocator<_Allocator>>
1766 _Hash = _Hash(), _Pred = _Pred(),
1767 _Allocator = _Allocator())
1769
1770 template<typename _InputIterator, typename _Allocator,
1771 typename = _RequireInputIter<_InputIterator>,
1772 typename = _RequireAllocator<_Allocator>>
1773 unordered_multiset(_InputIterator, _InputIterator,
1776 hash<typename
1778 equal_to<typename
1780 _Allocator>;
1781
1782 template<typename _InputIterator, typename _Hash, typename _Allocator,
1783 typename = _RequireInputIter<_InputIterator>,
1784 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1785 typename = _RequireAllocator<_Allocator>>
1786 unordered_multiset(_InputIterator, _InputIterator,
1788 _Hash, _Allocator)
1789 -> unordered_multiset<typename
1791 _Hash,
1792 equal_to<
1793 typename
1795 _Allocator>;
1796
1797 template<typename _Tp, typename _Allocator,
1798 typename = _RequireAllocator<_Allocator>>
1802
1803 template<typename _Tp, typename _Hash, typename _Allocator,
1804 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1805 typename = _RequireAllocator<_Allocator>>
1807 unordered_multiset<int>::size_type, _Hash, _Allocator)
1809
1810#endif
1811
1812 template<class _Value, class _Hash, class _Pred, class _Alloc>
1813 inline void
1816 noexcept(noexcept(__x.swap(__y)))
1817 { __x.swap(__y); }
1818
1819 template<class _Value, class _Hash, class _Pred, class _Alloc>
1820 inline void
1823 noexcept(noexcept(__x.swap(__y)))
1824 { __x.swap(__y); }
1825
1826 template<class _Value, class _Hash, class _Pred, class _Alloc>
1827 inline bool
1828 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1830 { return __x._M_h._M_equal(__y._M_h); }
1831
1832#if __cpp_impl_three_way_comparison < 201907L
1833 template<class _Value, class _Hash, class _Pred, class _Alloc>
1834 inline bool
1835 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
1837 { return !(__x == __y); }
1838#endif
1839
1840 template<class _Value, class _Hash, class _Pred, class _Alloc>
1841 inline bool
1844 { return __x._M_h._M_equal(__y._M_h); }
1845
1846#if __cpp_impl_three_way_comparison < 201907L
1847 template<class _Value, class _Hash, class _Pred, class _Alloc>
1848 inline bool
1851 { return !(__x == __y); }
1852#endif
1853
1854_GLIBCXX_END_NAMESPACE_CONTAINER
1855
1856#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1857 // Allow std::unordered_set access to internals of compatible sets.
1858 template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc,
1859 typename _Hash2, typename _Eq2>
1860 struct _Hash_merge_helper<
1861 _GLIBCXX_STD_C::unordered_set<_Val, _Hash1, _Eq1, _Alloc>, _Hash2, _Eq2>
1862 {
1863 private:
1864 template<typename... _Tp>
1865 using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
1866 template<typename... _Tp>
1867 using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
1868
1869 friend unordered_set<_Val, _Hash1, _Eq1, _Alloc>;
1870
1871 static auto&
1872 _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
1873 { return __set._M_h; }
1874
1875 static auto&
1876 _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
1877 { return __set._M_h; }
1878 };
1879
1880 // Allow std::unordered_multiset access to internals of compatible sets.
1881 template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc,
1882 typename _Hash2, typename _Eq2>
1883 struct _Hash_merge_helper<
1884 _GLIBCXX_STD_C::unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>,
1885 _Hash2, _Eq2>
1886 {
1887 private:
1888 template<typename... _Tp>
1889 using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
1890 template<typename... _Tp>
1891 using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
1892
1893 friend unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>;
1894
1895 static auto&
1896 _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
1897 { return __set._M_h; }
1898
1899 static auto&
1900 _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
1901 { return __set._M_h; }
1902 };
1903#endif // node_extract
1904
1905_GLIBCXX_END_NAMESPACE_VERSION
1906} // namespace std
1907
1908#endif /* _UNORDERED_SET_H */
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:138
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition move.h:52
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition move.h:72
ISO C++ entities toplevel namespace is std.
__detail::_Hashtable_traits< _Cache, true, false > __umset_traits
Base types for unordered_multiset.
__detail::_Hashtable_traits< _Cache, true, true > __uset_traits
Base types for unordered_set.
initializer_list
Primary class template hash.
The standard allocator, as per C++03 [20.4.1].
Definition allocator.h:134
One of the comparison functors.
Struct holding two objects of arbitrary type.
Definition stl_pair.h:286
Common iterator class.
Traits class for iterators.
A standard container composed of equivalent keys (possibly containing multiple of each key value) in ...
auto find(const _Kt &__x) const -> decltype(_M_h._M_find_tr(__x))
Tries to locate an element in an unordered_multiset.
iterator begin() noexcept
auto find(const _Kt &__x) -> decltype(_M_h._M_find_tr(__x))
Tries to locate an element in an unordered_multiset.
iterator insert(const_iterator __hint, const value_type &__x)
Inserts an element into the unordered_multiset.
void insert(initializer_list< value_type > __l)
Inserts a list of elements into the unordered_multiset.
bool contains(const key_type &__x) const
Finds whether an element with the given key exists.
void rehash(size_type __n)
May rehash the unordered_multiset.
local_iterator begin(size_type __n)
Returns a read-only (constant) iterator pointing to the first bucket element.
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_multiset.
float max_load_factor() const noexcept
Returns a positive number that the unordered_multiset tries to keep the load factor less than or equa...
bool empty() const noexcept
Returns true if the unordered_multiset is empty.
const_iterator cend() const noexcept
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
iterator emplace(_Args &&... __args)
Builds and insert an element into the unordered_multiset.
unordered_multiset(_InputIterator __first, _InputIterator __last, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_multiset from a range.
unordered_multiset(const allocator_type &__a)
Creates an unordered_multiset with no elements.
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
iterator find(const key_type &__x)
Tries to locate an element in an unordered_multiset.
unordered_multiset & operator=(unordered_multiset &&)=default
Move assignment operator.
float load_factor() const noexcept
Returns the average number of elements per bucket.
unordered_multiset()=default
Default constructor.
auto equal_range(const _Kt &__x) -> decltype(_M_h._M_equal_range_tr(__x))
Finds a subsequence matching given key.
unordered_multiset & operator=(const unordered_multiset &)=default
Copy assignment operator.
hasher hash_function() const
Returns the hash functor object with which the unordered_multiset was constructed.
unordered_multiset(initializer_list< value_type > __l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_multiset from an initializer_list.
auto contains(const _Kt &__x) const -> decltype(_M_h._M_find_tr(__x), void(), true)
Finds whether an element with the given key exists.
auto count(const _Kt &__x) const -> decltype(_M_h._M_count_tr(__x))
Finds the number of elements.
size_type count(const key_type &__x) const
Finds the number of elements.
iterator erase(const_iterator __position)
Erases an element from an unordered_multiset.
unordered_multiset(unordered_multiset &&)=default
Move constructor.
iterator end() noexcept
iterator emplace_hint(const_iterator __pos, _Args &&... __args)
Inserts an element into the unordered_multiset.
void swap(unordered_multiset &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another unordered_multiset.
const_iterator begin() const noexcept
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_multiset.
const_iterator cbegin() const noexcept
void insert(_InputIterator __first, _InputIterator __last)
A template function that inserts a range of elements.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
key_equal key_eq() const
Returns the key comparison object with which the unordered_multiset was constructed.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
iterator insert(value_type &&__x)
Inserts an element into the unordered_multiset.
iterator insert(const value_type &__x)
Inserts an element into the unordered_multiset.
const_iterator end() const noexcept
void reserve(size_type __n)
Prepare the unordered_multiset for a specified number of elements.
iterator insert(const_iterator __hint, value_type &&__x)
Inserts an element into the unordered_multiset.
iterator erase(iterator __position)
Erases an element from an unordered_multiset.
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_multiset.
unordered_multiset(size_type __n, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Default constructor creates no elements.
unordered_multiset & operator=(initializer_list< value_type > __l)
Unordered_multiset list assignment operator.
size_type size() const noexcept
Returns the size of the unordered_multiset.
local_iterator end(size_type __n)
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
auto equal_range(const _Kt &__x) const -> decltype(_M_h._M_equal_range_tr(__x))
Finds a subsequence matching given key.
size_type max_size() const noexcept
Returns the maximum size of the unordered_multiset.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
unordered_multiset(const unordered_multiset &)=default
Copy constructor.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_multiset.
allocator_type get_allocator() const noexcept
Returns the allocator object used by the unordered_multiset.
void max_load_factor(float __z)
Change the unordered_multiset maximum load factor.
A standard container composed of unique keys (containing at most one of each key value) in which the ...
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert an element into the unordered_set.
unordered_set(initializer_list< value_type > __l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_set from an initializer_list.
void max_load_factor(float __z)
Change the unordered_set maximum load factor.
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
const_iterator cend() const noexcept
auto find(const _Kt &__k) -> decltype(_M_h._M_find_tr(__k))
Tries to locate an element in an unordered_set.
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_set.
size_type count(const key_type &__x) const
Finds the number of elements.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
auto equal_range(const _Kt &__k) -> decltype(_M_h._M_equal_range_tr(__k))
Finds a subsequence matching given key.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
auto count(const _Kt &__k) const -> decltype(_M_h._M_count_tr(__k))
Finds the number of elements.
const_iterator begin() const noexcept
const_iterator cbegin() const noexcept
bool empty() const noexcept
Returns true if the unordered_set is empty.
unordered_set & operator=(initializer_list< value_type > __l)
Unordered_set list assignment operator.
iterator erase(iterator __position)
Erases an element from an unordered_set.
unordered_set(unordered_set &&)=default
Move constructor.
unordered_set(const allocator_type &__a)
Creates an unordered_set with no elements.
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
auto contains(const _Kt &__k) const -> decltype(_M_h._M_find_tr(__k), void(), true)
Finds whether an element with the given key exists.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
void swap(unordered_set &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another unordered_set.
iterator insert(const_iterator __hint, const value_type &__x)
Attempts to insert an element into the unordered_set.
std::pair< iterator, bool > insert(value_type &&__x)
Attempts to insert an element into the unordered_set.
float load_factor() const noexcept
Returns the average number of elements per bucket.
void rehash(size_type __n)
May rehash the unordered_set.
local_iterator end(size_type __n)
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
size_type size() const noexcept
Returns the size of the unordered_set.
hasher hash_function() const
Returns the hash functor object with which the unordered_set was constructed.
unordered_set(const unordered_set &)=default
Copy constructor.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
auto find(const _Kt &__k) const -> decltype(_M_h._M_find_tr(__k))
Tries to locate an element in an unordered_set.
iterator emplace_hint(const_iterator __pos, _Args &&... __args)
Attempts to insert an element into the unordered_set.
key_equal key_eq() const
Returns the key comparison object with which the unordered_set was constructed.
iterator insert(const_iterator __hint, value_type &&__x)
Attempts to insert an element into the unordered_set.
const_iterator end() const noexcept
iterator end() noexcept
local_iterator begin(size_type __n)
Returns a read-only (constant) iterator pointing to the first bucket element.
unordered_set()=default
Default constructor.
unordered_set & operator=(unordered_set &&)=default
Move assignment operator.
void insert(_InputIterator __first, _InputIterator __last)
A template function that attempts to insert a range of elements.
float max_load_factor() const noexcept
Returns a positive number that the unordered_set tries to keep the load factor less than or equal to.
bool contains(const key_type &__x) const
Finds whether an element with the given key exists.
std::pair< iterator, bool > emplace(_Args &&... __args)
Attempts to build and insert an element into the unordered_set.
unordered_set & operator=(const unordered_set &)=default
Copy assignment operator.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
unordered_set(size_type __n, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Default constructor creates no elements.
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_set.
iterator erase(const_iterator __position)
Erases an element from an unordered_set.
allocator_type get_allocator() const noexcept
Returns the allocator object used by the unordered_set.
auto equal_range(const _Kt &__k) const -> decltype(_M_h._M_equal_range_tr(__k))
Finds a subsequence matching given key.
void clear() noexcept
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the unordered_set.
unordered_set(_InputIterator __first, _InputIterator __last, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_set from a range.
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_set.
void reserve(size_type __n)
Prepare the unordered_set for a specified number of elements.
iterator begin() noexcept
iterator find(const key_type &__x)
Tries to locate an element in an unordered_set.
size_type max_size() const noexcept
Returns the maximum size of the unordered_set.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_set.