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