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)
204#if __glibcxx_containers_ranges
205 template<__detail::__container_compatible_range<value_type> _Rg>
208 const hasher& __hf = hasher(),
209 const key_equal& __eql = key_equal(),
210 const allocator_type& __a = allocator_type())
211 :
_Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __eql, __a)
214 template<__detail::__container_compatible_range<value_type> _Rg>
215 unordered_map(from_range_t, _Rg&& __rg,
const allocator_type& __a)
216 :
_Base(from_range, std::forward<_Rg>(__rg), __a)
219 template<__detail::__container_compatible_range<value_type> _Rg>
221 const allocator_type& __a)
222 :
_Base(from_range, std::forward<_Rg>(__rg), __n, __a)
225 template<__detail::__container_compatible_range<value_type> _Rg>
227 const hasher& __hf,
const allocator_type& __a)
228 :
_Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __a)
243 _Base::operator=(__l);
244 this->_M_invalidate_all();
248 using _Base::get_allocator;
251 using _Base::max_size;
255 noexcept(
noexcept(declval<_Base&>().swap(__x)) )
265 this->_M_invalidate_all();
270 {
return { _Base::begin(),
this }; }
273 begin()
const noexcept
274 {
return { _Base::begin(),
this }; }
278 {
return { _Base::end(),
this }; }
282 {
return { _Base::end(),
this }; }
285 cbegin()
const noexcept
286 {
return { _Base::cbegin(),
this }; }
289 cend()
const noexcept
290 {
return { _Base::cend(),
this }; }
296 __glibcxx_check_bucket_index(__b);
297 return { _Base::begin(__b),
this };
303 __glibcxx_check_bucket_index(__b);
304 return { _Base::end(__b),
this };
308 begin(size_type __b)
const
310 __glibcxx_check_bucket_index(__b);
311 return { _Base::begin(__b),
this };
315 end(size_type __b)
const
317 __glibcxx_check_bucket_index(__b);
318 return { _Base::end(__b),
this };
322 cbegin(size_type __b)
const
324 __glibcxx_check_bucket_index(__b);
325 return { _Base::cbegin(__b),
this };
329 cend(size_type __b)
const
331 __glibcxx_check_bucket_index(__b);
332 return { _Base::cend(__b),
this };
335 using _Base::bucket_count;
336 using _Base::max_bucket_count;
340 bucket_size(size_type __b)
const
342 __glibcxx_check_bucket_index(__b);
343 return _Base::bucket_size(__b);
346 using _Base::load_factor;
349 max_load_factor()
const noexcept
350 {
return _Base::max_load_factor(); }
353 max_load_factor(
float __f)
355 __glibcxx_check_max_load_factor(__f);
356 _Base::max_load_factor(__f);
359 template<
typename... _Args>
361 emplace(_Args&&... __args)
363 size_type __bucket_count = this->bucket_count();
364 auto __res = _Base::emplace(std::forward<_Args>(__args)...);
365 _M_check_rehashed(__bucket_count);
366 return { { __res.first,
this }, __res.second };
369 template<
typename... _Args>
374 size_type __bucket_count = this->bucket_count();
375 auto __it = _Base::emplace_hint(__hint.
base(),
376 std::forward<_Args>(__args)...);
377 _M_check_rehashed(__bucket_count);
378 return { __it,
this };
382 insert(
const value_type& __obj)
384 size_type __bucket_count = this->bucket_count();
385 auto __res = _Base::insert(__obj);
386 _M_check_rehashed(__bucket_count);
387 return { { __res.first,
this }, __res.second };
393 insert(value_type&& __x)
395 size_type __bucket_count = this->bucket_count();
396 auto __res = _Base::insert(
std::move(__x));
397 _M_check_rehashed(__bucket_count);
398 return { { __res.first,
this }, __res.second };
401 template<
typename _Pair,
typename =
typename
403 _Pair&&>::value>::type>
405 insert(_Pair&& __obj)
407 size_type __bucket_count = this->bucket_count();
408 auto __res = _Base::insert(std::forward<_Pair>(__obj));
409 _M_check_rehashed(__bucket_count);
410 return { { __res.first,
this }, __res.second };
417 size_type __bucket_count = this->bucket_count();
418 auto __it = _Base::insert(__hint.
base(), __obj);
419 _M_check_rehashed(__bucket_count);
420 return { __it,
this };
429 size_type __bucket_count = this->bucket_count();
431 _M_check_rehashed(__bucket_count);
432 return { __it,
this };
435 template<
typename _Pair,
typename =
typename
437 _Pair&&>::value>::type>
442 size_type __bucket_count = this->bucket_count();
443 auto __it = _Base::insert(__hint.
base(), std::forward<_Pair>(__obj));
444 _M_check_rehashed(__bucket_count);
445 return { __it,
this };
451 size_type __bucket_count = this->bucket_count();
453 _M_check_rehashed(__bucket_count);
456 template<
typename _InputIterator>
458 insert(_InputIterator __first, _InputIterator __last)
461 __glibcxx_check_valid_range2(__first, __last, __dist);
462 size_type __bucket_count = this->bucket_count();
464 if (__dist.
second >= __gnu_debug::__dp_sign)
465 _Base::insert(__gnu_debug::__unsafe(__first),
466 __gnu_debug::__unsafe(__last));
468 _Base::insert(__first, __last);
470 _M_check_rehashed(__bucket_count);
473#ifdef __glibcxx_unordered_map_try_emplace
474 template <
typename... _Args>
476 try_emplace(
const key_type& __k, _Args&&... __args)
478 auto __res = _Base::try_emplace(__k,
479 std::forward<_Args>(__args)...);
480 return { { __res.first,
this }, __res.second };
483 template <
typename... _Args>
485 try_emplace(key_type&& __k, _Args&&... __args)
487 auto __res = _Base::try_emplace(
std::move(__k),
488 std::forward<_Args>(__args)...);
489 return { { __res.first,
this }, __res.second };
492 template <
typename... _Args>
498 return { _Base::try_emplace(__hint.
base(), __k,
499 std::forward<_Args>(__args)...),
503 template <
typename... _Args>
505 try_emplace(
const_iterator __hint, key_type&& __k, _Args&&... __args)
509 std::forward<_Args>(__args)...),
513 template <
typename _Obj>
515 insert_or_assign(
const key_type& __k, _Obj&& __obj)
517 auto __res = _Base::insert_or_assign(__k,
518 std::forward<_Obj>(__obj));
519 return { { __res.first,
this }, __res.second };
522 template <
typename _Obj>
524 insert_or_assign(key_type&& __k, _Obj&& __obj)
526 auto __res = _Base::insert_or_assign(
std::move(__k),
527 std::forward<_Obj>(__obj));
528 return { { __res.first,
this }, __res.second };
531 template <
typename _Obj>
537 return { _Base::insert_or_assign(__hint.
base(), __k,
538 std::forward<_Obj>(__obj)),
542 template <
typename _Obj>
544 insert_or_assign(
const_iterator __hint, key_type&& __k, _Obj&& __obj)
547 return { _Base::insert_or_assign(__hint.
base(),
std::move(__k),
548 std::forward<_Obj>(__obj)),
553#if __cplusplus > 201402L
554 using node_type =
typename _Base::node_type;
561 return _M_extract(__position.
base());
565 extract(
const key_type& __key)
567 const auto __position = _Base::find(__key);
568 if (__position != _Base::end())
569 return _M_extract(__position);
574 insert(node_type&& __nh)
576 auto __ret = _Base::insert(
std::move(__nh));
578 { { __ret.position,
this }, __ret.inserted,
std::move(__ret.node) };
585 return { _Base::insert(__hint.
base(),
std::move(__nh)),
this };
588 template<
typename _H2,
typename _P2>
593 = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
594 _Base::merge(__source);
597 template<
typename _H2,
typename _P2>
602 template<
typename _H2,
typename _P2>
607 = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
608 _Base::merge(__source);
611 template<
typename _H2,
typename _P2>
617 using _Base::hash_function;
621 find(
const key_type& __key)
622 {
return { _Base::find(__key),
this }; }
624#if __cplusplus > 201703L
625 template<
typename _Kt,
626 typename = std::__has_is_transparent_t<_Hash, _Kt>,
627 typename = std::__has_is_transparent_t<_Pred, _Kt>>
630 {
return { _Base::find(__k),
this }; }
634 find(
const key_type& __key)
const
635 {
return { _Base::find(__key),
this }; }
637#if __cplusplus > 201703L
638 template<
typename _Kt,
639 typename = std::__has_is_transparent_t<_Hash, _Kt>,
640 typename = std::__has_is_transparent_t<_Pred, _Kt>>
642 find(
const _Kt& __k)
const
643 {
return { _Base::find(__k),
this }; }
647#if __cplusplus > 201703L
648 using _Base::contains;
652 equal_range(
const key_type& __key)
654 auto __res = _Base::equal_range(__key);
655 return { { __res.first,
this }, { __res.second,
this } };
658#if __cplusplus > 201703L
659 template<
typename _Kt,
660 typename = std::__has_is_transparent_t<_Hash, _Kt>,
661 typename = std::__has_is_transparent_t<_Pred, _Kt>>
663 equal_range(
const _Kt& __k)
665 auto __res = _Base::equal_range(__k);
666 return { { __res.first,
this }, { __res.second,
this } };
671 equal_range(
const key_type& __key)
const
673 auto __res = _Base::equal_range(__key);
674 return { { __res.first,
this }, { __res.second,
this } };
677#if __cplusplus > 201703L
678 template<
typename _Kt,
679 typename = std::__has_is_transparent_t<_Hash, _Kt>,
680 typename = std::__has_is_transparent_t<_Pred, _Kt>>
682 equal_range(
const _Kt& __k)
const
684 auto __res = _Base::equal_range(__k);
685 return { { __res.first,
this }, { __res.second,
this } };
689 using _Base::operator[];
693 erase(
const key_type& __key)
696 auto __victim = _Base::find(__key);
697 if (__victim != _Base::end())
709 return { _M_erase(__it.
base()),
this };
715 __glibcxx_check_erase2(__it);
716 return _M_erase(__it);
723 return { _M_erase(__it.
base()),
this };
730 for (
auto __tmp = __first.base(); __tmp != __last.
base(); ++__tmp)
732 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
733 _M_message(__gnu_debug::__msg_valid_range)
734 ._M_iterator(__first,
"first")
735 ._M_iterator(__last,
"last"));
736 _M_invalidate(__tmp);
739 size_type __bucket_count = this->bucket_count();
740 auto __next = _Base::erase(__first.base(), __last.
base());
741 _M_check_rehashed(__bucket_count);
742 return { __next,
this };
746 using _Base::reserve;
749 _M_base()
noexcept {
return *
this; }
752 _M_base()
const noexcept {
return *
this; }
756 _M_check_rehashed(size_type __prev_count)
758 if (__prev_count != this->bucket_count())
759 this->_M_invalidate_all();
765 this->_M_invalidate_if(
767 this->_M_invalidate_local_if(
769 {
return __it == __victim; });
775 _M_invalidate(__victim);
776 size_type __bucket_count = this->bucket_count();
778 _M_check_rehashed(__bucket_count);
782#if __cplusplus > 201402L
786 _M_invalidate(__victim);
787 return _Base::extract(__victim);
792#if __cpp_deduction_guides >= 201606
794 template<
typename _InputIterator,
798 typename = _RequireInputIter<_InputIterator>,
799 typename = _RequireNotAllocatorOrIntegral<_Hash>,
800 typename = _RequireNotAllocator<_Pred>,
801 typename = _RequireAllocator<_Allocator>>
803 typename unordered_map<int, int>::size_type = {},
804 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
806 __iter_val_t<_InputIterator>,
807 _Hash, _Pred, _Allocator>;
809 template<
typename _Key,
typename _Tp,
typename _Hash = hash<_Key>,
810 typename _Pred = equal_to<_Key>,
811 typename _Allocator = allocator<pair<const _Key, _Tp>>,
812 typename = _RequireNotAllocatorOrIntegral<_Hash>,
813 typename = _RequireNotAllocator<_Pred>,
814 typename = _RequireAllocator<_Allocator>>
817 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
818 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
820 template<
typename _InputIterator,
typename _Allocator,
821 typename = _RequireInputIter<_InputIterator>,
822 typename = _RequireAllocator<_Allocator>>
823 unordered_map(_InputIterator, _InputIterator,
824 typename unordered_map<int, int>::size_type, _Allocator)
825 -> unordered_map<__iter_key_t<_InputIterator>,
826 __iter_val_t<_InputIterator>,
827 hash<__iter_key_t<_InputIterator>>,
828 equal_to<__iter_key_t<_InputIterator>>,
831 template<
typename _InputIterator,
typename _Allocator,
832 typename = _RequireInputIter<_InputIterator>,
833 typename = _RequireAllocator<_Allocator>>
834 unordered_map(_InputIterator, _InputIterator, _Allocator)
835 -> unordered_map<__iter_key_t<_InputIterator>,
836 __iter_val_t<_InputIterator>,
837 hash<__iter_key_t<_InputIterator>>,
838 equal_to<__iter_key_t<_InputIterator>>,
841 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
842 typename = _RequireInputIter<_InputIterator>,
843 typename = _RequireNotAllocatorOrIntegral<_Hash>,
844 typename = _RequireAllocator<_Allocator>>
845 unordered_map(_InputIterator, _InputIterator,
846 typename unordered_map<int, int>::size_type,
848 -> unordered_map<__iter_key_t<_InputIterator>,
849 __iter_val_t<_InputIterator>, _Hash,
850 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
852 template<
typename _Key,
typename _Tp,
typename _Allocator,
853 typename = _RequireAllocator<_Allocator>>
854 unordered_map(initializer_list<pair<_Key, _Tp>>,
855 typename unordered_map<int, int>::size_type,
857 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
859 template<
typename _Key,
typename _Tp,
typename _Allocator,
860 typename = _RequireAllocator<_Allocator>>
861 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
862 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
864 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Allocator,
865 typename = _RequireNotAllocatorOrIntegral<_Hash>,
866 typename = _RequireAllocator<_Allocator>>
867 unordered_map(initializer_list<pair<_Key, _Tp>>,
868 typename unordered_map<int, int>::size_type,
870 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
872#if __glibcxx_containers_ranges
873 template<ranges::input_range _Rg,
874 __not_allocator_like _Hash = hash<__detail::__range_key_type<_Rg>>,
875 __not_allocator_like _Pred = equal_to<__detail::__range_key_type<_Rg>>,
876 __allocator_like _Allocator =
877 allocator<__detail::__range_to_alloc_type<_Rg>>>
878 unordered_map(from_range_t, _Rg&&, unordered_map<int, int>::size_type = {},
879 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
880 -> unordered_map<__detail::__range_key_type<_Rg>,
881 __detail::__range_mapped_type<_Rg>,
882 _Hash, _Pred, _Allocator>;
884 template<ranges::input_range _Rg,
885 __allocator_like _Allocator>
886 unordered_map(from_range_t, _Rg&&, unordered_map<int, int>::size_type,
888 -> unordered_map<__detail::__range_key_type<_Rg>,
889 __detail::__range_mapped_type<_Rg>,
890 hash<__detail::__range_key_type<_Rg>>,
891 equal_to<__detail::__range_key_type<_Rg>>,
894 template<ranges::input_range _Rg,
895 __allocator_like _Allocator>
896 unordered_map(from_range_t, _Rg&&, _Allocator)
897 -> unordered_map<__detail::__range_key_type<_Rg>,
898 __detail::__range_mapped_type<_Rg>,
899 hash<__detail::__range_key_type<_Rg>>,
900 equal_to<__detail::__range_key_type<_Rg>>,
903 template<ranges::input_range _Rg,
904 __not_allocator_like _Hash,
905 __allocator_like _Allocator>
906 unordered_map(from_range_t, _Rg&&, unordered_map<int, int>::size_type,
908 -> unordered_map<__detail::__range_key_type<_Rg>,
909 __detail::__range_mapped_type<_Rg>,
910 _Hash, equal_to<__detail::__range_key_type<_Rg>>,
915 template<
typename _Key,
typename _Tp,
typename _Hash,
916 typename _Pred,
typename _Alloc>
918 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
919 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
920 noexcept(
noexcept(__x.swap(__y)))
923 template<
typename _Key,
typename _Tp,
typename _Hash,
924 typename _Pred,
typename _Alloc>
926 operator==(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
927 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
928 {
return __x._M_base() == __y._M_base(); }
930#if __cpp_impl_three_way_comparison < 201907L
931 template<
typename _Key,
typename _Tp,
typename _Hash,
932 typename _Pred,
typename _Alloc>
934 operator!=(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
935 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
936 {
return !(__x == __y); }
940 template<
typename _Key,
typename _Tp,
946 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
947 __gnu_debug::_Safe_unordered_container>,
948 public _GLIBCXX_STD_C::unordered_multimap<
949 _Key, _Tp, _Hash, _Pred, _Alloc>
951 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
952 _Pred, _Alloc>
_Base;
960 template<
typename _ItT,
typename _SeqT,
typename _CatT>
961 friend class ::__gnu_debug::_Safe_iterator;
962 template<
typename _ItT,
typename _SeqT>
963 friend class ::__gnu_debug::_Safe_local_iterator;
968 _Base_ref(
const _Base& __r) : _M_ref(__r) { }
974 typedef typename _Base::size_type size_type;
975 typedef typename _Base::hasher hasher;
976 typedef typename _Base::key_equal key_equal;
977 typedef typename _Base::allocator_type allocator_type;
979 typedef typename _Base::key_type key_type;
980 typedef typename _Base::value_type value_type;
981 typedef typename _Base::mapped_type mapped_type;
983 typedef typename _Base::pointer pointer;
984 typedef typename _Base::const_pointer const_pointer;
985 typedef typename _Base::reference reference;
986 typedef typename _Base::const_reference const_reference;
995 typedef typename _Base::difference_type difference_type;
1001 const hasher& __hf = hasher(),
1002 const key_equal& __eql = key_equal(),
1003 const allocator_type& __a = allocator_type())
1004 :
_Base(__n, __hf, __eql, __a) { }
1006 template<
typename _InputIterator>
1009 const hasher& __hf = hasher(),
1010 const key_equal& __eql = key_equal(),
1011 const allocator_type& __a = allocator_type())
1013 __glibcxx_check_valid_constructor_range(__first, __last)),
1015 __hf, __eql, __a) { }
1020 :
_Base(__x._M_ref) { }
1029 const allocator_type& __a)
1030 :
_Base(__umap, __a) { }
1033 const allocator_type& __a)
1040 const hasher& __hf = hasher(),
1041 const key_equal& __eql = key_equal(),
1042 const allocator_type& __a = allocator_type())
1043 :
_Base(__l, __n, __hf, __eql, __a) { }
1050 const allocator_type& __a)
1054 template<
typename _InputIterator>
1057 const allocator_type& __a)
1061 template<
typename _InputIterator>
1063 size_type __n,
const hasher& __hf,
1064 const allocator_type& __a)
1070 const allocator_type& __a)
1075 size_type __n,
const hasher& __hf,
1076 const allocator_type& __a)
1080#if __glibcxx_containers_ranges
1081 template<__detail::__container_compatible_range<value_type> _Rg>
1084 const hasher& __hf = hasher(),
1085 const key_equal& __eql = key_equal(),
1086 const allocator_type& __a = allocator_type())
1087 :
_Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __eql, __a)
1090 template<__detail::__container_compatible_range<value_type> _Rg>
1092 :
_Base(from_range, std::forward<_Rg>(__rg), __a)
1095 template<__detail::__container_compatible_range<value_type> _Rg>
1097 const allocator_type& __a)
1098 :
_Base(from_range, std::forward<_Rg>(__rg), __n, __a)
1101 template<__detail::__container_compatible_range<value_type> _Rg>
1103 const hasher& __hf,
const allocator_type& __a)
1104 :
_Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __a)
1119 _Base::operator=(__l);
1120 this->_M_invalidate_all();
1124 using _Base::get_allocator;
1127 using _Base::max_size;
1131 noexcept(
noexcept(declval<_Base&>().swap(__x)) )
1133 _Safe::_M_swap(__x);
1141 this->_M_invalidate_all();
1146 {
return { _Base::begin(),
this }; }
1149 begin()
const noexcept
1150 {
return { _Base::begin(),
this }; }
1154 {
return { _Base::end(),
this }; }
1157 end()
const noexcept
1158 {
return { _Base::end(),
this }; }
1161 cbegin()
const noexcept
1162 {
return { _Base::cbegin(),
this }; }
1165 cend()
const noexcept
1166 {
return { _Base::cend(),
this }; }
1170 begin(size_type __b)
1172 __glibcxx_check_bucket_index(__b);
1173 return { _Base::begin(__b),
this };
1179 __glibcxx_check_bucket_index(__b);
1180 return { _Base::end(__b),
this };
1184 begin(size_type __b)
const
1186 __glibcxx_check_bucket_index(__b);
1187 return { _Base::begin(__b),
this };
1191 end(size_type __b)
const
1193 __glibcxx_check_bucket_index(__b);
1194 return { _Base::end(__b),
this };
1198 cbegin(size_type __b)
const
1200 __glibcxx_check_bucket_index(__b);
1201 return { _Base::cbegin(__b),
this };
1205 cend(size_type __b)
const
1207 __glibcxx_check_bucket_index(__b);
1208 return { _Base::cend(__b),
this };
1211 using _Base::bucket_count;
1212 using _Base::max_bucket_count;
1213 using _Base::bucket;
1216 bucket_size(size_type __b)
const
1218 __glibcxx_check_bucket_index(__b);
1219 return _Base::bucket_size(__b);
1223 max_load_factor()
const noexcept
1224 {
return _Base::max_load_factor(); }
1227 max_load_factor(
float __f)
1229 __glibcxx_check_max_load_factor(__f);
1230 _Base::max_load_factor(__f);
1233 template<
typename... _Args>
1235 emplace(_Args&&... __args)
1237 size_type __bucket_count = this->bucket_count();
1238 auto __it = _Base::emplace(std::forward<_Args>(__args)...);
1239 _M_check_rehashed(__bucket_count);
1240 return { __it,
this };
1243 template<
typename... _Args>
1248 size_type __bucket_count = this->bucket_count();
1249 auto __it = _Base::emplace_hint(__hint.
base(),
1250 std::forward<_Args>(__args)...);
1251 _M_check_rehashed(__bucket_count);
1252 return { __it,
this };
1256 insert(
const value_type& __obj)
1258 size_type __bucket_count = this->bucket_count();
1259 auto __it = _Base::insert(__obj);
1260 _M_check_rehashed(__bucket_count);
1261 return { __it,
this };
1267 insert(value_type&& __x)
1269 size_type __bucket_count = this->bucket_count();
1270 auto __it = _Base::insert(
std::move(__x));
1271 _M_check_rehashed(__bucket_count);
1272 return { __it,
this };
1279 size_type __bucket_count = this->bucket_count();
1280 auto __it = _Base::insert(__hint.
base(), __obj);
1281 _M_check_rehashed(__bucket_count);
1282 return { __it,
this };
1291 size_type __bucket_count = this->bucket_count();
1293 _M_check_rehashed(__bucket_count);
1294 return { __it,
this };
1297 template<
typename _Pair,
typename =
typename
1299 _Pair&&>::value>::type>
1301 insert(_Pair&& __obj)
1303 size_type __bucket_count = this->bucket_count();
1304 auto __it = _Base::insert(std::forward<_Pair>(__obj));
1305 _M_check_rehashed(__bucket_count);
1306 return { __it,
this };
1309 template<
typename _Pair,
typename =
typename
1311 _Pair&&>::value>::type>
1316 size_type __bucket_count = this->bucket_count();
1317 auto __it = _Base::insert(__hint.
base(), std::forward<_Pair>(__obj));
1318 _M_check_rehashed(__bucket_count);
1319 return { __it,
this };
1324 { _Base::insert(__l); }
1326 template<
typename _InputIterator>
1328 insert(_InputIterator __first, _InputIterator __last)
1331 __glibcxx_check_valid_range2(__first, __last, __dist);
1332 size_type __bucket_count = this->bucket_count();
1334 if (__dist.
second >= __gnu_debug::__dp_sign)
1335 _Base::insert(__gnu_debug::__unsafe(__first),
1336 __gnu_debug::__unsafe(__last));
1338 _Base::insert(__first, __last);
1340 _M_check_rehashed(__bucket_count);
1343#if __cplusplus > 201402L
1344 using node_type =
typename _Base::node_type;
1350 return _M_extract(__position.
base());
1354 extract(
const key_type& __key)
1356 const auto __position = _Base::find(__key);
1357 if (__position != _Base::end())
1358 return _M_extract(__position);
1363 insert(node_type&& __nh)
1364 {
return { _Base::insert(
std::move(__nh)),
this }; }
1370 return { _Base::insert(__hint.
base(),
std::move(__nh)),
this };
1373 template<
typename _H2,
typename _P2>
1378 = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
1379 _Base::merge(__source);
1382 template<
typename _H2,
typename _P2>
1385 { merge(__source); }
1387 template<
typename _H2,
typename _P2>
1392 = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
1393 _Base::merge(__source);
1396 template<
typename _H2,
typename _P2>
1399 { merge(__source); }
1402 using _Base::hash_function;
1403 using _Base::key_eq;
1406 find(
const key_type& __key)
1407 {
return { _Base::find(__key),
this }; }
1409#if __cplusplus > 201703L
1410 template<
typename _Kt,
1411 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1412 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1414 find(
const _Kt& __k)
1415 {
return { _Base::find(__k),
this }; }
1419 find(
const key_type& __key)
const
1420 {
return { _Base::find(__key),
this }; }
1422#if __cplusplus > 201703L
1423 template<
typename _Kt,
1424 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1425 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1427 find(
const _Kt& __k)
const
1428 {
return { _Base::find(__k),
this }; }
1432#if __cplusplus > 201703L
1433 using _Base::contains;
1437 equal_range(
const key_type& __key)
1439 auto __res = _Base::equal_range(__key);
1440 return { { __res.first,
this }, { __res.second,
this } };
1443#if __cplusplus > 201703L
1444 template<
typename _Kt,
1445 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1446 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1448 equal_range(
const _Kt& __k)
1450 auto __res = _Base::equal_range(__k);
1451 return { { __res.first,
this }, { __res.second,
this } };
1456 equal_range(
const key_type& __key)
const
1458 auto __res = _Base::equal_range(__key);
1459 return { { __res.first,
this }, { __res.second,
this } };
1462#if __cplusplus > 201703L
1463 template<
typename _Kt,
1464 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1465 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1467 equal_range(
const _Kt& __k)
const
1469 auto __res = _Base::equal_range(__k);
1470 return { { __res.first,
this }, { __res.second,
this } };
1475 erase(
const key_type& __key)
1478 size_type __bucket_count = this->bucket_count();
1479 auto __pair = _Base::equal_range(__key);
1480 for (
auto __victim = __pair.first; __victim != __pair.second;)
1482 _M_invalidate(__victim);
1483 __victim = _Base::erase(__victim);
1487 _M_check_rehashed(__bucket_count);
1495 return { _M_erase(__it.
base()),
this };
1501 __glibcxx_check_erase2(__it);
1502 return _M_erase(__it);
1509 return { _M_erase(__it.
base()),
this };
1516 for (
auto __tmp = __first.base(); __tmp != __last.
base(); ++__tmp)
1518 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1519 _M_message(__gnu_debug::__msg_valid_range)
1520 ._M_iterator(__first,
"first")
1521 ._M_iterator(__last,
"last"));
1522 _M_invalidate(__tmp);
1525 size_type __bucket_count = this->bucket_count();
1526 auto __next = _Base::erase(__first.base(), __last.
base());
1527 _M_check_rehashed(__bucket_count);
1528 return { __next,
this };
1531 using _Base::rehash;
1532 using _Base::reserve;
1535 _M_base()
noexcept {
return *
this; }
1538 _M_base()
const noexcept {
return *
this; }
1542 _M_check_rehashed(size_type __prev_count)
1544 if (__prev_count != this->bucket_count())
1545 this->_M_invalidate_all();
1551 this->_M_invalidate_if(
1553 this->_M_invalidate_local_if(
1555 {
return __it == __victim; });
1561 _M_invalidate(__victim);
1562 size_type __bucket_count = this->bucket_count();
1564 _M_check_rehashed(__bucket_count);
1568#if __cplusplus > 201402L
1572 _M_invalidate(__victim);
1573 return _Base::extract(__victim);
1578#if __cpp_deduction_guides >= 201606
1580 template<
typename _InputIterator,
1584 typename = _RequireInputIter<_InputIterator>,
1585 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1586 typename = _RequireNotAllocator<_Pred>,
1587 typename = _RequireAllocator<_Allocator>>
1589 unordered_multimap<int, int>::size_type = {},
1590 _Hash = _Hash(), _Pred = _Pred(),
1591 _Allocator = _Allocator())
1593 __iter_val_t<_InputIterator>, _Hash, _Pred,
1596 template<
typename _Key,
typename _Tp,
typename _Hash = hash<_Key>,
1597 typename _Pred = equal_to<_Key>,
1598 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1599 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1600 typename = _RequireNotAllocator<_Pred>,
1601 typename = _RequireAllocator<_Allocator>>
1604 _Hash = _Hash(), _Pred = _Pred(),
1605 _Allocator = _Allocator())
1606 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
1608 template<
typename _InputIterator,
typename _Allocator,
1609 typename = _RequireInputIter<_InputIterator>,
1610 typename = _RequireAllocator<_Allocator>>
1611 unordered_multimap(_InputIterator, _InputIterator,
1612 unordered_multimap<int, int>::size_type, _Allocator)
1613 -> unordered_multimap<__iter_key_t<_InputIterator>,
1614 __iter_val_t<_InputIterator>,
1615 hash<__iter_key_t<_InputIterator>>,
1616 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1618 template<
typename _InputIterator,
typename _Allocator,
1619 typename = _RequireInputIter<_InputIterator>,
1620 typename = _RequireAllocator<_Allocator>>
1621 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
1622 -> unordered_multimap<__iter_key_t<_InputIterator>,
1623 __iter_val_t<_InputIterator>,
1624 hash<__iter_key_t<_InputIterator>>,
1625 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1627 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
1628 typename = _RequireInputIter<_InputIterator>,
1629 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1630 typename = _RequireAllocator<_Allocator>>
1631 unordered_multimap(_InputIterator, _InputIterator,
1632 unordered_multimap<int, int>::size_type, _Hash,
1634 -> unordered_multimap<__iter_key_t<_InputIterator>,
1635 __iter_val_t<_InputIterator>, _Hash,
1636 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1638 template<
typename _Key,
typename _Tp,
typename _Allocator,
1639 typename = _RequireAllocator<_Allocator>>
1640 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1641 unordered_multimap<int, int>::size_type,
1643 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1645 template<
typename _Key,
typename _Tp,
typename _Allocator,
1646 typename = _RequireAllocator<_Allocator>>
1647 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
1648 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1650 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Allocator,
1651 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1652 typename = _RequireAllocator<_Allocator>>
1653 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1654 unordered_multimap<int, int>::size_type,
1656 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1658#if __glibcxx_containers_ranges
1659 template<ranges::input_range _Rg,
1660 __not_allocator_like _Hash = hash<__detail::__range_key_type<_Rg>>,
1661 __not_allocator_like _Pred = equal_to<__detail::__range_key_type<_Rg>>,
1662 __allocator_like _Allocator =
1663 allocator<__detail::__range_to_alloc_type<_Rg>>>
1664 unordered_multimap(from_range_t, _Rg&&,
1665 unordered_multimap<int, int>::size_type = {},
1666 _Hash = _Hash(), _Pred = _Pred(),
1667 _Allocator = _Allocator())
1668 -> unordered_multimap<__detail::__range_key_type<_Rg>,
1669 __detail::__range_mapped_type<_Rg>,
1670 _Hash, _Pred, _Allocator>;
1672 template<ranges::input_range _Rg,
1673 __allocator_like _Allocator>
1674 unordered_multimap(from_range_t, _Rg&&, unordered_multimap<int, int>::size_type,
1676 -> unordered_multimap<__detail::__range_key_type<_Rg>,
1677 __detail::__range_mapped_type<_Rg>,
1678 hash<__detail::__range_key_type<_Rg>>,
1679 equal_to<__detail::__range_key_type<_Rg>>,
1682 template<ranges::input_range _Rg,
1683 __allocator_like _Allocator>
1684 unordered_multimap(from_range_t, _Rg&&, _Allocator)
1685 -> unordered_multimap<__detail::__range_key_type<_Rg>,
1686 __detail::__range_mapped_type<_Rg>,
1687 hash<__detail::__range_key_type<_Rg>>,
1688 equal_to<__detail::__range_key_type<_Rg>>,
1691 template<ranges::input_range _Rg,
1692 __not_allocator_like _Hash,
1693 __allocator_like _Allocator>
1694 unordered_multimap(from_range_t, _Rg&&,
1695 unordered_multimap<int, int>::size_type,
1697 -> unordered_multimap<__detail::__range_key_type<_Rg>,
1698 __detail::__range_mapped_type<_Rg>,
1699 _Hash, equal_to<__detail::__range_key_type<_Rg>>,
1704 template<
typename _Key,
typename _Tp,
typename _Hash,
1705 typename _Pred,
typename _Alloc>
1707 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1708 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1709 noexcept(
noexcept(__x.swap(__y)))
1712 template<
typename _Key,
typename _Tp,
typename _Hash,
1713 typename _Pred,
typename _Alloc>
1715 operator==(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1716 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1717 {
return __x._M_base() == __y._M_base(); }
1719#if __cpp_impl_three_way_comparison < 201907L
1720 template<
typename _Key,
typename _Tp,
typename _Hash,
1721 typename _Pred,
typename _Alloc>
1723 operator!=(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1724 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1725 {
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.