29#ifndef _GLIBCXX_DEBUG_UNORDERED_MAP
30#define _GLIBCXX_DEBUG_UNORDERED_MAP 1
33#pragma GCC system_header
36#if __cplusplus < 201103L
40namespace std _GLIBCXX_VISIBILITY(default) {
namespace __debug {
41 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Pred,
44 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Pred,
46 class unordered_multimap;
56namespace std _GLIBCXX_VISIBILITY(default)
61 template<
typename _Key,
typename _Tp,
67 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
68 __gnu_debug::_Safe_unordered_container>,
69 public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
71 typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
81 template<
typename _ItT,
typename _SeqT,
typename _CatT>
82 friend class ::__gnu_debug::_Safe_iterator;
83 template<
typename _ItT,
typename _SeqT>
84 friend class ::__gnu_debug::_Safe_local_iterator;
89 _Base_ref(
const _Base& __r) : _M_ref(__r) { }
95 typedef typename _Base::size_type size_type;
96 typedef typename _Base::hasher hasher;
97 typedef typename _Base::key_equal key_equal;
98 typedef typename _Base::allocator_type allocator_type;
100 typedef typename _Base::key_type key_type;
101 typedef typename _Base::value_type value_type;
102 typedef typename _Base::mapped_type mapped_type;
104 typedef typename _Base::pointer pointer;
105 typedef typename _Base::const_pointer const_pointer;
106 typedef typename _Base::reference reference;
107 typedef typename _Base::const_reference const_reference;
116 typedef typename _Base::difference_type difference_type;
122 const hasher& __hf = hasher(),
123 const key_equal& __eql = key_equal(),
124 const allocator_type& __a = allocator_type())
125 :
_Base(__n, __hf, __eql, __a) { }
127 template<
typename _InputIterator>
130 const hasher& __hf = hasher(),
131 const key_equal& __eql = key_equal(),
132 const allocator_type& __a = allocator_type())
134 __glibcxx_check_valid_constructor_range(__first, __last)),
136 __hf, __eql, __a) { }
141 :
_Base(__x._M_ref) { }
150 const allocator_type& __a)
151 :
_Base(__umap, __a) { }
154 const allocator_type& __a)
161 const hasher& __hf = hasher(),
162 const key_equal& __eql = key_equal(),
163 const allocator_type& __a = allocator_type())
164 :
_Base(__l, __n, __hf, __eql, __a) { }
172 const allocator_type& __a)
176 template<
typename _InputIterator>
179 const allocator_type& __a)
180 :
unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
183 template<
typename _InputIterator>
187 const allocator_type& __a)
188 :
unordered_map(__first, __last, __n, __hf, key_equal(), __a)
193 const allocator_type& __a)
200 const allocator_type& __a)
215 _Base::operator=(__l);
216 this->_M_invalidate_all();
220 using _Base::get_allocator;
223 using _Base::max_size;
227 noexcept(
noexcept(declval<_Base&>().swap(__x)) )
237 this->_M_invalidate_all();
242 {
return { _Base::begin(),
this }; }
245 begin()
const noexcept
246 {
return { _Base::begin(),
this }; }
250 {
return { _Base::end(),
this }; }
254 {
return { _Base::end(),
this }; }
257 cbegin()
const noexcept
258 {
return { _Base::cbegin(),
this }; }
261 cend()
const noexcept
262 {
return { _Base::cend(),
this }; }
268 __glibcxx_check_bucket_index(__b);
269 return { _Base::begin(__b),
this };
275 __glibcxx_check_bucket_index(__b);
276 return { _Base::end(__b),
this };
280 begin(size_type __b)
const
282 __glibcxx_check_bucket_index(__b);
283 return { _Base::begin(__b),
this };
287 end(size_type __b)
const
289 __glibcxx_check_bucket_index(__b);
290 return { _Base::end(__b),
this };
294 cbegin(size_type __b)
const
296 __glibcxx_check_bucket_index(__b);
297 return { _Base::cbegin(__b),
this };
301 cend(size_type __b)
const
303 __glibcxx_check_bucket_index(__b);
304 return { _Base::cend(__b),
this };
307 using _Base::bucket_count;
308 using _Base::max_bucket_count;
312 bucket_size(size_type __b)
const
314 __glibcxx_check_bucket_index(__b);
315 return _Base::bucket_size(__b);
318 using _Base::load_factor;
321 max_load_factor()
const noexcept
322 {
return _Base::max_load_factor(); }
325 max_load_factor(
float __f)
327 __glibcxx_check_max_load_factor(__f);
328 _Base::max_load_factor(__f);
331 template<
typename... _Args>
333 emplace(_Args&&... __args)
335 size_type __bucket_count = this->bucket_count();
336 auto __res = _Base::emplace(std::forward<_Args>(__args)...);
337 _M_check_rehashed(__bucket_count);
338 return { { __res.first,
this }, __res.second };
341 template<
typename... _Args>
346 size_type __bucket_count = this->bucket_count();
347 auto __it = _Base::emplace_hint(__hint.
base(),
348 std::forward<_Args>(__args)...);
349 _M_check_rehashed(__bucket_count);
350 return { __it,
this };
354 insert(
const value_type& __obj)
356 size_type __bucket_count = this->bucket_count();
357 auto __res = _Base::insert(__obj);
358 _M_check_rehashed(__bucket_count);
359 return { { __res.first,
this }, __res.second };
365 insert(value_type&& __x)
367 size_type __bucket_count = this->bucket_count();
368 auto __res = _Base::insert(
std::move(__x));
369 _M_check_rehashed(__bucket_count);
370 return { { __res.first,
this }, __res.second };
373 template<
typename _Pair,
typename =
typename
375 _Pair&&>::value>::type>
377 insert(_Pair&& __obj)
379 size_type __bucket_count = this->bucket_count();
380 auto __res = _Base::insert(std::forward<_Pair>(__obj));
381 _M_check_rehashed(__bucket_count);
382 return { { __res.first,
this }, __res.second };
389 size_type __bucket_count = this->bucket_count();
390 auto __it = _Base::insert(__hint.
base(), __obj);
391 _M_check_rehashed(__bucket_count);
392 return { __it,
this };
401 size_type __bucket_count = this->bucket_count();
403 _M_check_rehashed(__bucket_count);
404 return { __it,
this };
407 template<
typename _Pair,
typename =
typename
409 _Pair&&>::value>::type>
414 size_type __bucket_count = this->bucket_count();
415 auto __it = _Base::insert(__hint.
base(), std::forward<_Pair>(__obj));
416 _M_check_rehashed(__bucket_count);
417 return { __it,
this };
423 size_type __bucket_count = this->bucket_count();
425 _M_check_rehashed(__bucket_count);
428 template<
typename _InputIterator>
430 insert(_InputIterator __first, _InputIterator __last)
433 __glibcxx_check_valid_range2(__first, __last, __dist);
434 size_type __bucket_count = this->bucket_count();
436 if (__dist.
second >= __gnu_debug::__dp_sign)
437 _Base::insert(__gnu_debug::__unsafe(__first),
438 __gnu_debug::__unsafe(__last));
440 _Base::insert(__first, __last);
442 _M_check_rehashed(__bucket_count);
445#ifdef __glibcxx_unordered_map_try_emplace
446 template <
typename... _Args>
448 try_emplace(
const key_type& __k, _Args&&... __args)
450 auto __res = _Base::try_emplace(__k,
451 std::forward<_Args>(__args)...);
452 return { { __res.first,
this }, __res.second };
455 template <
typename... _Args>
457 try_emplace(key_type&& __k, _Args&&... __args)
459 auto __res = _Base::try_emplace(
std::move(__k),
460 std::forward<_Args>(__args)...);
461 return { { __res.first,
this }, __res.second };
464 template <
typename... _Args>
470 return { _Base::try_emplace(__hint.
base(), __k,
471 std::forward<_Args>(__args)...),
475 template <
typename... _Args>
477 try_emplace(
const_iterator __hint, key_type&& __k, _Args&&... __args)
481 std::forward<_Args>(__args)...),
485 template <
typename _Obj>
487 insert_or_assign(
const key_type& __k, _Obj&& __obj)
489 auto __res = _Base::insert_or_assign(__k,
490 std::forward<_Obj>(__obj));
491 return { { __res.first,
this }, __res.second };
494 template <
typename _Obj>
496 insert_or_assign(key_type&& __k, _Obj&& __obj)
498 auto __res = _Base::insert_or_assign(
std::move(__k),
499 std::forward<_Obj>(__obj));
500 return { { __res.first,
this }, __res.second };
503 template <
typename _Obj>
509 return { _Base::insert_or_assign(__hint.
base(), __k,
510 std::forward<_Obj>(__obj)),
514 template <
typename _Obj>
516 insert_or_assign(
const_iterator __hint, key_type&& __k, _Obj&& __obj)
519 return { _Base::insert_or_assign(__hint.
base(),
std::move(__k),
520 std::forward<_Obj>(__obj)),
525#if __cplusplus > 201402L
526 using node_type =
typename _Base::node_type;
533 return _M_extract(__position.
base());
537 extract(
const key_type& __key)
539 const auto __position = _Base::find(__key);
540 if (__position != _Base::end())
541 return _M_extract(__position);
546 insert(node_type&& __nh)
548 auto __ret = _Base::insert(
std::move(__nh));
550 { { __ret.position,
this }, __ret.inserted,
std::move(__ret.node) };
557 return { _Base::insert(__hint.
base(),
std::move(__nh)),
this };
560 template<
typename _H2,
typename _P2>
565 = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
566 _Base::merge(__source);
569 template<
typename _H2,
typename _P2>
574 template<
typename _H2,
typename _P2>
579 = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
580 _Base::merge(__source);
583 template<
typename _H2,
typename _P2>
589 using _Base::hash_function;
593 find(
const key_type& __key)
594 {
return { _Base::find(__key),
this }; }
596#if __cplusplus > 201703L
597 template<
typename _Kt,
598 typename = std::__has_is_transparent_t<_Hash, _Kt>,
599 typename = std::__has_is_transparent_t<_Pred, _Kt>>
602 {
return { _Base::find(__k),
this }; }
606 find(
const key_type& __key)
const
607 {
return { _Base::find(__key),
this }; }
609#if __cplusplus > 201703L
610 template<
typename _Kt,
611 typename = std::__has_is_transparent_t<_Hash, _Kt>,
612 typename = std::__has_is_transparent_t<_Pred, _Kt>>
614 find(
const _Kt& __k)
const
615 {
return { _Base::find(__k),
this }; }
619#if __cplusplus > 201703L
620 using _Base::contains;
624 equal_range(
const key_type& __key)
626 auto __res = _Base::equal_range(__key);
627 return { { __res.first,
this }, { __res.second,
this } };
630#if __cplusplus > 201703L
631 template<
typename _Kt,
632 typename = std::__has_is_transparent_t<_Hash, _Kt>,
633 typename = std::__has_is_transparent_t<_Pred, _Kt>>
635 equal_range(
const _Kt& __k)
637 auto __res = _Base::equal_range(__k);
638 return { { __res.first,
this }, { __res.second,
this } };
643 equal_range(
const key_type& __key)
const
645 auto __res = _Base::equal_range(__key);
646 return { { __res.first,
this }, { __res.second,
this } };
649#if __cplusplus > 201703L
650 template<
typename _Kt,
651 typename = std::__has_is_transparent_t<_Hash, _Kt>,
652 typename = std::__has_is_transparent_t<_Pred, _Kt>>
654 equal_range(
const _Kt& __k)
const
656 auto __res = _Base::equal_range(__k);
657 return { { __res.first,
this }, { __res.second,
this } };
661 using _Base::operator[];
665 erase(
const key_type& __key)
668 auto __victim = _Base::find(__key);
669 if (__victim != _Base::end())
681 return { _M_erase(__it.
base()),
this };
687 __glibcxx_check_erase2(__it);
688 return _M_erase(__it);
695 return { _M_erase(__it.
base()),
this };
702 for (
auto __tmp = __first.base(); __tmp != __last.
base(); ++__tmp)
704 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
705 _M_message(__gnu_debug::__msg_valid_range)
706 ._M_iterator(__first,
"first")
707 ._M_iterator(__last,
"last"));
708 _M_invalidate(__tmp);
711 size_type __bucket_count = this->bucket_count();
712 auto __next = _Base::erase(__first.base(), __last.
base());
713 _M_check_rehashed(__bucket_count);
714 return { __next,
this };
718 using _Base::reserve;
721 _M_base()
noexcept {
return *
this; }
724 _M_base()
const noexcept {
return *
this; }
728 _M_check_rehashed(size_type __prev_count)
730 if (__prev_count != this->bucket_count())
731 this->_M_invalidate_all();
737 this->_M_invalidate_if(
739 this->_M_invalidate_local_if(
741 {
return __it == __victim; });
747 _M_invalidate(__victim);
748 size_type __bucket_count = this->bucket_count();
750 _M_check_rehashed(__bucket_count);
754#if __cplusplus > 201402L
758 _M_invalidate(__victim);
759 return _Base::extract(__victim);
764#if __cpp_deduction_guides >= 201606
766 template<
typename _InputIterator,
770 typename = _RequireInputIter<_InputIterator>,
771 typename = _RequireNotAllocatorOrIntegral<_Hash>,
772 typename = _RequireNotAllocator<_Pred>,
773 typename = _RequireAllocator<_Allocator>>
775 typename unordered_map<int, int>::size_type = {},
776 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
778 __iter_val_t<_InputIterator>,
779 _Hash, _Pred, _Allocator>;
781 template<
typename _Key,
typename _Tp,
typename _Hash = hash<_Key>,
782 typename _Pred = equal_to<_Key>,
783 typename _Allocator = allocator<pair<const _Key, _Tp>>,
784 typename = _RequireNotAllocatorOrIntegral<_Hash>,
785 typename = _RequireNotAllocator<_Pred>,
786 typename = _RequireAllocator<_Allocator>>
789 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
790 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
792 template<
typename _InputIterator,
typename _Allocator,
793 typename = _RequireInputIter<_InputIterator>,
794 typename = _RequireAllocator<_Allocator>>
795 unordered_map(_InputIterator, _InputIterator,
796 typename unordered_map<int, int>::size_type, _Allocator)
797 -> unordered_map<__iter_key_t<_InputIterator>,
798 __iter_val_t<_InputIterator>,
799 hash<__iter_key_t<_InputIterator>>,
800 equal_to<__iter_key_t<_InputIterator>>,
803 template<
typename _InputIterator,
typename _Allocator,
804 typename = _RequireInputIter<_InputIterator>,
805 typename = _RequireAllocator<_Allocator>>
806 unordered_map(_InputIterator, _InputIterator, _Allocator)
807 -> unordered_map<__iter_key_t<_InputIterator>,
808 __iter_val_t<_InputIterator>,
809 hash<__iter_key_t<_InputIterator>>,
810 equal_to<__iter_key_t<_InputIterator>>,
813 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
814 typename = _RequireInputIter<_InputIterator>,
815 typename = _RequireNotAllocatorOrIntegral<_Hash>,
816 typename = _RequireAllocator<_Allocator>>
817 unordered_map(_InputIterator, _InputIterator,
818 typename unordered_map<int, int>::size_type,
820 -> unordered_map<__iter_key_t<_InputIterator>,
821 __iter_val_t<_InputIterator>, _Hash,
822 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
824 template<
typename _Key,
typename _Tp,
typename _Allocator,
825 typename = _RequireAllocator<_Allocator>>
826 unordered_map(initializer_list<pair<_Key, _Tp>>,
827 typename unordered_map<int, int>::size_type,
829 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
831 template<
typename _Key,
typename _Tp,
typename _Allocator,
832 typename = _RequireAllocator<_Allocator>>
833 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
834 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
836 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Allocator,
837 typename = _RequireNotAllocatorOrIntegral<_Hash>,
838 typename = _RequireAllocator<_Allocator>>
839 unordered_map(initializer_list<pair<_Key, _Tp>>,
840 typename unordered_map<int, int>::size_type,
842 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
846 template<
typename _Key,
typename _Tp,
typename _Hash,
847 typename _Pred,
typename _Alloc>
849 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
850 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
851 noexcept(
noexcept(__x.swap(__y)))
854 template<
typename _Key,
typename _Tp,
typename _Hash,
855 typename _Pred,
typename _Alloc>
857 operator==(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
858 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
859 {
return __x._M_base() == __y._M_base(); }
861#if __cpp_impl_three_way_comparison < 201907L
862 template<
typename _Key,
typename _Tp,
typename _Hash,
863 typename _Pred,
typename _Alloc>
865 operator!=(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
866 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
867 {
return !(__x == __y); }
871 template<
typename _Key,
typename _Tp,
877 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
878 __gnu_debug::_Safe_unordered_container>,
879 public _GLIBCXX_STD_C::unordered_multimap<
880 _Key, _Tp, _Hash, _Pred, _Alloc>
882 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
883 _Pred, _Alloc>
_Base;
891 template<
typename _ItT,
typename _SeqT,
typename _CatT>
892 friend class ::__gnu_debug::_Safe_iterator;
893 template<
typename _ItT,
typename _SeqT>
894 friend class ::__gnu_debug::_Safe_local_iterator;
899 _Base_ref(
const _Base& __r) : _M_ref(__r) { }
905 typedef typename _Base::size_type size_type;
906 typedef typename _Base::hasher hasher;
907 typedef typename _Base::key_equal key_equal;
908 typedef typename _Base::allocator_type allocator_type;
910 typedef typename _Base::key_type key_type;
911 typedef typename _Base::value_type value_type;
912 typedef typename _Base::mapped_type mapped_type;
914 typedef typename _Base::pointer pointer;
915 typedef typename _Base::const_pointer const_pointer;
916 typedef typename _Base::reference reference;
917 typedef typename _Base::const_reference const_reference;
926 typedef typename _Base::difference_type difference_type;
932 const hasher& __hf = hasher(),
933 const key_equal& __eql = key_equal(),
934 const allocator_type& __a = allocator_type())
935 :
_Base(__n, __hf, __eql, __a) { }
937 template<
typename _InputIterator>
940 const hasher& __hf = hasher(),
941 const key_equal& __eql = key_equal(),
942 const allocator_type& __a = allocator_type())
944 __glibcxx_check_valid_constructor_range(__first, __last)),
946 __hf, __eql, __a) { }
951 :
_Base(__x._M_ref) { }
960 const allocator_type& __a)
961 :
_Base(__umap, __a) { }
964 const allocator_type& __a)
971 const hasher& __hf = hasher(),
972 const key_equal& __eql = key_equal(),
973 const allocator_type& __a = allocator_type())
974 :
_Base(__l, __n, __hf, __eql, __a) { }
981 const allocator_type& __a)
985 template<
typename _InputIterator>
988 const allocator_type& __a)
992 template<
typename _InputIterator>
994 size_type __n,
const hasher& __hf,
995 const allocator_type& __a)
1001 const allocator_type& __a)
1006 size_type __n,
const hasher& __hf,
1007 const allocator_type& __a)
1022 _Base::operator=(__l);
1023 this->_M_invalidate_all();
1027 using _Base::get_allocator;
1030 using _Base::max_size;
1034 noexcept(
noexcept(declval<_Base&>().swap(__x)) )
1036 _Safe::_M_swap(__x);
1044 this->_M_invalidate_all();
1049 {
return { _Base::begin(),
this }; }
1052 begin()
const noexcept
1053 {
return { _Base::begin(),
this }; }
1057 {
return { _Base::end(),
this }; }
1060 end()
const noexcept
1061 {
return { _Base::end(),
this }; }
1064 cbegin()
const noexcept
1065 {
return { _Base::cbegin(),
this }; }
1068 cend()
const noexcept
1069 {
return { _Base::cend(),
this }; }
1073 begin(size_type __b)
1075 __glibcxx_check_bucket_index(__b);
1076 return { _Base::begin(__b),
this };
1082 __glibcxx_check_bucket_index(__b);
1083 return { _Base::end(__b),
this };
1087 begin(size_type __b)
const
1089 __glibcxx_check_bucket_index(__b);
1090 return { _Base::begin(__b),
this };
1094 end(size_type __b)
const
1096 __glibcxx_check_bucket_index(__b);
1097 return { _Base::end(__b),
this };
1101 cbegin(size_type __b)
const
1103 __glibcxx_check_bucket_index(__b);
1104 return { _Base::cbegin(__b),
this };
1108 cend(size_type __b)
const
1110 __glibcxx_check_bucket_index(__b);
1111 return { _Base::cend(__b),
this };
1114 using _Base::bucket_count;
1115 using _Base::max_bucket_count;
1116 using _Base::bucket;
1119 bucket_size(size_type __b)
const
1121 __glibcxx_check_bucket_index(__b);
1122 return _Base::bucket_size(__b);
1126 max_load_factor()
const noexcept
1127 {
return _Base::max_load_factor(); }
1130 max_load_factor(
float __f)
1132 __glibcxx_check_max_load_factor(__f);
1133 _Base::max_load_factor(__f);
1136 template<
typename... _Args>
1138 emplace(_Args&&... __args)
1140 size_type __bucket_count = this->bucket_count();
1141 auto __it = _Base::emplace(std::forward<_Args>(__args)...);
1142 _M_check_rehashed(__bucket_count);
1143 return { __it,
this };
1146 template<
typename... _Args>
1151 size_type __bucket_count = this->bucket_count();
1152 auto __it = _Base::emplace_hint(__hint.
base(),
1153 std::forward<_Args>(__args)...);
1154 _M_check_rehashed(__bucket_count);
1155 return { __it,
this };
1159 insert(
const value_type& __obj)
1161 size_type __bucket_count = this->bucket_count();
1162 auto __it = _Base::insert(__obj);
1163 _M_check_rehashed(__bucket_count);
1164 return { __it,
this };
1170 insert(value_type&& __x)
1172 size_type __bucket_count = this->bucket_count();
1173 auto __it = _Base::insert(
std::move(__x));
1174 _M_check_rehashed(__bucket_count);
1175 return { __it,
this };
1182 size_type __bucket_count = this->bucket_count();
1183 auto __it = _Base::insert(__hint.
base(), __obj);
1184 _M_check_rehashed(__bucket_count);
1185 return { __it,
this };
1194 size_type __bucket_count = this->bucket_count();
1196 _M_check_rehashed(__bucket_count);
1197 return { __it,
this };
1200 template<
typename _Pair,
typename =
typename
1202 _Pair&&>::value>::type>
1204 insert(_Pair&& __obj)
1206 size_type __bucket_count = this->bucket_count();
1207 auto __it = _Base::insert(std::forward<_Pair>(__obj));
1208 _M_check_rehashed(__bucket_count);
1209 return { __it,
this };
1212 template<
typename _Pair,
typename =
typename
1214 _Pair&&>::value>::type>
1219 size_type __bucket_count = this->bucket_count();
1220 auto __it = _Base::insert(__hint.
base(), std::forward<_Pair>(__obj));
1221 _M_check_rehashed(__bucket_count);
1222 return { __it,
this };
1227 { _Base::insert(__l); }
1229 template<
typename _InputIterator>
1231 insert(_InputIterator __first, _InputIterator __last)
1234 __glibcxx_check_valid_range2(__first, __last, __dist);
1235 size_type __bucket_count = this->bucket_count();
1237 if (__dist.
second >= __gnu_debug::__dp_sign)
1238 _Base::insert(__gnu_debug::__unsafe(__first),
1239 __gnu_debug::__unsafe(__last));
1241 _Base::insert(__first, __last);
1243 _M_check_rehashed(__bucket_count);
1246#if __cplusplus > 201402L
1247 using node_type =
typename _Base::node_type;
1253 return _M_extract(__position.
base());
1257 extract(
const key_type& __key)
1259 const auto __position = _Base::find(__key);
1260 if (__position != _Base::end())
1261 return _M_extract(__position);
1266 insert(node_type&& __nh)
1267 {
return { _Base::insert(
std::move(__nh)),
this }; }
1273 return { _Base::insert(__hint.
base(),
std::move(__nh)),
this };
1276 template<
typename _H2,
typename _P2>
1281 = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
1282 _Base::merge(__source);
1285 template<
typename _H2,
typename _P2>
1288 { merge(__source); }
1290 template<
typename _H2,
typename _P2>
1295 = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
1296 _Base::merge(__source);
1299 template<
typename _H2,
typename _P2>
1302 { merge(__source); }
1305 using _Base::hash_function;
1306 using _Base::key_eq;
1309 find(
const key_type& __key)
1310 {
return { _Base::find(__key),
this }; }
1312#if __cplusplus > 201703L
1313 template<
typename _Kt,
1314 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1315 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1317 find(
const _Kt& __k)
1318 {
return { _Base::find(__k),
this }; }
1322 find(
const key_type& __key)
const
1323 {
return { _Base::find(__key),
this }; }
1325#if __cplusplus > 201703L
1326 template<
typename _Kt,
1327 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1328 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1330 find(
const _Kt& __k)
const
1331 {
return { _Base::find(__k),
this }; }
1335#if __cplusplus > 201703L
1336 using _Base::contains;
1340 equal_range(
const key_type& __key)
1342 auto __res = _Base::equal_range(__key);
1343 return { { __res.first,
this }, { __res.second,
this } };
1346#if __cplusplus > 201703L
1347 template<
typename _Kt,
1348 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1349 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1351 equal_range(
const _Kt& __k)
1353 auto __res = _Base::equal_range(__k);
1354 return { { __res.first,
this }, { __res.second,
this } };
1359 equal_range(
const key_type& __key)
const
1361 auto __res = _Base::equal_range(__key);
1362 return { { __res.first,
this }, { __res.second,
this } };
1365#if __cplusplus > 201703L
1366 template<
typename _Kt,
1367 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1368 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1370 equal_range(
const _Kt& __k)
const
1372 auto __res = _Base::equal_range(__k);
1373 return { { __res.first,
this }, { __res.second,
this } };
1378 erase(
const key_type& __key)
1381 size_type __bucket_count = this->bucket_count();
1382 auto __pair = _Base::equal_range(__key);
1383 for (
auto __victim = __pair.first; __victim != __pair.second;)
1385 _M_invalidate(__victim);
1386 __victim = _Base::erase(__victim);
1390 _M_check_rehashed(__bucket_count);
1398 return { _M_erase(__it.
base()),
this };
1404 __glibcxx_check_erase2(__it);
1405 return _M_erase(__it);
1412 return { _M_erase(__it.
base()),
this };
1419 for (
auto __tmp = __first.base(); __tmp != __last.
base(); ++__tmp)
1421 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1422 _M_message(__gnu_debug::__msg_valid_range)
1423 ._M_iterator(__first,
"first")
1424 ._M_iterator(__last,
"last"));
1425 _M_invalidate(__tmp);
1428 size_type __bucket_count = this->bucket_count();
1429 auto __next = _Base::erase(__first.base(), __last.
base());
1430 _M_check_rehashed(__bucket_count);
1431 return { __next,
this };
1434 using _Base::rehash;
1435 using _Base::reserve;
1438 _M_base()
noexcept {
return *
this; }
1441 _M_base()
const noexcept {
return *
this; }
1445 _M_check_rehashed(size_type __prev_count)
1447 if (__prev_count != this->bucket_count())
1448 this->_M_invalidate_all();
1454 this->_M_invalidate_if(
1456 this->_M_invalidate_local_if(
1458 {
return __it == __victim; });
1464 _M_invalidate(__victim);
1465 size_type __bucket_count = this->bucket_count();
1467 _M_check_rehashed(__bucket_count);
1471#if __cplusplus > 201402L
1475 _M_invalidate(__victim);
1476 return _Base::extract(__victim);
1481#if __cpp_deduction_guides >= 201606
1483 template<
typename _InputIterator,
1487 typename = _RequireInputIter<_InputIterator>,
1488 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1489 typename = _RequireNotAllocator<_Pred>,
1490 typename = _RequireAllocator<_Allocator>>
1492 unordered_multimap<int, int>::size_type = {},
1493 _Hash = _Hash(), _Pred = _Pred(),
1494 _Allocator = _Allocator())
1496 __iter_val_t<_InputIterator>, _Hash, _Pred,
1499 template<
typename _Key,
typename _Tp,
typename _Hash = hash<_Key>,
1500 typename _Pred = equal_to<_Key>,
1501 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1502 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1503 typename = _RequireNotAllocator<_Pred>,
1504 typename = _RequireAllocator<_Allocator>>
1507 _Hash = _Hash(), _Pred = _Pred(),
1508 _Allocator = _Allocator())
1509 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
1511 template<
typename _InputIterator,
typename _Allocator,
1512 typename = _RequireInputIter<_InputIterator>,
1513 typename = _RequireAllocator<_Allocator>>
1514 unordered_multimap(_InputIterator, _InputIterator,
1515 unordered_multimap<int, int>::size_type, _Allocator)
1516 -> unordered_multimap<__iter_key_t<_InputIterator>,
1517 __iter_val_t<_InputIterator>,
1518 hash<__iter_key_t<_InputIterator>>,
1519 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1521 template<
typename _InputIterator,
typename _Allocator,
1522 typename = _RequireInputIter<_InputIterator>,
1523 typename = _RequireAllocator<_Allocator>>
1524 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
1525 -> unordered_multimap<__iter_key_t<_InputIterator>,
1526 __iter_val_t<_InputIterator>,
1527 hash<__iter_key_t<_InputIterator>>,
1528 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1530 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
1531 typename = _RequireInputIter<_InputIterator>,
1532 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1533 typename = _RequireAllocator<_Allocator>>
1534 unordered_multimap(_InputIterator, _InputIterator,
1535 unordered_multimap<int, int>::size_type, _Hash,
1537 -> unordered_multimap<__iter_key_t<_InputIterator>,
1538 __iter_val_t<_InputIterator>, _Hash,
1539 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1541 template<
typename _Key,
typename _Tp,
typename _Allocator,
1542 typename = _RequireAllocator<_Allocator>>
1543 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1544 unordered_multimap<int, int>::size_type,
1546 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1548 template<
typename _Key,
typename _Tp,
typename _Allocator,
1549 typename = _RequireAllocator<_Allocator>>
1550 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
1551 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1553 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Allocator,
1554 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1555 typename = _RequireAllocator<_Allocator>>
1556 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1557 unordered_multimap<int, int>::size_type,
1559 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1563 template<
typename _Key,
typename _Tp,
typename _Hash,
1564 typename _Pred,
typename _Alloc>
1566 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1567 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1568 noexcept(
noexcept(__x.swap(__y)))
1571 template<
typename _Key,
typename _Tp,
typename _Hash,
1572 typename _Pred,
typename _Alloc>
1574 operator==(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1575 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1576 {
return __x._M_base() == __y._M_base(); }
1578#if __cpp_impl_three_way_comparison < 201907L
1579 template<
typename _Key,
typename _Tp,
typename _Hash,
1580 typename _Pred,
typename _Alloc>
1582 operator!=(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1583 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1584 {
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.