29#ifndef _GLIBCXX_DEBUG_UNORDERED_MAP
30#define _GLIBCXX_DEBUG_UNORDERED_MAP 1
32#pragma GCC system_header
34#if __cplusplus < 201103L
38namespace std _GLIBCXX_VISIBILITY(default) {
namespace __debug {
39 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Pred,
42 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Pred,
44 class unordered_multimap;
54namespace std _GLIBCXX_VISIBILITY(default)
59 template<
typename _Key,
typename _Tp,
65 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
66 __gnu_debug::_Safe_unordered_container>,
67 public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
69 typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
79 template<
typename _ItT,
typename _SeqT,
typename _CatT>
80 friend class ::__gnu_debug::_Safe_iterator;
81 template<
typename _ItT,
typename _SeqT>
82 friend class ::__gnu_debug::_Safe_local_iterator;
87 _Base_ref(
const _Base& __r) : _M_ref(__r) { }
93 typedef typename _Base::size_type size_type;
94 typedef typename _Base::hasher hasher;
95 typedef typename _Base::key_equal key_equal;
96 typedef typename _Base::allocator_type allocator_type;
98 typedef typename _Base::key_type key_type;
99 typedef typename _Base::value_type value_type;
100 typedef typename _Base::mapped_type mapped_type;
102 typedef typename _Base::pointer pointer;
103 typedef typename _Base::const_pointer const_pointer;
104 typedef typename _Base::reference reference;
105 typedef typename _Base::const_reference const_reference;
114 typedef typename _Base::difference_type difference_type;
120 const hasher& __hf = hasher(),
121 const key_equal& __eql = key_equal(),
122 const allocator_type& __a = allocator_type())
123 :
_Base(__n, __hf, __eql, __a) { }
125 template<
typename _InputIterator>
128 const hasher& __hf = hasher(),
129 const key_equal& __eql = key_equal(),
130 const allocator_type& __a = allocator_type())
132 __glibcxx_check_valid_constructor_range(__first, __last)),
134 __hf, __eql, __a) { }
139 :
_Base(__x._M_ref) { }
148 const allocator_type& __a)
149 :
_Base(__umap, __a) { }
152 const allocator_type& __a)
159 const hasher& __hf = hasher(),
160 const key_equal& __eql = key_equal(),
161 const allocator_type& __a = allocator_type())
162 :
_Base(__l, __n, __hf, __eql, __a) { }
170 const allocator_type& __a)
174 template<
typename _InputIterator>
177 const allocator_type& __a)
178 :
unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
181 template<
typename _InputIterator>
185 const allocator_type& __a)
186 :
unordered_map(__first, __last, __n, __hf, key_equal(), __a)
191 const allocator_type& __a)
198 const allocator_type& __a)
213 _Base::operator=(__l);
214 this->_M_invalidate_all();
218 using _Base::get_allocator;
221 using _Base::max_size;
225 noexcept(
noexcept(declval<_Base&>().swap(__x)) )
235 this->_M_invalidate_all();
240 {
return { _Base::begin(),
this }; }
243 begin()
const noexcept
244 {
return { _Base::begin(),
this }; }
248 {
return { _Base::end(),
this }; }
252 {
return { _Base::end(),
this }; }
255 cbegin()
const noexcept
256 {
return { _Base::cbegin(),
this }; }
259 cend()
const noexcept
260 {
return { _Base::cend(),
this }; }
266 __glibcxx_check_bucket_index(__b);
267 return { _Base::begin(__b),
this };
273 __glibcxx_check_bucket_index(__b);
274 return { _Base::end(__b),
this };
278 begin(size_type __b)
const
280 __glibcxx_check_bucket_index(__b);
281 return { _Base::begin(__b),
this };
285 end(size_type __b)
const
287 __glibcxx_check_bucket_index(__b);
288 return { _Base::end(__b),
this };
292 cbegin(size_type __b)
const
294 __glibcxx_check_bucket_index(__b);
295 return { _Base::cbegin(__b),
this };
299 cend(size_type __b)
const
301 __glibcxx_check_bucket_index(__b);
302 return { _Base::cend(__b),
this };
305 using _Base::bucket_count;
306 using _Base::max_bucket_count;
310 bucket_size(size_type __b)
const
312 __glibcxx_check_bucket_index(__b);
313 return _Base::bucket_size(__b);
316 using _Base::load_factor;
319 max_load_factor()
const noexcept
320 {
return _Base::max_load_factor(); }
323 max_load_factor(
float __f)
325 __glibcxx_check_max_load_factor(__f);
326 _Base::max_load_factor(__f);
329 template<
typename... _Args>
331 emplace(_Args&&... __args)
333 size_type __bucket_count = this->bucket_count();
334 auto __res = _Base::emplace(std::forward<_Args>(__args)...);
335 _M_check_rehashed(__bucket_count);
336 return { { __res.first,
this }, __res.second };
339 template<
typename... _Args>
344 size_type __bucket_count = this->bucket_count();
345 auto __it = _Base::emplace_hint(__hint.
base(),
346 std::forward<_Args>(__args)...);
347 _M_check_rehashed(__bucket_count);
348 return { __it,
this };
352 insert(
const value_type& __obj)
354 size_type __bucket_count = this->bucket_count();
355 auto __res = _Base::insert(__obj);
356 _M_check_rehashed(__bucket_count);
357 return { { __res.first,
this }, __res.second };
363 insert(value_type&& __x)
365 size_type __bucket_count = this->bucket_count();
366 auto __res = _Base::insert(
std::move(__x));
367 _M_check_rehashed(__bucket_count);
368 return { { __res.first,
this }, __res.second };
371 template<
typename _Pair,
typename =
typename
373 _Pair&&>::value>::type>
375 insert(_Pair&& __obj)
377 size_type __bucket_count = this->bucket_count();
378 auto __res = _Base::insert(std::forward<_Pair>(__obj));
379 _M_check_rehashed(__bucket_count);
380 return { { __res.first,
this }, __res.second };
387 size_type __bucket_count = this->bucket_count();
388 auto __it = _Base::insert(__hint.
base(), __obj);
389 _M_check_rehashed(__bucket_count);
390 return { __it,
this };
399 size_type __bucket_count = this->bucket_count();
401 _M_check_rehashed(__bucket_count);
402 return { __it,
this };
405 template<
typename _Pair,
typename =
typename
407 _Pair&&>::value>::type>
412 size_type __bucket_count = this->bucket_count();
413 auto __it = _Base::insert(__hint.
base(), std::forward<_Pair>(__obj));
414 _M_check_rehashed(__bucket_count);
415 return { __it,
this };
421 size_type __bucket_count = this->bucket_count();
423 _M_check_rehashed(__bucket_count);
426 template<
typename _InputIterator>
428 insert(_InputIterator __first, _InputIterator __last)
431 __glibcxx_check_valid_range2(__first, __last, __dist);
432 size_type __bucket_count = this->bucket_count();
434 if (__dist.
second >= __gnu_debug::__dp_sign)
435 _Base::insert(__gnu_debug::__unsafe(__first),
436 __gnu_debug::__unsafe(__last));
438 _Base::insert(__first, __last);
440 _M_check_rehashed(__bucket_count);
443#if __cplusplus > 201402L
444 template <
typename... _Args>
446 try_emplace(
const key_type& __k, _Args&&... __args)
448 auto __res = _Base::try_emplace(__k,
449 std::forward<_Args>(__args)...);
450 return { { __res.first,
this }, __res.second };
453 template <
typename... _Args>
455 try_emplace(key_type&& __k, _Args&&... __args)
457 auto __res = _Base::try_emplace(
std::move(__k),
458 std::forward<_Args>(__args)...);
459 return { { __res.first,
this }, __res.second };
462 template <
typename... _Args>
468 return { _Base::try_emplace(__hint.
base(), __k,
469 std::forward<_Args>(__args)...),
473 template <
typename... _Args>
475 try_emplace(
const_iterator __hint, key_type&& __k, _Args&&... __args)
479 std::forward<_Args>(__args)...),
483 template <
typename _Obj>
485 insert_or_assign(
const key_type& __k, _Obj&& __obj)
487 auto __res = _Base::insert_or_assign(__k,
488 std::forward<_Obj>(__obj));
489 return { { __res.first,
this }, __res.second };
492 template <
typename _Obj>
494 insert_or_assign(key_type&& __k, _Obj&& __obj)
496 auto __res = _Base::insert_or_assign(
std::move(__k),
497 std::forward<_Obj>(__obj));
498 return { { __res.first,
this }, __res.second };
501 template <
typename _Obj>
507 return { _Base::insert_or_assign(__hint.
base(), __k,
508 std::forward<_Obj>(__obj)),
512 template <
typename _Obj>
514 insert_or_assign(
const_iterator __hint, key_type&& __k, _Obj&& __obj)
517 return { _Base::insert_or_assign(__hint.
base(),
std::move(__k),
518 std::forward<_Obj>(__obj)),
523#if __cplusplus > 201402L
524 using node_type =
typename _Base::node_type;
531 return _M_extract(__position.
base());
535 extract(
const key_type& __key)
537 const auto __position = _Base::find(__key);
538 if (__position != _Base::end())
539 return _M_extract(__position);
544 insert(node_type&& __nh)
546 auto __ret = _Base::insert(
std::move(__nh));
548 { { __ret.position,
this }, __ret.inserted,
std::move(__ret.node) };
555 return { _Base::insert(__hint.
base(),
std::move(__nh)),
this };
558 template<
typename _H2,
typename _P2>
563 = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
564 _Base::merge(__source);
567 template<
typename _H2,
typename _P2>
572 template<
typename _H2,
typename _P2>
577 = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
578 _Base::merge(__source);
581 template<
typename _H2,
typename _P2>
587 using _Base::hash_function;
591 find(
const key_type& __key)
592 {
return { _Base::find(__key),
this }; }
594#if __cplusplus > 201703L
595 template<
typename _Kt,
596 typename = std::__has_is_transparent_t<_Hash, _Kt>,
597 typename = std::__has_is_transparent_t<_Pred, _Kt>>
600 {
return { _Base::find(__k),
this }; }
604 find(
const key_type& __key)
const
605 {
return { _Base::find(__key),
this }; }
607#if __cplusplus > 201703L
608 template<
typename _Kt,
609 typename = std::__has_is_transparent_t<_Hash, _Kt>,
610 typename = std::__has_is_transparent_t<_Pred, _Kt>>
612 find(
const _Kt& __k)
const
613 {
return { _Base::find(__k),
this }; }
617#if __cplusplus > 201703L
618 using _Base::contains;
622 equal_range(
const key_type& __key)
624 auto __res = _Base::equal_range(__key);
625 return { { __res.first,
this }, { __res.second,
this } };
628#if __cplusplus > 201703L
629 template<
typename _Kt,
630 typename = std::__has_is_transparent_t<_Hash, _Kt>,
631 typename = std::__has_is_transparent_t<_Pred, _Kt>>
633 equal_range(
const _Kt& __k)
635 auto __res = _Base::equal_range(__k);
636 return { { __res.first,
this }, { __res.second,
this } };
641 equal_range(
const key_type& __key)
const
643 auto __res = _Base::equal_range(__key);
644 return { { __res.first,
this }, { __res.second,
this } };
647#if __cplusplus > 201703L
648 template<
typename _Kt,
649 typename = std::__has_is_transparent_t<_Hash, _Kt>,
650 typename = std::__has_is_transparent_t<_Pred, _Kt>>
652 equal_range(
const _Kt& __k)
const
654 auto __res = _Base::equal_range(__k);
655 return { { __res.first,
this }, { __res.second,
this } };
659 using _Base::operator[];
663 erase(
const key_type& __key)
666 auto __victim = _Base::find(__key);
667 if (__victim != _Base::end())
679 return { _M_erase(__it.
base()),
this };
685 __glibcxx_check_erase2(__it);
686 return _M_erase(__it);
693 return { _M_erase(__it.
base()),
this };
700 for (
auto __tmp = __first.base(); __tmp != __last.
base(); ++__tmp)
702 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
703 _M_message(__gnu_debug::__msg_valid_range)
704 ._M_iterator(__first,
"first")
705 ._M_iterator(__last,
"last"));
706 _M_invalidate(__tmp);
709 size_type __bucket_count = this->bucket_count();
710 auto __next = _Base::erase(__first.base(), __last.
base());
711 _M_check_rehashed(__bucket_count);
712 return { __next,
this };
716 using _Base::reserve;
719 _M_base()
noexcept {
return *
this; }
722 _M_base()
const noexcept {
return *
this; }
726 _M_check_rehashed(size_type __prev_count)
728 if (__prev_count != this->bucket_count())
729 this->_M_invalidate_all();
735 this->_M_invalidate_if(
737 this->_M_invalidate_local_if(
739 {
return __it == __victim; });
745 _M_invalidate(__victim);
746 size_type __bucket_count = this->bucket_count();
748 _M_check_rehashed(__bucket_count);
752#if __cplusplus > 201402L
756 _M_invalidate(__victim);
757 return _Base::extract(__victim);
762#if __cpp_deduction_guides >= 201606
764 template<
typename _InputIterator,
768 typename = _RequireInputIter<_InputIterator>,
769 typename = _RequireNotAllocatorOrIntegral<_Hash>,
770 typename = _RequireNotAllocator<_Pred>,
771 typename = _RequireAllocator<_Allocator>>
773 typename unordered_map<int, int>::size_type = {},
774 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
776 __iter_val_t<_InputIterator>,
777 _Hash, _Pred, _Allocator>;
779 template<
typename _Key,
typename _Tp,
typename _Hash = hash<_Key>,
780 typename _Pred = equal_to<_Key>,
781 typename _Allocator = allocator<pair<const _Key, _Tp>>,
782 typename = _RequireNotAllocatorOrIntegral<_Hash>,
783 typename = _RequireNotAllocator<_Pred>,
784 typename = _RequireAllocator<_Allocator>>
787 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
788 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
790 template<
typename _InputIterator,
typename _Allocator,
791 typename = _RequireInputIter<_InputIterator>,
792 typename = _RequireAllocator<_Allocator>>
793 unordered_map(_InputIterator, _InputIterator,
794 typename unordered_map<int, int>::size_type, _Allocator)
795 -> unordered_map<__iter_key_t<_InputIterator>,
796 __iter_val_t<_InputIterator>,
797 hash<__iter_key_t<_InputIterator>>,
798 equal_to<__iter_key_t<_InputIterator>>,
801 template<
typename _InputIterator,
typename _Allocator,
802 typename = _RequireInputIter<_InputIterator>,
803 typename = _RequireAllocator<_Allocator>>
804 unordered_map(_InputIterator, _InputIterator, _Allocator)
805 -> unordered_map<__iter_key_t<_InputIterator>,
806 __iter_val_t<_InputIterator>,
807 hash<__iter_key_t<_InputIterator>>,
808 equal_to<__iter_key_t<_InputIterator>>,
811 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
812 typename = _RequireInputIter<_InputIterator>,
813 typename = _RequireNotAllocatorOrIntegral<_Hash>,
814 typename = _RequireAllocator<_Allocator>>
815 unordered_map(_InputIterator, _InputIterator,
816 typename unordered_map<int, int>::size_type,
818 -> unordered_map<__iter_key_t<_InputIterator>,
819 __iter_val_t<_InputIterator>, _Hash,
820 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
822 template<
typename _Key,
typename _Tp,
typename _Allocator,
823 typename = _RequireAllocator<_Allocator>>
824 unordered_map(initializer_list<pair<_Key, _Tp>>,
825 typename unordered_map<int, int>::size_type,
827 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
829 template<
typename _Key,
typename _Tp,
typename _Allocator,
830 typename = _RequireAllocator<_Allocator>>
831 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
832 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
834 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Allocator,
835 typename = _RequireNotAllocatorOrIntegral<_Hash>,
836 typename = _RequireAllocator<_Allocator>>
837 unordered_map(initializer_list<pair<_Key, _Tp>>,
838 typename unordered_map<int, int>::size_type,
840 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
844 template<
typename _Key,
typename _Tp,
typename _Hash,
845 typename _Pred,
typename _Alloc>
847 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
848 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
849 noexcept(
noexcept(__x.swap(__y)))
852 template<
typename _Key,
typename _Tp,
typename _Hash,
853 typename _Pred,
typename _Alloc>
855 operator==(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
856 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
857 {
return __x._M_base() == __y._M_base(); }
859#if __cpp_impl_three_way_comparison < 201907L
860 template<
typename _Key,
typename _Tp,
typename _Hash,
861 typename _Pred,
typename _Alloc>
863 operator!=(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
864 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
865 {
return !(__x == __y); }
869 template<
typename _Key,
typename _Tp,
875 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
876 __gnu_debug::_Safe_unordered_container>,
877 public _GLIBCXX_STD_C::unordered_multimap<
878 _Key, _Tp, _Hash, _Pred, _Alloc>
880 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
881 _Pred, _Alloc>
_Base;
889 template<
typename _ItT,
typename _SeqT,
typename _CatT>
890 friend class ::__gnu_debug::_Safe_iterator;
891 template<
typename _ItT,
typename _SeqT>
892 friend class ::__gnu_debug::_Safe_local_iterator;
897 _Base_ref(
const _Base& __r) : _M_ref(__r) { }
903 typedef typename _Base::size_type size_type;
904 typedef typename _Base::hasher hasher;
905 typedef typename _Base::key_equal key_equal;
906 typedef typename _Base::allocator_type allocator_type;
908 typedef typename _Base::key_type key_type;
909 typedef typename _Base::value_type value_type;
910 typedef typename _Base::mapped_type mapped_type;
912 typedef typename _Base::pointer pointer;
913 typedef typename _Base::const_pointer const_pointer;
914 typedef typename _Base::reference reference;
915 typedef typename _Base::const_reference const_reference;
924 typedef typename _Base::difference_type difference_type;
930 const hasher& __hf = hasher(),
931 const key_equal& __eql = key_equal(),
932 const allocator_type& __a = allocator_type())
933 :
_Base(__n, __hf, __eql, __a) { }
935 template<
typename _InputIterator>
938 const hasher& __hf = hasher(),
939 const key_equal& __eql = key_equal(),
940 const allocator_type& __a = allocator_type())
942 __glibcxx_check_valid_constructor_range(__first, __last)),
944 __hf, __eql, __a) { }
949 :
_Base(__x._M_ref) { }
958 const allocator_type& __a)
959 :
_Base(__umap, __a) { }
962 const allocator_type& __a)
969 const hasher& __hf = hasher(),
970 const key_equal& __eql = key_equal(),
971 const allocator_type& __a = allocator_type())
972 :
_Base(__l, __n, __hf, __eql, __a) { }
979 const allocator_type& __a)
983 template<
typename _InputIterator>
986 const allocator_type& __a)
990 template<
typename _InputIterator>
992 size_type __n,
const hasher& __hf,
993 const allocator_type& __a)
999 const allocator_type& __a)
1004 size_type __n,
const hasher& __hf,
1005 const allocator_type& __a)
1020 _Base::operator=(__l);
1021 this->_M_invalidate_all();
1025 using _Base::get_allocator;
1028 using _Base::max_size;
1032 noexcept(
noexcept(declval<_Base&>().swap(__x)) )
1034 _Safe::_M_swap(__x);
1042 this->_M_invalidate_all();
1047 {
return { _Base::begin(),
this }; }
1050 begin()
const noexcept
1051 {
return { _Base::begin(),
this }; }
1055 {
return { _Base::end(),
this }; }
1058 end()
const noexcept
1059 {
return { _Base::end(),
this }; }
1062 cbegin()
const noexcept
1063 {
return { _Base::cbegin(),
this }; }
1066 cend()
const noexcept
1067 {
return { _Base::cend(),
this }; }
1071 begin(size_type __b)
1073 __glibcxx_check_bucket_index(__b);
1074 return { _Base::begin(__b),
this };
1080 __glibcxx_check_bucket_index(__b);
1081 return { _Base::end(__b),
this };
1085 begin(size_type __b)
const
1087 __glibcxx_check_bucket_index(__b);
1088 return { _Base::begin(__b),
this };
1092 end(size_type __b)
const
1094 __glibcxx_check_bucket_index(__b);
1095 return { _Base::end(__b),
this };
1099 cbegin(size_type __b)
const
1101 __glibcxx_check_bucket_index(__b);
1102 return { _Base::cbegin(__b),
this };
1106 cend(size_type __b)
const
1108 __glibcxx_check_bucket_index(__b);
1109 return { _Base::cend(__b),
this };
1112 using _Base::bucket_count;
1113 using _Base::max_bucket_count;
1114 using _Base::bucket;
1117 bucket_size(size_type __b)
const
1119 __glibcxx_check_bucket_index(__b);
1120 return _Base::bucket_size(__b);
1124 max_load_factor()
const noexcept
1125 {
return _Base::max_load_factor(); }
1128 max_load_factor(
float __f)
1130 __glibcxx_check_max_load_factor(__f);
1131 _Base::max_load_factor(__f);
1134 template<
typename... _Args>
1136 emplace(_Args&&... __args)
1138 size_type __bucket_count = this->bucket_count();
1139 auto __it = _Base::emplace(std::forward<_Args>(__args)...);
1140 _M_check_rehashed(__bucket_count);
1141 return { __it,
this };
1144 template<
typename... _Args>
1149 size_type __bucket_count = this->bucket_count();
1150 auto __it = _Base::emplace_hint(__hint.
base(),
1151 std::forward<_Args>(__args)...);
1152 _M_check_rehashed(__bucket_count);
1153 return { __it,
this };
1157 insert(
const value_type& __obj)
1159 size_type __bucket_count = this->bucket_count();
1160 auto __it = _Base::insert(__obj);
1161 _M_check_rehashed(__bucket_count);
1162 return { __it,
this };
1168 insert(value_type&& __x)
1170 size_type __bucket_count = this->bucket_count();
1171 auto __it = _Base::insert(
std::move(__x));
1172 _M_check_rehashed(__bucket_count);
1173 return { __it,
this };
1180 size_type __bucket_count = this->bucket_count();
1181 auto __it = _Base::insert(__hint.
base(), __obj);
1182 _M_check_rehashed(__bucket_count);
1183 return { __it,
this };
1192 size_type __bucket_count = this->bucket_count();
1194 _M_check_rehashed(__bucket_count);
1195 return { __it,
this };
1198 template<
typename _Pair,
typename =
typename
1200 _Pair&&>::value>::type>
1202 insert(_Pair&& __obj)
1204 size_type __bucket_count = this->bucket_count();
1205 auto __it = _Base::insert(std::forward<_Pair>(__obj));
1206 _M_check_rehashed(__bucket_count);
1207 return { __it,
this };
1210 template<
typename _Pair,
typename =
typename
1212 _Pair&&>::value>::type>
1217 size_type __bucket_count = this->bucket_count();
1218 auto __it = _Base::insert(__hint.
base(), std::forward<_Pair>(__obj));
1219 _M_check_rehashed(__bucket_count);
1220 return { __it,
this };
1225 { _Base::insert(__l); }
1227 template<
typename _InputIterator>
1229 insert(_InputIterator __first, _InputIterator __last)
1232 __glibcxx_check_valid_range2(__first, __last, __dist);
1233 size_type __bucket_count = this->bucket_count();
1235 if (__dist.
second >= __gnu_debug::__dp_sign)
1236 _Base::insert(__gnu_debug::__unsafe(__first),
1237 __gnu_debug::__unsafe(__last));
1239 _Base::insert(__first, __last);
1241 _M_check_rehashed(__bucket_count);
1244#if __cplusplus > 201402L
1245 using node_type =
typename _Base::node_type;
1251 return _M_extract(__position.
base());
1255 extract(
const key_type& __key)
1257 const auto __position = _Base::find(__key);
1258 if (__position != _Base::end())
1259 return _M_extract(__position);
1264 insert(node_type&& __nh)
1265 {
return { _Base::insert(
std::move(__nh)),
this }; }
1271 return { _Base::insert(__hint.
base(),
std::move(__nh)),
this };
1274 template<
typename _H2,
typename _P2>
1279 = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
1280 _Base::merge(__source);
1283 template<
typename _H2,
typename _P2>
1286 { merge(__source); }
1288 template<
typename _H2,
typename _P2>
1293 = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
1294 _Base::merge(__source);
1297 template<
typename _H2,
typename _P2>
1300 { merge(__source); }
1303 using _Base::hash_function;
1304 using _Base::key_eq;
1307 find(
const key_type& __key)
1308 {
return { _Base::find(__key),
this }; }
1310#if __cplusplus > 201703L
1311 template<
typename _Kt,
1312 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1313 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1315 find(
const _Kt& __k)
1316 {
return { _Base::find(__k),
this }; }
1320 find(
const key_type& __key)
const
1321 {
return { _Base::find(__key),
this }; }
1323#if __cplusplus > 201703L
1324 template<
typename _Kt,
1325 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1326 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1328 find(
const _Kt& __k)
const
1329 {
return { _Base::find(__k),
this }; }
1333#if __cplusplus > 201703L
1334 using _Base::contains;
1338 equal_range(
const key_type& __key)
1340 auto __res = _Base::equal_range(__key);
1341 return { { __res.first,
this }, { __res.second,
this } };
1344#if __cplusplus > 201703L
1345 template<
typename _Kt,
1346 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1347 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1349 equal_range(
const _Kt& __k)
1351 auto __res = _Base::equal_range(__k);
1352 return { { __res.first,
this }, { __res.second,
this } };
1357 equal_range(
const key_type& __key)
const
1359 auto __res = _Base::equal_range(__key);
1360 return { { __res.first,
this }, { __res.second,
this } };
1363#if __cplusplus > 201703L
1364 template<
typename _Kt,
1365 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1366 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1368 equal_range(
const _Kt& __k)
const
1370 auto __res = _Base::equal_range(__k);
1371 return { { __res.first,
this }, { __res.second,
this } };
1376 erase(
const key_type& __key)
1379 size_type __bucket_count = this->bucket_count();
1380 auto __pair = _Base::equal_range(__key);
1381 for (
auto __victim = __pair.first; __victim != __pair.second;)
1383 _M_invalidate(__victim);
1384 __victim = _Base::erase(__victim);
1388 _M_check_rehashed(__bucket_count);
1396 return { _M_erase(__it.
base()),
this };
1402 __glibcxx_check_erase2(__it);
1403 return _M_erase(__it);
1410 return { _M_erase(__it.
base()),
this };
1417 for (
auto __tmp = __first.base(); __tmp != __last.
base(); ++__tmp)
1419 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1420 _M_message(__gnu_debug::__msg_valid_range)
1421 ._M_iterator(__first,
"first")
1422 ._M_iterator(__last,
"last"));
1423 _M_invalidate(__tmp);
1426 size_type __bucket_count = this->bucket_count();
1427 auto __next = _Base::erase(__first.base(), __last.
base());
1428 _M_check_rehashed(__bucket_count);
1429 return { __next,
this };
1432 using _Base::rehash;
1433 using _Base::reserve;
1436 _M_base()
noexcept {
return *
this; }
1439 _M_base()
const noexcept {
return *
this; }
1443 _M_check_rehashed(size_type __prev_count)
1445 if (__prev_count != this->bucket_count())
1446 this->_M_invalidate_all();
1452 this->_M_invalidate_if(
1454 this->_M_invalidate_local_if(
1456 {
return __it == __victim; });
1462 _M_invalidate(__victim);
1463 size_type __bucket_count = this->bucket_count();
1465 _M_check_rehashed(__bucket_count);
1469#if __cplusplus > 201402L
1473 _M_invalidate(__victim);
1474 return _Base::extract(__victim);
1479#if __cpp_deduction_guides >= 201606
1481 template<
typename _InputIterator,
1485 typename = _RequireInputIter<_InputIterator>,
1486 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1487 typename = _RequireNotAllocator<_Pred>,
1488 typename = _RequireAllocator<_Allocator>>
1490 unordered_multimap<int, int>::size_type = {},
1491 _Hash = _Hash(), _Pred = _Pred(),
1492 _Allocator = _Allocator())
1494 __iter_val_t<_InputIterator>, _Hash, _Pred,
1497 template<
typename _Key,
typename _Tp,
typename _Hash = hash<_Key>,
1498 typename _Pred = equal_to<_Key>,
1499 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1500 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1501 typename = _RequireNotAllocator<_Pred>,
1502 typename = _RequireAllocator<_Allocator>>
1505 _Hash = _Hash(), _Pred = _Pred(),
1506 _Allocator = _Allocator())
1507 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
1509 template<
typename _InputIterator,
typename _Allocator,
1510 typename = _RequireInputIter<_InputIterator>,
1511 typename = _RequireAllocator<_Allocator>>
1512 unordered_multimap(_InputIterator, _InputIterator,
1513 unordered_multimap<int, int>::size_type, _Allocator)
1514 -> unordered_multimap<__iter_key_t<_InputIterator>,
1515 __iter_val_t<_InputIterator>,
1516 hash<__iter_key_t<_InputIterator>>,
1517 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1519 template<
typename _InputIterator,
typename _Allocator,
1520 typename = _RequireInputIter<_InputIterator>,
1521 typename = _RequireAllocator<_Allocator>>
1522 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
1523 -> unordered_multimap<__iter_key_t<_InputIterator>,
1524 __iter_val_t<_InputIterator>,
1525 hash<__iter_key_t<_InputIterator>>,
1526 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1528 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
1529 typename = _RequireInputIter<_InputIterator>,
1530 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1531 typename = _RequireAllocator<_Allocator>>
1532 unordered_multimap(_InputIterator, _InputIterator,
1533 unordered_multimap<int, int>::size_type, _Hash,
1535 -> unordered_multimap<__iter_key_t<_InputIterator>,
1536 __iter_val_t<_InputIterator>, _Hash,
1537 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1539 template<
typename _Key,
typename _Tp,
typename _Allocator,
1540 typename = _RequireAllocator<_Allocator>>
1541 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1542 unordered_multimap<int, int>::size_type,
1544 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1546 template<
typename _Key,
typename _Tp,
typename _Allocator,
1547 typename = _RequireAllocator<_Allocator>>
1548 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
1549 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1551 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Allocator,
1552 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1553 typename = _RequireAllocator<_Allocator>>
1554 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1555 unordered_multimap<int, int>::size_type,
1557 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1561 template<
typename _Key,
typename _Tp,
typename _Hash,
1562 typename _Pred,
typename _Alloc>
1564 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1565 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1566 noexcept(
noexcept(__x.swap(__y)))
1569 template<
typename _Key,
typename _Tp,
typename _Hash,
1570 typename _Pred,
typename _Alloc>
1572 operator==(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1573 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1574 {
return __x._M_base() == __y._M_base(); }
1576#if __cpp_impl_three_way_comparison < 201907L
1577 template<
typename _Key,
typename _Tp,
typename _Hash,
1578 typename _Pred,
typename _Alloc>
1580 operator!=(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1581 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1582 {
return !(__x == __y); }
#define __glibcxx_check_insert(_Position)
#define __glibcxx_check_erase_range(_First, _Last)
#define __glibcxx_check_erase(_Position)
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
ISO C++ entities toplevel namespace is std.
constexpr _Iterator __base(_Iterator __it)
Primary class template hash.
Define a member typedef type only if a boolean constant is true.
The standard allocator, as per C++03 [20.4.1].
constexpr _Iterator & base() noexcept
Return the underlying iterator.
Return type of insert(node_handle&&) on unique maps/sets.
One of the comparison functors.
Struct holding two objects of arbitrary type.
_T2 second
The second member.
A standard container composed of equivalent keys (possibly containing multiple of each key value) tha...
_Hashtable::size_type size_type
Iterator-related typedefs.
A standard container composed of unique keys (containing at most one of each key value) that associat...
_Hashtable::size_type size_type
Iterator-related typedefs.
Safe class dealing with some allocator dependent operations.
Base class for constructing a safe unordered container type that tracks iterators that reference it.
Class std::unordered_map with safety/checking/debug instrumentation.
Class std::unordered_multimap with safety/checking/debug instrumentation.