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
32 #ifdef _GLIBCXX_SYSHDR
33 #pragma GCC system_header
36 #if __cplusplus < 201103L
37 # include <bits/c++0x_warning.h>
39 # include <bits/c++config.h>
40 namespace 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>
53 namespace 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 #if __glibcxx_containers_ranges // C++ >= 23
198 template<__detail::__container_compatible_range<value_type> _Rg>
199 unordered_set(from_range_t, _Rg&& __rg,
201 const hasher& __hf = hasher(),
202 const key_equal& __eql = key_equal(),
203 const allocator_type& __a = allocator_type())
204 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __eql, __a)
207 template<__detail::__container_compatible_range<value_type> _Rg>
208 unordered_set(from_range_t, _Rg&& __rg, const allocator_type& __a)
209 : _Base(from_range, std::forward<_Rg>(__rg), __a)
212 template<__detail::__container_compatible_range<value_type> _Rg>
213 unordered_set(from_range_t, _Rg&& __rg, size_type __n,
214 const allocator_type& __a)
215 : _Base(from_range, std::forward<_Rg>(__rg), __n, __a)
218 template<__detail::__container_compatible_range<value_type> _Rg>
219 unordered_set(from_range_t, _Rg&& __rg, size_type __n,
220 const hasher& __hf, const allocator_type& __a)
221 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __a)
225 ~unordered_set() = default;
228 operator=(const unordered_set&) = default;
231 operator=(unordered_set&&) = default;
234 operator=(initializer_list<value_type> __l)
236 _Base::operator=(__l);
237 this->_M_invalidate_all();
241 using _Base::get_allocator;
244 using _Base::max_size;
247 swap(unordered_set& __x)
248 noexcept( noexcept(declval<_Base&>().swap(__x)) )
258 this->_M_invalidate_all();
263 { return { _Base::begin(), this }; }
266 begin() const noexcept
267 { return { _Base::begin(), this }; }
271 { return { _Base::end(), this }; }
275 { return { _Base::end(), this }; }
278 cbegin() const noexcept
279 { return { _Base::cbegin(), this }; }
282 cend() const noexcept
283 { return { _Base::cend(), this }; }
289 __glibcxx_check_bucket_index(__b);
290 return { _Base::begin(__b), this };
296 __glibcxx_check_bucket_index(__b);
297 return { _Base::end(__b), this };
301 begin(size_type __b) const
303 __glibcxx_check_bucket_index(__b);
304 return { _Base::begin(__b), this };
308 end(size_type __b) const
310 __glibcxx_check_bucket_index(__b);
311 return { _Base::end(__b), this };
315 cbegin(size_type __b) const
317 __glibcxx_check_bucket_index(__b);
318 return { _Base::cbegin(__b), this };
322 cend(size_type __b) const
324 __glibcxx_check_bucket_index(__b);
325 return { _Base::cend(__b), this };
328 using _Base::bucket_count;
329 using _Base::max_bucket_count;
332 bucket_size(size_type __b) const
334 __glibcxx_check_bucket_index(__b);
335 return _Base::bucket_size(__b);
339 using _Base::load_factor;
342 max_load_factor() const noexcept
343 { return _Base::max_load_factor(); }
346 max_load_factor(float __f)
348 __glibcxx_check_max_load_factor(__f);
349 _Base::max_load_factor(__f);
353 using _Base::reserve;
355 template<typename... _Args>
356 std::pair<iterator, bool>
357 emplace(_Args&&... __args)
359 size_type __bucket_count = this->bucket_count();
360 auto __res = _Base::emplace(std::forward<_Args>(__args)...);
361 _M_check_rehashed(__bucket_count);
362 return { { __res.first, this }, __res.second };
365 template<typename... _Args>
367 emplace_hint(const_iterator __hint, _Args&&... __args)
369 __glibcxx_check_insert(__hint);
370 size_type __bucket_count = this->bucket_count();
371 auto __it = _Base::emplace_hint(__hint.base(),
372 std::forward<_Args>(__args)...);
373 _M_check_rehashed(__bucket_count);
374 return { __it, this };
377 std::pair<iterator, bool>
378 insert(const value_type& __obj)
380 size_type __bucket_count = this->bucket_count();
381 auto __res = _Base::insert(__obj);
382 _M_check_rehashed(__bucket_count);
383 return { { __res.first, this }, __res.second };
387 insert(const_iterator __hint, const value_type& __obj)
389 __glibcxx_check_insert(__hint);
390 size_type __bucket_count = this->bucket_count();
391 auto __it = _Base::insert(__hint.base(), __obj);
392 _M_check_rehashed(__bucket_count);
393 return { __it, this };
396 std::pair<iterator, bool>
397 insert(value_type&& __obj)
399 size_type __bucket_count = this->bucket_count();
400 auto __res = _Base::insert(std::move(__obj));
401 _M_check_rehashed(__bucket_count);
402 return { { __res.first, this }, __res.second };
406 insert(const_iterator __hint, value_type&& __obj)
408 __glibcxx_check_insert(__hint);
409 size_type __bucket_count = this->bucket_count();
410 auto __it = _Base::insert(__hint.base(), std::move(__obj));
411 _M_check_rehashed(__bucket_count);
412 return { __it, this };
416 insert(std::initializer_list<value_type> __l)
418 size_type __bucket_count = this->bucket_count();
420 _M_check_rehashed(__bucket_count);
423 template<typename _InputIterator>
425 insert(_InputIterator __first, _InputIterator __last)
427 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
428 __glibcxx_check_valid_range2(__first, __last, __dist);
429 size_type __bucket_count = this->bucket_count();
431 if (__dist.second >= __gnu_debug::__dp_sign)
432 _Base::insert(__gnu_debug::__unsafe(__first),
433 __gnu_debug::__unsafe(__last));
435 _Base::insert(__first, __last);
437 _M_check_rehashed(__bucket_count);
440 #if __cplusplus > 201402L
441 using node_type = typename _Base::node_type;
442 using insert_return_type = _Node_insert_return<iterator, node_type>;
445 extract(const_iterator __position)
447 __glibcxx_check_erase(__position);
448 return _M_extract(__position.base());
452 extract(const key_type& __key)
454 const auto __position = _Base::find(__key);
455 if (__position != _Base::end())
456 return _M_extract(__position);
461 insert(node_type&& __nh)
463 auto __ret = _Base::insert(std::move(__nh));
465 { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };
469 insert(const_iterator __hint, node_type&& __nh)
471 __glibcxx_check_insert(__hint);
472 return { _Base::insert(__hint.base(), std::move(__nh)), this };
475 template<typename _H2, typename _P2>
477 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
480 = _Safe::_S_uc_guard(std::__detail::_Identity{}, __source);
481 _Base::merge(__source);
484 template<typename _H2, typename _P2>
486 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
489 template<typename _H2, typename _P2>
491 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
494 = _Safe::_S_umc_guard(std::__detail::_Identity{}, __source);
495 _Base::merge(__source);
498 template<typename _H2, typename _P2>
500 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
504 using _Base::hash_function;
508 find(const key_type& __key)
509 { return { _Base::find(__key), this }; }
511 #if __cplusplus > 201703L
512 template<typename _Kt,
513 typename = std::__has_is_transparent_t<_Hash, _Kt>,
514 typename = std::__has_is_transparent_t<_Pred, _Kt>>
517 { return { _Base::find(__k), this }; }
521 find(const key_type& __key) const
522 { return { _Base::find(__key), this }; }
524 #if __cplusplus > 201703L
525 template<typename _Kt,
526 typename = std::__has_is_transparent_t<_Hash, _Kt>,
527 typename = std::__has_is_transparent_t<_Pred, _Kt>>
529 find(const _Kt& __k) const
530 { return { _Base::find(__k), this }; }
535 #if __cplusplus > 201703L
536 using _Base::contains;
539 std::pair<iterator, iterator>
540 equal_range(const key_type& __key)
542 auto __res = _Base::equal_range(__key);
543 return { { __res.first, this }, { __res.second, this } };
546 #if __cplusplus > 201703L
547 template<typename _Kt,
548 typename = std::__has_is_transparent_t<_Hash, _Kt>,
549 typename = std::__has_is_transparent_t<_Pred, _Kt>>
550 std::pair<iterator, iterator>
551 equal_range(const _Kt& __k)
553 auto __res = _Base::equal_range(__k);
554 return { { __res.first, this }, { __res.second, this } };
558 std::pair<const_iterator, const_iterator>
559 equal_range(const key_type& __key) const
561 auto __res = _Base::equal_range(__key);
562 return { { __res.first, this }, { __res.second, this } };
565 #if __cplusplus > 201703L
566 template<typename _Kt,
567 typename = std::__has_is_transparent_t<_Hash, _Kt>,
568 typename = std::__has_is_transparent_t<_Pred, _Kt>>
569 std::pair<const_iterator, const_iterator>
570 equal_range(const _Kt& __k) const
572 auto __res = _Base::equal_range(__k);
573 return { { __res.first, this }, { __res.second, this } };
578 erase(const key_type& __key)
581 auto __victim = _Base::find(__key);
582 if (__victim != _Base::end())
591 erase(const_iterator __it)
593 __glibcxx_check_erase(__it);
594 return { _M_erase(__it.base()), this };
598 erase(_Base_const_iterator __it)
600 __glibcxx_check_erase2(__it);
601 return _M_erase(__it);
607 __glibcxx_check_erase(__it);
608 return { _M_erase(__it.base()), this };
612 erase(const_iterator __first, const_iterator __last)
614 __glibcxx_check_erase_range(__first, __last);
615 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
617 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
618 _M_message(__gnu_debug::__msg_valid_range)
619 ._M_iterator(__first, "first")
620 ._M_iterator(__last, "last"));
621 _M_invalidate(__tmp);
624 size_type __bucket_count = this->bucket_count();
625 auto __next = _Base::erase(__first.base(), __last.base());
626 _M_check_rehashed(__bucket_count);
627 return { __next, this };
631 _M_base() noexcept { return *this; }
634 _M_base() const noexcept { return *this; }
638 _M_check_rehashed(size_type __prev_count)
640 if (__prev_count != this->bucket_count())
641 this->_M_invalidate_all();
645 _M_invalidate(_Base_const_iterator __victim)
647 this->_M_invalidate_if(
648 [__victim](_Base_const_iterator __it) { return __it == __victim; });
649 this->_M_invalidate_local_if(
650 [__victim](_Base_const_local_iterator __it)
651 { return __it == __victim; });
655 _M_erase(_Base_const_iterator __victim)
657 _M_invalidate(__victim);
658 size_type __bucket_count = this->bucket_count();
659 _Base_iterator __next = _Base::erase(__victim);
660 _M_check_rehashed(__bucket_count);
664 #if __cplusplus > 201402L
666 _M_extract(_Base_const_iterator __victim)
668 _M_invalidate(__victim);
669 return _Base::extract(__victim);
674 #if __cpp_deduction_guides >= 201606
676 template<typename _InputIterator,
678 hash<typename iterator_traits<_InputIterator>::value_type>,
680 equal_to<typename iterator_traits<_InputIterator>::value_type>,
681 typename _Allocator =
682 allocator<typename iterator_traits<_InputIterator>::value_type>,
683 typename = _RequireInputIter<_InputIterator>,
684 typename = _RequireNotAllocatorOrIntegral<_Hash>,
685 typename = _RequireNotAllocator<_Pred>,
686 typename = _RequireAllocator<_Allocator>>
687 unordered_set(_InputIterator, _InputIterator,
688 unordered_set<int>::size_type = {},
689 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
690 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
691 _Hash, _Pred, _Allocator>;
693 template<typename _Tp, typename _Hash = hash<_Tp>,
694 typename _Pred = equal_to<_Tp>,
695 typename _Allocator = allocator<_Tp>,
696 typename = _RequireNotAllocatorOrIntegral<_Hash>,
697 typename = _RequireNotAllocator<_Pred>,
698 typename = _RequireAllocator<_Allocator>>
699 unordered_set(initializer_list<_Tp>,
700 unordered_set<int>::size_type = {},
701 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
702 -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
704 template<typename _InputIterator, typename _Allocator,
705 typename = _RequireInputIter<_InputIterator>,
706 typename = _RequireAllocator<_Allocator>>
707 unordered_set(_InputIterator, _InputIterator,
708 unordered_set<int>::size_type, _Allocator)
709 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
711 typename iterator_traits<_InputIterator>::value_type>,
713 typename iterator_traits<_InputIterator>::value_type>,
716 template<typename _InputIterator, typename _Hash, typename _Allocator,
717 typename = _RequireInputIter<_InputIterator>,
718 typename = _RequireNotAllocatorOrIntegral<_Hash>,
719 typename = _RequireAllocator<_Allocator>>
720 unordered_set(_InputIterator, _InputIterator,
721 unordered_set<int>::size_type,
723 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
726 typename iterator_traits<_InputIterator>::value_type>,
729 template<typename _Tp, typename _Allocator,
730 typename = _RequireAllocator<_Allocator>>
731 unordered_set(initializer_list<_Tp>,
732 unordered_set<int>::size_type, _Allocator)
733 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
735 template<typename _Tp, typename _Hash, typename _Allocator,
736 typename = _RequireNotAllocatorOrIntegral<_Hash>,
737 typename = _RequireAllocator<_Allocator>>
738 unordered_set(initializer_list<_Tp>,
739 unordered_set<int>::size_type, _Hash, _Allocator)
740 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
744 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
746 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
747 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
748 noexcept(noexcept(__x.swap(__y)))
751 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
753 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
754 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
755 { return __x._M_base() == __y._M_base(); }
757 #if __cpp_impl_three_way_comparison < 201907L
758 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
760 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
761 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
762 { return !(__x == __y); }
765 /// Class std::unordered_multiset with safety/checking/debug instrumentation.
766 template<typename _Value,
767 typename _Hash = std::hash<_Value>,
768 typename _Pred = std::equal_to<_Value>,
769 typename _Alloc = std::allocator<_Value> >
770 class unordered_multiset
771 : public __gnu_debug::_Safe_container<
772 unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
773 __gnu_debug::_Safe_unordered_container>,
774 public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
776 typedef _GLIBCXX_STD_C::unordered_multiset<
777 _Value, _Hash, _Pred, _Alloc> _Base;
778 typedef __gnu_debug::_Safe_container<unordered_multiset,
779 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
780 typedef typename _Base::const_iterator _Base_const_iterator;
781 typedef typename _Base::iterator _Base_iterator;
782 typedef typename _Base::const_local_iterator
783 _Base_const_local_iterator;
784 typedef typename _Base::local_iterator _Base_local_iterator;
786 template<typename _ItT, typename _SeqT, typename _CatT>
787 friend class ::__gnu_debug::_Safe_iterator;
788 template<typename _ItT, typename _SeqT>
789 friend class ::__gnu_debug::_Safe_local_iterator;
791 // Reference wrapper for base class. See PR libstdc++/90102.
794 _Base_ref(const _Base& __r) : _M_ref(__r) { }
800 typedef typename _Base::size_type size_type;
801 typedef typename _Base::difference_type difference_type;
802 typedef typename _Base::hasher hasher;
803 typedef typename _Base::key_equal key_equal;
804 typedef typename _Base::allocator_type allocator_type;
806 typedef typename _Base::key_type key_type;
807 typedef typename _Base::value_type value_type;
809 typedef typename _Base::pointer pointer;
810 typedef typename _Base::const_pointer const_pointer;
811 typedef typename _Base::reference reference;
812 typedef typename _Base::const_reference const_reference;
813 typedef __gnu_debug::_Safe_iterator<
814 _Base_iterator, unordered_multiset> iterator;
815 typedef __gnu_debug::_Safe_iterator<
816 _Base_const_iterator, unordered_multiset> const_iterator;
817 typedef __gnu_debug::_Safe_local_iterator<
818 _Base_local_iterator, unordered_multiset> local_iterator;
819 typedef __gnu_debug::_Safe_local_iterator<
820 _Base_const_local_iterator, unordered_multiset> const_local_iterator;
822 unordered_multiset() = default;
825 unordered_multiset(size_type __n,
826 const hasher& __hf = hasher(),
827 const key_equal& __eql = key_equal(),
828 const allocator_type& __a = allocator_type())
829 : _Base(__n, __hf, __eql, __a) { }
831 template<typename _InputIterator>
832 unordered_multiset(_InputIterator __first, _InputIterator __last,
834 const hasher& __hf = hasher(),
835 const key_equal& __eql = key_equal(),
836 const allocator_type& __a = allocator_type())
837 : _Base(__gnu_debug::__base(
838 __glibcxx_check_valid_constructor_range(__first, __last)),
839 __gnu_debug::__base(__last), __n,
840 __hf, __eql, __a) { }
842 unordered_multiset(const unordered_multiset&) = default;
844 unordered_multiset(_Base_ref __x)
845 : _Base(__x._M_ref) { }
847 unordered_multiset(unordered_multiset&&) = default;
850 unordered_multiset(const allocator_type& __a)
853 unordered_multiset(const unordered_multiset& __uset,
854 const allocator_type& __a)
855 : _Base(__uset, __a) { }
857 unordered_multiset(unordered_multiset&& __uset,
858 const allocator_type& __a)
859 noexcept( noexcept(_Base(std::move(__uset), __a)) )
860 : _Safe(std::move(__uset), __a),
861 _Base(std::move(__uset), __a) { }
863 unordered_multiset(initializer_list<value_type> __l,
865 const hasher& __hf = hasher(),
866 const key_equal& __eql = key_equal(),
867 const allocator_type& __a = allocator_type())
868 : _Base(__l, __n, __hf, __eql, __a) { }
870 unordered_multiset(size_type __n, const allocator_type& __a)
871 : unordered_multiset(__n, hasher(), key_equal(), __a)
874 unordered_multiset(size_type __n, const hasher& __hf,
875 const allocator_type& __a)
876 : unordered_multiset(__n, __hf, key_equal(), __a)
879 template<typename _InputIterator>
880 unordered_multiset(_InputIterator __first, _InputIterator __last,
882 const allocator_type& __a)
883 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
886 template<typename _InputIterator>
887 unordered_multiset(_InputIterator __first, _InputIterator __last,
888 size_type __n, const hasher& __hf,
889 const allocator_type& __a)
890 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
893 unordered_multiset(initializer_list<value_type> __l,
895 const allocator_type& __a)
896 : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
899 unordered_multiset(initializer_list<value_type> __l,
900 size_type __n, const hasher& __hf,
901 const allocator_type& __a)
902 : unordered_multiset(__l, __n, __hf, key_equal(), __a)
905 #if __glibcxx_containers_ranges // C++ >= 23
906 template<__detail::__container_compatible_range<value_type> _Rg>
907 unordered_multiset(from_range_t, _Rg&& __rg,
909 const hasher& __hf = hasher(),
910 const key_equal& __eql = key_equal(),
911 const allocator_type& __a = allocator_type())
912 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __eql, __a)
915 template<__detail::__container_compatible_range<value_type> _Rg>
916 unordered_multiset(from_range_t, _Rg&& __rg, const allocator_type& __a)
917 : _Base(from_range, std::forward<_Rg>(__rg), __a)
920 template<__detail::__container_compatible_range<value_type> _Rg>
921 unordered_multiset(from_range_t, _Rg&& __rg, size_type __n,
922 const allocator_type& __a)
923 : _Base(from_range, std::forward<_Rg>(__rg), __n, __a)
926 template<__detail::__container_compatible_range<value_type> _Rg>
927 unordered_multiset(from_range_t, _Rg&& __rg, size_type __n,
928 const hasher& __hf, const allocator_type& __a)
929 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __a)
933 ~unordered_multiset() = default;
936 operator=(const unordered_multiset&) = default;
939 operator=(unordered_multiset&&) = default;
942 operator=(initializer_list<value_type> __l)
944 _Base::operator=(__l);
945 this->_M_invalidate_all();
949 using _Base::get_allocator;
952 using _Base::max_size;
955 swap(unordered_multiset& __x)
956 noexcept( noexcept(declval<_Base&>().swap(__x)) )
966 this->_M_invalidate_all();
971 { return { _Base::begin(), this }; }
974 begin() const noexcept
975 { return { _Base::begin(), this }; }
979 { return { _Base::end(), this }; }
983 { return { _Base::end(), this }; }
986 cbegin() const noexcept
987 { return { _Base::cbegin(), this }; }
990 cend() const noexcept
991 { return { _Base::cend(), this }; }
997 __glibcxx_check_bucket_index(__b);
998 return { _Base::begin(__b), this };
1004 __glibcxx_check_bucket_index(__b);
1005 return { _Base::end(__b), this };
1008 const_local_iterator
1009 begin(size_type __b) const
1011 __glibcxx_check_bucket_index(__b);
1012 return { _Base::begin(__b), this };
1015 const_local_iterator
1016 end(size_type __b) const
1018 __glibcxx_check_bucket_index(__b);
1019 return { _Base::end(__b), this };
1022 const_local_iterator
1023 cbegin(size_type __b) const
1025 __glibcxx_check_bucket_index(__b);
1026 return { _Base::cbegin(__b), this };
1029 const_local_iterator
1030 cend(size_type __b) const
1032 __glibcxx_check_bucket_index(__b);
1033 return { _Base::cend(__b), this };
1036 using _Base::bucket_count;
1037 using _Base::max_bucket_count;
1040 bucket_size(size_type __b) const
1042 __glibcxx_check_bucket_index(__b);
1043 return _Base::bucket_size(__b);
1046 using _Base::bucket;
1047 using _Base::load_factor;
1050 max_load_factor() const noexcept
1051 { return _Base::max_load_factor(); }
1054 max_load_factor(float __f)
1056 __glibcxx_check_max_load_factor(__f);
1057 _Base::max_load_factor(__f);
1060 using _Base::rehash;
1061 using _Base::reserve;
1063 template<typename... _Args>
1065 emplace(_Args&&... __args)
1067 size_type __bucket_count = this->bucket_count();
1068 auto __it = _Base::emplace(std::forward<_Args>(__args)...);
1069 _M_check_rehashed(__bucket_count);
1070 return { __it, this };
1073 template<typename... _Args>
1075 emplace_hint(const_iterator __hint, _Args&&... __args)
1077 __glibcxx_check_insert(__hint);
1078 size_type __bucket_count = this->bucket_count();
1079 auto __it = _Base::emplace_hint(__hint.base(),
1080 std::forward<_Args>(__args)...);
1081 _M_check_rehashed(__bucket_count);
1082 return { __it, this };
1086 insert(const value_type& __obj)
1088 size_type __bucket_count = this->bucket_count();
1089 auto __it = _Base::insert(__obj);
1090 _M_check_rehashed(__bucket_count);
1091 return { __it, this };
1095 insert(const_iterator __hint, const value_type& __obj)
1097 __glibcxx_check_insert(__hint);
1098 size_type __bucket_count = this->bucket_count();
1099 auto __it = _Base::insert(__hint.base(), __obj);
1100 _M_check_rehashed(__bucket_count);
1101 return { __it, this };
1105 insert(value_type&& __obj)
1107 size_type __bucket_count = this->bucket_count();
1108 auto __it = _Base::insert(std::move(__obj));
1109 _M_check_rehashed(__bucket_count);
1110 return { __it, this };
1114 insert(const_iterator __hint, value_type&& __obj)
1116 __glibcxx_check_insert(__hint);
1117 size_type __bucket_count = this->bucket_count();
1118 auto __it = _Base::insert(__hint.base(), std::move(__obj));
1119 _M_check_rehashed(__bucket_count);
1120 return { __it, this };
1124 insert(std::initializer_list<value_type> __l)
1126 size_type __bucket_count = this->bucket_count();
1128 _M_check_rehashed(__bucket_count);
1131 template<typename _InputIterator>
1133 insert(_InputIterator __first, _InputIterator __last)
1135 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
1136 __glibcxx_check_valid_range2(__first, __last, __dist);
1137 size_type __bucket_count = this->bucket_count();
1139 if (__dist.second >= __gnu_debug::__dp_sign)
1140 _Base::insert(__gnu_debug::__unsafe(__first),
1141 __gnu_debug::__unsafe(__last));
1143 _Base::insert(__first, __last);
1145 _M_check_rehashed(__bucket_count);
1148 #if __cplusplus > 201402L
1149 using node_type = typename _Base::node_type;
1152 extract(const_iterator __position)
1154 __glibcxx_check_erase(__position);
1155 return _M_extract(__position.base());
1159 extract(const key_type& __key)
1161 const auto __position = _Base::find(__key);
1162 if (__position != _Base::end())
1163 return _M_extract(__position);
1168 insert(node_type&& __nh)
1169 { return { _Base::insert(std::move(__nh)), this }; }
1172 insert(const_iterator __hint, node_type&& __nh)
1174 __glibcxx_check_insert(__hint);
1175 return { _Base::insert(__hint.base(), std::move(__nh)), this };
1178 template<typename _H2, typename _P2>
1180 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
1183 = _Safe::_S_umc_guard(std::__detail::_Identity{}, __source);
1184 _Base::merge(__source);
1187 template<typename _H2, typename _P2>
1189 merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
1190 { merge(__source); }
1192 template<typename _H2, typename _P2>
1194 merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
1197 = _Safe::_S_uc_guard(std::__detail::_Identity{}, __source);
1198 _Base::merge(__source);
1201 template<typename _H2, typename _P2>
1203 merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
1204 { merge(__source); }
1207 using _Base::hash_function;
1208 using _Base::key_eq;
1211 find(const key_type& __key)
1212 { return { _Base::find(__key), this }; }
1214 #if __cplusplus > 201703L
1215 template<typename _Kt,
1216 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1217 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1219 find(const _Kt& __k)
1220 { return { _Base::find(__k), this }; }
1224 find(const key_type& __key) const
1225 { return { _Base::find(__key), this }; }
1227 #if __cplusplus > 201703L
1228 template<typename _Kt,
1229 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1230 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1232 find(const _Kt& __k) const
1233 { return { _Base::find(__k), this }; }
1238 #if __cplusplus > 201703L
1239 using _Base::contains;
1242 std::pair<iterator, iterator>
1243 equal_range(const key_type& __key)
1245 auto __res = _Base::equal_range(__key);
1246 return { { __res.first, this }, { __res.second, this } };
1249 #if __cplusplus > 201703L
1250 template<typename _Kt,
1251 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1252 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1253 std::pair<iterator, iterator>
1254 equal_range(const _Kt& __k)
1256 auto __res = _Base::equal_range(__k);
1257 return { { __res.first, this }, { __res.second, this } };
1261 std::pair<const_iterator, const_iterator>
1262 equal_range(const key_type& __key) const
1264 auto __res = _Base::equal_range(__key);
1265 return { { __res.first, this }, { __res.second, this } };
1268 #if __cplusplus > 201703L
1269 template<typename _Kt,
1270 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1271 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1272 std::pair<const_iterator, const_iterator>
1273 equal_range(const _Kt& __k) const
1275 auto __res = _Base::equal_range(__k);
1276 return { { __res.first, this }, { __res.second, this } };
1281 erase(const key_type& __key)
1284 auto __pair = _Base::equal_range(__key);
1285 for (auto __victim = __pair.first; __victim != __pair.second;)
1287 _M_invalidate(__victim);
1288 __victim = _Base::erase(__victim);
1296 erase(const_iterator __it)
1298 __glibcxx_check_erase(__it);
1299 return { _M_erase(__it.base()), this };
1303 erase(_Base_const_iterator __it)
1305 __glibcxx_check_erase2(__it);
1306 return _M_erase(__it);
1310 erase(iterator __it)
1312 __glibcxx_check_erase(__it);
1313 return { _M_erase(__it.base()), this };
1317 erase(const_iterator __first, const_iterator __last)
1319 __glibcxx_check_erase_range(__first, __last);
1320 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1322 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1323 _M_message(__gnu_debug::__msg_valid_range)
1324 ._M_iterator(__first, "first")
1325 ._M_iterator(__last, "last"));
1326 _M_invalidate(__tmp);
1328 return { _Base::erase(__first.base(), __last.base()), this };
1332 _M_base() noexcept { return *this; }
1335 _M_base() const noexcept { return *this; }
1339 _M_check_rehashed(size_type __prev_count)
1341 if (__prev_count != this->bucket_count())
1342 this->_M_invalidate_all();
1346 _M_invalidate(_Base_const_iterator __victim)
1348 this->_M_invalidate_if(
1349 [__victim](_Base_const_iterator __it) { return __it == __victim; });
1350 this->_M_invalidate_local_if(
1351 [__victim](_Base_const_local_iterator __it)
1352 { return __it == __victim; });
1356 _M_erase(_Base_const_iterator __victim)
1358 _M_invalidate(__victim);
1359 size_type __bucket_count = this->bucket_count();
1360 _Base_iterator __next = _Base::erase(__victim);
1361 _M_check_rehashed(__bucket_count);
1365 #if __cplusplus > 201402L
1367 _M_extract(_Base_const_iterator __victim)
1369 _M_invalidate(__victim);
1370 return _Base::extract(__victim);
1375 #if __cpp_deduction_guides >= 201606
1377 template<typename _InputIterator,
1379 hash<typename iterator_traits<_InputIterator>::value_type>,
1381 equal_to<typename iterator_traits<_InputIterator>::value_type>,
1382 typename _Allocator =
1383 allocator<typename iterator_traits<_InputIterator>::value_type>,
1384 typename = _RequireInputIter<_InputIterator>,
1385 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1386 typename = _RequireNotAllocator<_Pred>,
1387 typename = _RequireAllocator<_Allocator>>
1388 unordered_multiset(_InputIterator, _InputIterator,
1389 unordered_multiset<int>::size_type = {},
1390 _Hash = _Hash(), _Pred = _Pred(),
1391 _Allocator = _Allocator())
1392 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1393 _Hash, _Pred, _Allocator>;
1395 template<typename _Tp, typename _Hash = hash<_Tp>,
1396 typename _Pred = equal_to<_Tp>,
1397 typename _Allocator = allocator<_Tp>,
1398 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1399 typename = _RequireNotAllocator<_Pred>,
1400 typename = _RequireAllocator<_Allocator>>
1401 unordered_multiset(initializer_list<_Tp>,
1402 unordered_multiset<int>::size_type = {},
1403 _Hash = _Hash(), _Pred = _Pred(),
1404 _Allocator = _Allocator())
1405 -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1407 template<typename _InputIterator, typename _Allocator,
1408 typename = _RequireInputIter<_InputIterator>,
1409 typename = _RequireAllocator<_Allocator>>
1410 unordered_multiset(_InputIterator, _InputIterator,
1411 unordered_multiset<int>::size_type, _Allocator)
1412 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1414 iterator_traits<_InputIterator>::value_type>,
1416 iterator_traits<_InputIterator>::value_type>,
1419 template<typename _InputIterator, typename _Hash, typename _Allocator,
1420 typename = _RequireInputIter<_InputIterator>,
1421 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1422 typename = _RequireAllocator<_Allocator>>
1423 unordered_multiset(_InputIterator, _InputIterator,
1424 unordered_multiset<int>::size_type,
1426 -> unordered_multiset<typename
1427 iterator_traits<_InputIterator>::value_type,
1431 iterator_traits<_InputIterator>::value_type>,
1434 template<typename _Tp, typename _Allocator,
1435 typename = _RequireAllocator<_Allocator>>
1436 unordered_multiset(initializer_list<_Tp>,
1437 unordered_multiset<int>::size_type, _Allocator)
1438 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1440 template<typename _Tp, typename _Hash, typename _Allocator,
1441 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1442 typename = _RequireAllocator<_Allocator>>
1443 unordered_multiset(initializer_list<_Tp>,
1444 unordered_multiset<int>::size_type, _Hash, _Allocator)
1445 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1447 #if __glibcxx_containers_ranges // C++ >= 23
1448 template<ranges::input_range _Rg,
1449 __not_allocator_like _Hash = hash<ranges::range_value_t<_Rg>>,
1450 __not_allocator_like _Pred = equal_to<ranges::range_value_t<_Rg>>,
1451 __allocator_like _Allocator = allocator<ranges::range_value_t<_Rg>>>
1452 unordered_set(from_range_t, _Rg&&, unordered_set<int>::size_type = {},
1453 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
1454 -> unordered_set<ranges::range_value_t<_Rg>, _Hash, _Pred, _Allocator>;
1456 template<ranges::input_range _Rg,
1457 __allocator_like _Allocator>
1458 unordered_set(from_range_t, _Rg&&, unordered_set<int>::size_type,
1460 -> unordered_set<ranges::range_value_t<_Rg>,
1461 hash<ranges::range_value_t<_Rg>>,
1462 equal_to<ranges::range_value_t<_Rg>>,
1465 template<ranges::input_range _Rg,
1466 __allocator_like _Allocator>
1467 unordered_set(from_range_t, _Rg&&, _Allocator)
1468 -> unordered_set<ranges::range_value_t<_Rg>,
1469 hash<ranges::range_value_t<_Rg>>,
1470 equal_to<ranges::range_value_t<_Rg>>,
1473 template<ranges::input_range _Rg,
1474 __not_allocator_like _Hash,
1475 __allocator_like _Allocator>
1476 unordered_set(from_range_t, _Rg&&, unordered_set<int>::size_type,
1478 -> unordered_set<ranges::range_value_t<_Rg>, _Hash,
1479 equal_to<ranges::range_value_t<_Rg>>,
1482 #if __glibcxx_containers_ranges // C++ >= 23
1483 template<ranges::input_range _Rg,
1484 __not_allocator_like _Hash = hash<ranges::range_value_t<_Rg>>,
1485 __not_allocator_like _Pred = equal_to<ranges::range_value_t<_Rg>>,
1486 __allocator_like _Allocator = allocator<ranges::range_value_t<_Rg>>>
1487 unordered_multiset(from_range_t, _Rg&&,
1488 unordered_multiset<int>::size_type = {},
1489 _Hash = _Hash(), _Pred = _Pred(),
1490 _Allocator = _Allocator())
1491 -> unordered_multiset<ranges::range_value_t<_Rg>, _Hash, _Pred, _Allocator>;
1493 template<ranges::input_range _Rg,
1494 __allocator_like _Allocator>
1495 unordered_multiset(from_range_t, _Rg&&, _Allocator)
1496 -> unordered_multiset<ranges::range_value_t<_Rg>,
1497 hash<ranges::range_value_t<_Rg>>,
1498 equal_to<ranges::range_value_t<_Rg>>,
1501 template<ranges::input_range _Rg,
1502 __allocator_like _Allocator>
1503 unordered_multiset(from_range_t, _Rg&&, unordered_multiset<int>::size_type,
1505 -> unordered_multiset<ranges::range_value_t<_Rg>,
1506 hash<ranges::range_value_t<_Rg>>,
1507 equal_to<ranges::range_value_t<_Rg>>,
1510 template<ranges::input_range _Rg,
1511 __not_allocator_like _Hash,
1512 __allocator_like _Allocator>
1513 unordered_multiset(from_range_t, _Rg&&,
1514 unordered_multiset<int>::size_type,
1516 -> unordered_multiset<ranges::range_value_t<_Rg>, _Hash,
1517 equal_to<ranges::range_value_t<_Rg>>,
1524 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1526 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1527 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1528 noexcept(noexcept(__x.swap(__y)))
1531 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1533 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1534 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1535 { return __x._M_base() == __y._M_base(); }
1537 #if __cpp_impl_three_way_comparison < 201907L
1538 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1540 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1541 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1542 { return !(__x == __y); }
1545 } // namespace __debug