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