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 */
214 unordered_set(unordered_set&& __uset,
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 // _GLIBCXX_RESOLVE_LIB_DEFECTS
298 // 2713. More missing allocator-extended constructors for unordered container
299 template<__detail::__container_compatible_range<_Value> _Rg>
300 unordered_set(from_range_t, _Rg&& __rg, const allocator_type& __a)
301 : _M_h(0, hasher(), key_equal(), __a)
302 { insert_range(std::forward<_Rg>(__rg)); }
303
304 template<__detail::__container_compatible_range<_Value> _Rg>
305 unordered_set(from_range_t, _Rg&& __rg, size_type __n,
306 const allocator_type& __a)
307 : _M_h(__n, hasher(), key_equal(), __a)
308 { insert_range(std::forward<_Rg>(__rg)); }
309
310 template<__detail::__container_compatible_range<_Value> _Rg>
311 unordered_set(from_range_t, _Rg&& __rg, size_type __n,
312 const hasher& __hf, const allocator_type& __a)
313 : _M_h(__n, __hf, key_equal(), __a)
314 { insert_range(std::forward<_Rg>(__rg)); }
315#endif
316
317 /// Copy assignment operator.
319 operator=(const unordered_set&) = default;
320
321 /// Move assignment operator.
324
325 /**
326 * @brief %Unordered_set list assignment operator.
327 * @param __l An initializer_list.
328 *
329 * This function fills an %unordered_set with copies of the elements in
330 * the initializer list @a __l.
331 *
332 * Note that the assignment completely changes the %unordered_set and
333 * that the resulting %unordered_set's size is the same as the number
334 * of elements assigned.
335 */
338 {
339 _M_h = __l;
340 return *this;
341 }
342
343 /// Returns the allocator object used by the %unordered_set.
344 allocator_type
345 get_allocator() const noexcept
346 { return _M_h.get_allocator(); }
347
348 // size and capacity:
349
350 /// Returns true if the %unordered_set is empty.
351 _GLIBCXX_NODISCARD bool
352 empty() const noexcept
353 { return _M_h.empty(); }
354
355 /// Returns the size of the %unordered_set.
357 size() const noexcept
358 { return _M_h.size(); }
359
360 /// Returns the maximum size of the %unordered_set.
362 max_size() const noexcept
363 { return _M_h.max_size(); }
364
365 // iterators.
366
367 ///@{
368 /**
369 * Returns a read-only (constant) iterator that points to the first
370 * element in the %unordered_set.
371 */
373 begin() noexcept
374 { return _M_h.begin(); }
375
376 const_iterator
377 begin() const noexcept
378 { return _M_h.begin(); }
379 ///@}
380
381 ///@{
382 /**
383 * Returns a read-only (constant) iterator that points one past the last
384 * element in the %unordered_set.
385 */
387 end() noexcept
388 { return _M_h.end(); }
389
390 const_iterator
391 end() const noexcept
392 { return _M_h.end(); }
393 ///@}
394
395 /**
396 * Returns a read-only (constant) iterator that points to the first
397 * element in the %unordered_set.
398 */
399 const_iterator
400 cbegin() const noexcept
401 { return _M_h.begin(); }
402
403 /**
404 * Returns a read-only (constant) iterator that points one past the last
405 * element in the %unordered_set.
406 */
407 const_iterator
408 cend() const noexcept
409 { return _M_h.end(); }
410
411 // modifiers.
412
413 /**
414 * @brief Attempts to build and insert an element into the
415 * %unordered_set.
416 * @param __args Arguments used to generate an element.
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 build and insert an element into the
422 * %unordered_set. An %unordered_set relies on unique keys and thus an
423 * element is only inserted if it is not already present in the
424 * %unordered_set.
425 *
426 * Insertion requires amortized constant time.
427 */
428 template<typename... _Args>
430 emplace(_Args&&... __args)
431 { return _M_h.emplace(std::forward<_Args>(__args)...); }
432
433 /**
434 * @brief Attempts to insert an element into the %unordered_set.
435 * @param __pos An iterator that serves as a hint as to where the
436 * element should be inserted.
437 * @param __args Arguments used to generate the element to be
438 * inserted.
439 * @return An iterator that points to the element with key equivalent to
440 * the one generated from @a __args (may or may not be the
441 * element itself).
442 *
443 * This function is not concerned about whether the insertion took place,
444 * and thus does not return a boolean like the single-argument emplace()
445 * does. Note that the first parameter is only a hint and can
446 * potentially improve the performance of the insertion process. A bad
447 * hint would cause no gains in efficiency.
448 *
449 * For more on @a hinting, see:
450 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
451 *
452 * Insertion requires amortized constant time.
453 */
454 template<typename... _Args>
456 emplace_hint(const_iterator __pos, _Args&&... __args)
457 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
458
459 ///@{
460 /**
461 * @brief Attempts to insert an element into the %unordered_set.
462 * @param __x Element to be inserted.
463 * @return A pair, of which the first element is an iterator that points
464 * to the possibly inserted element, and the second is a bool
465 * that is true if the element was actually inserted.
466 *
467 * This function attempts to insert an element into the %unordered_set.
468 * An %unordered_set relies on unique keys and thus an element is only
469 * inserted if it is not already present in the %unordered_set.
470 *
471 * Insertion requires amortized constant time.
472 */
474 insert(const value_type& __x)
475 { return _M_h.insert(__x); }
476
479 { return _M_h.insert(std::move(__x)); }
480 ///@}
481
482 ///@{
483 /**
484 * @brief Attempts to insert an element into the %unordered_set.
485 * @param __hint An iterator that serves as a hint as to where the
486 * element should be inserted.
487 * @param __x Element to be inserted.
488 * @return An iterator that points to the element with key of
489 * @a __x (may or may not be the element passed in).
490 *
491 * This function is not concerned about whether the insertion took place,
492 * and thus does not return a boolean like the single-argument insert()
493 * does. Note that the first parameter is only a hint and can
494 * potentially improve the performance of the insertion process. A bad
495 * hint would cause no gains in efficiency.
496 *
497 * For more on @a hinting, see:
498 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
499 *
500 * Insertion requires amortized constant.
501 */
503 insert(const_iterator __hint, const value_type& __x)
504 { return _M_h.insert(__hint, __x); }
505
508 { return _M_h.insert(__hint, std::move(__x)); }
509 ///@}
510
511 /**
512 * @brief A template function that attempts to insert a range of
513 * elements.
514 * @param __first Iterator pointing to the start of the range to be
515 * inserted.
516 * @param __last Iterator pointing to the end of the range.
517 *
518 * Complexity similar to that of the range constructor.
519 */
520 template<typename _InputIterator>
521 void
522 insert(_InputIterator __first, _InputIterator __last)
523 { _M_h.insert(__first, __last); }
524
525 /**
526 * @brief Attempts to insert a list of elements into the %unordered_set.
527 * @param __l A std::initializer_list<value_type> of elements
528 * to be inserted.
529 *
530 * Complexity similar to that of the range constructor.
531 */
532 void
534 { _M_h.insert(__l); }
535
536#if __glibcxx_ranges_to_container // C++ >= 23
537 /**
538 * @brief Inserts a range of elements.
539 * @since C++23
540 * @param __rg An input range of elements that can be converted to
541 * the set's value type.
542 */
543 template<__detail::__container_compatible_range<_Value> _Rg>
544 void
545 insert_range(_Rg&& __rg)
546 {
547 auto __first = ranges::begin(__rg);
548 const auto __last = ranges::end(__rg);
549 for (; __first != __last; ++__first)
550 _M_h.emplace(*__first);
551 }
552#endif
553
554#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
555 /// Extract a node.
556 node_type
557 extract(const_iterator __pos)
558 {
559 __glibcxx_assert(__pos != end());
560 return _M_h.extract(__pos);
561 }
562
563 /// Extract a node.
564 node_type
565 extract(const key_type& __key)
566 { return _M_h.extract(__key); }
567
568 /// Re-insert an extracted node.
569 insert_return_type
570 insert(node_type&& __nh)
571 { return _M_h._M_reinsert_node(std::move(__nh)); }
572
573 /// Re-insert an extracted node.
575 insert(const_iterator, node_type&& __nh)
576 { return _M_h._M_reinsert_node(std::move(__nh)).position; }
577#endif // node_extract
578
579 ///@{
580 /**
581 * @brief Erases an element from an %unordered_set.
582 * @param __position An iterator pointing to the element to be erased.
583 * @return An iterator pointing to the element immediately following
584 * @a __position prior to the element being erased. If no such
585 * element exists, end() is returned.
586 *
587 * This function erases an element, pointed to by the given iterator,
588 * from an %unordered_set. Note that this function only erases the
589 * element, and that if the element is itself a pointer, the pointed-to
590 * memory is not touched in any way. Managing the pointer is the user's
591 * responsibility.
592 */
595 { return _M_h.erase(__position); }
596
597 // LWG 2059.
599 erase(iterator __position)
600 { return _M_h.erase(__position); }
601 ///@}
602
603 /**
604 * @brief Erases elements according to the provided key.
605 * @param __x Key of element to be erased.
606 * @return The number of elements erased.
607 *
608 * This function erases all the elements located by the given key from
609 * an %unordered_set. For an %unordered_set the result of this function
610 * can only be 0 (not present) or 1 (present).
611 * Note that this function only erases the element, and that if
612 * the element is itself a pointer, the pointed-to memory is not touched
613 * in any way. Managing the pointer is the user's responsibility.
614 */
616 erase(const key_type& __x)
617 { return _M_h.erase(__x); }
618
619 /**
620 * @brief Erases a [__first,__last) range of elements from an
621 * %unordered_set.
622 * @param __first Iterator pointing to the start of the range to be
623 * erased.
624 * @param __last Iterator pointing to the end of the range to
625 * be erased.
626 * @return The iterator @a __last.
627 *
628 * This function erases a sequence of elements from an %unordered_set.
629 * Note that this function only erases the element, and that if
630 * the element is itself a pointer, the pointed-to memory is not touched
631 * in any way. Managing the pointer is the user's responsibility.
632 */
635 { return _M_h.erase(__first, __last); }
636
637 /**
638 * Erases all elements in an %unordered_set. Note that this function only
639 * erases the elements, and that if the elements themselves are pointers,
640 * the pointed-to memory is not touched in any way. Managing the pointer
641 * is the user's responsibility.
642 */
643 void
644 clear() noexcept
645 { _M_h.clear(); }
646
647 /**
648 * @brief Swaps data with another %unordered_set.
649 * @param __x An %unordered_set of the same element and allocator
650 * types.
651 *
652 * This exchanges the elements between two sets in constant time.
653 * Note that the global std::swap() function is specialized such that
654 * std::swap(s1,s2) will feed to this function.
655 */
656 void
658 noexcept( noexcept(_M_h.swap(__x._M_h)) )
659 { _M_h.swap(__x._M_h); }
660
661#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
662 template<typename, typename, typename>
663 friend class std::_Hash_merge_helper;
664
665 template<typename _H2, typename _P2>
666 void
668 {
669 if constexpr (is_same_v<_H2, _Hash> && is_same_v<_P2, _Pred>)
670 if (std::__addressof(__source) == this) [[__unlikely__]]
671 return;
672
673 using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
674 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
675 }
676
677 template<typename _H2, typename _P2>
678 void
679 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
680 {
681 using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
682 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
683 }
684
685 template<typename _H2, typename _P2>
686 void
687 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
688 {
689 using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
690 _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
691 }
692
693 template<typename _H2, typename _P2>
694 void
695 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
696 { merge(__source); }
697#endif // node_extract
698
699 // observers.
700
701 /// Returns the hash functor object with which the %unordered_set was
702 /// constructed.
703 hasher
705 { return _M_h.hash_function(); }
706
707 /// Returns the key comparison object with which the %unordered_set was
708 /// constructed.
710 key_eq() const
711 { return _M_h.key_eq(); }
712
713 // lookup.
714
715 ///@{
716 /**
717 * @brief Tries to locate an element in an %unordered_set.
718 * @param __x Element to be located.
719 * @return Iterator pointing to sought-after element, or end() if not
720 * found.
721 *
722 * This function takes a key and tries to locate the element with which
723 * the key matches. If successful the function returns an iterator
724 * pointing to the sought after element. If unsuccessful it returns the
725 * past-the-end ( @c end() ) iterator.
726 */
728 find(const key_type& __x)
729 { return _M_h.find(__x); }
730
731#if __cplusplus > 201703L
732 template<typename _Kt>
733 auto
734 find(const _Kt& __k)
735 -> decltype(_M_h._M_find_tr(__k))
736 { return _M_h._M_find_tr(__k); }
737#endif
738
739 const_iterator
740 find(const key_type& __x) const
741 { return _M_h.find(__x); }
742
743#if __cplusplus > 201703L
744 template<typename _Kt>
745 auto
746 find(const _Kt& __k) const
747 -> decltype(_M_h._M_find_tr(__k))
748 { return _M_h._M_find_tr(__k); }
749#endif
750 ///@}
751
752 ///@{
753 /**
754 * @brief Finds the number of elements.
755 * @param __x Element to located.
756 * @return Number of elements with specified key.
757 *
758 * This function only makes sense for unordered_multisets; for
759 * unordered_set the result will either be 0 (not present) or 1
760 * (present).
761 */
763 count(const key_type& __x) const
764 { return _M_h.count(__x); }
765
766#if __cplusplus > 201703L
767 template<typename _Kt>
768 auto
769 count(const _Kt& __k) const
770 -> decltype(_M_h._M_count_tr(__k))
771 { return _M_h._M_count_tr(__k); }
772#endif
773 ///@}
774
775#if __cplusplus > 201703L
776 ///@{
777 /**
778 * @brief Finds whether an element with the given key exists.
779 * @param __x Key of elements to be located.
780 * @return True if there is any element with the specified key.
781 */
782 bool
783 contains(const key_type& __x) const
784 { return _M_h.find(__x) != _M_h.end(); }
785
786 template<typename _Kt>
787 auto
788 contains(const _Kt& __k) const
789 -> decltype(_M_h._M_find_tr(__k), void(), true)
790 { return _M_h._M_find_tr(__k) != _M_h.end(); }
791 ///@}
792#endif
793
794 ///@{
795 /**
796 * @brief Finds a subsequence matching given key.
797 * @param __x Key to be located.
798 * @return Pair of iterators that possibly points to the subsequence
799 * matching given key.
800 *
801 * This function probably only makes sense for multisets.
802 */
805 { return _M_h.equal_range(__x); }
806
807#if __cplusplus > 201703L
808 template<typename _Kt>
809 auto
810 equal_range(const _Kt& __k)
811 -> decltype(_M_h._M_equal_range_tr(__k))
812 { return _M_h._M_equal_range_tr(__k); }
813#endif
814
816 equal_range(const key_type& __x) const
817 { return _M_h.equal_range(__x); }
818
819#if __cplusplus > 201703L
820 template<typename _Kt>
821 auto
822 equal_range(const _Kt& __k) const
823 -> decltype(_M_h._M_equal_range_tr(__k))
824 { return _M_h._M_equal_range_tr(__k); }
825#endif
826 ///@}
827
828 // bucket interface.
829
830 /// Returns the number of buckets of the %unordered_set.
832 bucket_count() const noexcept
833 { return _M_h.bucket_count(); }
834
835 /// Returns the maximum number of buckets of the %unordered_set.
837 max_bucket_count() const noexcept
838 { return _M_h.max_bucket_count(); }
839
840 /*
841 * @brief Returns the number of elements in a given bucket.
842 * @param __n A bucket index.
843 * @return The number of elements in the bucket.
844 */
846 bucket_size(size_type __n) const
847 { return _M_h.bucket_size(__n); }
848
849 /*
850 * @brief Returns the bucket index of a given element.
851 * @param __key A key instance.
852 * @return The key bucket index.
853 */
854 size_type
855 bucket(const key_type& __key) const
856 { return _M_h.bucket(__key); }
857
858 ///@{
859 /**
860 * @brief Returns a read-only (constant) iterator pointing to the first
861 * bucket element.
862 * @param __n The bucket index.
863 * @return A read-only local iterator.
864 */
867 { return _M_h.begin(__n); }
868
870 begin(size_type __n) const
871 { return _M_h.begin(__n); }
872
874 cbegin(size_type __n) const
875 { return _M_h.cbegin(__n); }
876 ///@}
877
878 ///@{
879 /**
880 * @brief Returns a read-only (constant) iterator pointing to one past
881 * the last bucket elements.
882 * @param __n The bucket index.
883 * @return A read-only local iterator.
884 */
887 { return _M_h.end(__n); }
888
890 end(size_type __n) const
891 { return _M_h.end(__n); }
892
894 cend(size_type __n) const
895 { return _M_h.cend(__n); }
896 ///@}
897
898 // hash policy.
899
900 /// Returns the average number of elements per bucket.
901 float
902 load_factor() const noexcept
903 { return _M_h.load_factor(); }
904
905 /// Returns a positive number that the %unordered_set tries to keep the
906 /// load factor less than or equal to.
907 float
908 max_load_factor() const noexcept
909 { return _M_h.max_load_factor(); }
910
911 /**
912 * @brief Change the %unordered_set maximum load factor.
913 * @param __z The new maximum load factor.
914 */
915 void
917 { _M_h.max_load_factor(__z); }
918
919 /**
920 * @brief May rehash the %unordered_set.
921 * @param __n The new number of buckets.
922 *
923 * Rehash will occur only if the new number of buckets respect the
924 * %unordered_set maximum load factor.
925 */
926 void
928 { _M_h.rehash(__n); }
929
930 /**
931 * @brief Prepare the %unordered_set for a specified number of
932 * elements.
933 * @param __n Number of elements required.
934 *
935 * Same as rehash(ceil(n / max_load_factor())).
936 */
937 void
939 { _M_h.reserve(__n); }
940
941 template<typename _Value1, typename _Hash1, typename _Pred1,
942 typename _Alloc1>
943 friend bool
946 };
947
948#if __cpp_deduction_guides >= 201606
949
950 template<typename _InputIterator,
951 typename _Hash =
952 hash<typename iterator_traits<_InputIterator>::value_type>,
953 typename _Pred =
954 equal_to<typename iterator_traits<_InputIterator>::value_type>,
955 typename _Allocator =
956 allocator<typename iterator_traits<_InputIterator>::value_type>,
957 typename = _RequireInputIter<_InputIterator>,
958 typename = _RequireNotAllocatorOrIntegral<_Hash>,
959 typename = _RequireNotAllocator<_Pred>,
960 typename = _RequireAllocator<_Allocator>>
961 unordered_set(_InputIterator, _InputIterator,
962 unordered_set<int>::size_type = {},
963 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
965 _Hash, _Pred, _Allocator>;
966
967 template<typename _Tp, typename _Hash = hash<_Tp>,
968 typename _Pred = equal_to<_Tp>,
969 typename _Allocator = allocator<_Tp>,
970 typename = _RequireNotAllocatorOrIntegral<_Hash>,
971 typename = _RequireNotAllocator<_Pred>,
972 typename = _RequireAllocator<_Allocator>>
975 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
977
978 template<typename _InputIterator, typename _Allocator,
979 typename = _RequireInputIter<_InputIterator>,
980 typename = _RequireAllocator<_Allocator>>
981 unordered_set(_InputIterator, _InputIterator,
984 hash<
986 equal_to<
988 _Allocator>;
989
990 template<typename _InputIterator, typename _Hash, typename _Allocator,
991 typename = _RequireInputIter<_InputIterator>,
992 typename = _RequireNotAllocatorOrIntegral<_Hash>,
993 typename = _RequireAllocator<_Allocator>>
994 unordered_set(_InputIterator, _InputIterator,
996 _Hash, _Allocator)
998 _Hash,
999 equal_to<
1001 _Allocator>;
1002
1003 template<typename _Tp, typename _Allocator,
1004 typename = _RequireAllocator<_Allocator>>
1008
1009 template<typename _Tp, typename _Hash, typename _Allocator,
1010 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1011 typename = _RequireAllocator<_Allocator>>
1013 unordered_set<int>::size_type, _Hash, _Allocator)
1015
1016#if __glibcxx_ranges_to_container // C++ >= 23
1017 template<ranges::input_range _Rg,
1018 __not_allocator_like _Hash = hash<ranges::range_value_t<_Rg>>,
1019 __not_allocator_like _Pred = equal_to<ranges::range_value_t<_Rg>>,
1020 __allocator_like _Allocator = allocator<ranges::range_value_t<_Rg>>>
1021 unordered_set(from_range_t, _Rg&&, unordered_set<int>::size_type = {},
1022 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1023 -> unordered_set<ranges::range_value_t<_Rg>, _Hash, _Pred, _Allocator>;
1024
1025 template<ranges::input_range _Rg,
1026 __allocator_like _Allocator>
1027 unordered_set(from_range_t, _Rg&&, unordered_set<int>::size_type,
1028 _Allocator)
1032 _Allocator>;
1033
1034 template<ranges::input_range _Rg,
1035 __allocator_like _Allocator>
1036 unordered_set(from_range_t, _Rg&&, _Allocator)
1040 _Allocator>;
1041
1042 template<ranges::input_range _Rg,
1043 __not_allocator_like _Hash,
1044 __allocator_like _Allocator>
1045 unordered_set(from_range_t, _Rg&&, unordered_set<int>::size_type,
1046 _Hash, _Allocator)
1049 _Allocator>;
1050#endif
1051#endif
1052
1053 /**
1054 * @brief A standard container composed of equivalent keys
1055 * (possibly containing multiple of each key value) in which the
1056 * elements' keys are the elements themselves.
1057 *
1058 * @ingroup unordered_associative_containers
1059 * @headerfile unordered_set
1060 * @since C++11
1061 *
1062 * @tparam _Value Type of key objects.
1063 * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
1064 * @tparam _Pred Predicate function object type, defaults
1065 * to equal_to<_Value>.
1066 * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
1067 *
1068 * Meets the requirements of a <a href="tables.html#65">container</a>, and
1069 * <a href="tables.html#xx">unordered associative container</a>
1070 *
1071 * Base is _Hashtable, dispatched at compile time via template
1072 * alias __umset_hashtable.
1073 */
1074 template<typename _Value,
1075 typename _Hash = hash<_Value>,
1076 typename _Pred = equal_to<_Value>,
1077 typename _Alloc = allocator<_Value>>
1079 {
1080 typedef __umset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
1081 _Hashtable _M_h;
1082
1083 public:
1084 // typedefs:
1085 ///@{
1086 /// Public typedefs.
1087 typedef typename _Hashtable::key_type key_type;
1088 typedef typename _Hashtable::value_type value_type;
1089 typedef typename _Hashtable::hasher hasher;
1090 typedef typename _Hashtable::key_equal key_equal;
1091 typedef typename _Hashtable::allocator_type allocator_type;
1092 ///@}
1093
1094 ///@{
1095 /// Iterator-related typedefs.
1096 typedef typename _Hashtable::pointer pointer;
1097 typedef typename _Hashtable::const_pointer const_pointer;
1098 typedef typename _Hashtable::reference reference;
1099 typedef typename _Hashtable::const_reference const_reference;
1100 typedef typename _Hashtable::iterator iterator;
1101 typedef typename _Hashtable::const_iterator const_iterator;
1102 typedef typename _Hashtable::local_iterator local_iterator;
1103 typedef typename _Hashtable::const_local_iterator const_local_iterator;
1104 typedef typename _Hashtable::size_type size_type;
1105 typedef typename _Hashtable::difference_type difference_type;
1106 ///@}
1107
1108#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1109 using node_type = typename _Hashtable::node_type;
1110#endif
1111
1112 // construct/destroy/copy
1113
1114 /// Default constructor.
1116
1117 /**
1118 * @brief Default constructor creates no elements.
1119 * @param __n Minimal initial number of buckets.
1120 * @param __hf A hash functor.
1121 * @param __eql A key equality functor.
1122 * @param __a An allocator object.
1123 */
1124 explicit
1126 const hasher& __hf = hasher(),
1127 const key_equal& __eql = key_equal(),
1128 const allocator_type& __a = allocator_type())
1129 : _M_h(__n, __hf, __eql, __a)
1130 { }
1131
1132 /**
1133 * @brief Builds an %unordered_multiset from a range.
1134 * @param __first An input iterator.
1135 * @param __last An input iterator.
1136 * @param __n Minimal initial number of buckets.
1137 * @param __hf A hash functor.
1138 * @param __eql A key equality functor.
1139 * @param __a An allocator object.
1140 *
1141 * Create an %unordered_multiset consisting of copies of the elements
1142 * from [__first,__last). This is linear in N (where N is
1143 * distance(__first,__last)).
1144 */
1145 template<typename _InputIterator>
1146 unordered_multiset(_InputIterator __first, _InputIterator __last,
1147 size_type __n = 0,
1148 const hasher& __hf = hasher(),
1149 const key_equal& __eql = key_equal(),
1150 const allocator_type& __a = allocator_type())
1151 : _M_h(__first, __last, __n, __hf, __eql, __a)
1152 { }
1153
1154 /// Copy constructor.
1156
1157 /// Move constructor.
1159
1160 /**
1161 * @brief Builds an %unordered_multiset from an initializer_list.
1162 * @param __l An initializer_list.
1163 * @param __n Minimal initial number of buckets.
1164 * @param __hf A hash functor.
1165 * @param __eql A key equality functor.
1166 * @param __a An allocator object.
1167 *
1168 * Create an %unordered_multiset consisting of copies of the elements in
1169 * the list. This is linear in N (where N is @a __l.size()).
1170 */
1172 size_type __n = 0,
1173 const hasher& __hf = hasher(),
1174 const key_equal& __eql = key_equal(),
1175 const allocator_type& __a = allocator_type())
1176 : _M_h(__l, __n, __hf, __eql, __a)
1177 { }
1178
1179 /// Copy assignment operator.
1182
1183 /// Move assignment operator.
1186
1187 /**
1188 * @brief Creates an %unordered_multiset with no elements.
1189 * @param __a An allocator object.
1190 */
1191 explicit
1193 : _M_h(__a)
1194 { }
1195
1196 /*
1197 * @brief Copy constructor with allocator argument.
1198 * @param __uset Input %unordered_multiset to copy.
1199 * @param __a An allocator object.
1200 */
1202 const allocator_type& __a)
1203 : _M_h(__umset._M_h, __a)
1204 { }
1205
1206 /*
1207 * @brief Move constructor with allocator argument.
1208 * @param __umset Input %unordered_multiset to move.
1209 * @param __a An allocator object.
1210 */
1211 unordered_multiset(unordered_multiset&& __umset,
1212 const allocator_type& __a)
1213 noexcept( noexcept(_Hashtable(std::move(__umset._M_h), __a)) )
1214 : _M_h(std::move(__umset._M_h), __a)
1215 { }
1216
1218 : unordered_multiset(__n, hasher(), key_equal(), __a)
1219 { }
1220
1221 unordered_multiset(size_type __n, const hasher& __hf,
1222 const allocator_type& __a)
1223 : unordered_multiset(__n, __hf, key_equal(), __a)
1224 { }
1225
1226 template<typename _InputIterator>
1227 unordered_multiset(_InputIterator __first, _InputIterator __last,
1228 size_type __n,
1229 const allocator_type& __a)
1230 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
1231 { }
1232
1233 template<typename _InputIterator>
1234 unordered_multiset(_InputIterator __first, _InputIterator __last,
1235 size_type __n, const hasher& __hf,
1236 const allocator_type& __a)
1237 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
1238 { }
1239
1240 unordered_multiset(initializer_list<value_type> __l,
1241 size_type __n,
1242 const allocator_type& __a)
1243 : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
1244 { }
1245
1246 unordered_multiset(initializer_list<value_type> __l,
1247 size_type __n, const hasher& __hf,
1248 const allocator_type& __a)
1249 : unordered_multiset(__l, __n, __hf, key_equal(), __a)
1250 { }
1251
1252#if __glibcxx_ranges_to_container // C++ >= 23
1253 /**
1254 * @brief Builds an %unordered_multiset from a range.
1255 * @since C++23
1256 * @param __rg An input range of elements that can be converted to
1257 * the set's value type.
1258 * @param __n Minimal initial number of buckets.
1259 * @param __hf A hash functor.
1260 * @param __eql A key equality functor.
1261 * @param __a An allocator object.
1262 *
1263 * Create an %unordered_multiset consisting of copies of the elements in the
1264 * range. This is linear in N (where N is `std::ranges::size(__rg)`).
1265 */
1266 template<__detail::__container_compatible_range<_Value> _Rg>
1267 unordered_multiset(from_range_t, _Rg&& __rg,
1268 size_type __n = 0,
1269 const hasher& __hf = hasher(),
1270 const key_equal& __eql = key_equal(),
1271 const allocator_type& __a = allocator_type())
1272 : _M_h(__n, __hf, __eql, __a)
1273 { insert_range(std::forward<_Rg>(__rg)); }
1274
1275
1276 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1277 // 2713. More missing allocator-extended constructors for unordered container
1278 template<__detail::__container_compatible_range<_Value> _Rg>
1279 unordered_multiset(from_range_t, _Rg&& __rg, const allocator_type& __a)
1280 : _M_h(0, hasher(), key_equal(), __a)
1281 { insert_range(std::forward<_Rg>(__rg)); }
1282
1283 template<__detail::__container_compatible_range<_Value> _Rg>
1284 unordered_multiset(from_range_t, _Rg&& __rg, size_type __n,
1285 const allocator_type& __a)
1286 : _M_h(__n, hasher(), key_equal(), __a)
1287 { insert_range(std::forward<_Rg>(__rg)); }
1288
1289 template<__detail::__container_compatible_range<_Value> _Rg>
1290 unordered_multiset(from_range_t, _Rg&& __rg, size_type __n,
1291 const hasher& __hf, const allocator_type& __a)
1292 : _M_h(__n, __hf, key_equal(), __a)
1293 { insert_range(std::forward<_Rg>(__rg)); }
1294#endif
1295
1296
1297 /**
1298 * @brief %Unordered_multiset list assignment operator.
1299 * @param __l An initializer_list.
1300 *
1301 * This function fills an %unordered_multiset with copies of the elements
1302 * in the initializer list @a __l.
1303 *
1304 * Note that the assignment completely changes the %unordered_multiset
1305 * and that the resulting %unordered_multiset's size is the same as the
1306 * number of elements assigned.
1307 */
1310 {
1311 _M_h = __l;
1312 return *this;
1313 }
1314
1315 /// Returns the allocator object used by the %unordered_multiset.
1316 allocator_type
1317 get_allocator() const noexcept
1318 { return _M_h.get_allocator(); }
1319
1320 // size and capacity:
1321
1322 /// Returns true if the %unordered_multiset is empty.
1323 _GLIBCXX_NODISCARD bool
1324 empty() const noexcept
1325 { return _M_h.empty(); }
1326
1327 /// Returns the size of the %unordered_multiset.
1328 size_type
1329 size() const noexcept
1330 { return _M_h.size(); }
1331
1332 /// Returns the maximum size of the %unordered_multiset.
1333 size_type
1334 max_size() const noexcept
1335 { return _M_h.max_size(); }
1336
1337 // iterators.
1338
1339 ///@{
1340 /**
1341 * Returns a read-only (constant) iterator that points to the first
1342 * element in the %unordered_multiset.
1343 */
1344 iterator
1345 begin() noexcept
1346 { return _M_h.begin(); }
1347
1348 const_iterator
1349 begin() const noexcept
1350 { return _M_h.begin(); }
1351 ///@}
1352
1353 ///@{
1354 /**
1355 * Returns a read-only (constant) iterator that points one past the last
1356 * element in the %unordered_multiset.
1357 */
1358 iterator
1359 end() noexcept
1360 { return _M_h.end(); }
1361
1362 const_iterator
1363 end() const noexcept
1364 { return _M_h.end(); }
1365 ///@}
1366
1367 /**
1368 * Returns a read-only (constant) iterator that points to the first
1369 * element in the %unordered_multiset.
1370 */
1371 const_iterator
1372 cbegin() const noexcept
1373 { return _M_h.begin(); }
1374
1375 /**
1376 * Returns a read-only (constant) iterator that points one past the last
1377 * element in the %unordered_multiset.
1378 */
1379 const_iterator
1380 cend() const noexcept
1381 { return _M_h.end(); }
1382
1383 // modifiers.
1384
1385 /**
1386 * @brief Builds and insert an element into the %unordered_multiset.
1387 * @param __args Arguments used to generate an element.
1388 * @return An iterator that points to the inserted element.
1389 *
1390 * Insertion requires amortized constant time.
1391 */
1392 template<typename... _Args>
1393 iterator
1394 emplace(_Args&&... __args)
1395 { return _M_h.emplace(std::forward<_Args>(__args)...); }
1396
1397 /**
1398 * @brief Inserts an element into the %unordered_multiset.
1399 * @param __pos An iterator that serves as a hint as to where the
1400 * element should be inserted.
1401 * @param __args Arguments used to generate the element to be
1402 * inserted.
1403 * @return An iterator that points to the inserted element.
1404 *
1405 * Note that the first parameter is only a hint and can potentially
1406 * improve the performance of the insertion process. A bad hint would
1407 * cause no gains in efficiency.
1408 *
1409 * For more on @a hinting, see:
1410 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1411 *
1412 * Insertion requires amortized constant time.
1413 */
1414 template<typename... _Args>
1415 iterator
1416 emplace_hint(const_iterator __pos, _Args&&... __args)
1417 { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
1418
1419 ///@{
1420 /**
1421 * @brief Inserts an element into the %unordered_multiset.
1422 * @param __x Element to be inserted.
1423 * @return An iterator that points to the inserted element.
1424 *
1425 * Insertion requires amortized constant time.
1426 */
1427 iterator
1428 insert(const value_type& __x)
1429 { return _M_h.insert(__x); }
1430
1431 iterator
1433 { return _M_h.insert(std::move(__x)); }
1434 ///@}
1435
1436 ///@{
1437 /**
1438 * @brief Inserts an element into the %unordered_multiset.
1439 * @param __hint An iterator that serves as a hint as to where the
1440 * element should be inserted.
1441 * @param __x Element to be inserted.
1442 * @return An iterator that points to the inserted element.
1443 *
1444 * Note that the first parameter is only a hint and can potentially
1445 * improve the performance of the insertion process. A bad hint would
1446 * cause no gains in efficiency.
1447 *
1448 * For more on @a hinting, see:
1449 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
1450 *
1451 * Insertion requires amortized constant.
1452 */
1453 iterator
1455 { return _M_h.insert(__hint, __x); }
1456
1457 iterator
1459 { return _M_h.insert(__hint, std::move(__x)); }
1460 ///@}
1461
1462 /**
1463 * @brief A template function that inserts a range of elements.
1464 * @param __first Iterator pointing to the start of the range to be
1465 * inserted.
1466 * @param __last Iterator pointing to the end of the range.
1467 *
1468 * Complexity similar to that of the range constructor.
1469 */
1470 template<typename _InputIterator>
1471 void
1472 insert(_InputIterator __first, _InputIterator __last)
1473 { _M_h.insert(__first, __last); }
1474
1475 /**
1476 * @brief Inserts a list of elements into the %unordered_multiset.
1477 * @param __l A std::initializer_list<value_type> of elements to be
1478 * inserted.
1479 *
1480 * Complexity similar to that of the range constructor.
1481 */
1482 void
1484 { _M_h.insert(__l); }
1485
1486#if __glibcxx_ranges_to_container // C++ >= 23
1487 /**
1488 * @brief Inserts a range of elements.
1489 * @since C++23
1490 * @param __rg An input range of elements that can be converted to
1491 * the set's value type.
1492 */
1493 template<__detail::__container_compatible_range<_Value> _Rg>
1494 void
1495 insert_range(_Rg&& __rg)
1496 {
1497 auto __first = ranges::begin(__rg);
1498 const auto __last = ranges::end(__rg);
1499 if (__first == __last)
1500 return;
1501
1502 if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
1503 _M_h._M_rehash_insert(size_type(ranges::distance(__rg)));
1504 else
1505 _M_h._M_rehash_insert(1);
1506
1507 for (; __first != __last; ++__first)
1508 _M_h.emplace(*__first);
1509 }
1510#endif
1511
1512#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1513 /// Extract a node.
1514 node_type
1515 extract(const_iterator __pos)
1516 {
1517 __glibcxx_assert(__pos != end());
1518 return _M_h.extract(__pos);
1519 }
1520
1521 /// Extract a node.
1522 node_type
1523 extract(const key_type& __key)
1524 { return _M_h.extract(__key); }
1525
1526 /// Re-insert an extracted node.
1527 iterator
1528 insert(node_type&& __nh)
1529 { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
1530
1531 /// Re-insert an extracted node.
1532 iterator
1533 insert(const_iterator __hint, node_type&& __nh)
1534 { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
1535#endif // node_extract
1536
1537 ///@{
1538 /**
1539 * @brief Erases an element from an %unordered_multiset.
1540 * @param __position An iterator pointing to the element to be erased.
1541 * @return An iterator pointing to the element immediately following
1542 * @a __position prior to the element being erased. If no such
1543 * element exists, end() is returned.
1544 *
1545 * This function erases an element, pointed to by the given iterator,
1546 * from an %unordered_multiset.
1547 *
1548 * Note that this function only erases the element, and that if the
1549 * element is itself a pointer, the pointed-to memory is not touched in
1550 * any way. Managing the pointer is the user's responsibility.
1551 */
1552 iterator
1554 { return _M_h.erase(__position); }
1555
1556 // LWG 2059.
1557 iterator
1558 erase(iterator __position)
1559 { return _M_h.erase(__position); }
1560 ///@}
1561
1562
1563 /**
1564 * @brief Erases elements according to the provided key.
1565 * @param __x Key of element to be erased.
1566 * @return The number of elements erased.
1567 *
1568 * This function erases all the elements located by the given key from
1569 * an %unordered_multiset.
1570 *
1571 * Note that this function only erases the element, and that if the
1572 * element is itself a pointer, the pointed-to memory is not touched in
1573 * any way. Managing the pointer is the user's responsibility.
1574 */
1575 size_type
1576 erase(const key_type& __x)
1577 { return _M_h.erase(__x); }
1578
1579 /**
1580 * @brief Erases a [__first,__last) range of elements from an
1581 * %unordered_multiset.
1582 * @param __first Iterator pointing to the start of the range to be
1583 * erased.
1584 * @param __last Iterator pointing to the end of the range to
1585 * be erased.
1586 * @return The iterator @a __last.
1587 *
1588 * This function erases a sequence of elements from an
1589 * %unordered_multiset.
1590 *
1591 * Note that this function only erases the element, and that if
1592 * the element is itself a pointer, the pointed-to memory is not touched
1593 * in any way. Managing the pointer is the user's responsibility.
1594 */
1595 iterator
1597 { return _M_h.erase(__first, __last); }
1598
1599 /**
1600 * Erases all elements in an %unordered_multiset.
1601 *
1602 * Note that this function only erases the elements, and that if the
1603 * elements themselves are pointers, the pointed-to memory is not touched
1604 * in any way. Managing the pointer is the user's responsibility.
1605 */
1606 void
1607 clear() noexcept
1608 { _M_h.clear(); }
1609
1610 /**
1611 * @brief Swaps data with another %unordered_multiset.
1612 * @param __x An %unordered_multiset of the same element and allocator
1613 * types.
1614 *
1615 * This exchanges the elements between two sets in constant time.
1616 * Note that the global std::swap() function is specialized such that
1617 * std::swap(s1,s2) will feed to this function.
1618 */
1619 void
1621 noexcept( noexcept(_M_h.swap(__x._M_h)) )
1622 { _M_h.swap(__x._M_h); }
1623
1624#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1625 template<typename, typename, typename>
1626 friend class std::_Hash_merge_helper;
1627
1628 template<typename _H2, typename _P2>
1629 void
1631 {
1632 if constexpr (is_same_v<_H2, _Hash> && is_same_v<_P2, _Pred>)
1633 if (std::__addressof(__source) == this) [[__unlikely__]]
1634 return;
1635
1636 using _Merge_helper
1637 = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1638 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1639 }
1640
1641 template<typename _H2, typename _P2>
1642 void
1643 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
1644 {
1645 using _Merge_helper
1646 = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1647 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1648 }
1649
1650 template<typename _H2, typename _P2>
1651 void
1652 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
1653 {
1654 using _Merge_helper
1655 = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
1656 _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
1657 }
1658
1659 template<typename _H2, typename _P2>
1660 void
1661 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
1662 { merge(__source); }
1663#endif // node_extract
1664
1665 // observers.
1666
1667 /// Returns the hash functor object with which the %unordered_multiset
1668 /// was constructed.
1669 hasher
1671 { return _M_h.hash_function(); }
1672
1673 /// Returns the key comparison object with which the %unordered_multiset
1674 /// was constructed.
1675 key_equal
1676 key_eq() const
1677 { return _M_h.key_eq(); }
1678
1679 // lookup.
1680
1681 ///@{
1682 /**
1683 * @brief Tries to locate an element in an %unordered_multiset.
1684 * @param __x Element to be located.
1685 * @return Iterator pointing to sought-after element, or end() if not
1686 * found.
1687 *
1688 * This function takes a key and tries to locate the element with which
1689 * the key matches. If successful the function returns an iterator
1690 * pointing to the sought after element. If unsuccessful it returns the
1691 * past-the-end ( @c end() ) iterator.
1692 */
1693 iterator
1694 find(const key_type& __x)
1695 { return _M_h.find(__x); }
1696
1697#if __cplusplus > 201703L
1698 template<typename _Kt>
1699 auto
1700 find(const _Kt& __x)
1701 -> decltype(_M_h._M_find_tr(__x))
1702 { return _M_h._M_find_tr(__x); }
1703#endif
1704
1705 const_iterator
1706 find(const key_type& __x) const
1707 { return _M_h.find(__x); }
1708
1709#if __cplusplus > 201703L
1710 template<typename _Kt>
1711 auto
1712 find(const _Kt& __x) const
1713 -> decltype(_M_h._M_find_tr(__x))
1714 { return _M_h._M_find_tr(__x); }
1715#endif
1716 ///@}
1717
1718 ///@{
1719 /**
1720 * @brief Finds the number of elements.
1721 * @param __x Element to located.
1722 * @return Number of elements with specified key.
1723 */
1724 size_type
1725 count(const key_type& __x) const
1726 { return _M_h.count(__x); }
1727
1728#if __cplusplus > 201703L
1729 template<typename _Kt>
1730 auto
1731 count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x))
1732 { return _M_h._M_count_tr(__x); }
1733#endif
1734 ///@}
1735
1736#if __cplusplus > 201703L
1737 ///@{
1738 /**
1739 * @brief Finds whether an element with the given key exists.
1740 * @param __x Key of elements to be located.
1741 * @return True if there is any element with the specified key.
1742 */
1743 bool
1744 contains(const key_type& __x) const
1745 { return _M_h.find(__x) != _M_h.end(); }
1746
1747 template<typename _Kt>
1748 auto
1749 contains(const _Kt& __x) const
1750 -> decltype(_M_h._M_find_tr(__x), void(), true)
1751 { return _M_h._M_find_tr(__x) != _M_h.end(); }
1752 ///@}
1753#endif
1754
1755 ///@{
1756 /**
1757 * @brief Finds a subsequence matching given key.
1758 * @param __x Key to be located.
1759 * @return Pair of iterators that possibly points to the subsequence
1760 * matching given key.
1761 */
1764 { return _M_h.equal_range(__x); }
1765
1766#if __cplusplus > 201703L
1767 template<typename _Kt>
1768 auto
1769 equal_range(const _Kt& __x)
1770 -> decltype(_M_h._M_equal_range_tr(__x))
1771 { return _M_h._M_equal_range_tr(__x); }
1772#endif
1773
1775 equal_range(const key_type& __x) const
1776 { return _M_h.equal_range(__x); }
1777
1778#if __cplusplus > 201703L
1779 template<typename _Kt>
1780 auto
1781 equal_range(const _Kt& __x) const
1782 -> decltype(_M_h._M_equal_range_tr(__x))
1783 { return _M_h._M_equal_range_tr(__x); }
1784#endif
1785 ///@}
1786
1787 // bucket interface.
1788
1789 /// Returns the number of buckets of the %unordered_multiset.
1790 size_type
1791 bucket_count() const noexcept
1792 { return _M_h.bucket_count(); }
1793
1794 /// Returns the maximum number of buckets of the %unordered_multiset.
1795 size_type
1796 max_bucket_count() const noexcept
1797 { return _M_h.max_bucket_count(); }
1798
1799 /*
1800 * @brief Returns the number of elements in a given bucket.
1801 * @param __n A bucket index.
1802 * @return The number of elements in the bucket.
1803 */
1804 size_type
1805 bucket_size(size_type __n) const
1806 { return _M_h.bucket_size(__n); }
1807
1808 /*
1809 * @brief Returns the bucket index of a given element.
1810 * @param __key A key instance.
1811 * @return The key bucket index.
1812 */
1813 size_type
1814 bucket(const key_type& __key) const
1815 { return _M_h.bucket(__key); }
1816
1817 ///@{
1818 /**
1819 * @brief Returns a read-only (constant) iterator pointing to the first
1820 * bucket element.
1821 * @param __n The bucket index.
1822 * @return A read-only local iterator.
1823 */
1826 { return _M_h.begin(__n); }
1827
1829 begin(size_type __n) const
1830 { return _M_h.begin(__n); }
1831
1834 { return _M_h.cbegin(__n); }
1835 ///@}
1836
1837 ///@{
1838 /**
1839 * @brief Returns a read-only (constant) iterator pointing to one past
1840 * the last bucket elements.
1841 * @param __n The bucket index.
1842 * @return A read-only local iterator.
1843 */
1846 { return _M_h.end(__n); }
1847
1849 end(size_type __n) const
1850 { return _M_h.end(__n); }
1851
1853 cend(size_type __n) const
1854 { return _M_h.cend(__n); }
1855 ///@}
1856
1857 // hash policy.
1858
1859 /// Returns the average number of elements per bucket.
1860 float
1861 load_factor() const noexcept
1862 { return _M_h.load_factor(); }
1863
1864 /// Returns a positive number that the %unordered_multiset tries to keep the
1865 /// load factor less than or equal to.
1866 float
1867 max_load_factor() const noexcept
1868 { return _M_h.max_load_factor(); }
1869
1870 /**
1871 * @brief Change the %unordered_multiset maximum load factor.
1872 * @param __z The new maximum load factor.
1873 */
1874 void
1876 { _M_h.max_load_factor(__z); }
1877
1878 /**
1879 * @brief May rehash the %unordered_multiset.
1880 * @param __n The new number of buckets.
1881 *
1882 * Rehash will occur only if the new number of buckets respect the
1883 * %unordered_multiset maximum load factor.
1884 */
1885 void
1887 { _M_h.rehash(__n); }
1888
1889 /**
1890 * @brief Prepare the %unordered_multiset for a specified number of
1891 * elements.
1892 * @param __n Number of elements required.
1893 *
1894 * Same as rehash(ceil(n / max_load_factor())).
1895 */
1896 void
1898 { _M_h.reserve(__n); }
1899
1900 template<typename _Value1, typename _Hash1, typename _Pred1,
1901 typename _Alloc1>
1902 friend bool
1905 };
1906
1907
1908#if __cpp_deduction_guides >= 201606
1909
1910 template<typename _InputIterator,
1911 typename _Hash =
1912 hash<typename iterator_traits<_InputIterator>::value_type>,
1913 typename _Pred =
1914 equal_to<typename iterator_traits<_InputIterator>::value_type>,
1915 typename _Allocator =
1916 allocator<typename iterator_traits<_InputIterator>::value_type>,
1917 typename = _RequireInputIter<_InputIterator>,
1918 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1919 typename = _RequireNotAllocator<_Pred>,
1920 typename = _RequireAllocator<_Allocator>>
1921 unordered_multiset(_InputIterator, _InputIterator,
1922 unordered_multiset<int>::size_type = {},
1923 _Hash = _Hash(), _Pred = _Pred(),
1924 _Allocator = _Allocator())
1926 _Hash, _Pred, _Allocator>;
1927
1928 template<typename _Tp, typename _Hash = hash<_Tp>,
1929 typename _Pred = equal_to<_Tp>,
1930 typename _Allocator = allocator<_Tp>,
1931 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1932 typename = _RequireNotAllocator<_Pred>,
1933 typename = _RequireAllocator<_Allocator>>
1936 _Hash = _Hash(), _Pred = _Pred(),
1937 _Allocator = _Allocator())
1939
1940 template<typename _InputIterator, typename _Allocator,
1941 typename = _RequireInputIter<_InputIterator>,
1942 typename = _RequireAllocator<_Allocator>>
1943 unordered_multiset(_InputIterator, _InputIterator,
1946 hash<typename
1948 equal_to<typename
1950 _Allocator>;
1951
1952 template<typename _InputIterator, typename _Hash, typename _Allocator,
1953 typename = _RequireInputIter<_InputIterator>,
1954 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1955 typename = _RequireAllocator<_Allocator>>
1956 unordered_multiset(_InputIterator, _InputIterator,
1958 _Hash, _Allocator)
1959 -> unordered_multiset<typename
1961 _Hash,
1962 equal_to<
1963 typename
1965 _Allocator>;
1966
1967 template<typename _Tp, typename _Allocator,
1968 typename = _RequireAllocator<_Allocator>>
1972
1973 template<typename _Tp, typename _Hash, typename _Allocator,
1974 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1975 typename = _RequireAllocator<_Allocator>>
1977 unordered_multiset<int>::size_type, _Hash, _Allocator)
1979
1980#if __glibcxx_ranges_to_container // C++ >= 23
1981 template<ranges::input_range _Rg,
1982 __not_allocator_like _Hash = hash<ranges::range_value_t<_Rg>>,
1983 __not_allocator_like _Pred = equal_to<ranges::range_value_t<_Rg>>,
1984 __allocator_like _Allocator = allocator<ranges::range_value_t<_Rg>>>
1985 unordered_multiset(from_range_t, _Rg&&,
1987 _Hash = _Hash(), _Pred = _Pred(),
1988 _Allocator = _Allocator())
1989 -> unordered_multiset<ranges::range_value_t<_Rg>, _Hash, _Pred, _Allocator>;
1990
1991 template<ranges::input_range _Rg,
1992 __allocator_like _Allocator>
1993 unordered_multiset(from_range_t, _Rg&&, _Allocator)
1997 _Allocator>;
1998
1999 template<ranges::input_range _Rg,
2000 __allocator_like _Allocator>
2002 _Allocator)
2006 _Allocator>;
2007
2008 template<ranges::input_range _Rg,
2009 __not_allocator_like _Hash,
2010 __allocator_like _Allocator>
2011 unordered_multiset(from_range_t, _Rg&&,
2013 _Hash, _Allocator)
2016 _Allocator>;
2017#endif
2018#endif
2019
2020 template<class _Value, class _Hash, class _Pred, class _Alloc>
2021 inline void
2024 noexcept(noexcept(__x.swap(__y)))
2025 { __x.swap(__y); }
2026
2027 template<class _Value, class _Hash, class _Pred, class _Alloc>
2028 inline void
2031 noexcept(noexcept(__x.swap(__y)))
2032 { __x.swap(__y); }
2033
2034 template<class _Value, class _Hash, class _Pred, class _Alloc>
2035 inline bool
2036 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
2038 { return __x._M_h._M_equal(__y._M_h); }
2039
2040#if __cpp_impl_three_way_comparison < 201907L
2041 template<class _Value, class _Hash, class _Pred, class _Alloc>
2042 inline bool
2043 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
2045 { return !(__x == __y); }
2046#endif
2047
2048 template<class _Value, class _Hash, class _Pred, class _Alloc>
2049 inline bool
2052 { return __x._M_h._M_equal(__y._M_h); }
2053
2054#if __cpp_impl_three_way_comparison < 201907L
2055 template<class _Value, class _Hash, class _Pred, class _Alloc>
2056 inline bool
2059 { return !(__x == __y); }
2060#endif
2061
2062_GLIBCXX_END_NAMESPACE_CONTAINER
2063
2064#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
2065 // Allow std::unordered_set access to internals of compatible sets.
2066 template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc,
2067 typename _Hash2, typename _Eq2>
2068 struct _Hash_merge_helper<
2069 _GLIBCXX_STD_C::unordered_set<_Val, _Hash1, _Eq1, _Alloc>, _Hash2, _Eq2>
2070 {
2071 private:
2072 template<typename... _Tp>
2073 using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
2074 template<typename... _Tp>
2075 using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
2076
2077 friend unordered_set<_Val, _Hash1, _Eq1, _Alloc>;
2078
2079 static auto&
2080 _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
2081 { return __set._M_h; }
2082
2083 static auto&
2084 _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
2085 { return __set._M_h; }
2086 };
2087
2088 // Allow std::unordered_multiset access to internals of compatible sets.
2089 template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc,
2090 typename _Hash2, typename _Eq2>
2091 struct _Hash_merge_helper<
2092 _GLIBCXX_STD_C::unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>,
2093 _Hash2, _Eq2>
2094 {
2095 private:
2096 template<typename... _Tp>
2097 using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
2098 template<typename... _Tp>
2099 using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
2100
2101 friend unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>;
2102
2103 static auto&
2104 _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
2105 { return __set._M_h; }
2106
2107 static auto&
2108 _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
2109 { return __set._M_h; }
2110 };
2111#endif // node_extract
2112
2113_GLIBCXX_END_NAMESPACE_VERSION
2114} // namespace std
2115
2116#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:304
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.