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();
315 auto __res = _Base::insert(__obj);
316 _M_check_rehashed(__bucket_count);
317 return {
iterator(__res.first,
this), __res.second };
323 insert(value_type&& __x)
325 size_type __bucket_count = this->bucket_count();
326 auto __res = _Base::insert(std::move(__x));
327 _M_check_rehashed(__bucket_count);
328 return {
iterator(__res.first,
this), __res.second };
331 template<
typename _Pair,
typename =
typename
332 std::enable_if<std::is_constructible<value_type,
333 _Pair&&>::value>::type>
335 insert(_Pair&& __obj)
337 size_type __bucket_count = this->bucket_count();
339 _Base::insert(std::forward<_Pair>(__obj));
340 _M_check_rehashed(__bucket_count);
348 size_type __bucket_count = this->bucket_count();
349 _Base_iterator __it = _Base::insert(__hint.
base(), __obj);
350 _M_check_rehashed(__bucket_count);
360 size_type __bucket_count = this->bucket_count();
361 auto __it = _Base::insert(__hint.
base(), std::move(__x));
362 _M_check_rehashed(__bucket_count);
366 template<
typename _Pair,
typename =
typename
367 std::enable_if<std::is_constructible<value_type,
368 _Pair&&>::value>::type>
373 size_type __bucket_count = this->bucket_count();
374 _Base_iterator __it =
375 _Base::insert(__hint.
base(), std::forward<_Pair>(__obj));
376 _M_check_rehashed(__bucket_count);
383 size_type __bucket_count = this->bucket_count();
385 _M_check_rehashed(__bucket_count);
388 template<
typename _InputIterator>
390 insert(_InputIterator __first, _InputIterator __last)
393 __glibcxx_check_valid_range2(__first, __last, __dist);
394 size_type __bucket_count = this->bucket_count();
396 if (__dist.
second >= __gnu_debug::__dp_sign)
397 _Base::insert(__gnu_debug::__unsafe(__first),
398 __gnu_debug::__unsafe(__last));
400 _Base::insert(__first, __last);
402 _M_check_rehashed(__bucket_count);
405 #if __cplusplus > 201402L
406 template <
typename... _Args>
408 try_emplace(
const key_type& __k, _Args&&... __args)
410 auto __res = _Base::try_emplace(__k,
411 std::forward<_Args>(__args)...);
412 return {
iterator(__res.first,
this), __res.second };
415 template <
typename... _Args>
417 try_emplace(key_type&& __k, _Args&&... __args)
419 auto __res = _Base::try_emplace(std::move(__k),
420 std::forward<_Args>(__args)...);
421 return {
iterator(__res.first,
this), __res.second };
424 template <
typename... _Args>
431 std::forward<_Args>(__args)...),
435 template <
typename... _Args>
437 try_emplace(
const_iterator __hint, key_type&& __k, _Args&&... __args)
440 return iterator(_Base::try_emplace(__hint.
base(), std::move(__k),
441 std::forward<_Args>(__args)...),
445 template <
typename _Obj>
447 insert_or_assign(
const key_type& __k, _Obj&& __obj)
449 auto __res = _Base::insert_or_assign(__k,
450 std::forward<_Obj>(__obj));
451 return {
iterator(__res.first,
this), __res.second };
454 template <
typename _Obj>
456 insert_or_assign(key_type&& __k, _Obj&& __obj)
458 auto __res = _Base::insert_or_assign(std::move(__k),
459 std::forward<_Obj>(__obj));
460 return {
iterator(__res.first,
this), __res.second };
463 template <
typename _Obj>
469 return iterator(_Base::insert_or_assign(__hint.
base(), __k,
470 std::forward<_Obj>(__obj)),
474 template <
typename _Obj>
476 insert_or_assign(
const_iterator __hint, key_type&& __k, _Obj&& __obj)
481 std::forward<_Obj>(__obj)),
486 #if __cplusplus > 201402L
487 using node_type =
typename _Base::node_type;
489 struct insert_return_type
500 _Base_const_iterator __victim = __position.
base();
502 [__victim](_Base_const_iterator __it) {
return __it == __victim; }
505 [__victim](_Base_const_local_iterator __it) {
506 return __it._M_curr() == __victim._M_cur;
508 return _Base::extract(__position.
base());
512 extract(
const key_type& __key)
514 const auto __position = find(__key);
515 if (__position != end())
516 return extract(__position);
521 insert(node_type&& __nh)
523 auto __ret = _Base::insert(std::move(__nh));
525 return { __ret.inserted, __pos, std::move(__ret.node) };
532 return iterator(_Base::insert(__hint.
base(), std::move(__nh)),
this);
539 find(
const key_type& __key)
540 {
return iterator(_Base::find(__key),
this); }
543 find(
const key_type& __key)
const
547 equal_range(
const key_type& __key)
550 _Base::equal_range(__key);
556 equal_range(
const key_type& __key)
const
559 _Base::equal_range(__key);
565 erase(
const key_type& __key)
568 _Base_iterator __victim(_Base::find(__key));
569 if (__victim != _Base::end())
572 {
return __it == __victim; });
574 [__victim](_Base_const_local_iterator __it)
575 {
return __it._M_curr() == __victim._M_cur; });
576 size_type __bucket_count = this->bucket_count();
577 _Base::erase(__victim);
578 _M_check_rehashed(__bucket_count);
588 _Base_const_iterator __victim = __it.
base();
590 {
return __it == __victim; });
592 [__victim](_Base_const_local_iterator __it)
593 {
return __it._M_curr() == __victim._M_cur; });
594 size_type __bucket_count = this->bucket_count();
595 _Base_iterator __next = _Base::erase(__it.base());
596 _M_check_rehashed(__bucket_count);
608 for (_Base_const_iterator __tmp = __first.
base();
609 __tmp != __last.
base(); ++__tmp)
611 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
612 _M_message(__gnu_debug::__msg_valid_range)
613 ._M_iterator(__first,
"first")
614 ._M_iterator(__last,
"last"));
616 {
return __it == __tmp; });
618 [__tmp](_Base_const_local_iterator __it)
619 {
return __it._M_curr() == __tmp._M_cur; });
621 size_type __bucket_count = this->bucket_count();
622 _Base_iterator __next = _Base::erase(__first.
base(), __last.
base());
623 _M_check_rehashed(__bucket_count);
628 _M_base() noexcept {
return *
this; }
631 _M_base()
const noexcept {
return *
this; }
635 _M_check_rehashed(size_type __prev_count)
637 if (__prev_count != this->bucket_count())
638 this->_M_invalidate_locals();
642 template<
typename _Key,
typename _Tp,
typename _Hash,
643 typename _Pred,
typename _Alloc>
647 noexcept(noexcept(__x.swap(__y)))
650 template<
typename _Key,
typename _Tp,
typename _Hash,
651 typename _Pred,
typename _Alloc>
655 {
return __x._M_base() == __y._M_base(); }
657 template<
typename _Key,
typename _Tp,
typename _Hash,
658 typename _Pred,
typename _Alloc>
660 operator!=(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
661 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
662 {
return !(__x == __y); }
666 template<
typename _Key,
typename _Tp,
672 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
673 __gnu_debug::_Safe_unordered_container>,
674 public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
676 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
677 _Pred, _Alloc>
_Base;
680 typedef typename _Base::const_iterator _Base_const_iterator;
681 typedef typename _Base::iterator _Base_iterator;
682 typedef typename _Base::const_local_iterator _Base_const_local_iterator;
683 typedef typename _Base::local_iterator _Base_local_iterator;
686 typedef typename _Base::size_type size_type;
687 typedef typename _Base::hasher hasher;
688 typedef typename _Base::key_equal key_equal;
689 typedef typename _Base::allocator_type allocator_type;
691 typedef typename _Base::key_type key_type;
692 typedef typename _Base::value_type value_type;
707 const hasher& __hf = hasher(),
708 const key_equal& __eql = key_equal(),
709 const allocator_type& __a = allocator_type())
710 :
_Base(__n, __hf, __eql, __a) { }
712 template<
typename _InputIterator>
715 const hasher& __hf = hasher(),
716 const key_equal& __eql = key_equal(),
717 const allocator_type& __a = allocator_type())
718 :
_Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
720 __gnu_debug::__base(__last), __n,
721 __hf, __eql, __a) { }
735 const allocator_type& __a)
736 :
_Base(__umap, __a) { }
739 const allocator_type& __a)
740 :
_Safe(std::move(__umap._M_safe()), __a),
741 _Base(std::move(__umap._M_base()), __a) { }
745 const hasher& __hf = hasher(),
746 const key_equal& __eql = key_equal(),
747 const allocator_type& __a = allocator_type())
748 :
_Base(__l, __n, __hf, __eql, __a) { }
755 const allocator_type& __a)
759 template<
typename _InputIterator>
762 const allocator_type& __a)
766 template<
typename _InputIterator>
768 size_type __n,
const hasher& __hf,
769 const allocator_type& __a)
775 const allocator_type& __a)
780 size_type __n,
const hasher& __hf,
781 const allocator_type& __a)
796 this->_M_base() = __l;
797 this->_M_invalidate_all();
803 noexcept( noexcept(declval<_Base&>().swap(__x)) )
813 this->_M_invalidate_all();
818 {
return iterator(_Base::begin(),
this); }
821 begin()
const noexcept
826 {
return iterator(_Base::end(),
this); }
833 cbegin()
const noexcept
837 cend()
const noexcept
844 __glibcxx_check_bucket_index(__b);
851 __glibcxx_check_bucket_index(__b);
856 begin(size_type __b)
const
858 __glibcxx_check_bucket_index(__b);
863 end(size_type __b)
const
865 __glibcxx_check_bucket_index(__b);
870 cbegin(size_type __b)
const
872 __glibcxx_check_bucket_index(__b);
877 cend(size_type __b)
const
879 __glibcxx_check_bucket_index(__b);
884 bucket_size(size_type __b)
const
886 __glibcxx_check_bucket_index(__b);
887 return _Base::bucket_size(__b);
891 max_load_factor()
const noexcept
892 {
return _Base::max_load_factor(); }
895 max_load_factor(
float __f)
897 __glibcxx_check_max_load_factor(__f);
898 _Base::max_load_factor(__f);
901 template<
typename... _Args>
903 emplace(_Args&&... __args)
905 size_type __bucket_count = this->bucket_count();
907 = _Base::emplace(std::forward<_Args>(__args)...);
908 _M_check_rehashed(__bucket_count);
912 template<
typename... _Args>
917 size_type __bucket_count = this->bucket_count();
918 _Base_iterator __it = _Base::emplace_hint(__hint.
base(),
919 std::forward<_Args>(__args)...);
920 _M_check_rehashed(__bucket_count);
925 insert(
const value_type& __obj)
927 size_type __bucket_count = this->bucket_count();
928 _Base_iterator __it = _Base::insert(__obj);
929 _M_check_rehashed(__bucket_count);
936 insert(value_type&& __x)
938 size_type __bucket_count = this->bucket_count();
939 auto __it = _Base::insert(std::move(__x));
940 _M_check_rehashed(__bucket_count);
941 return { __it,
this };
948 size_type __bucket_count = this->bucket_count();
949 _Base_iterator __it = _Base::insert(__hint.
base(), __obj);
950 _M_check_rehashed(__bucket_count);
960 size_type __bucket_count = this->bucket_count();
961 auto __it = _Base::insert(__hint.
base(), std::move(__x));
962 _M_check_rehashed(__bucket_count);
966 template<
typename _Pair,
typename =
typename
967 std::enable_if<std::is_constructible<value_type,
968 _Pair&&>::value>::type>
970 insert(_Pair&& __obj)
972 size_type __bucket_count = this->bucket_count();
973 _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj));
974 _M_check_rehashed(__bucket_count);
978 template<
typename _Pair,
typename =
typename
979 std::enable_if<std::is_constructible<value_type,
980 _Pair&&>::value>::type>
985 size_type __bucket_count = this->bucket_count();
986 _Base_iterator __it =
987 _Base::insert(__hint.
base(), std::forward<_Pair>(__obj));
988 _M_check_rehashed(__bucket_count);
994 { _Base::insert(__l); }
996 template<
typename _InputIterator>
998 insert(_InputIterator __first, _InputIterator __last)
1001 __glibcxx_check_valid_range2(__first, __last, __dist);
1002 size_type __bucket_count = this->bucket_count();
1004 if (__dist.
second >= __gnu_debug::__dp_sign)
1005 _Base::insert(__gnu_debug::__unsafe(__first),
1006 __gnu_debug::__unsafe(__last));
1008 _Base::insert(__first, __last);
1010 _M_check_rehashed(__bucket_count);
1013 #if __cplusplus > 201402L
1014 using node_type =
typename _Base::node_type;
1020 _Base_const_iterator __victim = __position.
base();
1022 [__victim](_Base_const_iterator __it) {
return __it == __victim; }
1025 [__victim](_Base_const_local_iterator __it) {
1026 return __it._M_curr() == __victim._M_cur;
1028 return _Base::extract(__position.
base());
1032 extract(
const key_type& __key)
1034 const auto __position = find(__key);
1035 if (__position != end())
1036 return extract(__position);
1041 insert(node_type&& __nh)
1042 {
return iterator(_Base::insert(std::move(__nh)),
this); }
1048 return iterator(_Base::insert(__hint.
base(), std::move(__nh)),
this);
1055 find(
const key_type& __key)
1056 {
return iterator(_Base::find(__key),
this); }
1059 find(
const key_type& __key)
const
1063 equal_range(
const key_type& __key)
1066 _Base::equal_range(__key);
1072 equal_range(
const key_type& __key)
const
1075 _Base::equal_range(__key);
1081 erase(
const key_type& __key)
1084 size_type __bucket_count = this->bucket_count();
1086 _Base::equal_range(__key);
1087 for (_Base_iterator __victim = __pair.
first; __victim != __pair.
second;)
1090 {
return __it == __victim; });
1092 [__victim](_Base_const_local_iterator __it)
1093 {
return __it._M_curr() == __victim._M_cur; });
1094 _Base::erase(__victim++);
1097 _M_check_rehashed(__bucket_count);
1105 _Base_const_iterator __victim = __it.
base();
1107 {
return __it == __victim; });
1109 [__victim](_Base_const_local_iterator __it)
1110 {
return __it._M_curr() == __victim._M_cur; });
1111 size_type __bucket_count = this->bucket_count();
1112 _Base_iterator __next = _Base::erase(__it.base());
1113 _M_check_rehashed(__bucket_count);
1125 for (_Base_const_iterator __tmp = __first.
base();
1126 __tmp != __last.
base(); ++__tmp)
1128 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
1129 _M_message(__gnu_debug::__msg_valid_range)
1130 ._M_iterator(__first,
"first")
1131 ._M_iterator(__last,
"last"));
1133 {
return __it == __tmp; });
1135 [__tmp](_Base_const_local_iterator __it)
1136 {
return __it._M_curr() == __tmp._M_cur; });
1138 size_type __bucket_count = this->bucket_count();
1139 _Base_iterator __next = _Base::erase(__first.
base(), __last.
base());
1140 _M_check_rehashed(__bucket_count);
1145 _M_base() noexcept {
return *
this; }
1148 _M_base()
const noexcept {
return *
this; }
1152 _M_check_rehashed(size_type __prev_count)
1154 if (__prev_count != this->bucket_count())
1155 this->_M_invalidate_locals();
1159 template<
typename _Key,
typename _Tp,
typename _Hash,
1160 typename _Pred,
typename _Alloc>
1164 noexcept(noexcept(__x.swap(__y)))
1167 template<
typename _Key,
typename _Tp,
typename _Hash,
1168 typename _Pred,
typename _Alloc>
1172 {
return __x._M_base() == __y._M_base(); }
1174 template<
typename _Key,
typename _Tp,
typename _Hash,
1175 typename _Pred,
typename _Alloc>
1177 operator!=(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1178 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1179 {
return !(__x == __y); }
A standard container composed of unique keys (containing at most one of each key value) that associat...
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.
_Iterator & base() noexcept
Return the underlying iterator.
Primary class template hash.
Base class for constructing a safe unordered container type that tracks iterators that reference it...
Class std::unordered_multimap with safety/checking/debug instrumentation.
The standard allocator, as per [20.4].
#define __glibcxx_check_erase_range(_First, _Last)
One of the comparison functors.
#define __glibcxx_check_insert(_Position)
Safe class dealing with some allocator dependent operations.
Base class that supports tracking of iterators that reference a sequence.
Class std::unordered_map with safety/checking/debug instrumentation.
void _M_invalidate_if(_Predicate __pred)
_T2 second
first is a copy of the first object
void _M_invalidate_local_if(_Predicate __pred)
Struct holding two objects of arbitrary type.
_T1 first
second_type is the second bound type
A standard container composed of equivalent keys (possibly containing multiple of each key value) tha...
#define __glibcxx_check_erase(_Position)