29 #ifndef _GLIBCXX_DEBUG_UNORDERED_MAP 30 #define _GLIBCXX_DEBUG_UNORDERED_MAP 1 32 #pragma GCC system_header 34 #if __cplusplus < 201103L 44 namespace std _GLIBCXX_VISIBILITY(default)
49 template<
typename _Key,
typename _Tp,
55 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
56 __gnu_debug::_Safe_unordered_container>,
57 public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
59 typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
63 typedef typename _Base::const_iterator _Base_const_iterator;
64 typedef typename _Base::iterator _Base_iterator;
65 typedef typename _Base::const_local_iterator
66 _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;
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>
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) { }
119 const allocator_type& __a)
120 :
_Base(__umap, __a) { }
123 const allocator_type& __a)
124 :
_Safe(std::move(__umap._M_safe()), __a),
125 _Base(std::move(__umap._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) { }
140 const allocator_type& __a)
144 template<
typename _InputIterator>
147 const allocator_type& __a)
148 :
unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
151 template<
typename _InputIterator>
155 const allocator_type& __a)
156 :
unordered_map(__first, __last, __n, __hf, key_equal(), __a)
161 const allocator_type& __a)
168 const allocator_type& __a)
184 this->_M_invalidate_all();
190 noexcept( noexcept(declval<_Base&>().swap(__x)) )
200 this->_M_invalidate_all();
205 {
return iterator(_Base::begin(),
this); }
208 begin()
const noexcept
213 {
return iterator(_Base::end(),
this); }
220 cbegin()
const noexcept
224 cend()
const noexcept
231 __glibcxx_check_bucket_index(__b);
238 __glibcxx_check_bucket_index(__b);
243 begin(size_type __b)
const 245 __glibcxx_check_bucket_index(__b);
250 end(size_type __b)
const 252 __glibcxx_check_bucket_index(__b);
257 cbegin(size_type __b)
const 259 __glibcxx_check_bucket_index(__b);
264 cend(size_type __b)
const 266 __glibcxx_check_bucket_index(__b);
271 bucket_size(size_type __b)
const 273 __glibcxx_check_bucket_index(__b);
274 return _Base::bucket_size(__b);
278 max_load_factor()
const noexcept
279 {
return _Base::max_load_factor(); }
282 max_load_factor(
float __f)
284 __glibcxx_check_max_load_factor(__f);
285 _Base::max_load_factor(__f);
288 template<
typename... _Args>
290 emplace(_Args&&... __args)
292 size_type __bucket_count = this->bucket_count();
294 = _Base::emplace(std::forward<_Args>(__args)...);
295 _M_check_rehashed(__bucket_count);
299 template<
typename... _Args>
304 size_type __bucket_count = this->bucket_count();
305 _Base_iterator __it = _Base::emplace_hint(__hint.
base(),
306 std::forward<_Args>(__args)...);
307 _M_check_rehashed(__bucket_count);
312 insert(
const value_type& __obj)
314 size_type __bucket_count = this->bucket_count();
316 _M_check_rehashed(__bucket_count);
324 size_type __bucket_count = this->bucket_count();
325 _Base_iterator __it = _Base::insert(__hint.
base(), __obj);
326 _M_check_rehashed(__bucket_count);
330 template<
typename _Pair,
typename =
typename 331 std::enable_if<std::is_constructible<value_type,
332 _Pair&&>::value>::type>
334 insert(_Pair&& __obj)
336 size_type __bucket_count = this->bucket_count();
338 _Base::insert(std::forward<_Pair>(__obj));
339 _M_check_rehashed(__bucket_count);
343 template<
typename _Pair,
typename =
typename 344 std::enable_if<std::is_constructible<value_type,
345 _Pair&&>::value>::type>
350 size_type __bucket_count = this->bucket_count();
351 _Base_iterator __it =
352 _Base::insert(__hint.
base(), std::forward<_Pair>(__obj));
353 _M_check_rehashed(__bucket_count);
360 size_type __bucket_count = this->bucket_count();
362 _M_check_rehashed(__bucket_count);
365 template<
typename _InputIterator>
367 insert(_InputIterator __first, _InputIterator __last)
370 __glibcxx_check_valid_range2(__first, __last, __dist);
371 size_type __bucket_count = this->bucket_count();
373 if (__dist.
second >= __gnu_debug::__dp_sign)
374 _Base::insert(__gnu_debug::__unsafe(__first),
375 __gnu_debug::__unsafe(__last));
377 _Base::insert(__first, __last);
379 _M_check_rehashed(__bucket_count);
382 #if __cplusplus > 201402L 383 template <
typename... _Args>
385 try_emplace(
const key_type& __k, _Args&&... __args)
387 auto __res = _Base::try_emplace(__k,
388 std::forward<_Args>(__args)...);
389 return {
iterator(__res.first,
this), __res.second };
392 template <
typename... _Args>
394 try_emplace(key_type&& __k, _Args&&... __args)
396 auto __res = _Base::try_emplace(std::move(__k),
397 std::forward<_Args>(__args)...);
398 return {
iterator(__res.first,
this), __res.second };
401 template <
typename... _Args>
408 std::forward<_Args>(__args)...),
412 template <
typename... _Args>
414 try_emplace(
const_iterator __hint, key_type&& __k, _Args&&... __args)
417 return iterator(_Base::try_emplace(__hint.
base(), std::move(__k),
418 std::forward<_Args>(__args)...),
422 template <
typename _Obj>
424 insert_or_assign(
const key_type& __k, _Obj&& __obj)
426 auto __res = _Base::insert_or_assign(__k,
427 std::forward<_Obj>(__obj));
428 return {
iterator(__res.first,
this), __res.second };
431 template <
typename _Obj>
433 insert_or_assign(key_type&& __k, _Obj&& __obj)
435 auto __res = _Base::insert_or_assign(std::move(__k),
436 std::forward<_Obj>(__obj));
437 return {
iterator(__res.first,
this), __res.second };
440 template <
typename _Obj>
446 return iterator(_Base::insert_or_assign(__hint.
base(), __k,
447 std::forward<_Obj>(__obj)),
451 template <
typename _Obj>
453 insert_or_assign(
const_iterator __hint, key_type&& __k, _Obj&& __obj)
458 std::forward<_Obj>(__obj)),
463 #if __cplusplus > 201402L 464 using node_type =
typename _Base::node_type;
466 struct insert_return_type
477 _Base_const_iterator __victim = __position.
base();
479 [__victim](_Base_const_iterator __it) {
return __it == __victim; }
482 [__victim](_Base_const_local_iterator __it) {
483 return __it._M_curr() == __victim._M_cur;
485 return _Base::extract(__position.
base());
489 extract(
const key_type& __key)
491 const auto __position = find(__key);
492 if (__position != end())
493 return extract(__position);
498 insert(node_type&& __nh)
500 auto __ret = _Base::insert(std::move(__nh));
502 return { __ret.inserted, __pos, std::move(__ret.node) };
509 return iterator(_Base::insert(__hint.
base(), std::move(__nh)),
this);
516 find(
const key_type& __key)
517 {
return iterator(_Base::find(__key),
this); }
520 find(
const key_type& __key)
const 524 equal_range(
const key_type& __key)
527 _Base::equal_range(__key);
533 equal_range(
const key_type& __key)
const 536 _Base::equal_range(__key);
542 erase(
const key_type& __key)
545 _Base_iterator __victim(_Base::find(__key));
546 if (__victim != _Base::end())
549 {
return __it == __victim; });
551 [__victim](_Base_const_local_iterator __it)
552 {
return __it._M_curr() == __victim._M_cur; });
553 size_type __bucket_count = this->bucket_count();
554 _Base::erase(__victim);
555 _M_check_rehashed(__bucket_count);
565 _Base_const_iterator __victim = __it.
base();
567 {
return __it == __victim; });
569 [__victim](_Base_const_local_iterator __it)
570 {
return __it._M_curr() == __victim._M_cur; });
571 size_type __bucket_count = this->bucket_count();
572 _Base_iterator __next = _Base::erase(__it.base());
573 _M_check_rehashed(__bucket_count);
585 for (_Base_const_iterator __tmp = __first.
base();
586 __tmp != __last.
base(); ++__tmp)
588 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
589 _M_message(__gnu_debug::__msg_valid_range)
590 ._M_iterator(__first,
"first")
591 ._M_iterator(__last,
"last"));
593 {
return __it == __tmp; });
595 [__tmp](_Base_const_local_iterator __it)
596 {
return __it._M_curr() == __tmp._M_cur; });
598 size_type __bucket_count = this->bucket_count();
599 _Base_iterator __next = _Base::erase(__first.
base(), __last.
base());
600 _M_check_rehashed(__bucket_count);
605 _M_base() noexcept {
return *
this; }
608 _M_base()
const noexcept {
return *
this; }
612 _M_check_rehashed(size_type __prev_count)
614 if (__prev_count != this->bucket_count())
615 this->_M_invalidate_locals();
619 template<
typename _Key,
typename _Tp,
typename _Hash,
620 typename _Pred,
typename _Alloc>
624 noexcept(noexcept(__x.swap(__y)))
627 template<
typename _Key,
typename _Tp,
typename _Hash,
628 typename _Pred,
typename _Alloc>
632 {
return __x._M_base() == __y._M_base(); }
634 template<
typename _Key,
typename _Tp,
typename _Hash,
635 typename _Pred,
typename _Alloc>
637 operator!=(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
638 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
639 {
return !(__x == __y); }
643 template<
typename _Key,
typename _Tp,
649 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
650 __gnu_debug::_Safe_unordered_container>,
651 public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
653 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
654 _Pred, _Alloc>
_Base;
657 typedef typename _Base::const_iterator _Base_const_iterator;
658 typedef typename _Base::iterator _Base_iterator;
659 typedef typename _Base::const_local_iterator _Base_const_local_iterator;
660 typedef typename _Base::local_iterator _Base_local_iterator;
663 typedef typename _Base::size_type size_type;
664 typedef typename _Base::hasher hasher;
665 typedef typename _Base::key_equal key_equal;
666 typedef typename _Base::allocator_type allocator_type;
668 typedef typename _Base::key_type key_type;
669 typedef typename _Base::value_type value_type;
684 const hasher& __hf = hasher(),
685 const key_equal& __eql = key_equal(),
686 const allocator_type& __a = allocator_type())
687 :
_Base(__n, __hf, __eql, __a) { }
689 template<
typename _InputIterator>
692 const hasher& __hf = hasher(),
693 const key_equal& __eql = key_equal(),
694 const allocator_type& __a = allocator_type())
695 :
_Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
697 __gnu_debug::__base(__last), __n,
698 __hf, __eql, __a) { }
712 const allocator_type& __a)
713 :
_Base(__umap, __a) { }
716 const allocator_type& __a)
717 :
_Safe(std::move(__umap._M_safe()), __a),
718 _Base(std::move(__umap._M_base()), __a) { }
722 const hasher& __hf = hasher(),
723 const key_equal& __eql = key_equal(),
724 const allocator_type& __a = allocator_type())
725 :
_Base(__l, __n, __hf, __eql, __a) { }
732 const allocator_type& __a)
736 template<
typename _InputIterator>
739 const allocator_type& __a)
743 template<
typename _InputIterator>
745 size_type __n,
const hasher& __hf,
746 const allocator_type& __a)
752 const allocator_type& __a)
757 size_type __n,
const hasher& __hf,
758 const allocator_type& __a)
773 this->_M_base() = __l;
774 this->_M_invalidate_all();
780 noexcept( noexcept(declval<_Base&>().swap(__x)) )
790 this->_M_invalidate_all();
795 {
return iterator(_Base::begin(),
this); }
798 begin()
const noexcept
803 {
return iterator(_Base::end(),
this); }
810 cbegin()
const noexcept
814 cend()
const noexcept
821 __glibcxx_check_bucket_index(__b);
828 __glibcxx_check_bucket_index(__b);
833 begin(size_type __b)
const 835 __glibcxx_check_bucket_index(__b);
840 end(size_type __b)
const 842 __glibcxx_check_bucket_index(__b);
847 cbegin(size_type __b)
const 849 __glibcxx_check_bucket_index(__b);
854 cend(size_type __b)
const 856 __glibcxx_check_bucket_index(__b);
861 bucket_size(size_type __b)
const 863 __glibcxx_check_bucket_index(__b);
864 return _Base::bucket_size(__b);
868 max_load_factor()
const noexcept
869 {
return _Base::max_load_factor(); }
872 max_load_factor(
float __f)
874 __glibcxx_check_max_load_factor(__f);
875 _Base::max_load_factor(__f);
878 template<
typename... _Args>
880 emplace(_Args&&... __args)
882 size_type __bucket_count = this->bucket_count();
884 = _Base::emplace(std::forward<_Args>(__args)...);
885 _M_check_rehashed(__bucket_count);
889 template<
typename... _Args>
894 size_type __bucket_count = this->bucket_count();
895 _Base_iterator __it = _Base::emplace_hint(__hint.
base(),
896 std::forward<_Args>(__args)...);
897 _M_check_rehashed(__bucket_count);
902 insert(
const value_type& __obj)
904 size_type __bucket_count = this->bucket_count();
905 _Base_iterator __it = _Base::insert(__obj);
906 _M_check_rehashed(__bucket_count);
914 size_type __bucket_count = this->bucket_count();
915 _Base_iterator __it = _Base::insert(__hint.
base(), __obj);
916 _M_check_rehashed(__bucket_count);
920 template<
typename _Pair,
typename =
typename 921 std::enable_if<std::is_constructible<value_type,
922 _Pair&&>::value>::type>
924 insert(_Pair&& __obj)
926 size_type __bucket_count = this->bucket_count();
927 _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj));
928 _M_check_rehashed(__bucket_count);
932 template<
typename _Pair,
typename =
typename 933 std::enable_if<std::is_constructible<value_type,
934 _Pair&&>::value>::type>
939 size_type __bucket_count = this->bucket_count();
940 _Base_iterator __it =
941 _Base::insert(__hint.
base(), std::forward<_Pair>(__obj));
942 _M_check_rehashed(__bucket_count);
948 { _Base::insert(__l); }
950 template<
typename _InputIterator>
952 insert(_InputIterator __first, _InputIterator __last)
955 __glibcxx_check_valid_range2(__first, __last, __dist);
956 size_type __bucket_count = this->bucket_count();
958 if (__dist.
second >= __gnu_debug::__dp_sign)
959 _Base::insert(__gnu_debug::__unsafe(__first),
960 __gnu_debug::__unsafe(__last));
962 _Base::insert(__first, __last);
964 _M_check_rehashed(__bucket_count);
967 #if __cplusplus > 201402L 968 using node_type =
typename _Base::node_type;
974 _Base_const_iterator __victim = __position.
base();
976 [__victim](_Base_const_iterator __it) {
return __it == __victim; }
979 [__victim](_Base_const_local_iterator __it) {
980 return __it._M_curr() == __victim._M_cur;
982 return _Base::extract(__position.
base());
986 extract(
const key_type& __key)
988 const auto __position = find(__key);
989 if (__position != end())
990 return extract(__position);
995 insert(node_type&& __nh)
996 {
return iterator(_Base::insert(std::move(__nh)),
this); }
1002 return iterator(_Base::insert(__hint.
base(), std::move(__nh)),
this);
1009 find(
const key_type& __key)
1010 {
return iterator(_Base::find(__key),
this); }
1013 find(
const key_type& __key)
const 1017 equal_range(
const key_type& __key)
1020 _Base::equal_range(__key);
1026 equal_range(
const key_type& __key)
const 1029 _Base::equal_range(__key);
1035 erase(
const key_type& __key)
1038 size_type __bucket_count = this->bucket_count();
1040 _Base::equal_range(__key);
1041 for (_Base_iterator __victim = __pair.
first; __victim != __pair.
second;)
1044 {
return __it == __victim; });
1046 [__victim](_Base_const_local_iterator __it)
1047 {
return __it._M_curr() == __victim._M_cur; });
1048 _Base::erase(__victim++);
1051 _M_check_rehashed(__bucket_count);
1059 _Base_const_iterator __victim = __it.
base();
1061 {
return __it == __victim; });
1063 [__victim](_Base_const_local_iterator __it)
1064 {
return __it._M_curr() == __victim._M_cur; });
1065 size_type __bucket_count = this->bucket_count();
1066 _Base_iterator __next = _Base::erase(__it.base());
1067 _M_check_rehashed(__bucket_count);
1079 for (_Base_const_iterator __tmp = __first.
base();
1080 __tmp != __last.
base(); ++__tmp)
1082 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
1083 _M_message(__gnu_debug::__msg_valid_range)
1084 ._M_iterator(__first,
"first")
1085 ._M_iterator(__last,
"last"));
1087 {
return __it == __tmp; });
1089 [__tmp](_Base_const_local_iterator __it)
1090 {
return __it._M_curr() == __tmp._M_cur; });
1092 size_type __bucket_count = this->bucket_count();
1093 _Base_iterator __next = _Base::erase(__first.
base(), __last.
base());
1094 _M_check_rehashed(__bucket_count);
1099 _M_base() noexcept {
return *
this; }
1102 _M_base()
const noexcept {
return *
this; }
1106 _M_check_rehashed(size_type __prev_count)
1108 if (__prev_count != this->bucket_count())
1109 this->_M_invalidate_locals();
1113 template<
typename _Key,
typename _Tp,
typename _Hash,
1114 typename _Pred,
typename _Alloc>
1118 noexcept(noexcept(__x.
swap(__y)))
1121 template<
typename _Key,
typename _Tp,
typename _Hash,
1122 typename _Pred,
typename _Alloc>
1126 {
return __x._M_base() == __y._M_base(); }
1128 template<
typename _Key,
typename _Tp,
typename _Hash,
1129 typename _Pred,
typename _Alloc>
1131 operator!=(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1132 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1133 {
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)
Class std::unordered_multimap with safety/checking/debug instrumentation.
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_map with safety/checking/debug instrumentation.
A standard container composed of equivalent keys (possibly containing multiple of each key value) tha...
ISO C++ entities toplevel namespace is std.
_T2 second
first is a copy of the first object
void swap(unordered_map &__x) noexcept(noexcept(_M_h.swap(__x._M_h)))
Swaps data with another unordered_map.
_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)
void _M_invalidate_if(_Predicate __pred)
Struct holding two objects of arbitrary type.
Base class that supports tracking of iterators that reference a sequence.
Primary class template hash.
A standard container composed of unique keys (containing at most one of each key value) that associat...
The standard allocator, as per [20.4].
#define __glibcxx_check_erase(_Position)