libstdc++
debug/unordered_set
Go to the documentation of this file.
1// Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
2
3// Copyright (C) 2003-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 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# ifdef __glibcxx_associative_heterogeneous_insertion
417 template <__heterogeneous_hash_key<unordered_set> _Kt>
418 std::pair<iterator, bool>
419 insert(_Kt&& __obj)
420 {
421 size_type __bucket_count = this->bucket_count();
422 auto __res = _Base::insert(std::forward<_Kt>(__obj));
423 _M_check_rehashed(__bucket_count);
424 return { { __res.first, this }, __res.second };
425 }
426#endif
427
428 iterator
429 insert(const_iterator __hint, value_type&& __obj)
430 {
431 __glibcxx_check_insert(__hint);
432 size_type __bucket_count = this->bucket_count();
433 auto __it = _Base::insert(__hint.base(), std::move(__obj));
434 _M_check_rehashed(__bucket_count);
435 return { __it, this };
436 }
437
438# ifdef __glibcxx_associative_heterogeneous_insertion
439 template <__heterogeneous_hash_key<unordered_set> _Kt>
440 iterator
441 insert(const_iterator __hint, _Kt&& __obj)
442 {
443 __glibcxx_check_insert(__hint);
444 size_type __bucket_count = this->bucket_count();
445 auto __it = _Base::insert(
446 __hint.base(), std::forward<_Kt>(__obj));
447 _M_check_rehashed(__bucket_count);
448 return { __it, this };
449 }
450#endif
451
452 void
453 insert(std::initializer_list<value_type> __l)
454 {
455 size_type __bucket_count = this->bucket_count();
456 _Base::insert(__l);
457 _M_check_rehashed(__bucket_count);
458 }
459
460 template<typename _InputIterator>
461 void
462 insert(_InputIterator __first, _InputIterator __last)
463 {
464 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
465 __glibcxx_check_valid_range2(__first, __last, __dist);
466 size_type __bucket_count = this->bucket_count();
467
468 if (__dist.second >= __gnu_debug::__dp_sign)
469 _Base::insert(__gnu_debug::__unsafe(__first),
470 __gnu_debug::__unsafe(__last));
471 else
472 _Base::insert(__first, __last);
473
474 _M_check_rehashed(__bucket_count);
475 }
476
477#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
478 using node_type = typename _Base::node_type;
479 using insert_return_type = _Node_insert_return<iterator, node_type>;
480
481 node_type
482 extract(const_iterator __position)
483 {
484 __glibcxx_check_erase(__position);
485 return _M_extract(__position.base());
486 }
487
488 node_type
489 extract(const key_type& __key)
490 {
491 const auto __position = _Base::find(__key);
492 if (__position != _Base::end())
493 return _M_extract(__position);
494 return {};
495 }
496
497# ifdef __glibcxx_associative_heterogeneous_erasure
498 template <__heterogeneous_hash_key<unordered_set> _Kt>
499 node_type
500 extract(_Kt&& __key)
501 {
502 const auto __position = _Base::find(__key);
503 if (__position != _Base::end())
504 return _M_extract(__position);
505 return {};
506 }
507#endif
508
509 insert_return_type
510 insert(node_type&& __nh)
511 {
512 auto __ret = _Base::insert(std::move(__nh));
513 return
514 { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };
515 }
516
517 iterator
518 insert(const_iterator __hint, node_type&& __nh)
519 {
520 __glibcxx_check_insert(__hint);
521 return { _Base::insert(__hint.base(), std::move(__nh)), this };
522 }
523
524 template<typename _H2, typename _P2>
525 void
526 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
527 {
528 auto __guard
529 = _Safe::_S_uc_guard(std::__detail::_Identity{}, __source);
530 _Base::merge(__source);
531 }
532
533 template<typename _H2, typename _P2>
534 void
535 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
536 { merge(__source); }
537
538 template<typename _H2, typename _P2>
539 void
540 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
541 {
542 auto __guard
543 = _Safe::_S_umc_guard(std::__detail::_Identity{}, __source);
544 _Base::merge(__source);
545 }
546
547 template<typename _H2, typename _P2>
548 void
549 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
550 { merge(__source); }
551#endif // C++17
552
553 using _Base::hash_function;
554 using _Base::key_eq;
555
556 iterator
557 find(const key_type& __key)
558 { return { _Base::find(__key), this }; }
559
560#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
561 template<typename _Kt,
562 typename = std::__has_is_transparent_t<_Hash, _Kt>,
563 typename = std::__has_is_transparent_t<_Pred, _Kt>>
564 iterator
565 find(const _Kt& __k)
566 { return { _Base::find(__k), this }; }
567#endif
568
569 const_iterator
570 find(const key_type& __key) const
571 { return { _Base::find(__key), this }; }
572
573#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
574 template<typename _Kt,
575 typename = std::__has_is_transparent_t<_Hash, _Kt>,
576 typename = std::__has_is_transparent_t<_Pred, _Kt>>
577 const_iterator
578 find(const _Kt& __k) const
579 { return { _Base::find(__k), this }; }
580#endif
581
582 using _Base::count;
583
584#if __cplusplus > 201703L
585 using _Base::contains;
586#endif
587
588 std::pair<iterator, iterator>
589 equal_range(const key_type& __key)
590 {
591 auto __res = _Base::equal_range(__key);
592 return { { __res.first, this }, { __res.second, this } };
593 }
594
595#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
596 template<typename _Kt,
597 typename = std::__has_is_transparent_t<_Hash, _Kt>,
598 typename = std::__has_is_transparent_t<_Pred, _Kt>>
599 std::pair<iterator, iterator>
600 equal_range(const _Kt& __k)
601 {
602 auto __res = _Base::equal_range(__k);
603 return { { __res.first, this }, { __res.second, this } };
604 }
605#endif
606
607 std::pair<const_iterator, const_iterator>
608 equal_range(const key_type& __key) const
609 {
610 auto __res = _Base::equal_range(__key);
611 return { { __res.first, this }, { __res.second, this } };
612 }
613
614#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
615 template<typename _Kt,
616 typename = std::__has_is_transparent_t<_Hash, _Kt>,
617 typename = std::__has_is_transparent_t<_Pred, _Kt>>
618 std::pair<const_iterator, const_iterator>
619 equal_range(const _Kt& __k) const
620 {
621 auto __res = _Base::equal_range(__k);
622 return { { __res.first, this }, { __res.second, this } };
623 }
624#endif
625
626 size_type
627 erase(const key_type& __key)
628 {
629 size_type __ret(0);
630 auto __victim = _Base::find(__key);
631 if (__victim != _Base::end())
632 {
633 _M_erase(__victim);
634 __ret = 1;
635 }
636 return __ret;
637 }
638
639# ifdef __glibcxx_associative_heterogeneous_erasure
640 template <__heterogeneous_hash_key<unordered_set> _Kt>
641 size_type
642 erase(_Kt&& __key)
643 {
644 auto __victim = _Base::find(__key);
645 if (__victim != _Base::end())
646 return _M_erase(__victim), 1;
647 return 0;
648 }
649#endif
650
651 iterator
652 erase(const_iterator __it)
653 {
654 __glibcxx_check_erase(__it);
655 return { _M_erase(__it.base()), this };
656 }
657
658 _Base_iterator
659 erase(_Base_const_iterator __it)
660 {
661 __glibcxx_check_erase2(__it);
662 return _M_erase(__it);
663 }
664
665 iterator
666 erase(iterator __it)
667 {
668 __glibcxx_check_erase(__it);
669 return { _M_erase(__it.base()), this };
670 }
671
672 iterator
673 erase(const_iterator __first, const_iterator __last)
674 {
675 __glibcxx_check_erase_range(__first, __last);
676 {
677 __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
678 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
679 {
680 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
681 _M_message(__gnu_debug::__msg_valid_range)
682 ._M_iterator(__first, "first")
683 ._M_iterator(__last, "last"));
684 this->_M_invalidate(__tmp, sentry);
685 }
686 }
687
688 auto __next = _Base::erase(__first.base(), __last.base());
689 return { __next, this };
690 }
691
692 _Base&
693 _M_base() noexcept { return *this; }
694
695 const _Base&
696 _M_base() const noexcept { return *this; }
697
698 private:
699 const unordered_set*
700 _M_self() const noexcept
701 { return this; }
702
703 void
704 _M_check_rehashed(size_type __prev_count)
705 {
706 if (__prev_count != this->bucket_count())
707 this->_M_invalidate_all();
708 }
709
710 _Base_iterator
711 _M_erase(_Base_const_iterator __victim)
712 {
713 this->_M_invalidate(__victim);
714 return _Base::erase(__victim);
715 }
716
717#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
718 node_type
719 _M_extract(_Base_const_iterator __victim)
720 {
721 this->_M_invalidate(__victim);
722 return _Base::extract(__victim);
723 }
724#endif
725 };
726
727#if __cpp_deduction_guides >= 201606
728
729 template<typename _InputIterator,
730 typename _Hash =
731 hash<typename iterator_traits<_InputIterator>::value_type>,
732 typename _Pred =
733 equal_to<typename iterator_traits<_InputIterator>::value_type>,
734 typename _Allocator =
735 allocator<typename iterator_traits<_InputIterator>::value_type>,
736 typename = _RequireInputIter<_InputIterator>,
737 typename = _RequireNotAllocatorOrIntegral<_Hash>,
738 typename = _RequireNotAllocator<_Pred>,
739 typename = _RequireAllocator<_Allocator>>
740 unordered_set(_InputIterator, _InputIterator,
741 unordered_set<int>::size_type = {},
742 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
743 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
744 _Hash, _Pred, _Allocator>;
745
746 template<typename _Tp, typename _Hash = hash<_Tp>,
747 typename _Pred = equal_to<_Tp>,
748 typename _Allocator = allocator<_Tp>,
749 typename = _RequireNotAllocatorOrIntegral<_Hash>,
750 typename = _RequireNotAllocator<_Pred>,
751 typename = _RequireAllocator<_Allocator>>
752 unordered_set(initializer_list<_Tp>,
753 unordered_set<int>::size_type = {},
754 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
755 -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
756
757 template<typename _InputIterator, typename _Allocator,
758 typename = _RequireInputIter<_InputIterator>,
759 typename = _RequireAllocator<_Allocator>>
760 unordered_set(_InputIterator, _InputIterator,
761 unordered_set<int>::size_type, _Allocator)
762 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
763 hash<
764 typename iterator_traits<_InputIterator>::value_type>,
765 equal_to<
766 typename iterator_traits<_InputIterator>::value_type>,
767 _Allocator>;
768
769 template<typename _InputIterator, typename _Allocator,
770 typename = _RequireInputIter<_InputIterator>,
771 typename = _RequireAllocator<_Allocator>>
772 unordered_set(_InputIterator, _InputIterator, _Allocator)
773 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
774 hash<
775 typename iterator_traits<_InputIterator>::value_type>,
776 equal_to<
777 typename iterator_traits<_InputIterator>::value_type>,
778 _Allocator>;
779
780 template<typename _InputIterator, typename _Hash, typename _Allocator,
781 typename = _RequireInputIter<_InputIterator>,
782 typename = _RequireNotAllocatorOrIntegral<_Hash>,
783 typename = _RequireAllocator<_Allocator>>
784 unordered_set(_InputIterator, _InputIterator,
785 unordered_set<int>::size_type,
786 _Hash, _Allocator)
787 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
788 _Hash,
789 equal_to<
790 typename iterator_traits<_InputIterator>::value_type>,
791 _Allocator>;
792
793 template<typename _Tp, typename _Allocator,
794 typename = _RequireAllocator<_Allocator>>
795 unordered_set(initializer_list<_Tp>,
796 unordered_set<int>::size_type, _Allocator)
797 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
798
799 template<typename _Tp, typename _Allocator,
800 typename = _RequireAllocator<_Allocator>>
801 unordered_set(initializer_list<_Tp>, _Allocator)
802 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
803
804 template<typename _Tp, typename _Hash, typename _Allocator,
805 typename = _RequireNotAllocatorOrIntegral<_Hash>,
806 typename = _RequireAllocator<_Allocator>>
807 unordered_set(initializer_list<_Tp>,
808 unordered_set<int>::size_type, _Hash, _Allocator)
809 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
810
811#endif
812
813 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
814 inline void
815 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
816 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
817 noexcept(noexcept(__x.swap(__y)))
818 { __x.swap(__y); }
819
820 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
821 inline bool
822 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
823 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
824 { return __x._M_base() == __y._M_base(); }
825
826#if __cpp_impl_three_way_comparison < 201907L
827 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
828 inline bool
829 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
830 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
831 { return !(__x == __y); }
832#endif
833
834 /// Class std::unordered_multiset with safety/checking/debug instrumentation.
835 template<typename _Value,
836 typename _Hash = std::hash<_Value>,
837 typename _Pred = std::equal_to<_Value>,
838 typename _Alloc = std::allocator<_Value> >
839 class unordered_multiset
840 : public __gnu_debug::_Safe_container<
841 unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
842 __gnu_debug::_Safe_unordered_container>,
843 public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
844 {
845 typedef _GLIBCXX_STD_C::unordered_multiset<
846 _Value, _Hash, _Pred, _Alloc> _Base;
847 typedef __gnu_debug::_Safe_container<unordered_multiset,
848 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
849 typedef typename _Base::const_iterator _Base_const_iterator;
850 typedef typename _Base::iterator _Base_iterator;
851 typedef typename _Base::const_local_iterator
852 _Base_const_local_iterator;
853 typedef typename _Base::local_iterator _Base_local_iterator;
854
855 template<typename _ItT, typename _SeqT, typename _CatT>
856 friend class ::__gnu_debug::_Safe_iterator;
857 template<typename _ItT, typename _SeqT>
858 friend class ::__gnu_debug::_Safe_local_iterator;
859
860 // Reference wrapper for base class. See PR libstdc++/90102.
861 struct _Base_ref
862 {
863 _Base_ref(const _Base& __r) : _M_ref(__r) { }
864
865 const _Base& _M_ref;
866 };
867
868 public:
869 typedef typename _Base::size_type size_type;
870 typedef typename _Base::difference_type difference_type;
871 typedef typename _Base::hasher hasher;
872 typedef typename _Base::key_equal key_equal;
873 typedef typename _Base::allocator_type allocator_type;
874
875 typedef typename _Base::key_type key_type;
876 typedef typename _Base::value_type value_type;
877
878 typedef typename _Base::pointer pointer;
879 typedef typename _Base::const_pointer const_pointer;
880 typedef typename _Base::reference reference;
881 typedef typename _Base::const_reference const_reference;
882 typedef __gnu_debug::_Safe_iterator<
883 _Base_iterator, unordered_multiset> iterator;
884 typedef __gnu_debug::_Safe_iterator<
885 _Base_const_iterator, unordered_multiset> const_iterator;
886 typedef __gnu_debug::_Safe_local_iterator<
887 _Base_local_iterator, unordered_multiset> local_iterator;
888 typedef __gnu_debug::_Safe_local_iterator<
889 _Base_const_local_iterator, unordered_multiset> const_local_iterator;
890
891 unordered_multiset() = default;
892
893 explicit
894 unordered_multiset(size_type __n,
895 const hasher& __hf = hasher(),
896 const key_equal& __eql = key_equal(),
897 const allocator_type& __a = allocator_type())
898 : _Base(__n, __hf, __eql, __a) { }
899
900 template<typename _InputIterator>
901 unordered_multiset(_InputIterator __first, _InputIterator __last,
902 size_type __n = 0,
903 const hasher& __hf = hasher(),
904 const key_equal& __eql = key_equal(),
905 const allocator_type& __a = allocator_type())
906 : _Base(__gnu_debug::__base(
907 __glibcxx_check_valid_constructor_range(__first, __last)),
908 __gnu_debug::__base(__last), __n,
909 __hf, __eql, __a) { }
910
911 unordered_multiset(const unordered_multiset&) = default;
912
913 unordered_multiset(_Base_ref __x)
914 : _Base(__x._M_ref) { }
915
916 unordered_multiset(unordered_multiset&&) = default;
917
918 explicit
919 unordered_multiset(const allocator_type& __a)
920 : _Base(__a) { }
921
922 unordered_multiset(const unordered_multiset& __uset,
923 const allocator_type& __a)
924 : _Base(__uset, __a) { }
925
926 unordered_multiset(unordered_multiset&& __uset,
927 const allocator_type& __a)
928 noexcept( noexcept(_Base(std::move(__uset), __a)) )
929 : _Safe(std::move(__uset), __a),
930 _Base(std::move(__uset), __a) { }
931
932 unordered_multiset(initializer_list<value_type> __l,
933 size_type __n = 0,
934 const hasher& __hf = hasher(),
935 const key_equal& __eql = key_equal(),
936 const allocator_type& __a = allocator_type())
937 : _Base(__l, __n, __hf, __eql, __a) { }
938
939 unordered_multiset(size_type __n, const allocator_type& __a)
940 : unordered_multiset(__n, hasher(), key_equal(), __a)
941 { }
942
943 unordered_multiset(size_type __n, const hasher& __hf,
944 const allocator_type& __a)
945 : unordered_multiset(__n, __hf, key_equal(), __a)
946 { }
947
948 template<typename _InputIterator>
949 unordered_multiset(_InputIterator __first, _InputIterator __last,
950 const allocator_type& __a)
951 : unordered_multiset(__first, __last, 0, hasher(), key_equal(), __a)
952 { }
953
954 template<typename _InputIterator>
955 unordered_multiset(_InputIterator __first, _InputIterator __last,
956 size_type __n,
957 const allocator_type& __a)
958 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
959 { }
960
961 template<typename _InputIterator>
962 unordered_multiset(_InputIterator __first, _InputIterator __last,
963 size_type __n, const hasher& __hf,
964 const allocator_type& __a)
965 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
966 { }
967
968 unordered_multiset(initializer_list<value_type> __l,
969 const allocator_type& __a)
970 : unordered_multiset(__l, 0, hasher(), key_equal(), __a)
971 { }
972
973 unordered_multiset(initializer_list<value_type> __l,
974 size_type __n,
975 const allocator_type& __a)
976 : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
977 { }
978
979 unordered_multiset(initializer_list<value_type> __l,
980 size_type __n, const hasher& __hf,
981 const allocator_type& __a)
982 : unordered_multiset(__l, __n, __hf, key_equal(), __a)
983 { }
984
985#if __glibcxx_containers_ranges // C++ >= 23
986 template<__detail::__container_compatible_range<value_type> _Rg>
987 unordered_multiset(from_range_t, _Rg&& __rg,
988 size_type __n = 0,
989 const hasher& __hf = hasher(),
990 const key_equal& __eql = key_equal(),
991 const allocator_type& __a = allocator_type())
992 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __eql, __a)
993 { }
994
995 template<__detail::__container_compatible_range<value_type> _Rg>
996 unordered_multiset(from_range_t, _Rg&& __rg, const allocator_type& __a)
997 : _Base(from_range, std::forward<_Rg>(__rg), __a)
998 { }
999
1000 template<__detail::__container_compatible_range<value_type> _Rg>
1001 unordered_multiset(from_range_t, _Rg&& __rg, size_type __n,
1002 const allocator_type& __a)
1003 : _Base(from_range, std::forward<_Rg>(__rg), __n, __a)
1004 { }
1005
1006 template<__detail::__container_compatible_range<value_type> _Rg>
1007 unordered_multiset(from_range_t, _Rg&& __rg, size_type __n,
1008 const hasher& __hf, const allocator_type& __a)
1009 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __a)
1010 { }
1011#endif
1012
1013 ~unordered_multiset() = default;
1014
1015 unordered_multiset&
1016 operator=(const unordered_multiset&) = default;
1017
1018 unordered_multiset&
1019 operator=(unordered_multiset&&) = default;
1020
1021 unordered_multiset&
1022 operator=(initializer_list<value_type> __l)
1023 {
1024 _Base::operator=(__l);
1025 this->_M_invalidate_all();
1026 return *this;
1027 }
1028
1029 using _Base::get_allocator;
1030 using _Base::empty;
1031 using _Base::size;
1032 using _Base::max_size;
1033
1034 void
1035 swap(unordered_multiset& __x)
1036 noexcept( noexcept(declval<_Base&>().swap(__x)) )
1037 {
1038 _Safe::_M_swap(__x);
1039 _Base::swap(__x);
1040 }
1041
1042 void
1043 clear() noexcept
1044 {
1045 _Base::clear();
1046 this->_M_invalidate_all();
1047 }
1048
1049 iterator
1050 begin() noexcept
1051 { return { _Base::begin(), this }; }
1052
1053 const_iterator
1054 begin() const noexcept
1055 { return { _Base::begin(), this }; }
1056
1057 iterator
1058 end() noexcept
1059 { return { _Base::end(), this }; }
1060
1061 const_iterator
1062 end() const noexcept
1063 { return { _Base::end(), this }; }
1064
1065 const_iterator
1066 cbegin() const noexcept
1067 { return { _Base::cbegin(), this }; }
1068
1069 const_iterator
1070 cend() const noexcept
1071 { return { _Base::cend(), this }; }
1072
1073 // local versions
1074 local_iterator
1075 begin(size_type __b)
1076 {
1077 __glibcxx_check_bucket_index(__b);
1078 return { _Base::begin(__b), this };
1079 }
1080
1081 local_iterator
1082 end(size_type __b)
1083 {
1084 __glibcxx_check_bucket_index(__b);
1085 return { _Base::end(__b), this };
1086 }
1087
1088 const_local_iterator
1089 begin(size_type __b) const
1090 {
1091 __glibcxx_check_bucket_index(__b);
1092 return { _Base::begin(__b), this };
1093 }
1094
1095 const_local_iterator
1096 end(size_type __b) const
1097 {
1098 __glibcxx_check_bucket_index(__b);
1099 return { _Base::end(__b), this };
1100 }
1101
1102 const_local_iterator
1103 cbegin(size_type __b) const
1104 {
1105 __glibcxx_check_bucket_index(__b);
1106 return { _Base::cbegin(__b), this };
1107 }
1108
1109 const_local_iterator
1110 cend(size_type __b) const
1111 {
1112 __glibcxx_check_bucket_index(__b);
1113 return { _Base::cend(__b), this };
1114 }
1115
1116 using _Base::bucket_count;
1117 using _Base::max_bucket_count;
1118
1119 size_type
1120 bucket_size(size_type __b) const
1121 {
1122 __glibcxx_check_bucket_index(__b);
1123 return _Base::bucket_size(__b);
1124 }
1125
1126 using _Base::bucket;
1127 using _Base::load_factor;
1128
1129 float
1130 max_load_factor() const noexcept
1131 { return _Base::max_load_factor(); }
1132
1133 void
1134 max_load_factor(float __f)
1135 {
1136 __glibcxx_check_max_load_factor(__f);
1137 _Base::max_load_factor(__f);
1138 }
1139
1140 using _Base::rehash;
1141 using _Base::reserve;
1142
1143 template<typename... _Args>
1144 iterator
1145 emplace(_Args&&... __args)
1146 {
1147 size_type __bucket_count = this->bucket_count();
1148 auto __it = _Base::emplace(std::forward<_Args>(__args)...);
1149 _M_check_rehashed(__bucket_count);
1150 return { __it, this };
1151 }
1152
1153 template<typename... _Args>
1154 iterator
1155 emplace_hint(const_iterator __hint, _Args&&... __args)
1156 {
1157 __glibcxx_check_insert(__hint);
1158 size_type __bucket_count = this->bucket_count();
1159 auto __it = _Base::emplace_hint(__hint.base(),
1160 std::forward<_Args>(__args)...);
1161 _M_check_rehashed(__bucket_count);
1162 return { __it, this };
1163 }
1164
1165 iterator
1166 insert(const value_type& __obj)
1167 {
1168 size_type __bucket_count = this->bucket_count();
1169 auto __it = _Base::insert(__obj);
1170 _M_check_rehashed(__bucket_count);
1171 return { __it, this };
1172 }
1173
1174 iterator
1175 insert(const_iterator __hint, const value_type& __obj)
1176 {
1177 __glibcxx_check_insert(__hint);
1178 size_type __bucket_count = this->bucket_count();
1179 auto __it = _Base::insert(__hint.base(), __obj);
1180 _M_check_rehashed(__bucket_count);
1181 return { __it, this };
1182 }
1183
1184 iterator
1185 insert(value_type&& __obj)
1186 {
1187 size_type __bucket_count = this->bucket_count();
1188 auto __it = _Base::insert(std::move(__obj));
1189 _M_check_rehashed(__bucket_count);
1190 return { __it, this };
1191 }
1192
1193 iterator
1194 insert(const_iterator __hint, value_type&& __obj)
1195 {
1196 __glibcxx_check_insert(__hint);
1197 size_type __bucket_count = this->bucket_count();
1198 auto __it = _Base::insert(__hint.base(), std::move(__obj));
1199 _M_check_rehashed(__bucket_count);
1200 return { __it, this };
1201 }
1202
1203 void
1204 insert(std::initializer_list<value_type> __l)
1205 {
1206 size_type __bucket_count = this->bucket_count();
1207 _Base::insert(__l);
1208 _M_check_rehashed(__bucket_count);
1209 }
1210
1211 template<typename _InputIterator>
1212 void
1213 insert(_InputIterator __first, _InputIterator __last)
1214 {
1215 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
1216 __glibcxx_check_valid_range2(__first, __last, __dist);
1217 size_type __bucket_count = this->bucket_count();
1218
1219 if (__dist.second >= __gnu_debug::__dp_sign)
1220 _Base::insert(__gnu_debug::__unsafe(__first),
1221 __gnu_debug::__unsafe(__last));
1222 else
1223 _Base::insert(__first, __last);
1224
1225 _M_check_rehashed(__bucket_count);
1226 }
1227
1228#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1229 using node_type = typename _Base::node_type;
1230
1231 node_type
1232 extract(const_iterator __position)
1233 {
1234 __glibcxx_check_erase(__position);
1235 return _M_extract(__position.base());
1236 }
1237
1238 node_type
1239 extract(const key_type& __key)
1240 {
1241 const auto __position = _Base::find(__key);
1242 if (__position != _Base::end())
1243 return _M_extract(__position);
1244 return {};
1245 }
1246
1247# ifdef __glibcxx_associative_heterogeneous_erasure
1248 template <__heterogeneous_hash_key<unordered_multiset> _Kt>
1249 node_type
1250 extract(const _Kt& __key)
1251 {
1252 const auto __position = _Base::find(__key);
1253 return __position != _Base::end() ?
1254 _M_extract(__position) : node_type{};
1255 }
1256#endif
1257
1258 iterator
1259 insert(node_type&& __nh)
1260 { return { _Base::insert(std::move(__nh)), this }; }
1261
1262 iterator
1263 insert(const_iterator __hint, node_type&& __nh)
1264 {
1265 __glibcxx_check_insert(__hint);
1266 return { _Base::insert(__hint.base(), std::move(__nh)), this };
1267 }
1268
1269 template<typename _H2, typename _P2>
1270 void
1271 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
1272 {
1273 auto __guard
1274 = _Safe::_S_umc_guard(std::__detail::_Identity{}, __source);
1275 _Base::merge(__source);
1276 }
1277
1278 template<typename _H2, typename _P2>
1279 void
1280 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
1281 { merge(__source); }
1282
1283 template<typename _H2, typename _P2>
1284 void
1285 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
1286 {
1287 auto __guard
1288 = _Safe::_S_uc_guard(std::__detail::_Identity{}, __source);
1289 _Base::merge(__source);
1290 }
1291
1292 template<typename _H2, typename _P2>
1293 void
1294 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
1295 { merge(__source); }
1296#endif // C++17
1297
1298 using _Base::hash_function;
1299 using _Base::key_eq;
1300
1301 iterator
1302 find(const key_type& __key)
1303 { return { _Base::find(__key), this }; }
1304
1305#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1306 template<typename _Kt,
1307 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1308 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1309 iterator
1310 find(const _Kt& __k)
1311 { return { _Base::find(__k), this }; }
1312#endif
1313
1314 const_iterator
1315 find(const key_type& __key) const
1316 { return { _Base::find(__key), this }; }
1317
1318#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1319 template<typename _Kt,
1320 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1321 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1322 const_iterator
1323 find(const _Kt& __k) const
1324 { return { _Base::find(__k), this }; }
1325#endif
1326
1327 using _Base::count;
1328
1329#if __cplusplus > 201703L
1330 using _Base::contains;
1331#endif
1332
1333 std::pair<iterator, iterator>
1334 equal_range(const key_type& __key)
1335 {
1336 auto __res = _Base::equal_range(__key);
1337 return { { __res.first, this }, { __res.second, this } };
1338 }
1339
1340#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1341 template<typename _Kt,
1342 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1343 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1344 std::pair<iterator, iterator>
1345 equal_range(const _Kt& __k)
1346 {
1347 auto __res = _Base::equal_range(__k);
1348 return { { __res.first, this }, { __res.second, this } };
1349 }
1350#endif
1351
1352 std::pair<const_iterator, const_iterator>
1353 equal_range(const key_type& __key) const
1354 {
1355 auto __res = _Base::equal_range(__key);
1356 return { { __res.first, this }, { __res.second, this } };
1357 }
1358
1359#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1360 template<typename _Kt,
1361 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1362 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1363 std::pair<const_iterator, const_iterator>
1364 equal_range(const _Kt& __k) const
1365 {
1366 auto __res = _Base::equal_range(__k);
1367 return { { __res.first, this }, { __res.second, this } };
1368 }
1369#endif
1370
1371 size_type
1372 erase(const key_type& __key)
1373 {
1374 auto __victims = _Base::equal_range(__key);
1375 return _M_erase(__victims.first, __victims.second);
1376 }
1377
1378# ifdef __glibcxx_associative_heterogeneous_erasure
1379 template <__heterogeneous_hash_key<unordered_multiset> _Kt>
1380 size_type
1381 erase(_Kt&& __key)
1382 {
1383 auto __victims = _Base::equal_range(__key);
1384 return _M_erase(__victims.first, __victims.second);
1385 }
1386#endif
1387
1388 iterator
1389 erase(const_iterator __it)
1390 {
1391 __glibcxx_check_erase(__it);
1392 return { _M_erase(__it.base()), this };
1393 }
1394
1395 _Base_iterator
1396 erase(_Base_const_iterator __it)
1397 {
1398 __glibcxx_check_erase2(__it);
1399 return _M_erase(__it);
1400 }
1401
1402 iterator
1403 erase(iterator __it)
1404 {
1405 __glibcxx_check_erase(__it);
1406 return { _M_erase(__it.base()), this };
1407 }
1408
1409 iterator
1410 erase(const_iterator __first, const_iterator __last)
1411 {
1412 __glibcxx_check_erase_range(__first, __last);
1413 {
1414 __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
1415 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1416 {
1417 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1418 _M_message(__gnu_debug::__msg_valid_range)
1419 ._M_iterator(__first, "first")
1420 ._M_iterator(__last, "last"));
1421 this->_M_invalidate(__tmp, sentry);
1422 }
1423 }
1424
1425 return { _Base::erase(__first.base(), __last.base()), this };
1426 }
1427
1428 _Base&
1429 _M_base() noexcept { return *this; }
1430
1431 const _Base&
1432 _M_base() const noexcept { return *this; }
1433
1434 private:
1435 const unordered_multiset*
1436 _M_self() const noexcept
1437 { return this; }
1438
1439 void
1440 _M_check_rehashed(size_type __prev_count)
1441 {
1442 if (__prev_count != this->bucket_count())
1443 this->_M_invalidate_all();
1444 }
1445
1446 _Base_iterator
1447 _M_erase(_Base_const_iterator __victim)
1448 {
1449 this->_M_invalidate(__victim);
1450 return _Base::erase(__victim);
1451 }
1452
1453 size_type
1454 _M_erase(_Base_iterator __first, _Base_iterator __last)
1455 {
1456 size_type __count(0);
1457 {
1458 __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
1459 for (auto __victim = __first; __victim != __last; ++__victim)
1460 {
1461 this->_M_invalidate(__victim, sentry);
1462 ++__count;
1463 }
1464 }
1465
1466 _Base::erase(__first, __last);
1467 return __count;
1468 }
1469
1470#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1471 node_type
1472 _M_extract(_Base_const_iterator __victim)
1473 {
1474 this->_M_invalidate(__victim);
1475 return _Base::extract(__victim);
1476 }
1477#endif
1478 };
1479
1480#if __cpp_deduction_guides >= 201606
1481
1482 template<typename _InputIterator,
1483 typename _Hash =
1484 hash<typename iterator_traits<_InputIterator>::value_type>,
1485 typename _Pred =
1486 equal_to<typename iterator_traits<_InputIterator>::value_type>,
1487 typename _Allocator =
1488 allocator<typename iterator_traits<_InputIterator>::value_type>,
1489 typename = _RequireInputIter<_InputIterator>,
1490 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1491 typename = _RequireNotAllocator<_Pred>,
1492 typename = _RequireAllocator<_Allocator>>
1493 unordered_multiset(_InputIterator, _InputIterator,
1494 unordered_multiset<int>::size_type = {},
1495 _Hash = _Hash(), _Pred = _Pred(),
1496 _Allocator = _Allocator())
1497 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1498 _Hash, _Pred, _Allocator>;
1499
1500 template<typename _Tp, typename _Hash = hash<_Tp>,
1501 typename _Pred = equal_to<_Tp>,
1502 typename _Allocator = allocator<_Tp>,
1503 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1504 typename = _RequireNotAllocator<_Pred>,
1505 typename = _RequireAllocator<_Allocator>>
1506 unordered_multiset(initializer_list<_Tp>,
1507 unordered_multiset<int>::size_type = {},
1508 _Hash = _Hash(), _Pred = _Pred(),
1509 _Allocator = _Allocator())
1510 -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1511
1512 template<typename _InputIterator, typename _Allocator,
1513 typename = _RequireInputIter<_InputIterator>,
1514 typename = _RequireAllocator<_Allocator>>
1515 unordered_multiset(_InputIterator, _InputIterator,
1516 unordered_multiset<int>::size_type, _Allocator)
1517 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1518 hash<typename
1519 iterator_traits<_InputIterator>::value_type>,
1520 equal_to<typename
1521 iterator_traits<_InputIterator>::value_type>,
1522 _Allocator>;
1523
1524 template<typename _InputIterator, typename _Allocator,
1525 typename = _RequireInputIter<_InputIterator>,
1526 typename = _RequireAllocator<_Allocator>>
1527 unordered_multiset(_InputIterator, _InputIterator, _Allocator)
1528 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1529 hash<typename
1530 iterator_traits<_InputIterator>::value_type>,
1531 equal_to<typename
1532 iterator_traits<_InputIterator>::value_type>,
1533 _Allocator>;
1534
1535 template<typename _InputIterator, typename _Hash, typename _Allocator,
1536 typename = _RequireInputIter<_InputIterator>,
1537 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1538 typename = _RequireAllocator<_Allocator>>
1539 unordered_multiset(_InputIterator, _InputIterator,
1540 unordered_multiset<int>::size_type,
1541 _Hash, _Allocator)
1542 -> unordered_multiset<typename
1543 iterator_traits<_InputIterator>::value_type,
1544 _Hash,
1545 equal_to<
1546 typename
1547 iterator_traits<_InputIterator>::value_type>,
1548 _Allocator>;
1549
1550 template<typename _Tp, typename _Allocator,
1551 typename = _RequireAllocator<_Allocator>>
1552 unordered_multiset(initializer_list<_Tp>,
1553 unordered_multiset<int>::size_type, _Allocator)
1554 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1555
1556 template<typename _Tp, typename _Allocator,
1557 typename = _RequireAllocator<_Allocator>>
1558 unordered_multiset(initializer_list<_Tp>, _Allocator)
1559 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1560
1561 template<typename _Tp, typename _Hash, typename _Allocator,
1562 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1563 typename = _RequireAllocator<_Allocator>>
1564 unordered_multiset(initializer_list<_Tp>,
1565 unordered_multiset<int>::size_type, _Hash, _Allocator)
1566 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1567
1568#if __glibcxx_containers_ranges // C++ >= 23
1569 template<ranges::input_range _Rg,
1570 __not_allocator_like _Hash = hash<ranges::range_value_t<_Rg>>,
1571 __not_allocator_like _Pred = equal_to<ranges::range_value_t<_Rg>>,
1572 __allocator_like _Allocator = allocator<ranges::range_value_t<_Rg>>>
1573 unordered_set(from_range_t, _Rg&&, unordered_set<int>::size_type = {},
1574 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1575 -> unordered_set<ranges::range_value_t<_Rg>, _Hash, _Pred, _Allocator>;
1576
1577 template<ranges::input_range _Rg,
1578 __allocator_like _Allocator>
1579 unordered_set(from_range_t, _Rg&&, unordered_set<int>::size_type,
1580 _Allocator)
1581 -> unordered_set<ranges::range_value_t<_Rg>,
1582 hash<ranges::range_value_t<_Rg>>,
1583 equal_to<ranges::range_value_t<_Rg>>,
1584 _Allocator>;
1585
1586 template<ranges::input_range _Rg,
1587 __allocator_like _Allocator>
1588 unordered_set(from_range_t, _Rg&&, _Allocator)
1589 -> unordered_set<ranges::range_value_t<_Rg>,
1590 hash<ranges::range_value_t<_Rg>>,
1591 equal_to<ranges::range_value_t<_Rg>>,
1592 _Allocator>;
1593
1594 template<ranges::input_range _Rg,
1595 __not_allocator_like _Hash,
1596 __allocator_like _Allocator>
1597 unordered_set(from_range_t, _Rg&&, unordered_set<int>::size_type,
1598 _Hash, _Allocator)
1599 -> unordered_set<ranges::range_value_t<_Rg>, _Hash,
1600 equal_to<ranges::range_value_t<_Rg>>,
1601 _Allocator>;
1602
1603#if __glibcxx_containers_ranges // C++ >= 23
1604 template<ranges::input_range _Rg,
1605 __not_allocator_like _Hash = hash<ranges::range_value_t<_Rg>>,
1606 __not_allocator_like _Pred = equal_to<ranges::range_value_t<_Rg>>,
1607 __allocator_like _Allocator = allocator<ranges::range_value_t<_Rg>>>
1608 unordered_multiset(from_range_t, _Rg&&,
1609 unordered_multiset<int>::size_type = {},
1610 _Hash = _Hash(), _Pred = _Pred(),
1611 _Allocator = _Allocator())
1612 -> unordered_multiset<ranges::range_value_t<_Rg>, _Hash, _Pred, _Allocator>;
1613
1614 template<ranges::input_range _Rg,
1615 __allocator_like _Allocator>
1616 unordered_multiset(from_range_t, _Rg&&, _Allocator)
1617 -> unordered_multiset<ranges::range_value_t<_Rg>,
1618 hash<ranges::range_value_t<_Rg>>,
1619 equal_to<ranges::range_value_t<_Rg>>,
1620 _Allocator>;
1621
1622 template<ranges::input_range _Rg,
1623 __allocator_like _Allocator>
1624 unordered_multiset(from_range_t, _Rg&&, unordered_multiset<int>::size_type,
1625 _Allocator)
1626 -> unordered_multiset<ranges::range_value_t<_Rg>,
1627 hash<ranges::range_value_t<_Rg>>,
1628 equal_to<ranges::range_value_t<_Rg>>,
1629 _Allocator>;
1630
1631 template<ranges::input_range _Rg,
1632 __not_allocator_like _Hash,
1633 __allocator_like _Allocator>
1634 unordered_multiset(from_range_t, _Rg&&,
1635 unordered_multiset<int>::size_type,
1636 _Hash, _Allocator)
1637 -> unordered_multiset<ranges::range_value_t<_Rg>, _Hash,
1638 equal_to<ranges::range_value_t<_Rg>>,
1639 _Allocator>;
1640#endif
1641#endif
1642
1643#endif
1644
1645 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1646 inline void
1647 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1648 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1649 noexcept(noexcept(__x.swap(__y)))
1650 { __x.swap(__y); }
1651
1652 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1653 inline bool
1654 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1655 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1656 { return __x._M_base() == __y._M_base(); }
1657
1658#if __cpp_impl_three_way_comparison < 201907L
1659 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1660 inline bool
1661 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1662 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1663 { return !(__x == __y); }
1664#endif
1665
1666} // namespace __debug
1667
1668#ifdef __glibcxx_erase_if // C++ >= 20 && HOSTED
1669_GLIBCXX_BEGIN_NAMESPACE_VERSION
1670 template<typename _Key, typename _Hash, typename _CPred, typename _Alloc,
1671 typename _Predicate>
1672 inline typename __debug::unordered_set<_Key, _Hash,
1673 _CPred, _Alloc>::size_type
1674 erase_if(__debug::unordered_set<_Key, _Hash, _CPred, _Alloc>& __cont,
1675 _Predicate __pred)
1676 { return __detail::__erase_nodes_if(__cont, __cont._M_base(), __pred); }
1677
1678 template<typename _Key, typename _Hash, typename _CPred, typename _Alloc,
1679 typename _Predicate>
1680 inline typename __debug::unordered_multiset<_Key, _Hash,
1681 _CPred, _Alloc>::size_type
1682 erase_if(__debug::unordered_multiset<_Key, _Hash, _CPred, _Alloc>& __cont,
1683 _Predicate __pred)
1684 { return __detail::__erase_nodes_if(__cont, __cont._M_base(), __pred); }
1685_GLIBCXX_END_NAMESPACE_VERSION
1686#endif // __glibcxx_erase_if
1687} // namespace std
1688
1689#endif // C++11
1690
1691#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:2714
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::iterator_traits
Traits class for iterators.
Definition stl_iterator_base_types.h:180
std::equal_to
One of the comparison functors.
Definition stl_function.h:374
std::pair
Struct holding two objects of arbitrary type.
Definition stl_pair.h:304
std::unordered_multiset
A standard container composed of equivalent keys (possibly containing multiple of each key value) in ...
Definition unordered_set.h:1152
std::unordered_multiset::size_type
_Hashtable::size_type size_type
Iterator-related typedefs.
Definition unordered_set.h:1177
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:844
__gnu_cxx::__scoped_lock
Scoped lock idiom.
Definition concurrence.h:234