1// Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
3// Copyright (C) 2003-2025 Free Software Foundation, Inc.
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)
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.
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.
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/>.
25/** @file debug/unordered_set
26 * This file is a GNU debug extension to the Standard C++ Library.
29#ifndef _GLIBCXX_DEBUG_UNORDERED_SET
30#define _GLIBCXX_DEBUG_UNORDERED_SET 1
33#pragma GCC system_header
36#if __cplusplus < 201103L
37# include <bits/c++0x_warning.h>
39# include <bits/c++config.h>
40namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug {
41 template<typename _Key, typename _Hash, typename _Pred, typename _Allocator>
43 template<typename _Key, typename _Hash, typename _Pred, typename _Allocator>
44 class unordered_multiset;
45} } // namespace std::__debug
46# include <unordered_set>
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>
53namespace std _GLIBCXX_VISIBILITY(default)
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> >
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>
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;
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;
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;
83 // Reference wrapper for base class. See PR libstdc++/90102.
86 _Base_ref(const _Base& __r) : _M_ref(__r) { }
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;
98 typedef typename _Base::key_type key_type;
99 typedef typename _Base::value_type value_type;
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;
114 unordered_set() = default;
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) { }
123 template<typename _InputIterator>
124 unordered_set(_InputIterator __first, _InputIterator __last,
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) { }
134 unordered_set(const unordered_set&) = default;
136 unordered_set(_Base_ref __x)
137 : _Base(__x._M_ref) { }
139 unordered_set(unordered_set&&) = default;
142 unordered_set(const allocator_type& __a)
145 unordered_set(const unordered_set& __uset,
146 const allocator_type& __a)
147 : _Base(__uset, __a) { }
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) { }
155 unordered_set(initializer_list<value_type> __l,
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) { }
162 unordered_set(size_type __n, const allocator_type& __a)
163 : unordered_set(__n, hasher(), key_equal(), __a)
166 unordered_set(size_type __n, const hasher& __hf,
167 const allocator_type& __a)
168 : unordered_set(__n, __hf, key_equal(), __a)
171 template<typename _InputIterator>
172 unordered_set(_InputIterator __first, _InputIterator __last,
174 const allocator_type& __a)
175 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
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)
185 unordered_set(initializer_list<value_type> __l,
187 const allocator_type& __a)
188 : unordered_set(__l, __n, hasher(), key_equal(), __a)
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)
197 ~unordered_set() = default;
200 operator=(const unordered_set&) = default;
203 operator=(unordered_set&&) = default;
206 operator=(initializer_list<value_type> __l)
208 _Base::operator=(__l);
209 this->_M_invalidate_all();
213 using _Base::get_allocator;
216 using _Base::max_size;
219 swap(unordered_set& __x)
220 noexcept( noexcept(declval<_Base&>().swap(__x)) )
230 this->_M_invalidate_all();
235 { return { _Base::begin(), this }; }
238 begin() const noexcept
239 { return { _Base::begin(), this }; }
243 { return { _Base::end(), this }; }
247 { return { _Base::end(), this }; }
250 cbegin() const noexcept
251 { return { _Base::cbegin(), this }; }
254 cend() const noexcept
255 { return { _Base::cend(), this }; }
261 __glibcxx_check_bucket_index(__b);
262 return { _Base::begin(__b), this };
268 __glibcxx_check_bucket_index(__b);
269 return { _Base::end(__b), this };
273 begin(size_type __b) const
275 __glibcxx_check_bucket_index(__b);
276 return { _Base::begin(__b), this };
280 end(size_type __b) const
282 __glibcxx_check_bucket_index(__b);
283 return { _Base::end(__b), this };
287 cbegin(size_type __b) const
289 __glibcxx_check_bucket_index(__b);
290 return { _Base::cbegin(__b), this };
294 cend(size_type __b) const
296 __glibcxx_check_bucket_index(__b);
297 return { _Base::cend(__b), this };
300 using _Base::bucket_count;
301 using _Base::max_bucket_count;
304 bucket_size(size_type __b) const
306 __glibcxx_check_bucket_index(__b);
307 return _Base::bucket_size(__b);
311 using _Base::load_factor;
314 max_load_factor() const noexcept
315 { return _Base::max_load_factor(); }
318 max_load_factor(float __f)
320 __glibcxx_check_max_load_factor(__f);
321 _Base::max_load_factor(__f);
325 using _Base::reserve;
327 template<typename... _Args>
328 std::pair<iterator, bool>
329 emplace(_Args&&... __args)
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 };
337 template<typename... _Args>
339 emplace_hint(const_iterator __hint, _Args&&... __args)
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 };
349 std::pair<iterator, bool>
350 insert(const value_type& __obj)
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 };
359 insert(const_iterator __hint, const value_type& __obj)
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 };
368 std::pair<iterator, bool>
369 insert(value_type&& __obj)
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 };
378 insert(const_iterator __hint, value_type&& __obj)
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 };
388 insert(std::initializer_list<value_type> __l)
390 size_type __bucket_count = this->bucket_count();
392 _M_check_rehashed(__bucket_count);
395 template<typename _InputIterator>
397 insert(_InputIterator __first, _InputIterator __last)
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();
403 if (__dist.second >= __gnu_debug::__dp_sign)
404 _Base::insert(__gnu_debug::__unsafe(__first),
405 __gnu_debug::__unsafe(__last));
407 _Base::insert(__first, __last);
409 _M_check_rehashed(__bucket_count);
412#if __cplusplus > 201402L
413 using node_type = typename _Base::node_type;
414 using insert_return_type = _Node_insert_return<iterator, node_type>;
417 extract(const_iterator __position)
419 __glibcxx_check_erase(__position);
420 return _M_extract(__position.base());
424 extract(const key_type& __key)
426 const auto __position = _Base::find(__key);
427 if (__position != _Base::end())
428 return _M_extract(__position);
433 insert(node_type&& __nh)
435 auto __ret = _Base::insert(std::move(__nh));
437 { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };
441 insert(const_iterator __hint, node_type&& __nh)
443 __glibcxx_check_insert(__hint);
444 return { _Base::insert(__hint.base(), std::move(__nh)), this };
447 template<typename _H2, typename _P2>
449 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
452 = _Safe::_S_uc_guard(std::__detail::_Identity{}, __source);
453 _Base::merge(__source);
456 template<typename _H2, typename _P2>
458 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
461 template<typename _H2, typename _P2>
463 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
466 = _Safe::_S_umc_guard(std::__detail::_Identity{}, __source);
467 _Base::merge(__source);
470 template<typename _H2, typename _P2>
472 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
476 using _Base::hash_function;
480 find(const key_type& __key)
481 { return { _Base::find(__key), this }; }
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>>
489 { return { _Base::find(__k), this }; }
493 find(const key_type& __key) const
494 { return { _Base::find(__key), this }; }
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>>
501 find(const _Kt& __k) const
502 { return { _Base::find(__k), this }; }
507#if __cplusplus > 201703L
508 using _Base::contains;
511 std::pair<iterator, iterator>
512 equal_range(const key_type& __key)
514 auto __res = _Base::equal_range(__key);
515 return { { __res.first, this }, { __res.second, this } };
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)
525 auto __res = _Base::equal_range(__k);
526 return { { __res.first, this }, { __res.second, this } };
530 std::pair<const_iterator, const_iterator>
531 equal_range(const key_type& __key) const
533 auto __res = _Base::equal_range(__key);
534 return { { __res.first, this }, { __res.second, this } };
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
544 auto __res = _Base::equal_range(__k);
545 return { { __res.first, this }, { __res.second, this } };
550 erase(const key_type& __key)
553 auto __victim = _Base::find(__key);
554 if (__victim != _Base::end())
563 erase(const_iterator __it)
565 __glibcxx_check_erase(__it);
566 return { _M_erase(__it.base()), this };
570 erase(_Base_const_iterator __it)
572 __glibcxx_check_erase2(__it);
573 return _M_erase(__it);
579 __glibcxx_check_erase(__it);
580 return { _M_erase(__it.base()), this };
584 erase(const_iterator __first, const_iterator __last)
586 __glibcxx_check_erase_range(__first, __last);
587 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
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);
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 };
603 _M_base() noexcept { return *this; }
606 _M_base() const noexcept { return *this; }
610 _M_check_rehashed(size_type __prev_count)
612 if (__prev_count != this->bucket_count())
613 this->_M_invalidate_all();
617 _M_invalidate(_Base_const_iterator __victim)
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; });
627 _M_erase(_Base_const_iterator __victim)
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);
636#if __cplusplus > 201402L
638 _M_extract(_Base_const_iterator __victim)
640 _M_invalidate(__victim);
641 return _Base::extract(__victim);
646#if __cpp_deduction_guides >= 201606
648 template<typename _InputIterator,
650 hash<typename iterator_traits<_InputIterator>::value_type>,
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>;
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>;
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,
683 typename iterator_traits<_InputIterator>::value_type>,
685 typename iterator_traits<_InputIterator>::value_type>,
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,
695 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
698 typename iterator_traits<_InputIterator>::value_type>,
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>;
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>;
716 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
718 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
719 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
720 noexcept(noexcept(__x.swap(__y)))
723 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
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(); }
729#if __cpp_impl_three_way_comparison < 201907L
730 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
732 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
733 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
734 { return !(__x == __y); }
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>
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;
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;
763 // Reference wrapper for base class. See PR libstdc++/90102.
766 _Base_ref(const _Base& __r) : _M_ref(__r) { }
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;
778 typedef typename _Base::key_type key_type;
779 typedef typename _Base::value_type value_type;
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;
794 unordered_multiset() = default;
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) { }
803 template<typename _InputIterator>
804 unordered_multiset(_InputIterator __first, _InputIterator __last,
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) { }
814 unordered_multiset(const unordered_multiset&) = default;
816 unordered_multiset(_Base_ref __x)
817 : _Base(__x._M_ref) { }
819 unordered_multiset(unordered_multiset&&) = default;
822 unordered_multiset(const allocator_type& __a)
825 unordered_multiset(const unordered_multiset& __uset,
826 const allocator_type& __a)
827 : _Base(__uset, __a) { }
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) { }
835 unordered_multiset(initializer_list<value_type> __l,
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) { }
842 unordered_multiset(size_type __n, const allocator_type& __a)
843 : unordered_multiset(__n, hasher(), key_equal(), __a)
846 unordered_multiset(size_type __n, const hasher& __hf,
847 const allocator_type& __a)
848 : unordered_multiset(__n, __hf, key_equal(), __a)
851 template<typename _InputIterator>
852 unordered_multiset(_InputIterator __first, _InputIterator __last,
854 const allocator_type& __a)
855 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
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)
865 unordered_multiset(initializer_list<value_type> __l,
867 const allocator_type& __a)
868 : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
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)
877 ~unordered_multiset() = default;
880 operator=(const unordered_multiset&) = default;
883 operator=(unordered_multiset&&) = default;
886 operator=(initializer_list<value_type> __l)
888 _Base::operator=(__l);
889 this->_M_invalidate_all();
893 using _Base::get_allocator;
896 using _Base::max_size;
899 swap(unordered_multiset& __x)
900 noexcept( noexcept(declval<_Base&>().swap(__x)) )
910 this->_M_invalidate_all();
915 { return { _Base::begin(), this }; }
918 begin() const noexcept
919 { return { _Base::begin(), this }; }
923 { return { _Base::end(), this }; }
927 { return { _Base::end(), this }; }
930 cbegin() const noexcept
931 { return { _Base::cbegin(), this }; }
934 cend() const noexcept
935 { return { _Base::cend(), this }; }
941 __glibcxx_check_bucket_index(__b);
942 return { _Base::begin(__b), this };
948 __glibcxx_check_bucket_index(__b);
949 return { _Base::end(__b), this };
953 begin(size_type __b) const
955 __glibcxx_check_bucket_index(__b);
956 return { _Base::begin(__b), this };
960 end(size_type __b) const
962 __glibcxx_check_bucket_index(__b);
963 return { _Base::end(__b), this };
967 cbegin(size_type __b) const
969 __glibcxx_check_bucket_index(__b);
970 return { _Base::cbegin(__b), this };
974 cend(size_type __b) const
976 __glibcxx_check_bucket_index(__b);
977 return { _Base::cend(__b), this };
980 using _Base::bucket_count;
981 using _Base::max_bucket_count;
984 bucket_size(size_type __b) const
986 __glibcxx_check_bucket_index(__b);
987 return _Base::bucket_size(__b);
991 using _Base::load_factor;
994 max_load_factor() const noexcept
995 { return _Base::max_load_factor(); }
998 max_load_factor(float __f)
1000 __glibcxx_check_max_load_factor(__f);
1001 _Base::max_load_factor(__f);
1004 using _Base::rehash;
1005 using _Base::reserve;
1007 template<typename... _Args>
1009 emplace(_Args&&... __args)
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 };
1017 template<typename... _Args>
1019 emplace_hint(const_iterator __hint, _Args&&... __args)
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 };
1030 insert(const value_type& __obj)
1032 size_type __bucket_count = this->bucket_count();
1033 auto __it = _Base::insert(__obj);
1034 _M_check_rehashed(__bucket_count);
1035 return { __it, this };
1039 insert(const_iterator __hint, const value_type& __obj)
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 };
1049 insert(value_type&& __obj)
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 };
1058 insert(const_iterator __hint, value_type&& __obj)
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 };
1068 insert(std::initializer_list<value_type> __l)
1070 size_type __bucket_count = this->bucket_count();
1072 _M_check_rehashed(__bucket_count);
1075 template<typename _InputIterator>
1077 insert(_InputIterator __first, _InputIterator __last)
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();
1083 if (__dist.second >= __gnu_debug::__dp_sign)
1084 _Base::insert(__gnu_debug::__unsafe(__first),
1085 __gnu_debug::__unsafe(__last));
1087 _Base::insert(__first, __last);
1089 _M_check_rehashed(__bucket_count);
1092#if __cplusplus > 201402L
1093 using node_type = typename _Base::node_type;
1096 extract(const_iterator __position)
1098 __glibcxx_check_erase(__position);
1099 return _M_extract(__position.base());
1103 extract(const key_type& __key)
1105 const auto __position = _Base::find(__key);
1106 if (__position != _Base::end())
1107 return _M_extract(__position);
1112 insert(node_type&& __nh)
1113 { return { _Base::insert(std::move(__nh)), this }; }
1116 insert(const_iterator __hint, node_type&& __nh)
1118 __glibcxx_check_insert(__hint);
1119 return { _Base::insert(__hint.base(), std::move(__nh)), this };
1122 template<typename _H2, typename _P2>
1124 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
1127 = _Safe::_S_umc_guard(std::__detail::_Identity{}, __source);
1128 _Base::merge(__source);
1131 template<typename _H2, typename _P2>
1133 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
1134 { merge(__source); }
1136 template<typename _H2, typename _P2>
1138 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
1141 = _Safe::_S_uc_guard(std::__detail::_Identity{}, __source);
1142 _Base::merge(__source);
1145 template<typename _H2, typename _P2>
1147 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
1148 { merge(__source); }
1151 using _Base::hash_function;
1152 using _Base::key_eq;
1155 find(const key_type& __key)
1156 { return { _Base::find(__key), this }; }
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>>
1163 find(const _Kt& __k)
1164 { return { _Base::find(__k), this }; }
1168 find(const key_type& __key) const
1169 { return { _Base::find(__key), this }; }
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>>
1176 find(const _Kt& __k) const
1177 { return { _Base::find(__k), this }; }
1182#if __cplusplus > 201703L
1183 using _Base::contains;
1186 std::pair<iterator, iterator>
1187 equal_range(const key_type& __key)
1189 auto __res = _Base::equal_range(__key);
1190 return { { __res.first, this }, { __res.second, this } };
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)
1200 auto __res = _Base::equal_range(__k);
1201 return { { __res.first, this }, { __res.second, this } };
1205 std::pair<const_iterator, const_iterator>
1206 equal_range(const key_type& __key) const
1208 auto __res = _Base::equal_range(__key);
1209 return { { __res.first, this }, { __res.second, this } };
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
1219 auto __res = _Base::equal_range(__k);
1220 return { { __res.first, this }, { __res.second, this } };
1225 erase(const key_type& __key)
1228 auto __pair = _Base::equal_range(__key);
1229 for (auto __victim = __pair.first; __victim != __pair.second;)
1231 _M_invalidate(__victim);
1232 __victim = _Base::erase(__victim);
1240 erase(const_iterator __it)
1242 __glibcxx_check_erase(__it);
1243 return { _M_erase(__it.base()), this };
1247 erase(_Base_const_iterator __it)
1249 __glibcxx_check_erase2(__it);
1250 return _M_erase(__it);
1254 erase(iterator __it)
1256 __glibcxx_check_erase(__it);
1257 return { _M_erase(__it.base()), this };
1261 erase(const_iterator __first, const_iterator __last)
1263 __glibcxx_check_erase_range(__first, __last);
1264 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
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);
1272 return { _Base::erase(__first.base(), __last.base()), this };
1276 _M_base() noexcept { return *this; }
1279 _M_base() const noexcept { return *this; }
1283 _M_check_rehashed(size_type __prev_count)
1285 if (__prev_count != this->bucket_count())
1286 this->_M_invalidate_all();
1290 _M_invalidate(_Base_const_iterator __victim)
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; });
1300 _M_erase(_Base_const_iterator __victim)
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);
1309#if __cplusplus > 201402L
1311 _M_extract(_Base_const_iterator __victim)
1313 _M_invalidate(__victim);
1314 return _Base::extract(__victim);
1319#if __cpp_deduction_guides >= 201606
1321 template<typename _InputIterator,
1323 hash<typename iterator_traits<_InputIterator>::value_type>,
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>;
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>;
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,
1358 iterator_traits<_InputIterator>::value_type>,
1360 iterator_traits<_InputIterator>::value_type>,
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,
1370 -> unordered_multiset<typename
1371 iterator_traits<_InputIterator>::value_type,
1375 iterator_traits<_InputIterator>::value_type>,
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>;
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>;
1393 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1395 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1396 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1397 noexcept(noexcept(__x.swap(__y)))
1400 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
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(); }
1406#if __cpp_impl_three_way_comparison < 201907L
1407 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1409 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1410 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1411 { return !(__x == __y); }
1414} // namespace __debug