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;
77 _Base_iterator, unordered_set>
iterator;
85 unordered_set() =
default;
88 unordered_set(size_type __n,
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>
95 unordered_set(_InputIterator __first, _InputIterator __last,
97 const hasher& __hf = hasher(),
98 const key_equal& __eql = key_equal(),
99 const allocator_type& __a = allocator_type())
103 __hf, __eql, __a) { }
105 unordered_set(
const unordered_set&) =
default;
107 unordered_set(
const _Base& __x)
110 unordered_set(unordered_set&&) =
default;
113 unordered_set(
const allocator_type& __a)
116 unordered_set(
const unordered_set& __uset,
117 const allocator_type& __a)
118 : _Base(__uset, __a) { }
120 unordered_set(unordered_set&& __uset,
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) { }
132 unordered_set(size_type __n,
const allocator_type& __a)
133 : unordered_set(__n, hasher(), key_equal(), __a)
136 unordered_set(size_type __n,
const hasher& __hf,
137 const allocator_type& __a)
138 : unordered_set(__n, __hf, key_equal(), __a)
141 template<
typename _InputIterator>
142 unordered_set(_InputIterator __first, _InputIterator __last,
144 const allocator_type& __a)
145 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
148 template<
typename _InputIterator>
149 unordered_set(_InputIterator __first, _InputIterator __last,
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)
158 : unordered_set(__l, __n, hasher(), key_equal(), __a)
162 size_type __n,
const hasher& __hf,
163 const allocator_type& __a)
164 : unordered_set(__l, __n, __hf, key_equal(), __a)
167 ~unordered_set() =
default;
170 operator=(
const unordered_set&) =
default;
173 operator=(unordered_set&&) =
default;
179 this->_M_invalidate_all();
184 swap(unordered_set& __x)
185 noexcept( noexcept(declval<_Base>().swap(__x)) )
195 this->_M_invalidate_all();
200 {
return iterator(_Base::begin(),
this); }
203 begin()
const noexcept
204 {
return const_iterator(_Base::begin(),
this); }
208 {
return iterator(_Base::end(),
this); }
212 {
return const_iterator(_Base::end(),
this); }
215 cbegin()
const noexcept
216 {
return const_iterator(_Base::begin(),
this); }
219 cend()
const noexcept
220 {
return const_iterator(_Base::end(),
this); }
226 __glibcxx_check_bucket_index(__b);
227 return local_iterator(_Base::begin(__b),
this);
233 __glibcxx_check_bucket_index(__b);
234 return local_iterator(_Base::end(__b),
this);
238 begin(size_type __b)
const
240 __glibcxx_check_bucket_index(__b);
241 return const_local_iterator(_Base::begin(__b),
this);
245 end(size_type __b)
const
247 __glibcxx_check_bucket_index(__b);
248 return const_local_iterator(_Base::end(__b),
this);
252 cbegin(size_type __b)
const
254 __glibcxx_check_bucket_index(__b);
255 return const_local_iterator(_Base::cbegin(__b),
this);
259 cend(size_type __b)
const
261 __glibcxx_check_bucket_index(__b);
262 return const_local_iterator(_Base::cend(__b),
this);
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>
296 emplace_hint(const_iterator __hint, _Args&&... __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);
303 return iterator(__it,
this);
307 insert(
const value_type& __obj)
309 size_type __bucket_count = this->bucket_count();
311 = _Base::insert(__obj);
312 _M_check_rehashed(__bucket_count);
317 insert(const_iterator __hint,
const value_type& __obj)
320 size_type __bucket_count = this->bucket_count();
321 _Base_iterator __it = _Base::insert(__hint.
base(), __obj);
322 _M_check_rehashed(__bucket_count);
323 return iterator(__it,
this);
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);
337 insert(const_iterator __hint, value_type&& __obj)
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);
343 return iterator(__it,
this);
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
371 {
return const_iterator(_Base::find(__key),
this); }
374 equal_range(
const key_type& __key)
377 = _Base::equal_range(__key);
379 iterator(__res.
second,
this));
383 equal_range(
const key_type& __key)
const
386 __res = _Base::equal_range(__key);
388 const_iterator(__res.
second,
this));
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);
413 erase(const_iterator __it)
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);
426 return iterator(__next,
this);
431 {
return erase(const_iterator(__it)); }
434 erase(const_iterator __first, const_iterator __last)
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);
455 return iterator(__next,
this);
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;
523 _Base_iterator, unordered_multiset>
iterator;
531 unordered_multiset() =
default;
534 unordered_multiset(size_type __n,
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>
541 unordered_multiset(_InputIterator __first, _InputIterator __last,
543 const hasher& __hf = hasher(),
544 const key_equal& __eql = key_equal(),
545 const allocator_type& __a = allocator_type())
549 __hf, __eql, __a) { }
551 unordered_multiset(
const unordered_multiset&) =
default;
553 unordered_multiset(
const _Base& __x)
556 unordered_multiset(unordered_multiset&&) =
default;
559 unordered_multiset(
const allocator_type& __a)
562 unordered_multiset(
const unordered_multiset& __uset,
563 const allocator_type& __a)
564 : _Base(__uset, __a) { }
566 unordered_multiset(unordered_multiset&& __uset,
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) { }
578 unordered_multiset(size_type __n,
const allocator_type& __a)
579 : unordered_multiset(__n, hasher(), key_equal(), __a)
582 unordered_multiset(size_type __n,
const hasher& __hf,
583 const allocator_type& __a)
584 : unordered_multiset(__n, __hf, key_equal(), __a)
587 template<
typename _InputIterator>
588 unordered_multiset(_InputIterator __first, _InputIterator __last,
590 const allocator_type& __a)
591 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
594 template<
typename _InputIterator>
595 unordered_multiset(_InputIterator __first, _InputIterator __last,
596 size_type __n,
const hasher& __hf,
597 const allocator_type& __a)
598 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
603 const allocator_type& __a)
604 : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
608 size_type __n,
const hasher& __hf,
609 const allocator_type& __a)
610 : unordered_multiset(__l, __n, __hf, key_equal(), __a)
613 ~unordered_multiset() =
default;
616 operator=(
const unordered_multiset&) =
default;
619 operator=(unordered_multiset&&) =
default;
624 this->_M_base() = __l;
625 this->_M_invalidate_all();
630 swap(unordered_multiset& __x)
631 noexcept( noexcept(declval<_Base>().swap(__x)) )
641 this->_M_invalidate_all();
646 {
return iterator(_Base::begin(),
this); }
649 begin()
const noexcept
650 {
return const_iterator(_Base::begin(),
this); }
654 {
return iterator(_Base::end(),
this); }
658 {
return const_iterator(_Base::end(),
this); }
661 cbegin()
const noexcept
662 {
return const_iterator(_Base::begin(),
this); }
665 cend()
const noexcept
666 {
return const_iterator(_Base::end(),
this); }
672 __glibcxx_check_bucket_index(__b);
673 return local_iterator(_Base::begin(__b),
this);
679 __glibcxx_check_bucket_index(__b);
680 return local_iterator(_Base::end(__b),
this);
684 begin(size_type __b)
const
686 __glibcxx_check_bucket_index(__b);
687 return const_local_iterator(_Base::begin(__b),
this);
691 end(size_type __b)
const
693 __glibcxx_check_bucket_index(__b);
694 return const_local_iterator(_Base::end(__b),
this);
698 cbegin(size_type __b)
const
700 __glibcxx_check_bucket_index(__b);
701 return const_local_iterator(_Base::cbegin(__b),
this);
705 cend(size_type __b)
const
707 __glibcxx_check_bucket_index(__b);
708 return const_local_iterator(_Base::cend(__b),
this);
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);
737 return iterator(__it,
this);
740 template<
typename... _Args>
742 emplace_hint(const_iterator __hint, _Args&&... __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);
749 return iterator(__it,
this);
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);
758 return iterator(__it,
this);
762 insert(const_iterator __hint,
const value_type& __obj)
765 size_type __bucket_count = this->bucket_count();
766 _Base_iterator __it = _Base::insert(__hint.
base(), __obj);
767 _M_check_rehashed(__bucket_count);
768 return iterator(__it,
this);
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);
777 return iterator(__it,
this);
781 insert(const_iterator __hint, value_type&& __obj)
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);
787 return iterator(__it,
this);
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
815 {
return const_iterator(_Base::find(__key),
this); }
818 equal_range(
const key_type& __key)
821 = _Base::equal_range(__key);
823 iterator(__res.
second,
this));
827 equal_range(
const key_type& __key)
const
830 __res = _Base::equal_range(__key);
832 const_iterator(__res.
second,
this));
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++);
855 erase(const_iterator __it)
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);
869 {
return erase(const_iterator(__it)); }
872 erase(const_iterator __first, const_iterator __last)
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; });
888 return iterator(_Base::erase(__first.
base(),
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); }
void _M_invalidate_local_if(_Predicate __pred)
A standard container composed of unique keys (containing at most one of each key value) in which the ...
Class std::unordered_multiset with safety/checking/debug instrumentation.
_Siter_base< _Iterator >::iterator_type __base(_Iterator __it)
_T1 first
second_type is the second bound type
Primary class template hash.
A standard container composed of equivalent keys (possibly containing multiple of each key value) in ...
_Iterator & base() noexcept
Return the underlying iterator.
#define __glibcxx_check_erase(_Position)
#define __glibcxx_check_erase_range(_First, _Last)
void _M_invalidate_if(_Predicate __pred)
Base class for constructing a safe unordered container type that tracks iterators that reference it...
ISO C++ entities toplevel namespace is std.
#define __glibcxx_check_insert(_Position)
One of the comparison functors.
Safe class dealing with some allocator dependent operations.
Struct holding two objects of arbitrary type.
Base class that supports tracking of iterators that reference a sequence.
Class std::unordered_set with safety/checking/debug instrumentation.
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.
_T2 second
first is a copy of the first object