29 #ifndef _GLIBCXX_DEBUG_UNORDERED_SET
30 #define _GLIBCXX_DEBUG_UNORDERED_SET 1
32 #pragma GCC system_header
34 #if __cplusplus < 201103L
44 namespace std _GLIBCXX_VISIBILITY(default)
49 template<
typename _Value,
55 unordered_set<_Value, _Hash, _Pred, _Alloc>, _Alloc,
56 __gnu_debug::_Safe_unordered_container>,
57 public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc>
59 typedef _GLIBCXX_STD_C::unordered_set<
60 _Value, _Hash, _Pred, _Alloc>
_Base;
64 typedef typename _Base::const_iterator _Base_const_iterator;
65 typedef typename _Base::iterator _Base_iterator;
66 typedef typename _Base::const_local_iterator _Base_const_local_iterator;
67 typedef typename _Base::local_iterator _Base_local_iterator;
70 typedef typename _Base::size_type size_type;
71 typedef typename _Base::hasher hasher;
72 typedef typename _Base::key_equal key_equal;
73 typedef typename _Base::allocator_type allocator_type;
75 typedef typename _Base::key_type key_type;
76 typedef typename _Base::value_type value_type;
91 const hasher& __hf = hasher(),
92 const key_equal& __eql = key_equal(),
93 const allocator_type& __a = allocator_type())
94 :
_Base(__n, __hf, __eql, __a) { }
96 template<
typename _InputIterator>
99 const hasher& __hf = hasher(),
100 const key_equal& __eql = key_equal(),
101 const allocator_type& __a = allocator_type())
102 :
_Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
104 __gnu_debug::__base(__last), __n,
105 __hf, __eql, __a) { }
119 const allocator_type& __a)
120 :
_Base(__uset, __a) { }
123 const allocator_type& __a)
124 :
_Safe(std::move(__uset._M_safe()), __a),
125 _Base(std::move(__uset._M_base()), __a) { }
129 const hasher& __hf = hasher(),
130 const key_equal& __eql = key_equal(),
131 const allocator_type& __a = allocator_type())
132 :
_Base(__l, __n, __hf, __eql, __a) { }
139 const allocator_type& __a)
143 template<
typename _InputIterator>
146 const allocator_type& __a)
147 :
unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
150 template<
typename _InputIterator>
152 size_type __n,
const hasher& __hf,
153 const allocator_type& __a)
154 :
unordered_set(__first, __last, __n, __hf, key_equal(), __a)
159 const allocator_type& __a)
164 size_type __n,
const hasher& __hf,
165 const allocator_type& __a)
181 this->_M_invalidate_all();
187 noexcept( noexcept(declval<_Base&>().swap(__x)) )
197 this->_M_invalidate_all();
202 {
return iterator(_Base::begin(),
this); }
205 begin()
const noexcept
210 {
return iterator(_Base::end(),
this); }
217 cbegin()
const noexcept
221 cend()
const noexcept
228 __glibcxx_check_bucket_index(__b);
235 __glibcxx_check_bucket_index(__b);
240 begin(size_type __b)
const
242 __glibcxx_check_bucket_index(__b);
247 end(size_type __b)
const
249 __glibcxx_check_bucket_index(__b);
254 cbegin(size_type __b)
const
256 __glibcxx_check_bucket_index(__b);
261 cend(size_type __b)
const
263 __glibcxx_check_bucket_index(__b);
268 bucket_size(size_type __b)
const
270 __glibcxx_check_bucket_index(__b);
271 return _Base::bucket_size(__b);
275 max_load_factor()
const noexcept
276 {
return _Base::max_load_factor(); }
279 max_load_factor(
float __f)
281 __glibcxx_check_max_load_factor(__f);
282 _Base::max_load_factor(__f);
285 template<
typename... _Args>
287 emplace(_Args&&... __args)
289 size_type __bucket_count = this->bucket_count();
291 = _Base::emplace(std::forward<_Args>(__args)...);
292 _M_check_rehashed(__bucket_count);
296 template<
typename... _Args>
301 size_type __bucket_count = this->bucket_count();
302 _Base_iterator __it = _Base::emplace_hint(__hint.
base(),
303 std::forward<_Args>(__args)...);
304 _M_check_rehashed(__bucket_count);
309 insert(
const value_type& __obj)
311 size_type __bucket_count = this->bucket_count();
313 = _Base::insert(__obj);
314 _M_check_rehashed(__bucket_count);
322 size_type __bucket_count = this->bucket_count();
323 _Base_iterator __it = _Base::insert(__hint.
base(), __obj);
324 _M_check_rehashed(__bucket_count);
329 insert(value_type&& __obj)
331 size_type __bucket_count = this->bucket_count();
333 = _Base::insert(std::move(__obj));
334 _M_check_rehashed(__bucket_count);
342 size_type __bucket_count = this->bucket_count();
343 _Base_iterator __it = _Base::insert(__hint.
base(), std::move(__obj));
344 _M_check_rehashed(__bucket_count);
351 size_type __bucket_count = this->bucket_count();
353 _M_check_rehashed(__bucket_count);
356 template<
typename _InputIterator>
358 insert(_InputIterator __first, _InputIterator __last)
361 __glibcxx_check_valid_range2(__first, __last, __dist);
362 size_type __bucket_count = this->bucket_count();
364 if (__dist.
second >= __gnu_debug::__dp_sign)
365 _Base::insert(__gnu_debug::__unsafe(__first),
366 __gnu_debug::__unsafe(__last));
368 _Base::insert(__first, __last);
370 _M_check_rehashed(__bucket_count);
373 #if __cplusplus > 201402L
374 using node_type =
typename _Base::node_type;
375 using insert_return_type = _Node_insert_return<iterator, node_type>;
381 _Base_const_iterator __victim = __position.
base();
383 [__victim](_Base_const_iterator __it) {
return __it == __victim; }
386 [__victim](_Base_const_local_iterator __it) {
387 return __it._M_curr() == __victim._M_cur;
389 return _Base::extract(__position.
base());
393 extract(
const key_type& __key)
395 const auto __position = find(__key);
396 if (__position != end())
397 return extract(__position);
402 insert(node_type&& __nh)
404 auto __ret = _Base::insert(std::move(__nh));
406 return { __pos, __ret.inserted, std::move(__ret.node) };
413 return iterator(_Base::insert(__hint.
base(), std::move(__nh)),
this);
420 find(
const key_type& __key)
421 {
return iterator(_Base::find(__key),
this); }
424 find(
const key_type& __key)
const
428 equal_range(
const key_type& __key)
431 = _Base::equal_range(__key);
437 equal_range(
const key_type& __key)
const
440 __res = _Base::equal_range(__key);
446 erase(
const key_type& __key)
449 _Base_iterator __victim(_Base::find(__key));
450 if (__victim != _Base::end())
453 [__victim](_Base_const_iterator __it)
454 {
return __it == __victim; });
456 [__victim](_Base_const_local_iterator __it)
457 {
return __it._M_curr() == __victim._M_cur; });
458 size_type __bucket_count = this->bucket_count();
459 _Base::erase(__victim);
460 _M_check_rehashed(__bucket_count);
470 _Base_const_iterator __victim = __it.
base();
472 [__victim](_Base_const_iterator __it)
473 {
return __it == __victim; });
475 [__victim](_Base_const_local_iterator __it)
476 {
return __it._M_curr() == __victim._M_cur; });
477 size_type __bucket_count = this->bucket_count();
478 _Base_iterator __next = _Base::erase(__it.base());
479 _M_check_rehashed(__bucket_count);
491 for (_Base_const_iterator __tmp = __first.
base();
492 __tmp != __last.
base(); ++__tmp)
494 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
495 _M_message(__gnu_debug::__msg_valid_range)
496 ._M_iterator(__first,
"first")
497 ._M_iterator(__last,
"last"));
499 [__tmp](_Base_const_iterator __it)
500 {
return __it == __tmp; });
502 [__tmp](_Base_const_local_iterator __it)
503 {
return __it._M_curr() == __tmp._M_cur; });
505 size_type __bucket_count = this->bucket_count();
506 _Base_iterator __next = _Base::erase(__first.
base(),
508 _M_check_rehashed(__bucket_count);
513 _M_base() noexcept {
return *
this; }
516 _M_base()
const noexcept {
return *
this; }
520 _M_check_rehashed(size_type __prev_count)
522 if (__prev_count != this->bucket_count())
523 this->_M_invalidate_locals();
527 #if __cpp_deduction_guides >= 201606
529 template<
typename _InputIterator,
534 typename _Allocator =
536 typename = _RequireInputIter<_InputIterator>,
537 typename = _RequireAllocator<_Allocator>>
539 unordered_set<int>::size_type = {},
540 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
541 ->
unordered_set<
typename iterator_traits<_InputIterator>::value_type,
542 _Hash, _Pred, _Allocator>;
544 template<
typename _Tp,
typename _Hash = hash<_Tp>,
545 typename _Pred = equal_to<_Tp>,
546 typename _Allocator = allocator<_Tp>,
547 typename = _RequireAllocator<_Allocator>>
550 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
551 -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
553 template<
typename _InputIterator,
typename _Allocator,
554 typename = _RequireInputIter<_InputIterator>,
555 typename = _RequireAllocator<_Allocator>>
556 unordered_set(_InputIterator, _InputIterator,
557 unordered_set<int>::size_type, _Allocator)
558 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
560 typename iterator_traits<_InputIterator>::value_type>,
562 typename iterator_traits<_InputIterator>::value_type>,
565 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
566 typename = _RequireInputIter<_InputIterator>,
567 typename = _RequireAllocator<_Allocator>>
568 unordered_set(_InputIterator, _InputIterator,
569 unordered_set<int>::size_type,
571 -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
574 typename iterator_traits<_InputIterator>::value_type>,
577 template<
typename _Tp,
typename _Allocator,
578 typename = _RequireAllocator<_Allocator>>
579 unordered_set(initializer_list<_Tp>,
580 unordered_set<int>::size_type, _Allocator)
581 -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
583 template<
typename _Tp,
typename _Hash,
typename _Allocator,
584 typename = _RequireAllocator<_Allocator>>
585 unordered_set(initializer_list<_Tp>,
586 unordered_set<int>::size_type, _Hash, _Allocator)
587 -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
591 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
593 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
594 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
595 noexcept(noexcept(__x.swap(__y)))
598 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
600 operator==(
const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
601 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
602 {
return __x._M_base() == __y._M_base(); }
604 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
606 operator!=(
const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
607 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
608 {
return !(__x == __y); }
612 template<
typename _Value,
618 unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
619 __gnu_debug::_Safe_unordered_container>,
620 public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
622 typedef _GLIBCXX_STD_C::unordered_multiset<
623 _Value, _Hash, _Pred, _Alloc>
_Base;
626 typedef typename _Base::const_iterator _Base_const_iterator;
627 typedef typename _Base::iterator _Base_iterator;
628 typedef typename _Base::const_local_iterator
629 _Base_const_local_iterator;
630 typedef typename _Base::local_iterator _Base_local_iterator;
633 typedef typename _Base::size_type size_type;
634 typedef typename _Base::hasher hasher;
635 typedef typename _Base::key_equal key_equal;
636 typedef typename _Base::allocator_type allocator_type;
638 typedef typename _Base::key_type key_type;
639 typedef typename _Base::value_type value_type;
654 const hasher& __hf = hasher(),
655 const key_equal& __eql = key_equal(),
656 const allocator_type& __a = allocator_type())
657 :
_Base(__n, __hf, __eql, __a) { }
659 template<
typename _InputIterator>
662 const hasher& __hf = hasher(),
663 const key_equal& __eql = key_equal(),
664 const allocator_type& __a = allocator_type())
665 :
_Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
667 __gnu_debug::__base(__last), __n,
668 __hf, __eql, __a) { }
682 const allocator_type& __a)
683 :
_Base(__uset, __a) { }
686 const allocator_type& __a)
687 :
_Safe(std::move(__uset._M_safe()), __a),
688 _Base(std::move(__uset._M_base()), __a) { }
692 const hasher& __hf = hasher(),
693 const key_equal& __eql = key_equal(),
694 const allocator_type& __a = allocator_type())
695 :
_Base(__l, __n, __hf, __eql, __a) { }
702 const allocator_type& __a)
706 template<
typename _InputIterator>
709 const allocator_type& __a)
713 template<
typename _InputIterator>
715 size_type __n,
const hasher& __hf,
716 const allocator_type& __a)
722 const allocator_type& __a)
727 size_type __n,
const hasher& __hf,
728 const allocator_type& __a)
743 this->_M_base() = __l;
744 this->_M_invalidate_all();
750 noexcept( noexcept(declval<_Base&>().swap(__x)) )
760 this->_M_invalidate_all();
765 {
return iterator(_Base::begin(),
this); }
768 begin()
const noexcept
773 {
return iterator(_Base::end(),
this); }
780 cbegin()
const noexcept
784 cend()
const noexcept
791 __glibcxx_check_bucket_index(__b);
798 __glibcxx_check_bucket_index(__b);
803 begin(size_type __b)
const
805 __glibcxx_check_bucket_index(__b);
810 end(size_type __b)
const
812 __glibcxx_check_bucket_index(__b);
817 cbegin(size_type __b)
const
819 __glibcxx_check_bucket_index(__b);
824 cend(size_type __b)
const
826 __glibcxx_check_bucket_index(__b);
831 bucket_size(size_type __b)
const
833 __glibcxx_check_bucket_index(__b);
834 return _Base::bucket_size(__b);
838 max_load_factor()
const noexcept
839 {
return _Base::max_load_factor(); }
842 max_load_factor(
float __f)
844 __glibcxx_check_max_load_factor(__f);
845 _Base::max_load_factor(__f);
848 template<
typename... _Args>
850 emplace(_Args&&... __args)
852 size_type __bucket_count = this->bucket_count();
854 = _Base::emplace(std::forward<_Args>(__args)...);
855 _M_check_rehashed(__bucket_count);
859 template<
typename... _Args>
864 size_type __bucket_count = this->bucket_count();
865 _Base_iterator __it = _Base::emplace_hint(__hint.
base(),
866 std::forward<_Args>(__args)...);
867 _M_check_rehashed(__bucket_count);
872 insert(
const value_type& __obj)
874 size_type __bucket_count = this->bucket_count();
875 _Base_iterator __it = _Base::insert(__obj);
876 _M_check_rehashed(__bucket_count);
884 size_type __bucket_count = this->bucket_count();
885 _Base_iterator __it = _Base::insert(__hint.
base(), __obj);
886 _M_check_rehashed(__bucket_count);
891 insert(value_type&& __obj)
893 size_type __bucket_count = this->bucket_count();
894 _Base_iterator __it = _Base::insert(std::move(__obj));
895 _M_check_rehashed(__bucket_count);
903 size_type __bucket_count = this->bucket_count();
904 _Base_iterator __it = _Base::insert(__hint.
base(), std::move(__obj));
905 _M_check_rehashed(__bucket_count);
912 size_type __bucket_count = this->bucket_count();
914 _M_check_rehashed(__bucket_count);
917 template<
typename _InputIterator>
919 insert(_InputIterator __first, _InputIterator __last)
922 __glibcxx_check_valid_range2(__first, __last, __dist);
923 size_type __bucket_count = this->bucket_count();
925 if (__dist.
second >= __gnu_debug::__dp_sign)
926 _Base::insert(__gnu_debug::__unsafe(__first),
927 __gnu_debug::__unsafe(__last));
929 _Base::insert(__first, __last);
931 _M_check_rehashed(__bucket_count);
934 #if __cplusplus > 201402L
935 using node_type =
typename _Base::node_type;
941 _Base_const_iterator __victim = __position.
base();
943 [__victim](_Base_const_iterator __it) {
return __it == __victim; }
946 [__victim](_Base_const_local_iterator __it) {
947 return __it._M_curr() == __victim._M_cur;
949 return _Base::extract(__position.
base());
953 extract(
const key_type& __key)
955 const auto __position = find(__key);
956 if (__position != end())
957 return extract(__position);
962 insert(node_type&& __nh)
963 {
return iterator(_Base::insert(std::move(__nh)),
this); }
969 return iterator(_Base::insert(__hint.
base(), std::move(__nh)),
this);
976 find(
const key_type& __key)
977 {
return iterator(_Base::find(__key),
this); }
980 find(
const key_type& __key)
const
984 equal_range(
const key_type& __key)
987 = _Base::equal_range(__key);
993 equal_range(
const key_type& __key)
const
996 __res = _Base::equal_range(__key);
1002 erase(
const key_type& __key)
1006 _Base::equal_range(__key);
1007 for (_Base_iterator __victim = __pair.
first; __victim != __pair.
second;)
1010 {
return __it == __victim; });
1012 [__victim](_Base_const_local_iterator __it)
1013 {
return __it._M_curr() == __victim._M_cur; });
1014 _Base::erase(__victim++);
1024 _Base_const_iterator __victim = __it.
base();
1026 {
return __it == __victim; });
1028 [__victim](_Base_const_local_iterator __it)
1029 {
return __it._M_curr() == __victim._M_cur; });
1030 return iterator(_Base::erase(__it.base()),
this);
1041 for (_Base_const_iterator __tmp = __first.
base();
1042 __tmp != __last.
base(); ++__tmp)
1044 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
1045 _M_message(__gnu_debug::__msg_valid_range)
1046 ._M_iterator(__first,
"first")
1047 ._M_iterator(__last,
"last"));
1049 {
return __it == __tmp; });
1051 [__tmp](_Base_const_local_iterator __it)
1052 {
return __it._M_curr() == __tmp._M_cur; });
1055 __last.
base()),
this);
1059 _M_base() noexcept {
return *
this; }
1062 _M_base()
const noexcept {
return *
this; }
1066 _M_check_rehashed(size_type __prev_count)
1068 if (__prev_count != this->bucket_count())
1069 this->_M_invalidate_locals();
1073 #if __cpp_deduction_guides >= 201606
1075 template<
typename _InputIterator,
1080 typename _Allocator =
1082 typename = _RequireInputIter<_InputIterator>,
1083 typename = _RequireAllocator<_Allocator>>
1085 unordered_multiset<int>::size_type = {},
1086 _Hash = _Hash(), _Pred = _Pred(),
1087 _Allocator = _Allocator())
1089 _Hash, _Pred, _Allocator>;
1091 template<
typename _Tp,
typename _Hash = hash<_Tp>,
1092 typename _Pred = equal_to<_Tp>,
1093 typename _Allocator = allocator<_Tp>,
1094 typename = _RequireAllocator<_Allocator>>
1097 _Hash = _Hash(), _Pred = _Pred(),
1098 _Allocator = _Allocator())
1099 -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1101 template<
typename _InputIterator,
typename _Allocator,
1102 typename = _RequireInputIter<_InputIterator>,
1103 typename = _RequireAllocator<_Allocator>>
1104 unordered_multiset(_InputIterator, _InputIterator,
1105 unordered_multiset<int>::size_type, _Allocator)
1106 -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1108 iterator_traits<_InputIterator>::value_type>,
1110 iterator_traits<_InputIterator>::value_type>,
1113 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
1114 typename = _RequireInputIter<_InputIterator>,
1115 typename = _RequireAllocator<_Allocator>>
1116 unordered_multiset(_InputIterator, _InputIterator,
1117 unordered_multiset<int>::size_type,
1119 -> unordered_multiset<
typename
1120 iterator_traits<_InputIterator>::value_type,
1124 iterator_traits<_InputIterator>::value_type>,
1127 template<
typename _Tp,
typename _Allocator,
1128 typename = _RequireAllocator<_Allocator>>
1129 unordered_multiset(initializer_list<_Tp>,
1130 unordered_multiset<int>::size_type, _Allocator)
1131 -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1133 template<
typename _Tp,
typename _Hash,
typename _Allocator,
1134 typename = _RequireAllocator<_Allocator>>
1135 unordered_multiset(initializer_list<_Tp>,
1136 unordered_multiset<int>::size_type, _Hash, _Allocator)
1137 -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1141 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
1143 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1144 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1145 noexcept(noexcept(__x.swap(__y)))
1148 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
1150 operator==(
const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1151 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1152 {
return __x._M_base() == __y._M_base(); }
1154 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
1156 operator!=(
const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1157 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1158 {
return !(__x == __y); }
Class std::unordered_multiset with safety/checking/debug instrumentation.
Safe class dealing with some allocator dependent operations.
_Iterator & base() noexcept
Return the underlying iterator.
Base class that supports tracking of iterators that reference a sequence.
A standard container composed of unique keys (containing at most one of each key value) in which the ...
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
_Hashtable::size_type size_type
Iterator-related typedefs.
Struct holding two objects of arbitrary type.
The standard allocator, as per [20.4].
A standard container composed of equivalent keys (possibly containing multiple of each key value) in ...
void _M_invalidate_local_if(_Predicate __pred)
_Hashtable::size_type size_type
Iterator-related typedefs.
_T2 second
first is a copy of the first object
Class std::unordered_set with safety/checking/debug instrumentation.
Primary class template hash.
void _M_invalidate_if(_Predicate __pred)
#define __glibcxx_check_erase_range(_First, _Last)
#define __glibcxx_check_insert(_Position)
One of the comparison functors.
#define __glibcxx_check_erase(_Position)
Base class for constructing a safe unordered container type that tracks iterators that reference it...
_T1 first
second_type is the second bound type