libstdc++
debug/unordered_set
Go to the documentation of this file.
1// Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
2
3// Copyright (C) 2003-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 debug/unordered_set
26 * This file is a GNU debug extension to the Standard C++ Library.
27 */
28
29#ifndef _GLIBCXX_DEBUG_UNORDERED_SET
30#define _GLIBCXX_DEBUG_UNORDERED_SET 1
31
32#ifdef _GLIBCXX_SYSHDR
33#pragma GCC system_header
34#endif
35
36#if __cplusplus < 201103L
37# include <bits/c++0x_warning.h>
38#else
39# include <bits/c++config.h>
40namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug {
41 template<typename _Key, typename _Hash, typename _Pred, typename _Allocator>
42 class unordered_set;
43 template<typename _Key, typename _Hash, typename _Pred, typename _Allocator>
44 class unordered_multiset;
45} } // namespace std::__debug
46# include <unordered_set>
47
48#include <debug/safe_unordered_container.h>
49#include <debug/safe_container.h>
50#include <debug/safe_iterator.h>
51#include <debug/safe_local_iterator.h>
52
53namespace std _GLIBCXX_VISIBILITY(default)
54{
55namespace __debug
56{
57 /// Class std::unordered_set with safety/checking/debug instrumentation.
58 template<typename _Value,
59 typename _Hash = std::hash<_Value>,
60 typename _Pred = std::equal_to<_Value>,
61 typename _Alloc = std::allocator<_Value> >
62 class unordered_set
63 : public __gnu_debug::_Safe_container<
64 unordered_set<_Value, _Hash, _Pred, _Alloc>, _Alloc,
65 __gnu_debug::_Safe_unordered_container>,
66 public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc>
67 {
68 typedef _GLIBCXX_STD_C::unordered_set<
69 _Value, _Hash, _Pred, _Alloc> _Base;
70 typedef __gnu_debug::_Safe_container<
71 unordered_set, _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
72
73 typedef typename _Base::const_iterator _Base_const_iterator;
74 typedef typename _Base::iterator _Base_iterator;
75 typedef typename _Base::const_local_iterator _Base_const_local_iterator;
76 typedef typename _Base::local_iterator _Base_local_iterator;
77
78 template<typename _ItT, typename _SeqT, typename _CatT>
79 friend class ::__gnu_debug::_Safe_iterator;
80 template<typename _ItT, typename _SeqT>
81 friend class ::__gnu_debug::_Safe_local_iterator;
82
83 // Reference wrapper for base class. See PR libstdc++/90102.
84 struct _Base_ref
85 {
86 _Base_ref(const _Base& __r) : _M_ref(__r) { }
87
88 const _Base& _M_ref;
89 };
90
91 public:
92 typedef typename _Base::size_type size_type;
93 typedef typename _Base::difference_type difference_type;
94 typedef typename _Base::hasher hasher;
95 typedef typename _Base::key_equal key_equal;
96 typedef typename _Base::allocator_type allocator_type;
97
98 typedef typename _Base::key_type key_type;
99 typedef typename _Base::value_type value_type;
100
101 typedef typename _Base::pointer pointer;
102 typedef typename _Base::const_pointer const_pointer;
103 typedef typename _Base::reference reference;
104 typedef typename _Base::const_reference const_reference;
105 typedef __gnu_debug::_Safe_iterator<
106 _Base_iterator, unordered_set> iterator;
107 typedef __gnu_debug::_Safe_iterator<
108 _Base_const_iterator, unordered_set> const_iterator;
109 typedef __gnu_debug::_Safe_local_iterator<
110 _Base_local_iterator, unordered_set> local_iterator;
111 typedef __gnu_debug::_Safe_local_iterator<
112 _Base_const_local_iterator, unordered_set> const_local_iterator;
113
114 unordered_set() = default;
115
116 explicit
117 unordered_set(size_type __n,
118 const hasher& __hf = hasher(),
119 const key_equal& __eql = key_equal(),
120 const allocator_type& __a = allocator_type())
121 : _Base(__n, __hf, __eql, __a) { }
122
123 template<typename _InputIterator>
124 unordered_set(_InputIterator __first, _InputIterator __last,
125 size_type __n = 0,
126 const hasher& __hf = hasher(),
127 const key_equal& __eql = key_equal(),
128 const allocator_type& __a = allocator_type())
129 : _Base(__gnu_debug::__base(
130 __glibcxx_check_valid_constructor_range(__first, __last)),
131 __gnu_debug::__base(__last), __n,
132 __hf, __eql, __a) { }
133
134 unordered_set(const unordered_set&) = default;
135
136 unordered_set(_Base_ref __x)
137 : _Base(__x._M_ref) { }
138
139 unordered_set(unordered_set&&) = default;
140
141 explicit
142 unordered_set(const allocator_type& __a)
143 : _Base(__a) { }
144
145 unordered_set(const unordered_set& __uset,
146 const allocator_type& __a)
147 : _Base(__uset, __a) { }
148
149 unordered_set(unordered_set&& __uset,
150 const allocator_type& __a)
151 noexcept( noexcept(_Base(std::move(__uset), __a)) )
152 : _Safe(std::move(__uset), __a),
153 _Base(std::move(__uset), __a) { }
154
155 unordered_set(initializer_list<value_type> __l,
156 size_type __n = 0,
157 const hasher& __hf = hasher(),
158 const key_equal& __eql = key_equal(),
159 const allocator_type& __a = allocator_type())
160 : _Base(__l, __n, __hf, __eql, __a) { }
161
162 unordered_set(size_type __n, const allocator_type& __a)
163 : unordered_set(__n, hasher(), key_equal(), __a)
164 { }
165
166 unordered_set(size_type __n, const hasher& __hf,
167 const allocator_type& __a)
168 : unordered_set(__n, __hf, key_equal(), __a)
169 { }
170
171 template<typename _InputIterator>
172 unordered_set(_InputIterator __first, _InputIterator __last,
173 const allocator_type& __a)
174 : unordered_set(__first, __last, 0, hasher(), key_equal(), __a)
175 { }
176
177 template<typename _InputIterator>
178 unordered_set(_InputIterator __first, _InputIterator __last,
179 size_type __n,
180 const allocator_type& __a)
181 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
182 { }
183
184 template<typename _InputIterator>
185 unordered_set(_InputIterator __first, _InputIterator __last,
186 size_type __n, const hasher& __hf,
187 const allocator_type& __a)
188 : unordered_set(__first, __last, __n, __hf, key_equal(), __a)
189 { }
190
191 unordered_set(initializer_list<value_type> __l,
192 const allocator_type& __a)
193 : unordered_set(__l, 0, hasher(), key_equal(), __a)
194 { }
195
196 unordered_set(initializer_list<value_type> __l,
197 size_type __n,
198 const allocator_type& __a)
199 : unordered_set(__l, __n, hasher(), key_equal(), __a)
200 { }
201
202 unordered_set(initializer_list<value_type> __l,
203 size_type __n, const hasher& __hf,
204 const allocator_type& __a)
205 : unordered_set(__l, __n, __hf, key_equal(), __a)
206 { }
207
208#if __glibcxx_containers_ranges // C++ >= 23
209 template<__detail::__container_compatible_range<value_type> _Rg>
210 unordered_set(from_range_t, _Rg&& __rg,
211 size_type __n = 0,
212 const hasher& __hf = hasher(),
213 const key_equal& __eql = key_equal(),
214 const allocator_type& __a = allocator_type())
215 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __eql, __a)
216 { }
217
218 template<__detail::__container_compatible_range<value_type> _Rg>
219 unordered_set(from_range_t, _Rg&& __rg, const allocator_type& __a)
220 : _Base(from_range, std::forward<_Rg>(__rg), __a)
221 { }
222
223 template<__detail::__container_compatible_range<value_type> _Rg>
224 unordered_set(from_range_t, _Rg&& __rg, size_type __n,
225 const allocator_type& __a)
226 : _Base(from_range, std::forward<_Rg>(__rg), __n, __a)
227 { }
228
229 template<__detail::__container_compatible_range<value_type> _Rg>
230 unordered_set(from_range_t, _Rg&& __rg, size_type __n,
231 const hasher& __hf, const allocator_type& __a)
232 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __a)
233 { }
234#endif
235
236 ~unordered_set() = default;
237
238 unordered_set&
239 operator=(const unordered_set&) = default;
240
241 unordered_set&
242 operator=(unordered_set&&) = default;
243
244 unordered_set&
245 operator=(initializer_list<value_type> __l)
246 {
247 _Base::operator=(__l);
248 this->_M_invalidate_all();
249 return *this;
250 }
251
252 using _Base::get_allocator;
253 using _Base::empty;
254 using _Base::size;
255 using _Base::max_size;
256
257 void
258 swap(unordered_set& __x)
259 noexcept( noexcept(declval<_Base&>().swap(__x)) )
260 {
261 _Safe::_M_swap(__x);
262 _Base::swap(__x);
263 }
264
265 void
266 clear() noexcept
267 {
268 _Base::clear();
269 this->_M_invalidate_all();
270 }
271
272 iterator
273 begin() noexcept
274 { return { _Base::begin(), this }; }
275
276 const_iterator
277 begin() const noexcept
278 { return { _Base::begin(), this }; }
279
280 iterator
281 end() noexcept
282 { return { _Base::end(), this }; }
283
284 const_iterator
285 end() const noexcept
286 { return { _Base::end(), this }; }
287
288 const_iterator
289 cbegin() const noexcept
290 { return { _Base::cbegin(), this }; }
291
292 const_iterator
293 cend() const noexcept
294 { return { _Base::cend(), this }; }
295
296 // local versions
297 local_iterator
298 begin(size_type __b)
299 {
300 __glibcxx_check_bucket_index(__b);
301 return { _Base::begin(__b), this };
302 }
303
304 local_iterator
305 end(size_type __b)
306 {
307 __glibcxx_check_bucket_index(__b);
308 return { _Base::end(__b), this };
309 }
310
311 const_local_iterator
312 begin(size_type __b) const
313 {
314 __glibcxx_check_bucket_index(__b);
315 return { _Base::begin(__b), this };
316 }
317
318 const_local_iterator
319 end(size_type __b) const
320 {
321 __glibcxx_check_bucket_index(__b);
322 return { _Base::end(__b), this };
323 }
324
325 const_local_iterator
326 cbegin(size_type __b) const
327 {
328 __glibcxx_check_bucket_index(__b);
329 return { _Base::cbegin(__b), this };
330 }
331
332 const_local_iterator
333 cend(size_type __b) const
334 {
335 __glibcxx_check_bucket_index(__b);
336 return { _Base::cend(__b), this };
337 }
338
339 using _Base::bucket_count;
340 using _Base::max_bucket_count;
341
342 size_type
343 bucket_size(size_type __b) const
344 {
345 __glibcxx_check_bucket_index(__b);
346 return _Base::bucket_size(__b);
347 }
348
349 using _Base::bucket;
350 using _Base::load_factor;
351
352 float
353 max_load_factor() const noexcept
354 { return _Base::max_load_factor(); }
355
356 void
357 max_load_factor(float __f)
358 {
359 __glibcxx_check_max_load_factor(__f);
360 _Base::max_load_factor(__f);
361 }
362
363 using _Base::rehash;
364 using _Base::reserve;
365
366 template<typename... _Args>
367 std::pair<iterator, bool>
368 emplace(_Args&&... __args)
369 {
370 size_type __bucket_count = this->bucket_count();
371 auto __res = _Base::emplace(std::forward<_Args>(__args)...);
372 _M_check_rehashed(__bucket_count);
373 return { { __res.first, this }, __res.second };
374 }
375
376 template<typename... _Args>
377 iterator
378 emplace_hint(const_iterator __hint, _Args&&... __args)
379 {
380 __glibcxx_check_insert(__hint);
381 size_type __bucket_count = this->bucket_count();
382 auto __it = _Base::emplace_hint(__hint.base(),
383 std::forward<_Args>(__args)...);
384 _M_check_rehashed(__bucket_count);
385 return { __it, this };
386 }
387
388 std::pair<iterator, bool>
389 insert(const value_type& __obj)
390 {
391 size_type __bucket_count = this->bucket_count();
392 auto __res = _Base::insert(__obj);
393 _M_check_rehashed(__bucket_count);
394 return { { __res.first, this }, __res.second };
395 }
396
397 iterator
398 insert(const_iterator __hint, const value_type& __obj)
399 {
400 __glibcxx_check_insert(__hint);
401 size_type __bucket_count = this->bucket_count();
402 auto __it = _Base::insert(__hint.base(), __obj);
403 _M_check_rehashed(__bucket_count);
404 return { __it, this };
405 }
406
407 std::pair<iterator, bool>
408 insert(value_type&& __obj)
409 {
410 size_type __bucket_count = this->bucket_count();
411 auto __res = _Base::insert(std::move(__obj));
412 _M_check_rehashed(__bucket_count);
413 return { { __res.first, this }, __res.second };
414 }
415
416 iterator
417 insert(const_iterator __hint, value_type&& __obj)
418 {
419 __glibcxx_check_insert(__hint);
420 size_type __bucket_count = this->bucket_count();
421 auto __it = _Base::insert(__hint.base(), std::move(__obj));
422 _M_check_rehashed(__bucket_count);
423 return { __it, this };
424 }
425
426 void
427 insert(std::initializer_list<value_type> __l)
428 {
429 size_type __bucket_count = this->bucket_count();
430 _Base::insert(__l);
431 _M_check_rehashed(__bucket_count);
432 }
433
434 template<typename _InputIterator>
435 void
436 insert(_InputIterator __first, _InputIterator __last)
437 {
438 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
439 __glibcxx_check_valid_range2(__first, __last, __dist);
440 size_type __bucket_count = this->bucket_count();
441
442 if (__dist.second >= __gnu_debug::__dp_sign)
443 _Base::insert(__gnu_debug::__unsafe(__first),
444 __gnu_debug::__unsafe(__last));
445 else
446 _Base::insert(__first, __last);
447
448 _M_check_rehashed(__bucket_count);
449 }
450
451#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
452 using node_type = typename _Base::node_type;
453 using insert_return_type = _Node_insert_return<iterator, node_type>;
454
455 node_type
456 extract(const_iterator __position)
457 {
458 __glibcxx_check_erase(__position);
459 return _M_extract(__position.base());
460 }
461
462 node_type
463 extract(const key_type& __key)
464 {
465 const auto __position = _Base::find(__key);
466 if (__position != _Base::end())
467 return _M_extract(__position);
468 return {};
469 }
470
471 insert_return_type
472 insert(node_type&& __nh)
473 {
474 auto __ret = _Base::insert(std::move(__nh));
475 return
476 { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };
477 }
478
479 iterator
480 insert(const_iterator __hint, node_type&& __nh)
481 {
482 __glibcxx_check_insert(__hint);
483 return { _Base::insert(__hint.base(), std::move(__nh)), this };
484 }
485
486 template<typename _H2, typename _P2>
487 void
488 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
489 {
490 auto __guard
491 = _Safe::_S_uc_guard(std::__detail::_Identity{}, __source);
492 _Base::merge(__source);
493 }
494
495 template<typename _H2, typename _P2>
496 void
497 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
498 { merge(__source); }
499
500 template<typename _H2, typename _P2>
501 void
502 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
503 {
504 auto __guard
505 = _Safe::_S_umc_guard(std::__detail::_Identity{}, __source);
506 _Base::merge(__source);
507 }
508
509 template<typename _H2, typename _P2>
510 void
511 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
512 { merge(__source); }
513#endif // C++17
514
515 using _Base::hash_function;
516 using _Base::key_eq;
517
518 iterator
519 find(const key_type& __key)
520 { return { _Base::find(__key), this }; }
521
522#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
523 template<typename _Kt,
524 typename = std::__has_is_transparent_t<_Hash, _Kt>,
525 typename = std::__has_is_transparent_t<_Pred, _Kt>>
526 iterator
527 find(const _Kt& __k)
528 { return { _Base::find(__k), this }; }
529#endif
530
531 const_iterator
532 find(const key_type& __key) const
533 { return { _Base::find(__key), this }; }
534
535#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
536 template<typename _Kt,
537 typename = std::__has_is_transparent_t<_Hash, _Kt>,
538 typename = std::__has_is_transparent_t<_Pred, _Kt>>
539 const_iterator
540 find(const _Kt& __k) const
541 { return { _Base::find(__k), this }; }
542#endif
543
544 using _Base::count;
545
546#if __cplusplus > 201703L
547 using _Base::contains;
548#endif
549
550 std::pair<iterator, iterator>
551 equal_range(const key_type& __key)
552 {
553 auto __res = _Base::equal_range(__key);
554 return { { __res.first, this }, { __res.second, this } };
555 }
556
557#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
558 template<typename _Kt,
559 typename = std::__has_is_transparent_t<_Hash, _Kt>,
560 typename = std::__has_is_transparent_t<_Pred, _Kt>>
561 std::pair<iterator, iterator>
562 equal_range(const _Kt& __k)
563 {
564 auto __res = _Base::equal_range(__k);
565 return { { __res.first, this }, { __res.second, this } };
566 }
567#endif
568
569 std::pair<const_iterator, const_iterator>
570 equal_range(const key_type& __key) const
571 {
572 auto __res = _Base::equal_range(__key);
573 return { { __res.first, this }, { __res.second, this } };
574 }
575
576#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
577 template<typename _Kt,
578 typename = std::__has_is_transparent_t<_Hash, _Kt>,
579 typename = std::__has_is_transparent_t<_Pred, _Kt>>
580 std::pair<const_iterator, const_iterator>
581 equal_range(const _Kt& __k) const
582 {
583 auto __res = _Base::equal_range(__k);
584 return { { __res.first, this }, { __res.second, this } };
585 }
586#endif
587
588 size_type
589 erase(const key_type& __key)
590 {
591 size_type __ret(0);
592 auto __victim = _Base::find(__key);
593 if (__victim != _Base::end())
594 {
595 _M_erase(__victim);
596 __ret = 1;
597 }
598 return __ret;
599 }
600
601 iterator
602 erase(const_iterator __it)
603 {
604 __glibcxx_check_erase(__it);
605 return { _M_erase(__it.base()), this };
606 }
607
608 _Base_iterator
609 erase(_Base_const_iterator __it)
610 {
611 __glibcxx_check_erase2(__it);
612 return _M_erase(__it);
613 }
614
615 iterator
616 erase(iterator __it)
617 {
618 __glibcxx_check_erase(__it);
619 return { _M_erase(__it.base()), this };
620 }
621
622 iterator
623 erase(const_iterator __first, const_iterator __last)
624 {
625 __glibcxx_check_erase_range(__first, __last);
626 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
627 {
628 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
629 _M_message(__gnu_debug::__msg_valid_range)
630 ._M_iterator(__first, "first")
631 ._M_iterator(__last, "last"));
632 _M_invalidate(__tmp);
633 }
634
635 size_type __bucket_count = this->bucket_count();
636 auto __next = _Base::erase(__first.base(), __last.base());
637 _M_check_rehashed(__bucket_count);
638 return { __next, this };
639 }
640
641 _Base&
642 _M_base() noexcept { return *this; }
643
644 const _Base&
645 _M_base() const noexcept { return *this; }
646
647 private:
648 void
649 _M_check_rehashed(size_type __prev_count)
650 {
651 if (__prev_count != this->bucket_count())
652 this->_M_invalidate_all();
653 }
654
655 void
656 _M_invalidate(_Base_const_iterator __victim)
657 {
658 this->_M_invalidate_if(
659 [__victim](_Base_const_iterator __it) { return __it == __victim; });
660 this->_M_invalidate_local_if(
661 [__victim](_Base_const_local_iterator __it)
662 { return __it == __victim; });
663 }
664
665 _Base_iterator
666 _M_erase(_Base_const_iterator __victim)
667 {
668 _M_invalidate(__victim);
669 size_type __bucket_count = this->bucket_count();
670 _Base_iterator __next = _Base::erase(__victim);
671 _M_check_rehashed(__bucket_count);
672 return __next;
673 }
674
675#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
676 node_type
677 _M_extract(_Base_const_iterator __victim)
678 {
679 _M_invalidate(__victim);
680 return _Base::extract(__victim);
681 }
682#endif
683 };
684
685#if __cpp_deduction_guides >= 201606
686
687 template<typename _InputIterator,
688 typename _Hash =
689 hash<typename iterator_traits<_InputIterator>::value_type>,
690 typename _Pred =
691 equal_to<typename iterator_traits<_InputIterator>::value_type>,
692 typename _Allocator =
693 allocator<typename iterator_traits<_InputIterator>::value_type>,
694 typename = _RequireInputIter<_InputIterator>,
695 typename = _RequireNotAllocatorOrIntegral<_Hash>,
696 typename = _RequireNotAllocator<_Pred>,
697 typename = _RequireAllocator<_Allocator>>
698 unordered_set(_InputIterator, _InputIterator,
699 unordered_set<int>::size_type = {},
700 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
701 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
702 _Hash, _Pred, _Allocator>;
703
704 template<typename _Tp, typename _Hash = hash<_Tp>,
705 typename _Pred = equal_to<_Tp>,
706 typename _Allocator = allocator<_Tp>,
707 typename = _RequireNotAllocatorOrIntegral<_Hash>,
708 typename = _RequireNotAllocator<_Pred>,
709 typename = _RequireAllocator<_Allocator>>
710 unordered_set(initializer_list<_Tp>,
711 unordered_set<int>::size_type = {},
712 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
713 -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
714
715 template<typename _InputIterator, typename _Allocator,
716 typename = _RequireInputIter<_InputIterator>,
717 typename = _RequireAllocator<_Allocator>>
718 unordered_set(_InputIterator, _InputIterator,
719 unordered_set<int>::size_type, _Allocator)
720 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
721 hash<
722 typename iterator_traits<_InputIterator>::value_type>,
723 equal_to<
724 typename iterator_traits<_InputIterator>::value_type>,
725 _Allocator>;
726
727 template<typename _InputIterator, typename _Allocator,
728 typename = _RequireInputIter<_InputIterator>,
729 typename = _RequireAllocator<_Allocator>>
730 unordered_set(_InputIterator, _InputIterator, _Allocator)
731 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
732 hash<
733 typename iterator_traits<_InputIterator>::value_type>,
734 equal_to<
735 typename iterator_traits<_InputIterator>::value_type>,
736 _Allocator>;
737
738 template<typename _InputIterator, typename _Hash, typename _Allocator,
739 typename = _RequireInputIter<_InputIterator>,
740 typename = _RequireNotAllocatorOrIntegral<_Hash>,
741 typename = _RequireAllocator<_Allocator>>
742 unordered_set(_InputIterator, _InputIterator,
743 unordered_set<int>::size_type,
744 _Hash, _Allocator)
745 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
746 _Hash,
747 equal_to<
748 typename iterator_traits<_InputIterator>::value_type>,
749 _Allocator>;
750
751 template<typename _Tp, typename _Allocator,
752 typename = _RequireAllocator<_Allocator>>
753 unordered_set(initializer_list<_Tp>,
754 unordered_set<int>::size_type, _Allocator)
755 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
756
757 template<typename _Tp, typename _Allocator,
758 typename = _RequireAllocator<_Allocator>>
759 unordered_set(initializer_list<_Tp>, _Allocator)
760 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
761
762 template<typename _Tp, typename _Hash, typename _Allocator,
763 typename = _RequireNotAllocatorOrIntegral<_Hash>,
764 typename = _RequireAllocator<_Allocator>>
765 unordered_set(initializer_list<_Tp>,
766 unordered_set<int>::size_type, _Hash, _Allocator)
767 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
768
769#endif
770
771 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
772 inline void
773 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
774 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
775 noexcept(noexcept(__x.swap(__y)))
776 { __x.swap(__y); }
777
778 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
779 inline bool
780 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
781 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
782 { return __x._M_base() == __y._M_base(); }
783
784#if __cpp_impl_three_way_comparison < 201907L
785 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
786 inline bool
787 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
788 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
789 { return !(__x == __y); }
790#endif
791
792 /// Class std::unordered_multiset with safety/checking/debug instrumentation.
793 template<typename _Value,
794 typename _Hash = std::hash<_Value>,
795 typename _Pred = std::equal_to<_Value>,
796 typename _Alloc = std::allocator<_Value> >
797 class unordered_multiset
798 : public __gnu_debug::_Safe_container<
799 unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
800 __gnu_debug::_Safe_unordered_container>,
801 public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
802 {
803 typedef _GLIBCXX_STD_C::unordered_multiset<
804 _Value, _Hash, _Pred, _Alloc> _Base;
805 typedef __gnu_debug::_Safe_container<unordered_multiset,
806 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
807 typedef typename _Base::const_iterator _Base_const_iterator;
808 typedef typename _Base::iterator _Base_iterator;
809 typedef typename _Base::const_local_iterator
810 _Base_const_local_iterator;
811 typedef typename _Base::local_iterator _Base_local_iterator;
812
813 template<typename _ItT, typename _SeqT, typename _CatT>
814 friend class ::__gnu_debug::_Safe_iterator;
815 template<typename _ItT, typename _SeqT>
816 friend class ::__gnu_debug::_Safe_local_iterator;
817
818 // Reference wrapper for base class. See PR libstdc++/90102.
819 struct _Base_ref
820 {
821 _Base_ref(const _Base& __r) : _M_ref(__r) { }
822
823 const _Base& _M_ref;
824 };
825
826 public:
827 typedef typename _Base::size_type size_type;
828 typedef typename _Base::difference_type difference_type;
829 typedef typename _Base::hasher hasher;
830 typedef typename _Base::key_equal key_equal;
831 typedef typename _Base::allocator_type allocator_type;
832
833 typedef typename _Base::key_type key_type;
834 typedef typename _Base::value_type value_type;
835
836 typedef typename _Base::pointer pointer;
837 typedef typename _Base::const_pointer const_pointer;
838 typedef typename _Base::reference reference;
839 typedef typename _Base::const_reference const_reference;
840 typedef __gnu_debug::_Safe_iterator<
841 _Base_iterator, unordered_multiset> iterator;
842 typedef __gnu_debug::_Safe_iterator<
843 _Base_const_iterator, unordered_multiset> const_iterator;
844 typedef __gnu_debug::_Safe_local_iterator<
845 _Base_local_iterator, unordered_multiset> local_iterator;
846 typedef __gnu_debug::_Safe_local_iterator<
847 _Base_const_local_iterator, unordered_multiset> const_local_iterator;
848
849 unordered_multiset() = default;
850
851 explicit
852 unordered_multiset(size_type __n,
853 const hasher& __hf = hasher(),
854 const key_equal& __eql = key_equal(),
855 const allocator_type& __a = allocator_type())
856 : _Base(__n, __hf, __eql, __a) { }
857
858 template<typename _InputIterator>
859 unordered_multiset(_InputIterator __first, _InputIterator __last,
860 size_type __n = 0,
861 const hasher& __hf = hasher(),
862 const key_equal& __eql = key_equal(),
863 const allocator_type& __a = allocator_type())
864 : _Base(__gnu_debug::__base(
865 __glibcxx_check_valid_constructor_range(__first, __last)),
866 __gnu_debug::__base(__last), __n,
867 __hf, __eql, __a) { }
868
869 unordered_multiset(const unordered_multiset&) = default;
870
871 unordered_multiset(_Base_ref __x)
872 : _Base(__x._M_ref) { }
873
874 unordered_multiset(unordered_multiset&&) = default;
875
876 explicit
877 unordered_multiset(const allocator_type& __a)
878 : _Base(__a) { }
879
880 unordered_multiset(const unordered_multiset& __uset,
881 const allocator_type& __a)
882 : _Base(__uset, __a) { }
883
884 unordered_multiset(unordered_multiset&& __uset,
885 const allocator_type& __a)
886 noexcept( noexcept(_Base(std::move(__uset), __a)) )
887 : _Safe(std::move(__uset), __a),
888 _Base(std::move(__uset), __a) { }
889
890 unordered_multiset(initializer_list<value_type> __l,
891 size_type __n = 0,
892 const hasher& __hf = hasher(),
893 const key_equal& __eql = key_equal(),
894 const allocator_type& __a = allocator_type())
895 : _Base(__l, __n, __hf, __eql, __a) { }
896
897 unordered_multiset(size_type __n, const allocator_type& __a)
898 : unordered_multiset(__n, hasher(), key_equal(), __a)
899 { }
900
901 unordered_multiset(size_type __n, const hasher& __hf,
902 const allocator_type& __a)
903 : unordered_multiset(__n, __hf, key_equal(), __a)
904 { }
905
906 template<typename _InputIterator>
907 unordered_multiset(_InputIterator __first, _InputIterator __last,
908 const allocator_type& __a)
909 : unordered_multiset(__first, __last, 0, hasher(), key_equal(), __a)
910 { }
911
912 template<typename _InputIterator>
913 unordered_multiset(_InputIterator __first, _InputIterator __last,
914 size_type __n,
915 const allocator_type& __a)
916 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
917 { }
918
919 template<typename _InputIterator>
920 unordered_multiset(_InputIterator __first, _InputIterator __last,
921 size_type __n, const hasher& __hf,
922 const allocator_type& __a)
923 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
924 { }
925
926 unordered_multiset(initializer_list<value_type> __l,
927 const allocator_type& __a)
928 : unordered_multiset(__l, 0, hasher(), key_equal(), __a)
929 { }
930
931 unordered_multiset(initializer_list<value_type> __l,
932 size_type __n,
933 const allocator_type& __a)
934 : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
935 { }
936
937 unordered_multiset(initializer_list<value_type> __l,
938 size_type __n, const hasher& __hf,
939 const allocator_type& __a)
940 : unordered_multiset(__l, __n, __hf, key_equal(), __a)
941 { }
942
943#if __glibcxx_containers_ranges // C++ >= 23
944 template<__detail::__container_compatible_range<value_type> _Rg>
945 unordered_multiset(from_range_t, _Rg&& __rg,
946 size_type __n = 0,
947 const hasher& __hf = hasher(),
948 const key_equal& __eql = key_equal(),
949 const allocator_type& __a = allocator_type())
950 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __eql, __a)
951 { }
952
953 template<__detail::__container_compatible_range<value_type> _Rg>
954 unordered_multiset(from_range_t, _Rg&& __rg, const allocator_type& __a)
955 : _Base(from_range, std::forward<_Rg>(__rg), __a)
956 { }
957
958 template<__detail::__container_compatible_range<value_type> _Rg>
959 unordered_multiset(from_range_t, _Rg&& __rg, size_type __n,
960 const allocator_type& __a)
961 : _Base(from_range, std::forward<_Rg>(__rg), __n, __a)
962 { }
963
964 template<__detail::__container_compatible_range<value_type> _Rg>
965 unordered_multiset(from_range_t, _Rg&& __rg, size_type __n,
966 const hasher& __hf, const allocator_type& __a)
967 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __a)
968 { }
969#endif
970
971 ~unordered_multiset() = default;
972
973 unordered_multiset&
974 operator=(const unordered_multiset&) = default;
975
976 unordered_multiset&
977 operator=(unordered_multiset&&) = default;
978
979 unordered_multiset&
980 operator=(initializer_list<value_type> __l)
981 {
982 _Base::operator=(__l);
983 this->_M_invalidate_all();
984 return *this;
985 }
986
987 using _Base::get_allocator;
988 using _Base::empty;
989 using _Base::size;
990 using _Base::max_size;
991
992 void
993 swap(unordered_multiset& __x)
994 noexcept( noexcept(declval<_Base&>().swap(__x)) )
995 {
996 _Safe::_M_swap(__x);
997 _Base::swap(__x);
998 }
999
1000 void
1001 clear() noexcept
1002 {
1003 _Base::clear();
1004 this->_M_invalidate_all();
1005 }
1006
1007 iterator
1008 begin() noexcept
1009 { return { _Base::begin(), this }; }
1010
1011 const_iterator
1012 begin() const noexcept
1013 { return { _Base::begin(), this }; }
1014
1015 iterator
1016 end() noexcept
1017 { return { _Base::end(), this }; }
1018
1019 const_iterator
1020 end() const noexcept
1021 { return { _Base::end(), this }; }
1022
1023 const_iterator
1024 cbegin() const noexcept
1025 { return { _Base::cbegin(), this }; }
1026
1027 const_iterator
1028 cend() const noexcept
1029 { return { _Base::cend(), this }; }
1030
1031 // local versions
1032 local_iterator
1033 begin(size_type __b)
1034 {
1035 __glibcxx_check_bucket_index(__b);
1036 return { _Base::begin(__b), this };
1037 }
1038
1039 local_iterator
1040 end(size_type __b)
1041 {
1042 __glibcxx_check_bucket_index(__b);
1043 return { _Base::end(__b), this };
1044 }
1045
1046 const_local_iterator
1047 begin(size_type __b) const
1048 {
1049 __glibcxx_check_bucket_index(__b);
1050 return { _Base::begin(__b), this };
1051 }
1052
1053 const_local_iterator
1054 end(size_type __b) const
1055 {
1056 __glibcxx_check_bucket_index(__b);
1057 return { _Base::end(__b), this };
1058 }
1059
1060 const_local_iterator
1061 cbegin(size_type __b) const
1062 {
1063 __glibcxx_check_bucket_index(__b);
1064 return { _Base::cbegin(__b), this };
1065 }
1066
1067 const_local_iterator
1068 cend(size_type __b) const
1069 {
1070 __glibcxx_check_bucket_index(__b);
1071 return { _Base::cend(__b), this };
1072 }
1073
1074 using _Base::bucket_count;
1075 using _Base::max_bucket_count;
1076
1077 size_type
1078 bucket_size(size_type __b) const
1079 {
1080 __glibcxx_check_bucket_index(__b);
1081 return _Base::bucket_size(__b);
1082 }
1083
1084 using _Base::bucket;
1085 using _Base::load_factor;
1086
1087 float
1088 max_load_factor() const noexcept
1089 { return _Base::max_load_factor(); }
1090
1091 void
1092 max_load_factor(float __f)
1093 {
1094 __glibcxx_check_max_load_factor(__f);
1095 _Base::max_load_factor(__f);
1096 }
1097
1098 using _Base::rehash;
1099 using _Base::reserve;
1100
1101 template<typename... _Args>
1102 iterator
1103 emplace(_Args&&... __args)
1104 {
1105 size_type __bucket_count = this->bucket_count();
1106 auto __it = _Base::emplace(std::forward<_Args>(__args)...);
1107 _M_check_rehashed(__bucket_count);
1108 return { __it, this };
1109 }
1110
1111 template<typename... _Args>
1112 iterator
1113 emplace_hint(const_iterator __hint, _Args&&... __args)
1114 {
1115 __glibcxx_check_insert(__hint);
1116 size_type __bucket_count = this->bucket_count();
1117 auto __it = _Base::emplace_hint(__hint.base(),
1118 std::forward<_Args>(__args)...);
1119 _M_check_rehashed(__bucket_count);
1120 return { __it, this };
1121 }
1122
1123 iterator
1124 insert(const value_type& __obj)
1125 {
1126 size_type __bucket_count = this->bucket_count();
1127 auto __it = _Base::insert(__obj);
1128 _M_check_rehashed(__bucket_count);
1129 return { __it, this };
1130 }
1131
1132 iterator
1133 insert(const_iterator __hint, const value_type& __obj)
1134 {
1135 __glibcxx_check_insert(__hint);
1136 size_type __bucket_count = this->bucket_count();
1137 auto __it = _Base::insert(__hint.base(), __obj);
1138 _M_check_rehashed(__bucket_count);
1139 return { __it, this };
1140 }
1141
1142 iterator
1143 insert(value_type&& __obj)
1144 {
1145 size_type __bucket_count = this->bucket_count();
1146 auto __it = _Base::insert(std::move(__obj));
1147 _M_check_rehashed(__bucket_count);
1148 return { __it, this };
1149 }
1150
1151 iterator
1152 insert(const_iterator __hint, value_type&& __obj)
1153 {
1154 __glibcxx_check_insert(__hint);
1155 size_type __bucket_count = this->bucket_count();
1156 auto __it = _Base::insert(__hint.base(), std::move(__obj));
1157 _M_check_rehashed(__bucket_count);
1158 return { __it, this };
1159 }
1160
1161 void
1162 insert(std::initializer_list<value_type> __l)
1163 {
1164 size_type __bucket_count = this->bucket_count();
1165 _Base::insert(__l);
1166 _M_check_rehashed(__bucket_count);
1167 }
1168
1169 template<typename _InputIterator>
1170 void
1171 insert(_InputIterator __first, _InputIterator __last)
1172 {
1173 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
1174 __glibcxx_check_valid_range2(__first, __last, __dist);
1175 size_type __bucket_count = this->bucket_count();
1176
1177 if (__dist.second >= __gnu_debug::__dp_sign)
1178 _Base::insert(__gnu_debug::__unsafe(__first),
1179 __gnu_debug::__unsafe(__last));
1180 else
1181 _Base::insert(__first, __last);
1182
1183 _M_check_rehashed(__bucket_count);
1184 }
1185
1186#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1187 using node_type = typename _Base::node_type;
1188
1189 node_type
1190 extract(const_iterator __position)
1191 {
1192 __glibcxx_check_erase(__position);
1193 return _M_extract(__position.base());
1194 }
1195
1196 node_type
1197 extract(const key_type& __key)
1198 {
1199 const auto __position = _Base::find(__key);
1200 if (__position != _Base::end())
1201 return _M_extract(__position);
1202 return {};
1203 }
1204
1205 iterator
1206 insert(node_type&& __nh)
1207 { return { _Base::insert(std::move(__nh)), this }; }
1208
1209 iterator
1210 insert(const_iterator __hint, node_type&& __nh)
1211 {
1212 __glibcxx_check_insert(__hint);
1213 return { _Base::insert(__hint.base(), std::move(__nh)), this };
1214 }
1215
1216 template<typename _H2, typename _P2>
1217 void
1218 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
1219 {
1220 auto __guard
1221 = _Safe::_S_umc_guard(std::__detail::_Identity{}, __source);
1222 _Base::merge(__source);
1223 }
1224
1225 template<typename _H2, typename _P2>
1226 void
1227 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
1228 { merge(__source); }
1229
1230 template<typename _H2, typename _P2>
1231 void
1232 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
1233 {
1234 auto __guard
1235 = _Safe::_S_uc_guard(std::__detail::_Identity{}, __source);
1236 _Base::merge(__source);
1237 }
1238
1239 template<typename _H2, typename _P2>
1240 void
1241 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
1242 { merge(__source); }
1243#endif // C++17
1244
1245 using _Base::hash_function;
1246 using _Base::key_eq;
1247
1248 iterator
1249 find(const key_type& __key)
1250 { return { _Base::find(__key), this }; }
1251
1252#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1253 template<typename _Kt,
1254 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1255 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1256 iterator
1257 find(const _Kt& __k)
1258 { return { _Base::find(__k), this }; }
1259#endif
1260
1261 const_iterator
1262 find(const key_type& __key) const
1263 { return { _Base::find(__key), this }; }
1264
1265#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1266 template<typename _Kt,
1267 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1268 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1269 const_iterator
1270 find(const _Kt& __k) const
1271 { return { _Base::find(__k), this }; }
1272#endif
1273
1274 using _Base::count;
1275
1276#if __cplusplus > 201703L
1277 using _Base::contains;
1278#endif
1279
1280 std::pair<iterator, iterator>
1281 equal_range(const key_type& __key)
1282 {
1283 auto __res = _Base::equal_range(__key);
1284 return { { __res.first, this }, { __res.second, this } };
1285 }
1286
1287#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1288 template<typename _Kt,
1289 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1290 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1291 std::pair<iterator, iterator>
1292 equal_range(const _Kt& __k)
1293 {
1294 auto __res = _Base::equal_range(__k);
1295 return { { __res.first, this }, { __res.second, this } };
1296 }
1297#endif
1298
1299 std::pair<const_iterator, const_iterator>
1300 equal_range(const key_type& __key) const
1301 {
1302 auto __res = _Base::equal_range(__key);
1303 return { { __res.first, this }, { __res.second, this } };
1304 }
1305
1306#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1307 template<typename _Kt,
1308 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1309 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1310 std::pair<const_iterator, const_iterator>
1311 equal_range(const _Kt& __k) const
1312 {
1313 auto __res = _Base::equal_range(__k);
1314 return { { __res.first, this }, { __res.second, this } };
1315 }
1316#endif
1317
1318 size_type
1319 erase(const key_type& __key)
1320 {
1321 size_type __ret(0);
1322 auto __pair = _Base::equal_range(__key);
1323 for (auto __victim = __pair.first; __victim != __pair.second;)
1324 {
1325 _M_invalidate(__victim);
1326 __victim = _Base::erase(__victim);
1327 ++__ret;
1328 }
1329
1330 return __ret;
1331 }
1332
1333 iterator
1334 erase(const_iterator __it)
1335 {
1336 __glibcxx_check_erase(__it);
1337 return { _M_erase(__it.base()), this };
1338 }
1339
1340 _Base_iterator
1341 erase(_Base_const_iterator __it)
1342 {
1343 __glibcxx_check_erase2(__it);
1344 return _M_erase(__it);
1345 }
1346
1347 iterator
1348 erase(iterator __it)
1349 {
1350 __glibcxx_check_erase(__it);
1351 return { _M_erase(__it.base()), this };
1352 }
1353
1354 iterator
1355 erase(const_iterator __first, const_iterator __last)
1356 {
1357 __glibcxx_check_erase_range(__first, __last);
1358 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1359 {
1360 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1361 _M_message(__gnu_debug::__msg_valid_range)
1362 ._M_iterator(__first, "first")
1363 ._M_iterator(__last, "last"));
1364 _M_invalidate(__tmp);
1365 }
1366 return { _Base::erase(__first.base(), __last.base()), this };
1367 }
1368
1369 _Base&
1370 _M_base() noexcept { return *this; }
1371
1372 const _Base&
1373 _M_base() const noexcept { return *this; }
1374
1375 private:
1376 void
1377 _M_check_rehashed(size_type __prev_count)
1378 {
1379 if (__prev_count != this->bucket_count())
1380 this->_M_invalidate_all();
1381 }
1382
1383 void
1384 _M_invalidate(_Base_const_iterator __victim)
1385 {
1386 this->_M_invalidate_if(
1387 [__victim](_Base_const_iterator __it) { return __it == __victim; });
1388 this->_M_invalidate_local_if(
1389 [__victim](_Base_const_local_iterator __it)
1390 { return __it == __victim; });
1391 }
1392
1393 _Base_iterator
1394 _M_erase(_Base_const_iterator __victim)
1395 {
1396 _M_invalidate(__victim);
1397 size_type __bucket_count = this->bucket_count();
1398 _Base_iterator __next = _Base::erase(__victim);
1399 _M_check_rehashed(__bucket_count);
1400 return __next;
1401 }
1402
1403#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1404 node_type
1405 _M_extract(_Base_const_iterator __victim)
1406 {
1407 _M_invalidate(__victim);
1408 return _Base::extract(__victim);
1409 }
1410#endif
1411 };
1412
1413#if __cpp_deduction_guides >= 201606
1414
1415 template<typename _InputIterator,
1416 typename _Hash =
1417 hash<typename iterator_traits<_InputIterator>::value_type>,
1418 typename _Pred =
1419 equal_to<typename iterator_traits<_InputIterator>::value_type>,
1420 typename _Allocator =
1421 allocator<typename iterator_traits<_InputIterator>::value_type>,
1422 typename = _RequireInputIter<_InputIterator>,
1423 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1424 typename = _RequireNotAllocator<_Pred>,
1425 typename = _RequireAllocator<_Allocator>>
1426 unordered_multiset(_InputIterator, _InputIterator,
1427 unordered_multiset<int>::size_type = {},
1428 _Hash = _Hash(), _Pred = _Pred(),
1429 _Allocator = _Allocator())
1430 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1431 _Hash, _Pred, _Allocator>;
1432
1433 template<typename _Tp, typename _Hash = hash<_Tp>,
1434 typename _Pred = equal_to<_Tp>,
1435 typename _Allocator = allocator<_Tp>,
1436 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1437 typename = _RequireNotAllocator<_Pred>,
1438 typename = _RequireAllocator<_Allocator>>
1439 unordered_multiset(initializer_list<_Tp>,
1440 unordered_multiset<int>::size_type = {},
1441 _Hash = _Hash(), _Pred = _Pred(),
1442 _Allocator = _Allocator())
1443 -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1444
1445 template<typename _InputIterator, typename _Allocator,
1446 typename = _RequireInputIter<_InputIterator>,
1447 typename = _RequireAllocator<_Allocator>>
1448 unordered_multiset(_InputIterator, _InputIterator,
1449 unordered_multiset<int>::size_type, _Allocator)
1450 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1451 hash<typename
1452 iterator_traits<_InputIterator>::value_type>,
1453 equal_to<typename
1454 iterator_traits<_InputIterator>::value_type>,
1455 _Allocator>;
1456
1457 template<typename _InputIterator, typename _Allocator,
1458 typename = _RequireInputIter<_InputIterator>,
1459 typename = _RequireAllocator<_Allocator>>
1460 unordered_multiset(_InputIterator, _InputIterator, _Allocator)
1461 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1462 hash<typename
1463 iterator_traits<_InputIterator>::value_type>,
1464 equal_to<typename
1465 iterator_traits<_InputIterator>::value_type>,
1466 _Allocator>;
1467
1468 template<typename _InputIterator, typename _Hash, typename _Allocator,
1469 typename = _RequireInputIter<_InputIterator>,
1470 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1471 typename = _RequireAllocator<_Allocator>>
1472 unordered_multiset(_InputIterator, _InputIterator,
1473 unordered_multiset<int>::size_type,
1474 _Hash, _Allocator)
1475 -> unordered_multiset<typename
1476 iterator_traits<_InputIterator>::value_type,
1477 _Hash,
1478 equal_to<
1479 typename
1480 iterator_traits<_InputIterator>::value_type>,
1481 _Allocator>;
1482
1483 template<typename _Tp, typename _Allocator,
1484 typename = _RequireAllocator<_Allocator>>
1485 unordered_multiset(initializer_list<_Tp>,
1486 unordered_multiset<int>::size_type, _Allocator)
1487 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1488
1489 template<typename _Tp, typename _Allocator,
1490 typename = _RequireAllocator<_Allocator>>
1491 unordered_multiset(initializer_list<_Tp>, _Allocator)
1492 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1493
1494 template<typename _Tp, typename _Hash, typename _Allocator,
1495 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1496 typename = _RequireAllocator<_Allocator>>
1497 unordered_multiset(initializer_list<_Tp>,
1498 unordered_multiset<int>::size_type, _Hash, _Allocator)
1499 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1500
1501#if __glibcxx_containers_ranges // C++ >= 23
1502 template<ranges::input_range _Rg,
1503 __not_allocator_like _Hash = hash<ranges::range_value_t<_Rg>>,
1504 __not_allocator_like _Pred = equal_to<ranges::range_value_t<_Rg>>,
1505 __allocator_like _Allocator = allocator<ranges::range_value_t<_Rg>>>
1506 unordered_set(from_range_t, _Rg&&, unordered_set<int>::size_type = {},
1507 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1508 -> unordered_set<ranges::range_value_t<_Rg>, _Hash, _Pred, _Allocator>;
1509
1510 template<ranges::input_range _Rg,
1511 __allocator_like _Allocator>
1512 unordered_set(from_range_t, _Rg&&, unordered_set<int>::size_type,
1513 _Allocator)
1514 -> unordered_set<ranges::range_value_t<_Rg>,
1515 hash<ranges::range_value_t<_Rg>>,
1516 equal_to<ranges::range_value_t<_Rg>>,
1517 _Allocator>;
1518
1519 template<ranges::input_range _Rg,
1520 __allocator_like _Allocator>
1521 unordered_set(from_range_t, _Rg&&, _Allocator)
1522 -> unordered_set<ranges::range_value_t<_Rg>,
1523 hash<ranges::range_value_t<_Rg>>,
1524 equal_to<ranges::range_value_t<_Rg>>,
1525 _Allocator>;
1526
1527 template<ranges::input_range _Rg,
1528 __not_allocator_like _Hash,
1529 __allocator_like _Allocator>
1530 unordered_set(from_range_t, _Rg&&, unordered_set<int>::size_type,
1531 _Hash, _Allocator)
1532 -> unordered_set<ranges::range_value_t<_Rg>, _Hash,
1533 equal_to<ranges::range_value_t<_Rg>>,
1534 _Allocator>;
1535
1536#if __glibcxx_containers_ranges // C++ >= 23
1537 template<ranges::input_range _Rg,
1538 __not_allocator_like _Hash = hash<ranges::range_value_t<_Rg>>,
1539 __not_allocator_like _Pred = equal_to<ranges::range_value_t<_Rg>>,
1540 __allocator_like _Allocator = allocator<ranges::range_value_t<_Rg>>>
1541 unordered_multiset(from_range_t, _Rg&&,
1542 unordered_multiset<int>::size_type = {},
1543 _Hash = _Hash(), _Pred = _Pred(),
1544 _Allocator = _Allocator())
1545 -> unordered_multiset<ranges::range_value_t<_Rg>, _Hash, _Pred, _Allocator>;
1546
1547 template<ranges::input_range _Rg,
1548 __allocator_like _Allocator>
1549 unordered_multiset(from_range_t, _Rg&&, _Allocator)
1550 -> unordered_multiset<ranges::range_value_t<_Rg>,
1551 hash<ranges::range_value_t<_Rg>>,
1552 equal_to<ranges::range_value_t<_Rg>>,
1553 _Allocator>;
1554
1555 template<ranges::input_range _Rg,
1556 __allocator_like _Allocator>
1557 unordered_multiset(from_range_t, _Rg&&, unordered_multiset<int>::size_type,
1558 _Allocator)
1559 -> unordered_multiset<ranges::range_value_t<_Rg>,
1560 hash<ranges::range_value_t<_Rg>>,
1561 equal_to<ranges::range_value_t<_Rg>>,
1562 _Allocator>;
1563
1564 template<ranges::input_range _Rg,
1565 __not_allocator_like _Hash,
1566 __allocator_like _Allocator>
1567 unordered_multiset(from_range_t, _Rg&&,
1568 unordered_multiset<int>::size_type,
1569 _Hash, _Allocator)
1570 -> unordered_multiset<ranges::range_value_t<_Rg>, _Hash,
1571 equal_to<ranges::range_value_t<_Rg>>,
1572 _Allocator>;
1573#endif
1574#endif
1575
1576#endif
1577
1578 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1579 inline void
1580 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1581 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1582 noexcept(noexcept(__x.swap(__y)))
1583 { __x.swap(__y); }
1584
1585 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1586 inline bool
1587 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1588 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1589 { return __x._M_base() == __y._M_base(); }
1590
1591#if __cpp_impl_three_way_comparison < 201907L
1592 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1593 inline bool
1594 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1595 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1596 { return !(__x == __y); }
1597#endif
1598
1599} // namespace __debug
1600} // namespace std
1601
1602#endif // C++11
1603
1604#endif
__glibcxx_check_insert
#define __glibcxx_check_insert(_Position)
Definition macros.h:143
__glibcxx_check_erase_range
#define __glibcxx_check_erase_range(_First, _Last)
Definition macros.h:245
__glibcxx_check_erase
#define __glibcxx_check_erase(_Position)
Definition macros.h:209
std::declval
auto declval() noexcept -> decltype(__declval< _Tp >(0))
Definition type_traits:2672
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:138
std::forward
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition move.h:72
std
ISO C++ entities toplevel namespace is std.
__gnu_debug::__base
constexpr _Iterator __base(_Iterator __it)
Definition helper_functions.h:320
std::__debug
GNU debug code, replaces standard behavior with debug behavior.
std::initializer_list
initializer_list
Definition initializer_list:48
std::hash
Primary class template hash.
Definition functional_hash.h:106
std::allocator
The standard allocator, as per C++03 [20.4.1].
Definition allocator.h:134
__gnu_debug::_Safe_iterator
Safe iterator wrapper.
Definition safe_iterator.h:133
__gnu_debug::_Safe_iterator::base
constexpr _Iterator & base() noexcept
Return the underlying iterator.
Definition safe_iterator.h:433
std::equal_to
One of the comparison functors.
Definition stl_function.h:371
std::pair
Struct holding two objects of arbitrary type.
Definition stl_pair.h:304
std::iterator_traits
Traits class for iterators.
Definition stl_iterator_base_types.h:180
std::unordered_multiset
A standard container composed of equivalent keys (possibly containing multiple of each key value) in ...
Definition unordered_set.h:1115
std::unordered_multiset::size_type
_Hashtable::size_type size_type
Iterator-related typedefs.
Definition unordered_set.h:1140
std::unordered_set
A standard container composed of unique keys (containing at most one of each key value) in which the ...
Definition unordered_set.h:108
std::unordered_set::size_type
_Hashtable::size_type size_type
Iterator-related typedefs.
Definition unordered_set.h:133
__gnu_debug::_Safe_container
Safe class dealing with some allocator dependent operations.
Definition safe_container.h:43
__gnu_debug::_Safe_unordered_container
Base class for constructing a safe unordered container type that tracks iterators that reference it.
Definition safe_unordered_container.h:59
std::__debug::unordered_set
Class std::unordered_set with safety/checking/debug instrumentation.
Definition debug/unordered_set:67
std::__debug::unordered_multiset
Class std::unordered_multiset with safety/checking/debug instrumentation.
Definition debug/unordered_set:802