29 #ifndef _GLIBCXX_DEBUG_UNORDERED_SET
30 #define _GLIBCXX_DEBUG_UNORDERED_SET 1
32 #if __cplusplus < 201103L
42 namespace std _GLIBCXX_VISIBILITY(default)
47 template<
typename _Value,
53 unordered_set<_Value, _Hash, _Pred, _Alloc>, _Alloc,
54 __gnu_debug::_Safe_unordered_container>,
55 public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc>
57 typedef _GLIBCXX_STD_C::unordered_set<
58 _Value, _Hash, _Pred, _Alloc>
_Base;
62 typedef typename _Base::const_iterator _Base_const_iterator;
63 typedef typename _Base::iterator _Base_iterator;
64 typedef typename _Base::const_local_iterator _Base_const_local_iterator;
65 typedef typename _Base::local_iterator _Base_local_iterator;
68 typedef typename _Base::size_type size_type;
69 typedef typename _Base::hasher hasher;
70 typedef typename _Base::key_equal key_equal;
71 typedef typename _Base::allocator_type allocator_type;
73 typedef typename _Base::key_type key_type;
74 typedef typename _Base::value_type value_type;
89 const hasher& __hf = hasher(),
90 const key_equal& __eql = key_equal(),
91 const allocator_type& __a = allocator_type())
92 :
_Base(__n, __hf, __eql, __a) { }
94 template<
typename _InputIterator>
97 const hasher& __hf = hasher(),
98 const key_equal& __eql = key_equal(),
99 const allocator_type& __a = allocator_type())
100 :
_Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
102 __gnu_debug::__base(__last), __n,
103 __hf, __eql, __a) { }
117 const allocator_type& __a)
118 :
_Base(__uset, __a) { }
121 const allocator_type& __a)
122 :
_Safe(std::move(__uset._M_safe()), __a),
123 _Base(std::move(__uset._M_base()), __a) { }
127 const hasher& __hf = hasher(),
128 const key_equal& __eql = key_equal(),
129 const allocator_type& __a = allocator_type())
130 :
_Base(__l, __n, __hf, __eql, __a) { }
137 const allocator_type& __a)
141 template<
typename _InputIterator>
144 const allocator_type& __a)
145 :
unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
148 template<
typename _InputIterator>
150 size_type __n,
const hasher& __hf,
151 const allocator_type& __a)
152 :
unordered_set(__first, __last, __n, __hf, key_equal(), __a)
157 const allocator_type& __a)
162 size_type __n,
const hasher& __hf,
163 const allocator_type& __a)
179 this->_M_invalidate_all();
185 noexcept( noexcept(declval<_Base&>().swap(__x)) )
195 this->_M_invalidate_all();
200 {
return iterator(_Base::begin(),
this); }
203 begin()
const noexcept
208 {
return iterator(_Base::end(),
this); }
215 cbegin()
const noexcept
219 cend()
const noexcept
226 __glibcxx_check_bucket_index(__b);
233 __glibcxx_check_bucket_index(__b);
238 begin(size_type __b)
const
240 __glibcxx_check_bucket_index(__b);
245 end(size_type __b)
const
247 __glibcxx_check_bucket_index(__b);
252 cbegin(size_type __b)
const
254 __glibcxx_check_bucket_index(__b);
259 cend(size_type __b)
const
261 __glibcxx_check_bucket_index(__b);
266 bucket_size(size_type __b)
const
268 __glibcxx_check_bucket_index(__b);
269 return _Base::bucket_size(__b);
273 max_load_factor()
const noexcept
274 {
return _Base::max_load_factor(); }
277 max_load_factor(
float __f)
279 __glibcxx_check_max_load_factor(__f);
280 _Base::max_load_factor(__f);
283 template<
typename... _Args>
285 emplace(_Args&&... __args)
287 size_type __bucket_count = this->bucket_count();
289 = _Base::emplace(std::forward<_Args>(__args)...);
290 _M_check_rehashed(__bucket_count);
294 template<
typename... _Args>
299 size_type __bucket_count = this->bucket_count();
300 _Base_iterator __it = _Base::emplace_hint(__hint.
base(),
301 std::forward<_Args>(__args)...);
302 _M_check_rehashed(__bucket_count);
307 insert(
const value_type& __obj)
309 size_type __bucket_count = this->bucket_count();
311 = _Base::insert(__obj);
312 _M_check_rehashed(__bucket_count);
320 size_type __bucket_count = this->bucket_count();
321 _Base_iterator __it = _Base::insert(__hint.
base(), __obj);
322 _M_check_rehashed(__bucket_count);
327 insert(value_type&& __obj)
329 size_type __bucket_count = this->bucket_count();
331 = _Base::insert(std::move(__obj));
332 _M_check_rehashed(__bucket_count);
340 size_type __bucket_count = this->bucket_count();
341 _Base_iterator __it = _Base::insert(__hint.
base(), std::move(__obj));
342 _M_check_rehashed(__bucket_count);
349 size_type __bucket_count = this->bucket_count();
351 _M_check_rehashed(__bucket_count);
354 template<
typename _InputIterator>
356 insert(_InputIterator __first, _InputIterator __last)
359 __glibcxx_check_valid_range2(__first, __last, __dist);
360 size_type __bucket_count = this->bucket_count();
362 if (__dist.
second >= __gnu_debug::__dp_sign)
363 _Base::insert(__gnu_debug::__unsafe(__first),
364 __gnu_debug::__unsafe(__last));
366 _Base::insert(__first, __last);
368 _M_check_rehashed(__bucket_count);
372 find(
const key_type& __key)
373 {
return iterator(_Base::find(__key),
this); }
376 find(
const key_type& __key)
const
380 equal_range(
const key_type& __key)
383 = _Base::equal_range(__key);
389 equal_range(
const key_type& __key)
const
392 __res = _Base::equal_range(__key);
398 erase(
const key_type& __key)
401 _Base_iterator __victim(_Base::find(__key));
402 if (__victim != _Base::end())
405 [__victim](_Base_const_iterator __it)
406 {
return __it == __victim; });
408 [__victim](_Base_const_local_iterator __it)
409 {
return __it._M_curr() == __victim._M_cur; });
410 size_type __bucket_count = this->bucket_count();
411 _Base::erase(__victim);
412 _M_check_rehashed(__bucket_count);
422 _Base_const_iterator __victim = __it.
base();
424 [__victim](_Base_const_iterator __it)
425 {
return __it == __victim; });
427 [__victim](_Base_const_local_iterator __it)
428 {
return __it._M_curr() == __victim._M_cur; });
429 size_type __bucket_count = this->bucket_count();
430 _Base_iterator __next = _Base::erase(__it.base());
431 _M_check_rehashed(__bucket_count);
443 for (_Base_const_iterator __tmp = __first.
base();
444 __tmp != __last.
base(); ++__tmp)
446 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
447 _M_message(__gnu_debug::__msg_valid_range)
448 ._M_iterator(__first,
"first")
449 ._M_iterator(__last,
"last"));
451 [__tmp](_Base_const_iterator __it)
452 {
return __it == __tmp; });
454 [__tmp](_Base_const_local_iterator __it)
455 {
return __it._M_curr() == __tmp._M_cur; });
457 size_type __bucket_count = this->bucket_count();
458 _Base_iterator __next = _Base::erase(__first.
base(),
460 _M_check_rehashed(__bucket_count);
465 _M_base() noexcept {
return *
this; }
468 _M_base()
const noexcept {
return *
this; }
472 _M_check_rehashed(size_type __prev_count)
474 if (__prev_count != this->bucket_count())
475 this->_M_invalidate_locals();
479 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
483 noexcept(noexcept(__x.swap(__y)))
486 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
490 {
return __x._M_base() == __y._M_base(); }
492 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
494 operator!=(
const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
495 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
496 {
return !(__x == __y); }
500 template<
typename _Value,
506 unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
507 __gnu_debug::_Safe_unordered_container>,
508 public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
510 typedef _GLIBCXX_STD_C::unordered_multiset<
511 _Value, _Hash, _Pred, _Alloc>
_Base;
514 typedef typename _Base::const_iterator _Base_const_iterator;
515 typedef typename _Base::iterator _Base_iterator;
516 typedef typename _Base::const_local_iterator
517 _Base_const_local_iterator;
518 typedef typename _Base::local_iterator _Base_local_iterator;
521 typedef typename _Base::size_type size_type;
522 typedef typename _Base::hasher hasher;
523 typedef typename _Base::key_equal key_equal;
524 typedef typename _Base::allocator_type allocator_type;
526 typedef typename _Base::key_type key_type;
527 typedef typename _Base::value_type value_type;
542 const hasher& __hf = hasher(),
543 const key_equal& __eql = key_equal(),
544 const allocator_type& __a = allocator_type())
545 :
_Base(__n, __hf, __eql, __a) { }
547 template<
typename _InputIterator>
550 const hasher& __hf = hasher(),
551 const key_equal& __eql = key_equal(),
552 const allocator_type& __a = allocator_type())
553 :
_Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
555 __gnu_debug::__base(__last), __n,
556 __hf, __eql, __a) { }
570 const allocator_type& __a)
571 :
_Base(__uset, __a) { }
574 const allocator_type& __a)
575 :
_Safe(std::move(__uset._M_safe()), __a),
576 _Base(std::move(__uset._M_base()), __a) { }
580 const hasher& __hf = hasher(),
581 const key_equal& __eql = key_equal(),
582 const allocator_type& __a = allocator_type())
583 :
_Base(__l, __n, __hf, __eql, __a) { }
590 const allocator_type& __a)
594 template<
typename _InputIterator>
597 const allocator_type& __a)
601 template<
typename _InputIterator>
603 size_type __n,
const hasher& __hf,
604 const allocator_type& __a)
610 const allocator_type& __a)
615 size_type __n,
const hasher& __hf,
616 const allocator_type& __a)
631 this->_M_base() = __l;
632 this->_M_invalidate_all();
638 noexcept( noexcept(declval<_Base&>().swap(__x)) )
648 this->_M_invalidate_all();
653 {
return iterator(_Base::begin(),
this); }
656 begin()
const noexcept
661 {
return iterator(_Base::end(),
this); }
668 cbegin()
const noexcept
672 cend()
const noexcept
679 __glibcxx_check_bucket_index(__b);
686 __glibcxx_check_bucket_index(__b);
691 begin(size_type __b)
const
693 __glibcxx_check_bucket_index(__b);
698 end(size_type __b)
const
700 __glibcxx_check_bucket_index(__b);
705 cbegin(size_type __b)
const
707 __glibcxx_check_bucket_index(__b);
712 cend(size_type __b)
const
714 __glibcxx_check_bucket_index(__b);
719 bucket_size(size_type __b)
const
721 __glibcxx_check_bucket_index(__b);
722 return _Base::bucket_size(__b);
726 max_load_factor()
const noexcept
727 {
return _Base::max_load_factor(); }
730 max_load_factor(
float __f)
732 __glibcxx_check_max_load_factor(__f);
733 _Base::max_load_factor(__f);
736 template<
typename... _Args>
738 emplace(_Args&&... __args)
740 size_type __bucket_count = this->bucket_count();
742 = _Base::emplace(std::forward<_Args>(__args)...);
743 _M_check_rehashed(__bucket_count);
747 template<
typename... _Args>
752 size_type __bucket_count = this->bucket_count();
753 _Base_iterator __it = _Base::emplace_hint(__hint.
base(),
754 std::forward<_Args>(__args)...);
755 _M_check_rehashed(__bucket_count);
760 insert(
const value_type& __obj)
762 size_type __bucket_count = this->bucket_count();
763 _Base_iterator __it = _Base::insert(__obj);
764 _M_check_rehashed(__bucket_count);
772 size_type __bucket_count = this->bucket_count();
773 _Base_iterator __it = _Base::insert(__hint.
base(), __obj);
774 _M_check_rehashed(__bucket_count);
779 insert(value_type&& __obj)
781 size_type __bucket_count = this->bucket_count();
782 _Base_iterator __it = _Base::insert(std::move(__obj));
783 _M_check_rehashed(__bucket_count);
791 size_type __bucket_count = this->bucket_count();
792 _Base_iterator __it = _Base::insert(__hint.
base(), std::move(__obj));
793 _M_check_rehashed(__bucket_count);
800 size_type __bucket_count = this->bucket_count();
802 _M_check_rehashed(__bucket_count);
805 template<
typename _InputIterator>
807 insert(_InputIterator __first, _InputIterator __last)
810 __glibcxx_check_valid_range2(__first, __last, __dist);
811 size_type __bucket_count = this->bucket_count();
813 if (__dist.
second >= __gnu_debug::__dp_sign)
814 _Base::insert(__gnu_debug::__unsafe(__first),
815 __gnu_debug::__unsafe(__last));
817 _Base::insert(__first, __last);
819 _M_check_rehashed(__bucket_count);
823 find(
const key_type& __key)
824 {
return iterator(_Base::find(__key),
this); }
827 find(
const key_type& __key)
const
831 equal_range(
const key_type& __key)
834 = _Base::equal_range(__key);
840 equal_range(
const key_type& __key)
const
843 __res = _Base::equal_range(__key);
849 erase(
const key_type& __key)
853 _Base::equal_range(__key);
854 for (_Base_iterator __victim = __pair.
first; __victim != __pair.
second;)
857 {
return __it == __victim; });
859 [__victim](_Base_const_local_iterator __it)
860 {
return __it._M_curr() == __victim._M_cur; });
861 _Base::erase(__victim++);
871 _Base_const_iterator __victim = __it.
base();
873 {
return __it == __victim; });
875 [__victim](_Base_const_local_iterator __it)
876 {
return __it._M_curr() == __victim._M_cur; });
877 return iterator(_Base::erase(__it.base()),
this);
888 for (_Base_const_iterator __tmp = __first.
base();
889 __tmp != __last.
base(); ++__tmp)
891 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
892 _M_message(__gnu_debug::__msg_valid_range)
893 ._M_iterator(__first,
"first")
894 ._M_iterator(__last,
"last"));
896 {
return __it == __tmp; });
898 [__tmp](_Base_const_local_iterator __it)
899 {
return __it._M_curr() == __tmp._M_cur; });
902 __last.
base()),
this);
906 _M_base() noexcept {
return *
this; }
909 _M_base()
const noexcept {
return *
this; }
913 _M_check_rehashed(size_type __prev_count)
915 if (__prev_count != this->bucket_count())
916 this->_M_invalidate_locals();
920 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
924 noexcept(noexcept(__x.
swap(__y)))
927 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
931 {
return __x._M_base() == __y._M_base(); }
933 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
935 operator!=(
const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
936 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
937 {
return !(__x == __y); }
void _M_invalidate_local_if(_Predicate __pred)
_T1 first
second_type is the second bound type
#define __glibcxx_check_erase(_Position)
#define __glibcxx_check_insert(_Position)
Struct holding two objects of arbitrary type.
A standard container composed of equivalent keys (possibly containing multiple of each key value) in ...
_Iterator & base() noexcept
Return the underlying iterator.
Class std::unordered_set with safety/checking/debug instrumentation.
void _M_invalidate_if(_Predicate __pred)
Base class for constructing a safe unordered container type that tracks iterators that reference it...
Class std::unordered_multiset with safety/checking/debug instrumentation.
Primary class template hash.
#define __glibcxx_check_erase_range(_First, _Last)
The standard allocator, as per [20.4].
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.
Safe class dealing with some allocator dependent operations.
void swap(unordered_set &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another unordered_set.
_T2 second
first is a copy of the first object
Base class that supports tracking of iterators that reference a sequence.
One of the comparison functors.
A standard container composed of unique keys (containing at most one of each key value) in which the ...