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>
53namespace std _GLIBCXX_VISIBILITY(default)
58 template<
typename _Value,
59 typename _Hash = std::hash<_Value>,
60 typename _Pred = std::equal_to<_Value>,
61 typename _Alloc = std::allocator<_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;
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;
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;
106 _Base_iterator, unordered_set> iterator;
108 _Base_const_iterator, unordered_set> const_iterator;
110 _Base_local_iterator, unordered_set> 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())
130 __glibcxx_check_valid_constructor_range(__first, __last)),
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)) )
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)
187 const allocator_type& __a)
188 : unordered_set(__l, __n, hasher(), key_equal(), __a)
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
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())
207 template<__detail::__container_compatible_range<value_type> _Rg>
208 unordered_set(from_range_t, _Rg&& __rg,
const allocator_type& __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)
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)
225 ~unordered_set() =
default;
228 operator=(
const unordered_set&) =
default;
231 operator=(unordered_set&&) =
default;
236 _Base::operator=(__l);
237 this->_M_invalidate_all();
241 using _Base::get_allocator;
244 using _Base::max_size;
247 swap(unordered_set& __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();
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)
370 size_type __bucket_count = this->bucket_count();
371 auto __it = _Base::emplace_hint(__hint.
base(),
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 };
387 insert(const_iterator __hint,
const value_type& __obj)
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 };
406 insert(const_iterator __hint, value_type&& __obj)
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)
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)
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)
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>
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())
591 erase(const_iterator __it)
594 return { _M_erase(__it.
base()),
this };
598 erase(_Base_const_iterator __it)
600 __glibcxx_check_erase2(__it);
601 return _M_erase(__it);
608 return { _M_erase(__it.
base()),
this };
612 erase(const_iterator __first, const_iterator __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,
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>
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>
762 {
return !(__x == __y); }
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
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;
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;
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;
814 _Base_iterator, unordered_multiset> iterator;
816 _Base_const_iterator, unordered_multiset> const_iterator;
818 _Base_local_iterator, unordered_multiset> 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())
838 __glibcxx_check_valid_constructor_range(__first, __last)),
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)) )
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)
895 const allocator_type& __a)
896 : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
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
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())
915 template<__detail::__container_compatible_range<value_type> _Rg>
916 unordered_multiset(from_range_t, _Rg&& __rg,
const allocator_type& __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)
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)
933 ~unordered_multiset() =
default;
936 operator=(
const unordered_multiset&) =
default;
939 operator=(unordered_multiset&&) =
default;
944 _Base::operator=(__l);
945 this->_M_invalidate_all();
949 using _Base::get_allocator;
952 using _Base::max_size;
955 swap(unordered_multiset& __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();
1069 _M_check_rehashed(__bucket_count);
1070 return { __it,
this };
1073 template<
typename... _Args>
1075 emplace_hint(const_iterator __hint, _Args&&... __args)
1078 size_type __bucket_count = this->bucket_count();
1079 auto __it = _Base::emplace_hint(__hint.
base(),
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)
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)
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)
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)
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)
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>
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);
1296 erase(const_iterator __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)
1313 return { _M_erase(__it.
base()),
this };
1317 erase(const_iterator __first, const_iterator __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,
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,
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>
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,
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>>>
1488 unordered_multiset<int>::size_type = {},
1489 _Hash = _Hash(), _Pred = _Pred(),
1490 _Allocator = _Allocator())
1493 template<ranges::input_range _Rg,
1494 __allocator_like _Allocator>
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>
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>
1514 unordered_multiset<int>::size_type,
1517 equal_to<ranges::range_value_t<_Rg>>,
1524 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
1528 noexcept(
noexcept(__x.swap(__y)))
1531 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
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>
1542 {
return !(__x == __y); }
#define __glibcxx_check_insert(_Position)
#define __glibcxx_check_erase_range(_First, _Last)
#define __glibcxx_check_erase(_Position)
auto declval() noexcept -> decltype(__declval< _Tp >(0))
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
ISO C++ entities toplevel namespace is std.
constexpr _Iterator __base(_Iterator __it)
GNU debug code, replaces standard behavior with debug behavior.
Primary class template hash.
The standard allocator, as per C++03 [20.4.1].
constexpr _Iterator & base() noexcept
Return the underlying iterator.
One of the comparison functors.
Struct holding two objects of arbitrary type.
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.