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;
79 _Base_iterator, unordered_set>
iterator;
87 unordered_set() =
default;
90 unordered_set(size_type __n,
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>
97 unordered_set(_InputIterator __first, _InputIterator __last,
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) { }
107 unordered_set(
const unordered_set&) =
default;
109 unordered_set(
const _Base& __x)
112 unordered_set(unordered_set&&) =
default;
115 unordered_set(
const allocator_type& __a)
118 unordered_set(
const unordered_set& __uset,
119 const allocator_type& __a)
120 : _Base(__uset, __a) { }
122 unordered_set(unordered_set&& __uset,
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) { }
134 unordered_set(size_type __n,
const allocator_type& __a)
135 : unordered_set(__n, hasher(), key_equal(), __a)
138 unordered_set(size_type __n,
const hasher& __hf,
139 const allocator_type& __a)
140 : unordered_set(__n, __hf, key_equal(), __a)
143 template<
typename _InputIterator>
144 unordered_set(_InputIterator __first, _InputIterator __last,
146 const allocator_type& __a)
147 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
150 template<
typename _InputIterator>
151 unordered_set(_InputIterator __first, _InputIterator __last,
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)
160 : unordered_set(__l, __n, hasher(), key_equal(), __a)
164 size_type __n,
const hasher& __hf,
165 const allocator_type& __a)
166 : unordered_set(__l, __n, __hf, key_equal(), __a)
169 ~unordered_set() =
default;
172 operator=(
const unordered_set&) =
default;
175 operator=(unordered_set&&) =
default;
181 this->_M_invalidate_all();
186 swap(unordered_set& __x)
187 noexcept( noexcept(declval<_Base&>().swap(__x)) )
197 this->_M_invalidate_all();
202 {
return iterator(_Base::begin(),
this); }
205 begin()
const noexcept
206 {
return const_iterator(_Base::begin(),
this); }
210 {
return iterator(_Base::end(),
this); }
214 {
return const_iterator(_Base::end(),
this); }
217 cbegin()
const noexcept
218 {
return const_iterator(_Base::begin(),
this); }
221 cend()
const noexcept
222 {
return const_iterator(_Base::end(),
this); }
228 __glibcxx_check_bucket_index(__b);
229 return local_iterator(_Base::begin(__b),
this);
235 __glibcxx_check_bucket_index(__b);
236 return local_iterator(_Base::end(__b),
this);
240 begin(size_type __b)
const 242 __glibcxx_check_bucket_index(__b);
243 return const_local_iterator(_Base::begin(__b),
this);
247 end(size_type __b)
const 249 __glibcxx_check_bucket_index(__b);
250 return const_local_iterator(_Base::end(__b),
this);
254 cbegin(size_type __b)
const 256 __glibcxx_check_bucket_index(__b);
257 return const_local_iterator(_Base::cbegin(__b),
this);
261 cend(size_type __b)
const 263 __glibcxx_check_bucket_index(__b);
264 return const_local_iterator(_Base::cend(__b),
this);
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>
298 emplace_hint(const_iterator __hint, _Args&&... __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);
305 return iterator(__it,
this);
309 insert(
const value_type& __obj)
311 size_type __bucket_count = this->bucket_count();
313 = _Base::insert(__obj);
314 _M_check_rehashed(__bucket_count);
319 insert(const_iterator __hint,
const value_type& __obj)
322 size_type __bucket_count = this->bucket_count();
323 _Base_iterator __it = _Base::insert(__hint.
base(), __obj);
324 _M_check_rehashed(__bucket_count);
325 return iterator(__it,
this);
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);
339 insert(const_iterator __hint, value_type&& __obj)
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);
345 return iterator(__it,
this);
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
384 extract(const_iterator __position)
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));
411 iterator __pos = iterator(__ret.position,
this);
412 return { __ret.inserted, __pos, std::move(__ret.node) };
416 insert(const_iterator __hint, node_type&& __nh)
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 431 {
return const_iterator(_Base::find(__key),
this); }
434 equal_range(
const key_type& __key)
437 = _Base::equal_range(__key);
439 iterator(__res.
second,
this));
443 equal_range(
const key_type& __key)
const 446 __res = _Base::equal_range(__key);
448 const_iterator(__res.
second,
this));
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);
473 erase(const_iterator __it)
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);
486 return iterator(__next,
this);
491 {
return erase(const_iterator(__it)); }
494 erase(const_iterator __first, const_iterator __last)
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);
515 return iterator(__next,
this);
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>
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;
584 _Base_iterator, unordered_multiset>
iterator;
592 unordered_multiset() =
default;
595 unordered_multiset(size_type __n,
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>
602 unordered_multiset(_InputIterator __first, _InputIterator __last,
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) { }
612 unordered_multiset(
const unordered_multiset&) =
default;
614 unordered_multiset(
const _Base& __x)
617 unordered_multiset(unordered_multiset&&) =
default;
620 unordered_multiset(
const allocator_type& __a)
623 unordered_multiset(
const unordered_multiset& __uset,
624 const allocator_type& __a)
625 : _Base(__uset, __a) { }
627 unordered_multiset(unordered_multiset&& __uset,
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) { }
639 unordered_multiset(size_type __n,
const allocator_type& __a)
640 : unordered_multiset(__n, hasher(), key_equal(), __a)
643 unordered_multiset(size_type __n,
const hasher& __hf,
644 const allocator_type& __a)
645 : unordered_multiset(__n, __hf, key_equal(), __a)
648 template<
typename _InputIterator>
649 unordered_multiset(_InputIterator __first, _InputIterator __last,
651 const allocator_type& __a)
652 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
655 template<
typename _InputIterator>
656 unordered_multiset(_InputIterator __first, _InputIterator __last,
657 size_type __n,
const hasher& __hf,
658 const allocator_type& __a)
659 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
664 const allocator_type& __a)
665 : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
669 size_type __n,
const hasher& __hf,
670 const allocator_type& __a)
671 : unordered_multiset(__l, __n, __hf, key_equal(), __a)
674 ~unordered_multiset() =
default;
677 operator=(
const unordered_multiset&) =
default;
680 operator=(unordered_multiset&&) =
default;
685 this->_M_base() = __l;
686 this->_M_invalidate_all();
691 swap(unordered_multiset& __x)
692 noexcept( noexcept(declval<_Base&>().swap(__x)) )
702 this->_M_invalidate_all();
707 {
return iterator(_Base::begin(),
this); }
710 begin()
const noexcept
711 {
return const_iterator(_Base::begin(),
this); }
715 {
return iterator(_Base::end(),
this); }
719 {
return const_iterator(_Base::end(),
this); }
723 {
return const_iterator(_Base::begin(),
this); }
726 cend()
const noexcept
727 {
return const_iterator(_Base::end(),
this); }
733 __glibcxx_check_bucket_index(__b);
734 return local_iterator(_Base::begin(__b),
this);
740 __glibcxx_check_bucket_index(__b);
741 return local_iterator(_Base::end(__b),
this);
745 begin(size_type __b)
const 747 __glibcxx_check_bucket_index(__b);
748 return const_local_iterator(_Base::begin(__b),
this);
752 end(size_type __b)
const 754 __glibcxx_check_bucket_index(__b);
755 return const_local_iterator(_Base::end(__b),
this);
759 cbegin(size_type __b)
const 761 __glibcxx_check_bucket_index(__b);
762 return const_local_iterator(_Base::cbegin(__b),
this);
766 cend(size_type __b)
const 768 __glibcxx_check_bucket_index(__b);
769 return const_local_iterator(_Base::cend(__b),
this);
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);
798 return iterator(__it,
this);
801 template<
typename... _Args>
803 emplace_hint(const_iterator __hint, _Args&&... __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);
810 return iterator(__it,
this);
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);
819 return iterator(__it,
this);
823 insert(const_iterator __hint,
const value_type& __obj)
826 size_type __bucket_count = this->bucket_count();
827 _Base_iterator __it = _Base::insert(__hint.
base(), __obj);
828 _M_check_rehashed(__bucket_count);
829 return iterator(__it,
this);
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);
838 return iterator(__it,
this);
842 insert(const_iterator __hint, value_type&& __obj)
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);
848 return iterator(__it,
this);
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;
880 extract(const_iterator __position)
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); }
908 insert(const_iterator __hint, node_type&& __nh)
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 923 {
return const_iterator(_Base::find(__key),
this); }
926 equal_range(
const key_type& __key)
929 = _Base::equal_range(__key);
931 iterator(__res.
second,
this));
935 equal_range(
const key_type& __key)
const 938 __res = _Base::equal_range(__key);
940 const_iterator(__res.
second,
this));
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++);
963 erase(const_iterator __it)
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);
977 {
return erase(const_iterator(__it)); }
980 erase(const_iterator __first, const_iterator __last)
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; });
996 return iterator(_Base::erase(__first.
base(),
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>
1032 {
return !(__x == __y); }
Base class for constructing a safe unordered container type that tracks iterators that reference it...
_T1 first
second_type is the second bound type
#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.
Class std::unordered_multiset with safety/checking/debug instrumentation.
Class std::unordered_set with safety/checking/debug instrumentation.
ISO C++ entities toplevel namespace is std.
_T2 second
first is a copy of the first object
_Iterator & base() noexcept
Return the underlying iterator.
One of the comparison functors.
Safe class dealing with some allocator dependent operations.
void _M_invalidate_local_if(_Predicate __pred)
#define __glibcxx_check_insert(_Position)
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
void _M_invalidate_if(_Predicate __pred)
Struct holding two objects of arbitrary type.
Base class that supports tracking of iterators that reference a sequence.
constexpr auto cbegin(const _Container &__cont) noexcept(noexcept(std::begin(__cont))) -> decltype(std::begin(__cont))
Return an iterator pointing to the first element of the const container.
Primary class template hash.
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
The standard allocator, as per [20.4].
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
#define __glibcxx_check_erase(_Position)