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