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 ...
#define __glibcxx_check_insert(_Position)
Class std::unordered_multiset with safety/checking/debug instrumentation.
_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.
ISO C++ entities toplevel namespace is std.
void _M_invalidate_if(_Predicate __pred)
#define __glibcxx_check_erase(_Position)
Base class for constructing a safe unordered container type that tracks iterators that reference it...
#define __glibcxx_check_erase_range(_First, _Last)
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.
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].
_Siter_base< _Iterator >::iterator_type __base(_Iterator __it)
_T2 second
first is a copy of the first object