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;
376 struct insert_return_type
387 _Base_const_iterator __victim = __position.
base();
389 [__victim](_Base_const_iterator __it) {
return __it == __victim; }
392 [__victim](_Base_const_local_iterator __it) {
393 return __it._M_curr() == __victim._M_cur;
395 return _Base::extract(__position.
base());
399 extract(
const key_type& __key)
401 const auto __position = find(__key);
402 if (__position != end())
403 return extract(__position);
408 insert(node_type&& __nh)
410 auto __ret = _Base::insert(std::move(__nh));
412 return { __ret.inserted, __pos, std::move(__ret.node) };
419 return iterator(_Base::insert(__hint.
base(), std::move(__nh)),
this);
426 find(
const key_type& __key)
427 {
return iterator(_Base::find(__key),
this); }
430 find(
const key_type& __key)
const
434 equal_range(
const key_type& __key)
437 = _Base::equal_range(__key);
443 equal_range(
const key_type& __key)
const
446 __res = _Base::equal_range(__key);
452 erase(
const key_type& __key)
455 _Base_iterator __victim(_Base::find(__key));
456 if (__victim != _Base::end())
459 [__victim](_Base_const_iterator __it)
460 {
return __it == __victim; });
462 [__victim](_Base_const_local_iterator __it)
463 {
return __it._M_curr() == __victim._M_cur; });
464 size_type __bucket_count = this->bucket_count();
465 _Base::erase(__victim);
466 _M_check_rehashed(__bucket_count);
476 _Base_const_iterator __victim = __it.
base();
478 [__victim](_Base_const_iterator __it)
479 {
return __it == __victim; });
481 [__victim](_Base_const_local_iterator __it)
482 {
return __it._M_curr() == __victim._M_cur; });
483 size_type __bucket_count = this->bucket_count();
484 _Base_iterator __next = _Base::erase(__it.base());
485 _M_check_rehashed(__bucket_count);
497 for (_Base_const_iterator __tmp = __first.
base();
498 __tmp != __last.
base(); ++__tmp)
500 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
501 _M_message(__gnu_debug::__msg_valid_range)
502 ._M_iterator(__first,
"first")
503 ._M_iterator(__last,
"last"));
505 [__tmp](_Base_const_iterator __it)
506 {
return __it == __tmp; });
508 [__tmp](_Base_const_local_iterator __it)
509 {
return __it._M_curr() == __tmp._M_cur; });
511 size_type __bucket_count = this->bucket_count();
512 _Base_iterator __next = _Base::erase(__first.
base(),
514 _M_check_rehashed(__bucket_count);
519 _M_base() noexcept {
return *
this; }
522 _M_base()
const noexcept {
return *
this; }
526 _M_check_rehashed(size_type __prev_count)
528 if (__prev_count != this->bucket_count())
529 this->_M_invalidate_locals();
533 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
537 noexcept(noexcept(__x.swap(__y)))
540 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
544 {
return __x._M_base() == __y._M_base(); }
546 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
548 operator!=(
const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
549 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
550 {
return !(__x == __y); }
554 template<
typename _Value,
560 unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
561 __gnu_debug::_Safe_unordered_container>,
562 public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
564 typedef _GLIBCXX_STD_C::unordered_multiset<
565 _Value, _Hash, _Pred, _Alloc>
_Base;
568 typedef typename _Base::const_iterator _Base_const_iterator;
569 typedef typename _Base::iterator _Base_iterator;
570 typedef typename _Base::const_local_iterator
571 _Base_const_local_iterator;
572 typedef typename _Base::local_iterator _Base_local_iterator;
575 typedef typename _Base::size_type size_type;
576 typedef typename _Base::hasher hasher;
577 typedef typename _Base::key_equal key_equal;
578 typedef typename _Base::allocator_type allocator_type;
580 typedef typename _Base::key_type key_type;
581 typedef typename _Base::value_type value_type;
596 const hasher& __hf = hasher(),
597 const key_equal& __eql = key_equal(),
598 const allocator_type& __a = allocator_type())
599 :
_Base(__n, __hf, __eql, __a) { }
601 template<
typename _InputIterator>
604 const hasher& __hf = hasher(),
605 const key_equal& __eql = key_equal(),
606 const allocator_type& __a = allocator_type())
607 :
_Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
609 __gnu_debug::__base(__last), __n,
610 __hf, __eql, __a) { }
624 const allocator_type& __a)
625 :
_Base(__uset, __a) { }
628 const allocator_type& __a)
629 :
_Safe(std::move(__uset._M_safe()), __a),
630 _Base(std::move(__uset._M_base()), __a) { }
634 const hasher& __hf = hasher(),
635 const key_equal& __eql = key_equal(),
636 const allocator_type& __a = allocator_type())
637 :
_Base(__l, __n, __hf, __eql, __a) { }
644 const allocator_type& __a)
648 template<
typename _InputIterator>
651 const allocator_type& __a)
655 template<
typename _InputIterator>
657 size_type __n,
const hasher& __hf,
658 const allocator_type& __a)
664 const allocator_type& __a)
669 size_type __n,
const hasher& __hf,
670 const allocator_type& __a)
685 this->_M_base() = __l;
686 this->_M_invalidate_all();
692 noexcept( noexcept(declval<_Base&>().swap(__x)) )
702 this->_M_invalidate_all();
707 {
return iterator(_Base::begin(),
this); }
710 begin()
const noexcept
715 {
return iterator(_Base::end(),
this); }
722 cbegin()
const noexcept
726 cend()
const noexcept
733 __glibcxx_check_bucket_index(__b);
740 __glibcxx_check_bucket_index(__b);
745 begin(size_type __b)
const
747 __glibcxx_check_bucket_index(__b);
752 end(size_type __b)
const
754 __glibcxx_check_bucket_index(__b);
759 cbegin(size_type __b)
const
761 __glibcxx_check_bucket_index(__b);
766 cend(size_type __b)
const
768 __glibcxx_check_bucket_index(__b);
773 bucket_size(size_type __b)
const
775 __glibcxx_check_bucket_index(__b);
776 return _Base::bucket_size(__b);
780 max_load_factor()
const noexcept
781 {
return _Base::max_load_factor(); }
784 max_load_factor(
float __f)
786 __glibcxx_check_max_load_factor(__f);
787 _Base::max_load_factor(__f);
790 template<
typename... _Args>
792 emplace(_Args&&... __args)
794 size_type __bucket_count = this->bucket_count();
796 = _Base::emplace(std::forward<_Args>(__args)...);
797 _M_check_rehashed(__bucket_count);
801 template<
typename... _Args>
806 size_type __bucket_count = this->bucket_count();
807 _Base_iterator __it = _Base::emplace_hint(__hint.
base(),
808 std::forward<_Args>(__args)...);
809 _M_check_rehashed(__bucket_count);
814 insert(
const value_type& __obj)
816 size_type __bucket_count = this->bucket_count();
817 _Base_iterator __it = _Base::insert(__obj);
818 _M_check_rehashed(__bucket_count);
826 size_type __bucket_count = this->bucket_count();
827 _Base_iterator __it = _Base::insert(__hint.
base(), __obj);
828 _M_check_rehashed(__bucket_count);
833 insert(value_type&& __obj)
835 size_type __bucket_count = this->bucket_count();
836 _Base_iterator __it = _Base::insert(std::move(__obj));
837 _M_check_rehashed(__bucket_count);
845 size_type __bucket_count = this->bucket_count();
846 _Base_iterator __it = _Base::insert(__hint.
base(), std::move(__obj));
847 _M_check_rehashed(__bucket_count);
854 size_type __bucket_count = this->bucket_count();
856 _M_check_rehashed(__bucket_count);
859 template<
typename _InputIterator>
861 insert(_InputIterator __first, _InputIterator __last)
864 __glibcxx_check_valid_range2(__first, __last, __dist);
865 size_type __bucket_count = this->bucket_count();
867 if (__dist.
second >= __gnu_debug::__dp_sign)
868 _Base::insert(__gnu_debug::__unsafe(__first),
869 __gnu_debug::__unsafe(__last));
871 _Base::insert(__first, __last);
873 _M_check_rehashed(__bucket_count);
876 #if __cplusplus > 201402L
877 using node_type =
typename _Base::node_type;
883 _Base_const_iterator __victim = __position.
base();
885 [__victim](_Base_const_iterator __it) {
return __it == __victim; }
888 [__victim](_Base_const_local_iterator __it) {
889 return __it._M_curr() == __victim._M_cur;
891 return _Base::extract(__position.
base());
895 extract(
const key_type& __key)
897 const auto __position = find(__key);
898 if (__position != end())
899 return extract(__position);
904 insert(node_type&& __nh)
905 {
return iterator(_Base::insert(std::move(__nh)),
this); }
911 return iterator(_Base::insert(__hint.
base(), std::move(__nh)),
this);
918 find(
const key_type& __key)
919 {
return iterator(_Base::find(__key),
this); }
922 find(
const key_type& __key)
const
926 equal_range(
const key_type& __key)
929 = _Base::equal_range(__key);
935 equal_range(
const key_type& __key)
const
938 __res = _Base::equal_range(__key);
944 erase(
const key_type& __key)
948 _Base::equal_range(__key);
949 for (_Base_iterator __victim = __pair.
first; __victim != __pair.
second;)
952 {
return __it == __victim; });
954 [__victim](_Base_const_local_iterator __it)
955 {
return __it._M_curr() == __victim._M_cur; });
956 _Base::erase(__victim++);
966 _Base_const_iterator __victim = __it.
base();
968 {
return __it == __victim; });
970 [__victim](_Base_const_local_iterator __it)
971 {
return __it._M_curr() == __victim._M_cur; });
972 return iterator(_Base::erase(__it.base()),
this);
983 for (_Base_const_iterator __tmp = __first.
base();
984 __tmp != __last.
base(); ++__tmp)
986 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
987 _M_message(__gnu_debug::__msg_valid_range)
988 ._M_iterator(__first,
"first")
989 ._M_iterator(__last,
"last"));
991 {
return __it == __tmp; });
993 [__tmp](_Base_const_local_iterator __it)
994 {
return __it._M_curr() == __tmp._M_cur; });
997 __last.
base()),
this);
1001 _M_base() noexcept {
return *
this; }
1004 _M_base()
const noexcept {
return *
this; }
1008 _M_check_rehashed(size_type __prev_count)
1010 if (__prev_count != this->bucket_count())
1011 this->_M_invalidate_locals();
1015 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
1019 noexcept(noexcept(__x.swap(__y)))
1022 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
1026 {
return __x._M_base() == __y._M_base(); }
1028 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
1030 operator!=(
const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1031 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1032 {
return !(__x == __y); }
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.
_Iterator & base() noexcept
Return the underlying iterator.
Primary class template hash.
A standard container composed of unique keys (containing at most one of each key value) in which the ...
Base class for constructing a safe unordered container type that tracks iterators that reference it...
The standard allocator, as per [20.4].
#define __glibcxx_check_erase_range(_First, _Last)
One of the comparison functors.
#define __glibcxx_check_insert(_Position)
Safe class dealing with some allocator dependent operations.
Base class that supports tracking of iterators that reference a sequence.
void _M_invalidate_if(_Predicate __pred)
A standard container composed of equivalent keys (possibly containing multiple of each key value) in ...
Class std::unordered_set with safety/checking/debug instrumentation.
_T2 second
first is a copy of the first object
void _M_invalidate_local_if(_Predicate __pred)
Struct holding two objects of arbitrary type.
_T1 first
second_type is the second bound type
Class std::unordered_multiset with safety/checking/debug instrumentation.
#define __glibcxx_check_erase(_Position)