29#ifndef _GLIBCXX_DEBUG_UNORDERED_SET
30#define _GLIBCXX_DEBUG_UNORDERED_SET 1
33#pragma GCC system_header
36#if __cplusplus < 201103L
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;
53namespace std _GLIBCXX_VISIBILITY(default)
58 template<
typename _Value,
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;
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;
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;
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>
126 const hasher& __hf = hasher(),
127 const key_equal& __eql = key_equal(),
128 const allocator_type& __a = allocator_type())
130 __glibcxx_check_valid_constructor_range(__first, __last)),
132 __hf, __eql, __a) { }
137 :
_Base(__x._M_ref) { }
146 const allocator_type& __a)
147 :
_Base(__uset, __a) { }
150 const allocator_type& __a)
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) { }
167 const allocator_type& __a)
171 template<
typename _InputIterator>
174 const allocator_type& __a)
175 :
unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
178 template<
typename _InputIterator>
180 size_type __n,
const hasher& __hf,
181 const allocator_type& __a)
182 :
unordered_set(__first, __last, __n, __hf, key_equal(), __a)
187 const allocator_type& __a)
192 size_type __n,
const hasher& __hf,
193 const allocator_type& __a)
197#if __glibcxx_containers_ranges
198 template<__detail::__container_compatible_range<value_type> _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>
214 const allocator_type& __a)
215 :
_Base(from_range, std::forward<_Rg>(__rg), __n, __a)
218 template<__detail::__container_compatible_range<value_type> _Rg>
220 const hasher& __hf,
const allocator_type& __a)
221 :
_Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __a)
236 _Base::operator=(__l);
237 this->_M_invalidate_all();
241 using _Base::get_allocator;
244 using _Base::max_size;
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>
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>
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 };
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 };
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 };
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 };
409 size_type __bucket_count = this->bucket_count();
411 _M_check_rehashed(__bucket_count);
412 return { __it,
this };
418 size_type __bucket_count = this->bucket_count();
420 _M_check_rehashed(__bucket_count);
423 template<
typename _InputIterator>
425 insert(_InputIterator __first, _InputIterator __last)
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;
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) };
472 return { _Base::insert(__hint.
base(),
std::move(__nh)),
this };
475 template<
typename _H2,
typename _P2>
480 = _Safe::_S_uc_guard(std::__detail::_Identity{}, __source);
481 _Base::merge(__source);
484 template<
typename _H2,
typename _P2>
489 template<
typename _H2,
typename _P2>
494 = _Safe::_S_umc_guard(std::__detail::_Identity{}, __source);
495 _Base::merge(__source);
498 template<
typename _H2,
typename _P2>
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;
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>>
551 equal_range(
const _Kt& __k)
553 auto __res = _Base::equal_range(__k);
554 return { { __res.first,
this }, { __res.second,
this } };
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>>
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())
594 return { _M_erase(__it.
base()),
this };
600 __glibcxx_check_erase2(__it);
601 return _M_erase(__it);
608 return { _M_erase(__it.
base()),
this };
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();
647 this->_M_invalidate_if(
649 this->_M_invalidate_local_if(
651 {
return __it == __victim; });
657 _M_invalidate(__victim);
658 size_type __bucket_count = this->bucket_count();
660 _M_check_rehashed(__bucket_count);
664#if __cplusplus > 201402L
668 _M_invalidate(__victim);
669 return _Base::extract(__victim);
674#if __cpp_deduction_guides >= 201606
676 template<
typename _InputIterator,
681 typename _Allocator =
683 typename = _RequireInputIter<_InputIterator>,
684 typename = _RequireNotAllocatorOrIntegral<_Hash>,
685 typename = _RequireNotAllocator<_Pred>,
686 typename = _RequireAllocator<_Allocator>>
688 unordered_set<int>::size_type = {},
689 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
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>>
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); }
766 template<
typename _Value,
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;
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;
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;
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>
834 const hasher& __hf = hasher(),
835 const key_equal& __eql = key_equal(),
836 const allocator_type& __a = allocator_type())
838 __glibcxx_check_valid_constructor_range(__first, __last)),
840 __hf, __eql, __a) { }
845 :
_Base(__x._M_ref) { }
854 const allocator_type& __a)
855 :
_Base(__uset, __a) { }
858 const allocator_type& __a)
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) { }
875 const allocator_type& __a)
879 template<
typename _InputIterator>
882 const allocator_type& __a)
886 template<
typename _InputIterator>
888 size_type __n,
const hasher& __hf,
889 const allocator_type& __a)
895 const allocator_type& __a)
900 size_type __n,
const hasher& __hf,
901 const allocator_type& __a)
905#if __glibcxx_containers_ranges
906 template<__detail::__container_compatible_range<value_type> _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>
917 :
_Base(from_range, std::forward<_Rg>(__rg), __a)
920 template<__detail::__container_compatible_range<value_type> _Rg>
922 const allocator_type& __a)
923 :
_Base(from_range, std::forward<_Rg>(__rg), __n, __a)
926 template<__detail::__container_compatible_range<value_type> _Rg>
928 const hasher& __hf,
const allocator_type& __a)
929 :
_Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __a)
944 _Base::operator=(__l);
945 this->_M_invalidate_all();
949 using _Base::get_allocator;
952 using _Base::max_size;
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 };
1009 begin(size_type __b)
const
1011 __glibcxx_check_bucket_index(__b);
1012 return { _Base::begin(__b),
this };
1016 end(size_type __b)
const
1018 __glibcxx_check_bucket_index(__b);
1019 return { _Base::end(__b),
this };
1023 cbegin(size_type __b)
const
1025 __glibcxx_check_bucket_index(__b);
1026 return { _Base::cbegin(__b),
this };
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>
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 };
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 };
1117 size_type __bucket_count = this->bucket_count();
1119 _M_check_rehashed(__bucket_count);
1120 return { __it,
this };
1126 size_type __bucket_count = this->bucket_count();
1128 _M_check_rehashed(__bucket_count);
1131 template<
typename _InputIterator>
1133 insert(_InputIterator __first, _InputIterator __last)
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;
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 }; }
1175 return { _Base::insert(__hint.
base(),
std::move(__nh)),
this };
1178 template<
typename _H2,
typename _P2>
1183 = _Safe::_S_umc_guard(std::__detail::_Identity{}, __source);
1184 _Base::merge(__source);
1187 template<
typename _H2,
typename _P2>
1190 { merge(__source); }
1192 template<
typename _H2,
typename _P2>
1197 = _Safe::_S_uc_guard(std::__detail::_Identity{}, __source);
1198 _Base::merge(__source);
1201 template<
typename _H2,
typename _P2>
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;
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>>
1254 equal_range(
const _Kt& __k)
1256 auto __res = _Base::equal_range(__k);
1257 return { { __res.first,
this }, { __res.second,
this } };
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>>
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);
1299 return { _M_erase(__it.
base()),
this };
1305 __glibcxx_check_erase2(__it);
1306 return _M_erase(__it);
1313 return { _M_erase(__it.
base()),
this };
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();
1348 this->_M_invalidate_if(
1350 this->_M_invalidate_local_if(
1352 {
return __it == __victim; });
1358 _M_invalidate(__victim);
1359 size_type __bucket_count = this->bucket_count();
1361 _M_check_rehashed(__bucket_count);
1365#if __cplusplus > 201402L
1369 _M_invalidate(__victim);
1370 return _Base::extract(__victim);
1375#if __cpp_deduction_guides >= 201606
1377 template<
typename _InputIterator,
1382 typename _Allocator =
1384 typename = _RequireInputIter<_InputIterator>,
1385 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1386 typename = _RequireNotAllocator<_Pred>,
1387 typename = _RequireAllocator<_Allocator>>
1389 unordered_multiset<int>::size_type = {},
1390 _Hash = _Hash(), _Pred = _Pred(),
1391 _Allocator = _Allocator())
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>>
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
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
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); }
#define __glibcxx_check_insert(_Position)
#define __glibcxx_check_erase_range(_First, _Last)
#define __glibcxx_check_erase(_Position)
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
ISO C++ entities toplevel namespace is std.
constexpr _Iterator __base(_Iterator __it)
Primary class template hash.
The standard allocator, as per C++03 [20.4.1].
constexpr _Iterator & base() noexcept
Return the underlying iterator.
Return type of insert(node_handle&&) on unique maps/sets.
One of the comparison functors.
Struct holding two objects of arbitrary type.
_T2 second
The second member.
Traits class for iterators.
A standard container composed of equivalent keys (possibly containing multiple of each key value) in ...
_Hashtable::size_type size_type
Iterator-related typedefs.
A standard container composed of unique keys (containing at most one of each key value) in which the ...
_Hashtable::size_type size_type
Iterator-related typedefs.
Safe class dealing with some allocator dependent operations.
Base class for constructing a safe unordered container type that tracks iterators that reference it.
Class std::unordered_set with safety/checking/debug instrumentation.
Class std::unordered_multiset with safety/checking/debug instrumentation.