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())
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)
358 __glibcxx_check_valid_range(__first, __last);
359 size_type __bucket_count = this->bucket_count();
362 _M_check_rehashed(__bucket_count);
366 find(
const key_type& __key)
367 {
return iterator(_Base::find(__key),
this); }
370 find(
const key_type& __key)
const
374 equal_range(
const key_type& __key)
377 = _Base::equal_range(__key);
383 equal_range(
const key_type& __key)
const
386 __res = _Base::equal_range(__key);
392 erase(
const key_type& __key)
395 _Base_iterator __victim(_Base::find(__key));
396 if (__victim != _Base::end())
399 [__victim](_Base_const_iterator __it)
400 {
return __it == __victim; });
402 [__victim](_Base_const_local_iterator __it)
403 {
return __it._M_curr() == __victim._M_cur; });
404 size_type __bucket_count = this->bucket_count();
405 _Base::erase(__victim);
406 _M_check_rehashed(__bucket_count);
416 _Base_const_iterator __victim = __it.
base();
418 [__victim](_Base_const_iterator __it)
419 {
return __it == __victim; });
421 [__victim](_Base_const_local_iterator __it)
422 {
return __it._M_curr() == __victim._M_cur; });
423 size_type __bucket_count = this->bucket_count();
424 _Base_iterator __next = _Base::erase(__it.base());
425 _M_check_rehashed(__bucket_count);
437 for (_Base_const_iterator __tmp = __first.
base();
438 __tmp != __last.
base(); ++__tmp)
440 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
441 _M_message(__gnu_debug::__msg_valid_range)
442 ._M_iterator(__first,
"first")
443 ._M_iterator(__last,
"last"));
445 [__tmp](_Base_const_iterator __it)
446 {
return __it == __tmp; });
448 [__tmp](_Base_const_local_iterator __it)
449 {
return __it._M_curr() == __tmp._M_cur; });
451 size_type __bucket_count = this->bucket_count();
452 _Base_iterator __next = _Base::erase(__first.
base(),
454 _M_check_rehashed(__bucket_count);
459 _M_base() noexcept {
return *
this; }
462 _M_base()
const noexcept {
return *
this; }
466 _M_check_rehashed(size_type __prev_count)
468 if (__prev_count != this->bucket_count())
469 this->_M_invalidate_locals();
473 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
479 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
483 {
return __x._M_base() == __y._M_base(); }
485 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
487 operator!=(
const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
488 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
489 {
return !(__x == __y); }
493 template<
typename _Value,
499 unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
500 __gnu_debug::_Safe_unordered_container>,
501 public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
503 typedef _GLIBCXX_STD_C::unordered_multiset<
504 _Value, _Hash, _Pred, _Alloc>
_Base;
507 typedef typename _Base::const_iterator _Base_const_iterator;
508 typedef typename _Base::iterator _Base_iterator;
509 typedef typename _Base::const_local_iterator
510 _Base_const_local_iterator;
511 typedef typename _Base::local_iterator _Base_local_iterator;
514 typedef typename _Base::size_type size_type;
515 typedef typename _Base::hasher hasher;
516 typedef typename _Base::key_equal key_equal;
517 typedef typename _Base::allocator_type allocator_type;
519 typedef typename _Base::key_type key_type;
520 typedef typename _Base::value_type value_type;
535 const hasher& __hf = hasher(),
536 const key_equal& __eql = key_equal(),
537 const allocator_type& __a = allocator_type())
538 :
_Base(__n, __hf, __eql, __a) { }
540 template<
typename _InputIterator>
543 const hasher& __hf = hasher(),
544 const key_equal& __eql = key_equal(),
545 const allocator_type& __a = allocator_type())
549 __hf, __eql, __a) { }
563 const allocator_type& __a)
564 :
_Base(__uset, __a) { }
567 const allocator_type& __a)
568 :
_Safe(std::move(__uset._M_safe()), __a),
569 _Base(std::move(__uset._M_base()), __a) { }
573 const hasher& __hf = hasher(),
574 const key_equal& __eql = key_equal(),
575 const allocator_type& __a = allocator_type())
576 :
_Base(__l, __n, __hf, __eql, __a) { }
583 const allocator_type& __a)
587 template<
typename _InputIterator>
590 const allocator_type& __a)
594 template<
typename _InputIterator>
596 size_type __n,
const hasher& __hf,
597 const allocator_type& __a)
603 const allocator_type& __a)
608 size_type __n,
const hasher& __hf,
609 const allocator_type& __a)
624 this->_M_base() = __l;
625 this->_M_invalidate_all();
631 noexcept( noexcept(declval<_Base>().
swap(__x)) )
641 this->_M_invalidate_all();
646 {
return iterator(_Base::begin(),
this); }
649 begin()
const noexcept
654 {
return iterator(_Base::end(),
this); }
661 cbegin()
const noexcept
665 cend()
const noexcept
672 __glibcxx_check_bucket_index(__b);
679 __glibcxx_check_bucket_index(__b);
684 begin(size_type __b)
const
686 __glibcxx_check_bucket_index(__b);
691 end(size_type __b)
const
693 __glibcxx_check_bucket_index(__b);
698 cbegin(size_type __b)
const
700 __glibcxx_check_bucket_index(__b);
705 cend(size_type __b)
const
707 __glibcxx_check_bucket_index(__b);
712 bucket_size(size_type __b)
const
714 __glibcxx_check_bucket_index(__b);
715 return _Base::bucket_size(__b);
719 max_load_factor()
const noexcept
720 {
return _Base::max_load_factor(); }
723 max_load_factor(
float __f)
725 __glibcxx_check_max_load_factor(__f);
726 _Base::max_load_factor(__f);
729 template<
typename... _Args>
731 emplace(_Args&&... __args)
733 size_type __bucket_count = this->bucket_count();
735 = _Base::emplace(std::forward<_Args>(__args)...);
736 _M_check_rehashed(__bucket_count);
740 template<
typename... _Args>
745 size_type __bucket_count = this->bucket_count();
746 _Base_iterator __it = _Base::emplace_hint(__hint.
base(),
747 std::forward<_Args>(__args)...);
748 _M_check_rehashed(__bucket_count);
753 insert(
const value_type& __obj)
755 size_type __bucket_count = this->bucket_count();
756 _Base_iterator __it = _Base::insert(__obj);
757 _M_check_rehashed(__bucket_count);
765 size_type __bucket_count = this->bucket_count();
766 _Base_iterator __it = _Base::insert(__hint.
base(), __obj);
767 _M_check_rehashed(__bucket_count);
772 insert(value_type&& __obj)
774 size_type __bucket_count = this->bucket_count();
775 _Base_iterator __it = _Base::insert(std::move(__obj));
776 _M_check_rehashed(__bucket_count);
784 size_type __bucket_count = this->bucket_count();
785 _Base_iterator __it = _Base::insert(__hint.
base(), std::move(__obj));
786 _M_check_rehashed(__bucket_count);
793 size_type __bucket_count = this->bucket_count();
795 _M_check_rehashed(__bucket_count);
798 template<
typename _InputIterator>
800 insert(_InputIterator __first, _InputIterator __last)
802 __glibcxx_check_valid_range(__first, __last);
803 size_type __bucket_count = this->bucket_count();
806 _M_check_rehashed(__bucket_count);
810 find(
const key_type& __key)
811 {
return iterator(_Base::find(__key),
this); }
814 find(
const key_type& __key)
const
818 equal_range(
const key_type& __key)
821 = _Base::equal_range(__key);
827 equal_range(
const key_type& __key)
const
830 __res = _Base::equal_range(__key);
836 erase(
const key_type& __key)
840 _Base::equal_range(__key);
841 for (_Base_iterator __victim = __pair.
first; __victim != __pair.
second;)
844 {
return __it == __victim; });
846 [__victim](_Base_const_local_iterator __it)
847 {
return __it._M_curr() == __victim._M_cur; });
848 _Base::erase(__victim++);
858 _Base_const_iterator __victim = __it.
base();
860 {
return __it == __victim; });
862 [__victim](_Base_const_local_iterator __it)
863 {
return __it._M_curr() == __victim._M_cur; });
864 return iterator(_Base::erase(__it.base()),
this);
875 for (_Base_const_iterator __tmp = __first.
base();
876 __tmp != __last.
base(); ++__tmp)
878 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
879 _M_message(__gnu_debug::__msg_valid_range)
880 ._M_iterator(__first,
"first")
881 ._M_iterator(__last,
"last"));
883 {
return __it == __tmp; });
885 [__tmp](_Base_const_local_iterator __it)
886 {
return __it._M_curr() == __tmp._M_cur; });
889 __last.
base()),
this);
893 _M_base() noexcept {
return *
this; }
896 _M_base()
const noexcept {
return *
this; }
900 _M_check_rehashed(size_type __prev_count)
902 if (__prev_count != this->bucket_count())
903 this->_M_invalidate_locals();
907 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
913 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
917 {
return __x._M_base() == __y._M_base(); }
919 template<
typename _Value,
typename _Hash,
typename _Pred,
typename _Alloc>
921 operator!=(
const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
922 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
923 {
return !(__x == __y); }
_T1 first
second_type is the second bound type
void _M_invalidate_local_if(_Predicate __pred)
Primary class template hash.
A standard container composed of unique keys (containing at most one of each key value) in which the ...
_Iterator & base() noexcept
Return the underlying iterator.
void _M_invalidate_if(_Predicate __pred)
#define __glibcxx_check_erase_range(_First, _Last)
Struct holding two objects of arbitrary type.
Class std::unordered_set with safety/checking/debug instrumentation.
Base class for constructing a safe unordered container type that tracks iterators that reference it...
#define __glibcxx_check_erase(_Position)
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.
A standard container composed of equivalent keys (possibly containing multiple of each key value) in ...
One of the comparison functors.
Safe class dealing with some allocator dependent operations.
_T2 second
first is a copy of the first object
#define __glibcxx_check_insert(_Position)
Class std::unordered_multiset with safety/checking/debug instrumentation.
Base class that supports tracking of iterators that reference a sequence.
void swap(basic_filebuf< _CharT, _Traits > &__x, basic_filebuf< _CharT, _Traits > &__y)
Swap specialization for filebufs.
_Siter_base< _Iterator >::iterator_type __base(_Iterator __it)
The standard allocator, as per [20.4].