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