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