29 #ifndef _GLIBCXX_DEBUG_UNORDERED_MAP
30 #define _GLIBCXX_DEBUG_UNORDERED_MAP 1
32 #pragma GCC system_header
34 #if __cplusplus < 201103L
38 namespace 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,
54 namespace 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,
73 typedef typename _Base::const_iterator _Base_const_iterator;
74 typedef typename _Base::iterator _Base_iterator;
75 typedef typename _Base::const_local_iterator
76 _Base_const_local_iterator;
77 typedef typename _Base::local_iterator _Base_local_iterator;
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;
102 _Base_iterator, unordered_map> iterator;
104 _Base_const_iterator, unordered_map> const_iterator;
106 _Base_local_iterator, unordered_map> local_iterator;
108 _Base_const_local_iterator, unordered_map> const_local_iterator;
110 unordered_map() =
default;
113 unordered_map(size_type __n,
114 const hasher& __hf = hasher(),
115 const key_equal& __eql = key_equal(),
116 const allocator_type& __a = allocator_type())
117 : _Base(__n, __hf, __eql, __a) { }
119 template<
typename _InputIterator>
120 unordered_map(_InputIterator __first, _InputIterator __last,
122 const hasher& __hf = hasher(),
123 const key_equal& __eql = key_equal(),
124 const allocator_type& __a = allocator_type())
125 : _Base(__gnu_debug::
__base(
126 __glibcxx_check_valid_constructor_range(__first, __last)),
127 __gnu_debug::
__base(__last), __n,
128 __hf, __eql, __a) { }
130 unordered_map(
const unordered_map&) =
default;
132 unordered_map(_Base_ref __x)
133 : _Base(__x._M_ref) { }
135 unordered_map(unordered_map&&) =
default;
138 unordered_map(
const allocator_type& __a)
141 unordered_map(
const unordered_map& __umap,
142 const allocator_type& __a)
143 : _Base(__umap, __a) { }
145 unordered_map(unordered_map&& __umap,
146 const allocator_type& __a)
147 noexcept( noexcept(_Base(
std::move(__umap._M_base()), __a)) )
148 : _Safe(std::
move(__umap._M_safe()), __a),
149 _Base(std::
move(__umap._M_base()), __a) { }
151 unordered_map(initializer_list<value_type> __l,
153 const hasher& __hf = hasher(),
154 const key_equal& __eql = key_equal(),
155 const allocator_type& __a = allocator_type())
156 : _Base(__l, __n, __hf, __eql, __a) { }
158 unordered_map(size_type __n,
const allocator_type& __a)
159 : unordered_map(__n, hasher(), key_equal(), __a)
162 unordered_map(size_type __n,
164 const allocator_type& __a)
165 : unordered_map(__n, __hf, key_equal(), __a)
168 template<
typename _InputIterator>
169 unordered_map(_InputIterator __first, _InputIterator __last,
171 const allocator_type& __a)
172 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
175 template<
typename _InputIterator>
176 unordered_map(_InputIterator __first, _InputIterator __last,
179 const allocator_type& __a)
180 : unordered_map(__first, __last, __n, __hf, key_equal(), __a)
183 unordered_map(initializer_list<value_type> __l,
185 const allocator_type& __a)
186 : unordered_map(__l, __n, hasher(), key_equal(), __a)
189 unordered_map(initializer_list<value_type> __l,
192 const allocator_type& __a)
193 : unordered_map(__l, __n, __hf, key_equal(), __a)
196 ~unordered_map() =
default;
199 operator=(
const unordered_map&) =
default;
202 operator=(unordered_map&&) =
default;
205 operator=(initializer_list<value_type> __l)
208 this->_M_invalidate_all();
213 swap(unordered_map& __x)
214 noexcept( noexcept(declval<_Base&>().swap(__x)) )
224 this->_M_invalidate_all();
229 {
return { _Base::begin(),
this }; }
232 begin() const noexcept
233 {
return { _Base::begin(),
this }; }
237 {
return { _Base::end(),
this }; }
241 {
return { _Base::end(),
this }; }
244 cbegin() const noexcept
245 {
return { _Base::cbegin(),
this }; }
248 cend() const noexcept
249 {
return { _Base::cend(),
this }; }
255 __glibcxx_check_bucket_index(__b);
256 return { _Base::begin(__b),
this };
262 __glibcxx_check_bucket_index(__b);
263 return { _Base::end(__b),
this };
267 begin(size_type __b)
const
269 __glibcxx_check_bucket_index(__b);
270 return { _Base::begin(__b),
this };
274 end(size_type __b)
const
276 __glibcxx_check_bucket_index(__b);
277 return { _Base::end(__b),
this };
281 cbegin(size_type __b)
const
283 __glibcxx_check_bucket_index(__b);
284 return { _Base::cbegin(__b),
this };
288 cend(size_type __b)
const
290 __glibcxx_check_bucket_index(__b);
291 return { _Base::cend(__b),
this };
295 bucket_size(size_type __b)
const
297 __glibcxx_check_bucket_index(__b);
298 return _Base::bucket_size(__b);
302 max_load_factor() const noexcept
303 {
return _Base::max_load_factor(); }
306 max_load_factor(
float __f)
308 __glibcxx_check_max_load_factor(__f);
309 _Base::max_load_factor(__f);
312 template<
typename... _Args>
314 emplace(_Args&&... __args)
316 size_type __bucket_count = this->bucket_count();
317 auto __res = _Base::emplace(std::forward<_Args>(__args)...);
318 _M_check_rehashed(__bucket_count);
319 return { { __res.first,
this }, __res.second };
322 template<
typename... _Args>
324 emplace_hint(const_iterator __hint, _Args&&... __args)
327 size_type __bucket_count = this->bucket_count();
328 auto __it = _Base::emplace_hint(__hint.base(),
329 std::forward<_Args>(__args)...);
330 _M_check_rehashed(__bucket_count);
331 return { __it,
this };
335 insert(
const value_type& __obj)
337 size_type __bucket_count = this->bucket_count();
338 auto __res = _Base::insert(__obj);
339 _M_check_rehashed(__bucket_count);
340 return { { __res.first,
this }, __res.second };
346 insert(value_type&& __x)
348 size_type __bucket_count = this->bucket_count();
349 auto __res = _Base::insert(
std::move(__x));
350 _M_check_rehashed(__bucket_count);
351 return { { __res.first,
this }, __res.second };
354 template<
typename _Pair,
typename =
typename
356 _Pair&&>::value>::type>
358 insert(_Pair&& __obj)
360 size_type __bucket_count = this->bucket_count();
361 auto __res = _Base::insert(std::forward<_Pair>(__obj));
362 _M_check_rehashed(__bucket_count);
363 return { { __res.first,
this }, __res.second };
367 insert(const_iterator __hint,
const value_type& __obj)
370 size_type __bucket_count = this->bucket_count();
371 auto __it = _Base::insert(__hint.base(), __obj);
372 _M_check_rehashed(__bucket_count);
373 return { __it,
this };
379 insert(const_iterator __hint, value_type&& __x)
382 size_type __bucket_count = this->bucket_count();
383 auto __it = _Base::insert(__hint.base(),
std::move(__x));
384 _M_check_rehashed(__bucket_count);
385 return { __it,
this };
388 template<
typename _Pair,
typename =
typename
390 _Pair&&>::value>::type>
392 insert(const_iterator __hint, _Pair&& __obj)
395 size_type __bucket_count = this->bucket_count();
396 auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
397 _M_check_rehashed(__bucket_count);
398 return { __it,
this };
404 size_type __bucket_count = this->bucket_count();
406 _M_check_rehashed(__bucket_count);
409 template<
typename _InputIterator>
411 insert(_InputIterator __first, _InputIterator __last)
414 __glibcxx_check_valid_range2(__first, __last, __dist);
415 size_type __bucket_count = this->bucket_count();
417 if (__dist.
second >= __gnu_debug::__dp_sign)
418 _Base::insert(__gnu_debug::__unsafe(__first),
419 __gnu_debug::__unsafe(__last));
421 _Base::insert(__first, __last);
423 _M_check_rehashed(__bucket_count);
426 #if __cplusplus > 201402L
427 template <
typename... _Args>
429 try_emplace(
const key_type& __k, _Args&&... __args)
431 auto __res = _Base::try_emplace(__k,
432 std::forward<_Args>(__args)...);
433 return { { __res.first,
this }, __res.second };
436 template <
typename... _Args>
438 try_emplace(key_type&& __k, _Args&&... __args)
440 auto __res = _Base::try_emplace(
std::move(__k),
441 std::forward<_Args>(__args)...);
442 return { { __res.first,
this }, __res.second };
445 template <
typename... _Args>
447 try_emplace(const_iterator __hint,
const key_type& __k,
451 return { _Base::try_emplace(__hint.base(), __k,
452 std::forward<_Args>(__args)...),
456 template <
typename... _Args>
458 try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
461 return { _Base::try_emplace(__hint.base(),
std::move(__k),
462 std::forward<_Args>(__args)...),
466 template <
typename _Obj>
468 insert_or_assign(
const key_type& __k, _Obj&& __obj)
470 auto __res = _Base::insert_or_assign(__k,
471 std::forward<_Obj>(__obj));
472 return { { __res.first,
this }, __res.second };
475 template <
typename _Obj>
477 insert_or_assign(key_type&& __k, _Obj&& __obj)
479 auto __res = _Base::insert_or_assign(
std::move(__k),
480 std::forward<_Obj>(__obj));
481 return { { __res.first,
this }, __res.second };
484 template <
typename _Obj>
486 insert_or_assign(const_iterator __hint,
const key_type& __k,
490 return { _Base::insert_or_assign(__hint.base(), __k,
491 std::forward<_Obj>(__obj)),
495 template <
typename _Obj>
497 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
500 return { _Base::insert_or_assign(__hint.base(),
std::move(__k),
501 std::forward<_Obj>(__obj)),
506 #if __cplusplus > 201402L
507 using node_type =
typename _Base::node_type;
508 using insert_return_type = _Node_insert_return<iterator, node_type>;
511 extract(const_iterator __position)
514 return _M_extract(__position.base());
518 extract(
const key_type& __key)
520 const auto __position = _Base::find(__key);
521 if (__position != _Base::end())
522 return _M_extract(__position);
527 insert(node_type&& __nh)
529 auto __ret = _Base::insert(
std::move(__nh));
531 { { __ret.position,
this }, __ret.inserted,
std::move(__ret.node) };
535 insert(const_iterator __hint, node_type&& __nh)
538 return { _Base::insert(__hint.base(),
std::move(__nh)),
this };
545 find(
const key_type& __key)
546 {
return { _Base::find(__key),
this }; }
548 #if __cplusplus > 201703L
549 template<
typename _Kt,
550 typename = std::__has_is_transparent_t<_Hash, _Kt>,
551 typename = std::__has_is_transparent_t<_Pred, _Kt>>
554 {
return { _Base::find(__k),
this }; }
558 find(
const key_type& __key)
const
559 {
return { _Base::find(__key),
this }; }
561 #if __cplusplus > 201703L
562 template<
typename _Kt,
563 typename = std::__has_is_transparent_t<_Hash, _Kt>,
564 typename = std::__has_is_transparent_t<_Pred, _Kt>>
566 find(
const _Kt& __k)
const
567 {
return { _Base::find(__k),
this }; }
571 equal_range(
const key_type& __key)
573 auto __res = _Base::equal_range(__key);
574 return { { __res.first,
this }, { __res.second,
this } };
577 #if __cplusplus > 201703L
578 template<
typename _Kt,
579 typename = std::__has_is_transparent_t<_Hash, _Kt>,
580 typename = std::__has_is_transparent_t<_Pred, _Kt>>
582 equal_range(
const _Kt& __k)
584 auto __res = _Base::equal_range(__k);
585 return { { __res.first,
this }, { __res.second,
this } };
590 equal_range(
const key_type& __key)
const
592 auto __res = _Base::equal_range(__key);
593 return { { __res.first,
this }, { __res.second,
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>>
601 equal_range(
const _Kt& __k)
const
603 auto __res = _Base::equal_range(__k);
604 return { { __res.first,
this }, { __res.second,
this } };
609 erase(
const key_type& __key)
612 auto __victim = _Base::find(__key);
613 if (__victim != _Base::end())
622 erase(const_iterator __it)
625 return { _M_erase(__it.base()),
this };
632 return { _M_erase(__it.base()),
this };
636 erase(const_iterator __first, const_iterator __last)
639 for (
auto __tmp = __first.base(); __tmp != __last.
base(); ++__tmp)
641 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
642 _M_message(__gnu_debug::__msg_valid_range)
643 ._M_iterator(__first,
"first")
644 ._M_iterator(__last,
"last"));
645 _M_invalidate(__tmp);
648 size_type __bucket_count = this->bucket_count();
649 auto __next = _Base::erase(__first.base(), __last.base());
650 _M_check_rehashed(__bucket_count);
651 return { __next,
this };
655 _M_base() noexcept {
return *
this; }
658 _M_base() const noexcept {
return *
this; }
662 _M_check_rehashed(size_type __prev_count)
664 if (__prev_count != this->bucket_count())
665 this->_M_invalidate_all();
669 _M_invalidate(_Base_const_iterator __victim)
672 [__victim](_Base_const_iterator __it) {
return __it == __victim; });
674 [__victim](_Base_const_local_iterator __it)
675 {
return __it == __victim; });
679 _M_erase(_Base_const_iterator __victim)
681 _M_invalidate(__victim);
682 size_type __bucket_count = this->bucket_count();
683 _Base_iterator __next = _Base::erase(__victim);
684 _M_check_rehashed(__bucket_count);
688 #if __cplusplus > 201402L
690 _M_extract(_Base_const_iterator __victim)
692 _M_invalidate(__victim);
693 return _Base::extract(__victim);
698 #if __cpp_deduction_guides >= 201606
700 template<
typename _InputIterator,
701 typename _Hash = hash<__iter_key_t<_InputIterator>>,
702 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
703 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
704 typename = _RequireInputIter<_InputIterator>,
705 typename = _RequireNotAllocatorOrIntegral<_Hash>,
706 typename = _RequireNotAllocator<_Pred>,
707 typename = _RequireAllocator<_Allocator>>
708 unordered_map(_InputIterator, _InputIterator,
709 typename unordered_map<int, int>::size_type = {},
710 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
711 -> unordered_map<__iter_key_t<_InputIterator>,
712 __iter_val_t<_InputIterator>,
713 _Hash, _Pred, _Allocator>;
715 template<
typename _Key,
typename _Tp,
typename _Hash = hash<_Key>,
716 typename _Pred = equal_to<_Key>,
717 typename _Allocator = allocator<pair<const _Key, _Tp>>,
718 typename = _RequireNotAllocatorOrIntegral<_Hash>,
719 typename = _RequireNotAllocator<_Pred>,
720 typename = _RequireAllocator<_Allocator>>
721 unordered_map(initializer_list<pair<_Key, _Tp>>,
722 typename unordered_map<int, int>::size_type = {},
723 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
724 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
726 template<
typename _InputIterator,
typename _Allocator,
727 typename = _RequireInputIter<_InputIterator>,
728 typename = _RequireAllocator<_Allocator>>
729 unordered_map(_InputIterator, _InputIterator,
730 typename unordered_map<int, int>::size_type, _Allocator)
731 -> unordered_map<__iter_key_t<_InputIterator>,
732 __iter_val_t<_InputIterator>,
733 hash<__iter_key_t<_InputIterator>>,
734 equal_to<__iter_key_t<_InputIterator>>,
737 template<
typename _InputIterator,
typename _Allocator,
738 typename = _RequireInputIter<_InputIterator>,
739 typename = _RequireAllocator<_Allocator>>
740 unordered_map(_InputIterator, _InputIterator, _Allocator)
741 -> unordered_map<__iter_key_t<_InputIterator>,
742 __iter_val_t<_InputIterator>,
743 hash<__iter_key_t<_InputIterator>>,
744 equal_to<__iter_key_t<_InputIterator>>,
747 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
748 typename = _RequireInputIter<_InputIterator>,
749 typename = _RequireNotAllocatorOrIntegral<_Hash>,
750 typename = _RequireAllocator<_Allocator>>
751 unordered_map(_InputIterator, _InputIterator,
752 typename unordered_map<int, int>::size_type,
754 -> unordered_map<__iter_key_t<_InputIterator>,
755 __iter_val_t<_InputIterator>, _Hash,
756 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
758 template<
typename _Key,
typename _Tp,
typename _Allocator,
759 typename = _RequireAllocator<_Allocator>>
760 unordered_map(initializer_list<pair<_Key, _Tp>>,
761 typename unordered_map<int, int>::size_type,
763 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
765 template<
typename _Key,
typename _Tp,
typename _Allocator,
766 typename = _RequireAllocator<_Allocator>>
767 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
768 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
770 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Allocator,
771 typename = _RequireNotAllocatorOrIntegral<_Hash>,
772 typename = _RequireAllocator<_Allocator>>
773 unordered_map(initializer_list<pair<_Key, _Tp>>,
774 typename unordered_map<int, int>::size_type,
776 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
780 template<
typename _Key,
typename _Tp,
typename _Hash,
781 typename _Pred,
typename _Alloc>
783 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
784 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
785 noexcept(noexcept(__x.swap(__y)))
788 template<
typename _Key,
typename _Tp,
typename _Hash,
789 typename _Pred,
typename _Alloc>
791 operator==(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
792 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
793 {
return __x._M_base() == __y._M_base(); }
795 #if __cpp_impl_three_way_comparison < 201907L
796 template<
typename _Key,
typename _Tp,
typename _Hash,
797 typename _Pred,
typename _Alloc>
799 operator!=(
const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
800 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
801 {
return !(__x == __y); }
805 template<
typename _Key,
typename _Tp,
809 class unordered_multimap
811 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
812 __gnu_debug::_Safe_unordered_container>,
813 public _GLIBCXX_STD_C::unordered_multimap<
814 _Key, _Tp, _Hash, _Pred, _Alloc>
816 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
817 _Pred, _Alloc> _Base;
820 typedef typename _Base::const_iterator _Base_const_iterator;
821 typedef typename _Base::iterator _Base_iterator;
822 typedef typename _Base::const_local_iterator _Base_const_local_iterator;
823 typedef typename _Base::local_iterator _Base_local_iterator;
825 template<
typename _ItT,
typename _SeqT,
typename _CatT>
826 friend class ::__gnu_debug::_Safe_iterator;
827 template<
typename _ItT,
typename _SeqT>
828 friend class ::__gnu_debug::_Safe_local_iterator;
833 _Base_ref(
const _Base& __r) : _M_ref(__r) { }
839 typedef typename _Base::size_type size_type;
840 typedef typename _Base::hasher hasher;
841 typedef typename _Base::key_equal key_equal;
842 typedef typename _Base::allocator_type allocator_type;
844 typedef typename _Base::key_type key_type;
845 typedef typename _Base::value_type value_type;
848 _Base_iterator, unordered_multimap> iterator;
850 _Base_const_iterator, unordered_multimap> const_iterator;
852 _Base_local_iterator, unordered_multimap> local_iterator;
854 _Base_const_local_iterator, unordered_multimap> const_local_iterator;
856 unordered_multimap() =
default;
859 unordered_multimap(size_type __n,
860 const hasher& __hf = hasher(),
861 const key_equal& __eql = key_equal(),
862 const allocator_type& __a = allocator_type())
863 : _Base(__n, __hf, __eql, __a) { }
865 template<
typename _InputIterator>
866 unordered_multimap(_InputIterator __first, _InputIterator __last,
868 const hasher& __hf = hasher(),
869 const key_equal& __eql = key_equal(),
870 const allocator_type& __a = allocator_type())
871 : _Base(__gnu_debug::
__base(
872 __glibcxx_check_valid_constructor_range(__first, __last)),
873 __gnu_debug::
__base(__last), __n,
874 __hf, __eql, __a) { }
876 unordered_multimap(
const unordered_multimap&) =
default;
878 unordered_multimap(_Base_ref __x)
879 : _Base(__x._M_ref) { }
881 unordered_multimap(unordered_multimap&&) =
default;
884 unordered_multimap(
const allocator_type& __a)
887 unordered_multimap(
const unordered_multimap& __umap,
888 const allocator_type& __a)
889 : _Base(__umap, __a) { }
891 unordered_multimap(unordered_multimap&& __umap,
892 const allocator_type& __a)
893 noexcept( noexcept(_Base(
std::move(__umap._M_base()), __a)) )
894 : _Safe(std::
move(__umap._M_safe()), __a),
895 _Base(std::
move(__umap._M_base()), __a) { }
897 unordered_multimap(initializer_list<value_type> __l,
899 const hasher& __hf = hasher(),
900 const key_equal& __eql = key_equal(),
901 const allocator_type& __a = allocator_type())
902 : _Base(__l, __n, __hf, __eql, __a) { }
904 unordered_multimap(size_type __n,
const allocator_type& __a)
905 : unordered_multimap(__n, hasher(), key_equal(), __a)
908 unordered_multimap(size_type __n,
const hasher& __hf,
909 const allocator_type& __a)
910 : unordered_multimap(__n, __hf, key_equal(), __a)
913 template<
typename _InputIterator>
914 unordered_multimap(_InputIterator __first, _InputIterator __last,
916 const allocator_type& __a)
917 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
920 template<
typename _InputIterator>
921 unordered_multimap(_InputIterator __first, _InputIterator __last,
922 size_type __n,
const hasher& __hf,
923 const allocator_type& __a)
924 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
927 unordered_multimap(initializer_list<value_type> __l,
929 const allocator_type& __a)
930 : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
933 unordered_multimap(initializer_list<value_type> __l,
934 size_type __n,
const hasher& __hf,
935 const allocator_type& __a)
936 : unordered_multimap(__l, __n, __hf, key_equal(), __a)
939 ~unordered_multimap() =
default;
942 operator=(
const unordered_multimap&) =
default;
945 operator=(unordered_multimap&&) =
default;
948 operator=(initializer_list<value_type> __l)
950 this->_M_base() = __l;
951 this->_M_invalidate_all();
956 swap(unordered_multimap& __x)
957 noexcept( noexcept(declval<_Base&>().swap(__x)) )
967 this->_M_invalidate_all();
972 {
return { _Base::begin(),
this }; }
975 begin() const noexcept
976 {
return { _Base::begin(),
this }; }
980 {
return { _Base::end(),
this }; }
984 {
return { _Base::end(),
this }; }
988 {
return { _Base::cbegin(),
this }; }
991 cend() const noexcept
992 {
return { _Base::cend(),
this }; }
998 __glibcxx_check_bucket_index(__b);
999 return { _Base::begin(__b),
this };
1005 __glibcxx_check_bucket_index(__b);
1006 return { _Base::end(__b),
this };
1009 const_local_iterator
1010 begin(size_type __b)
const
1012 __glibcxx_check_bucket_index(__b);
1013 return { _Base::begin(__b),
this };
1016 const_local_iterator
1017 end(size_type __b)
const
1019 __glibcxx_check_bucket_index(__b);
1020 return { _Base::end(__b),
this };
1023 const_local_iterator
1024 cbegin(size_type __b)
const
1026 __glibcxx_check_bucket_index(__b);
1027 return { _Base::cbegin(__b),
this };
1030 const_local_iterator
1031 cend(size_type __b)
const
1033 __glibcxx_check_bucket_index(__b);
1034 return { _Base::cend(__b),
this };
1038 bucket_size(size_type __b)
const
1040 __glibcxx_check_bucket_index(__b);
1041 return _Base::bucket_size(__b);
1045 max_load_factor() const noexcept
1046 {
return _Base::max_load_factor(); }
1049 max_load_factor(
float __f)
1051 __glibcxx_check_max_load_factor(__f);
1052 _Base::max_load_factor(__f);
1055 template<
typename... _Args>
1057 emplace(_Args&&... __args)
1059 size_type __bucket_count = this->bucket_count();
1060 auto __it = _Base::emplace(std::forward<_Args>(__args)...);
1061 _M_check_rehashed(__bucket_count);
1062 return { __it,
this };
1065 template<
typename... _Args>
1067 emplace_hint(const_iterator __hint, _Args&&... __args)
1070 size_type __bucket_count = this->bucket_count();
1071 auto __it = _Base::emplace_hint(__hint.base(),
1072 std::forward<_Args>(__args)...);
1073 _M_check_rehashed(__bucket_count);
1074 return { __it,
this };
1078 insert(
const value_type& __obj)
1080 size_type __bucket_count = this->bucket_count();
1081 auto __it = _Base::insert(__obj);
1082 _M_check_rehashed(__bucket_count);
1083 return { __it,
this };
1089 insert(value_type&& __x)
1091 size_type __bucket_count = this->bucket_count();
1092 auto __it = _Base::insert(
std::move(__x));
1093 _M_check_rehashed(__bucket_count);
1094 return { __it,
this };
1098 insert(const_iterator __hint,
const value_type& __obj)
1101 size_type __bucket_count = this->bucket_count();
1102 auto __it = _Base::insert(__hint.base(), __obj);
1103 _M_check_rehashed(__bucket_count);
1104 return { __it,
this };
1110 insert(const_iterator __hint, value_type&& __x)
1113 size_type __bucket_count = this->bucket_count();
1114 auto __it = _Base::insert(__hint.base(),
std::move(__x));
1115 _M_check_rehashed(__bucket_count);
1116 return { __it,
this };
1119 template<
typename _Pair,
typename =
typename
1121 _Pair&&>::value>::type>
1123 insert(_Pair&& __obj)
1125 size_type __bucket_count = this->bucket_count();
1126 auto __it = _Base::insert(std::forward<_Pair>(__obj));
1127 _M_check_rehashed(__bucket_count);
1128 return { __it,
this };
1131 template<
typename _Pair,
typename =
typename
1133 _Pair&&>::value>::type>
1135 insert(const_iterator __hint, _Pair&& __obj)
1138 size_type __bucket_count = this->bucket_count();
1139 auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
1140 _M_check_rehashed(__bucket_count);
1141 return { __it,
this };
1146 { _Base::insert(__l); }
1148 template<
typename _InputIterator>
1150 insert(_InputIterator __first, _InputIterator __last)
1153 __glibcxx_check_valid_range2(__first, __last, __dist);
1154 size_type __bucket_count = this->bucket_count();
1156 if (__dist.
second >= __gnu_debug::__dp_sign)
1157 _Base::insert(__gnu_debug::__unsafe(__first),
1158 __gnu_debug::__unsafe(__last));
1160 _Base::insert(__first, __last);
1162 _M_check_rehashed(__bucket_count);
1165 #if __cplusplus > 201402L
1166 using node_type =
typename _Base::node_type;
1169 extract(const_iterator __position)
1172 return _M_extract(__position.base());
1176 extract(
const key_type& __key)
1178 const auto __position = _Base::find(__key);
1179 if (__position != _Base::end())
1180 return _M_extract(__position);
1185 insert(node_type&& __nh)
1186 {
return { _Base::insert(
std::move(__nh)),
this }; }
1189 insert(const_iterator __hint, node_type&& __nh)
1192 return { _Base::insert(__hint.base(),
std::move(__nh)),
this };
1199 find(
const key_type& __key)
1200 {
return { _Base::find(__key),
this }; }
1202 #if __cplusplus > 201703L
1203 template<
typename _Kt,
1204 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1205 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1207 find(
const _Kt& __k)
1208 {
return { _Base::find(__k),
this }; }
1212 find(
const key_type& __key)
const
1213 {
return { _Base::find(__key),
this }; }
1215 #if __cplusplus > 201703L
1216 template<
typename _Kt,
1217 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1218 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1220 find(
const _Kt& __k)
const
1221 {
return { _Base::find(__k),
this }; }
1225 equal_range(
const key_type& __key)
1227 auto __res = _Base::equal_range(__key);
1228 return { { __res.first,
this }, { __res.second,
this } };
1231 #if __cplusplus > 201703L
1232 template<
typename _Kt,
1233 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1234 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1236 equal_range(
const _Kt& __k)
1238 auto __res = _Base::equal_range(__k);
1239 return { { __res.first,
this }, { __res.second,
this } };
1244 equal_range(
const key_type& __key)
const
1246 auto __res = _Base::equal_range(__key);
1247 return { { __res.first,
this }, { __res.second,
this } };
1250 #if __cplusplus > 201703L
1251 template<
typename _Kt,
1252 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1253 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1255 equal_range(
const _Kt& __k)
const
1257 auto __res = _Base::equal_range(__k);
1258 return { { __res.first,
this }, { __res.second,
this } };
1263 erase(
const key_type& __key)
1266 size_type __bucket_count = this->bucket_count();
1267 auto __pair = _Base::equal_range(__key);
1268 for (
auto __victim = __pair.first; __victim != __pair.second;)
1270 _M_invalidate(__victim);
1271 __victim = _Base::erase(__victim);
1275 _M_check_rehashed(__bucket_count);
1280 erase(const_iterator __it)
1283 return { _M_erase(__it.base()),
this };
1287 erase(iterator __it)
1290 return { _M_erase(__it.base()),
this };
1294 erase(const_iterator __first, const_iterator __last)
1297 for (
auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1299 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1300 _M_message(__gnu_debug::__msg_valid_range)
1301 ._M_iterator(__first,
"first")
1302 ._M_iterator(__last,
"last"));
1303 _M_invalidate(__tmp);
1306 size_type __bucket_count = this->bucket_count();
1307 auto __next = _Base::erase(__first.base(), __last.base());
1308 _M_check_rehashed(__bucket_count);
1309 return { __next,
this };
1313 _M_base() noexcept {
return *
this; }
1316 _M_base() const noexcept {
return *
this; }
1320 _M_check_rehashed(size_type __prev_count)
1322 if (__prev_count != this->bucket_count())
1323 this->_M_invalidate_all();
1327 _M_invalidate(_Base_const_iterator __victim)
1330 [__victim](_Base_const_iterator __it) {
return __it == __victim; });
1332 [__victim](_Base_const_local_iterator __it)
1333 {
return __it == __victim; });
1337 _M_erase(_Base_const_iterator __victim)
1339 _M_invalidate(__victim);
1340 size_type __bucket_count = this->bucket_count();
1341 _Base_iterator __next = _Base::erase(__victim);
1342 _M_check_rehashed(__bucket_count);
1346 #if __cplusplus > 201402L
1348 _M_extract(_Base_const_iterator __victim)
1350 _M_invalidate(__victim);
1351 return _Base::extract(__victim);
1356 #if __cpp_deduction_guides >= 201606
1358 template<
typename _InputIterator,
1359 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1360 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1361 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1362 typename = _RequireInputIter<_InputIterator>,
1363 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1364 typename = _RequireNotAllocator<_Pred>,
1365 typename = _RequireAllocator<_Allocator>>
1366 unordered_multimap(_InputIterator, _InputIterator,
1367 unordered_multimap<int, int>::size_type = {},
1368 _Hash = _Hash(), _Pred = _Pred(),
1369 _Allocator = _Allocator())
1370 -> unordered_multimap<__iter_key_t<_InputIterator>,
1371 __iter_val_t<_InputIterator>, _Hash, _Pred,
1374 template<
typename _Key,
typename _Tp,
typename _Hash = hash<_Key>,
1375 typename _Pred = equal_to<_Key>,
1376 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1377 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1378 typename = _RequireNotAllocator<_Pred>,
1379 typename = _RequireAllocator<_Allocator>>
1380 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1381 unordered_multimap<int, int>::size_type = {},
1382 _Hash = _Hash(), _Pred = _Pred(),
1383 _Allocator = _Allocator())
1384 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
1386 template<
typename _InputIterator,
typename _Allocator,
1387 typename = _RequireInputIter<_InputIterator>,
1388 typename = _RequireAllocator<_Allocator>>
1389 unordered_multimap(_InputIterator, _InputIterator,
1390 unordered_multimap<int, int>::size_type, _Allocator)
1391 -> unordered_multimap<__iter_key_t<_InputIterator>,
1392 __iter_val_t<_InputIterator>,
1393 hash<__iter_key_t<_InputIterator>>,
1394 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1396 template<
typename _InputIterator,
typename _Allocator,
1397 typename = _RequireInputIter<_InputIterator>,
1398 typename = _RequireAllocator<_Allocator>>
1399 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
1400 -> unordered_multimap<__iter_key_t<_InputIterator>,
1401 __iter_val_t<_InputIterator>,
1402 hash<__iter_key_t<_InputIterator>>,
1403 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1405 template<
typename _InputIterator,
typename _Hash,
typename _Allocator,
1406 typename = _RequireInputIter<_InputIterator>,
1407 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1408 typename = _RequireAllocator<_Allocator>>
1409 unordered_multimap(_InputIterator, _InputIterator,
1410 unordered_multimap<int, int>::size_type, _Hash,
1412 -> unordered_multimap<__iter_key_t<_InputIterator>,
1413 __iter_val_t<_InputIterator>, _Hash,
1414 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1416 template<
typename _Key,
typename _Tp,
typename _Allocator,
1417 typename = _RequireAllocator<_Allocator>>
1418 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1419 unordered_multimap<int, int>::size_type,
1421 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1423 template<
typename _Key,
typename _Tp,
typename _Allocator,
1424 typename = _RequireAllocator<_Allocator>>
1425 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
1426 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1428 template<
typename _Key,
typename _Tp,
typename _Hash,
typename _Allocator,
1429 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1430 typename = _RequireAllocator<_Allocator>>
1431 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1432 unordered_multimap<int, int>::size_type,
1434 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1438 template<
typename _Key,
typename _Tp,
typename _Hash,
1439 typename _Pred,
typename _Alloc>
1441 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1442 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1443 noexcept(noexcept(__x.swap(__y)))
1446 template<
typename _Key,
typename _Tp,
typename _Hash,
1447 typename _Pred,
typename _Alloc>
1449 operator==(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1450 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1451 {
return __x._M_base() == __y._M_base(); }
1453 #if __cpp_impl_three_way_comparison < 201907L
1454 template<
typename _Key,
typename _Tp,
typename _Hash,
1455 typename _Pred,
typename _Alloc>
1457 operator!=(
const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1458 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1459 {
return !(__x == __y); }
constexpr auto cbegin(const _Container &__cont) noexcept(noexcept(std::begin(__cont))) -> decltype(std::begin(__cont))
Return an iterator pointing to the first element of the const container.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Primary class template hash.
void _M_invalidate_local_if(_Predicate __pred)
Struct holding two objects of arbitrary type.
One of the comparison functors.
Class std::unordered_multimap with safety/checking/debug instrumentation.
Class std::unordered_map with safety/checking/debug instrumentation.
_Tp * begin(valarray< _Tp > &__va)
Return an iterator pointing to the first element of the valarray.
_Tp * end(valarray< _Tp > &__va)
Return an iterator pointing to one past the last element of the valarray.
_Iterator & base() noexcept
Return the underlying iterator.
#define __glibcxx_check_erase(_Position)
A standard container composed of unique keys (containing at most one of each key value) that associat...
void _M_invalidate_if(_Predicate __pred)
Base class for constructing a safe unordered container type that tracks iterators that reference it...
The standard allocator, as per C++03 [20.4.1].
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
constexpr _Iterator __base(_Iterator __it)
Safe class dealing with some allocator dependent operations.
Define a member typedef type only if a boolean constant is true.
_T2 second
The second member.
#define __glibcxx_check_erase_range(_First, _Last)
#define __glibcxx_check_insert(_Position)
auto_ptr & operator=(auto_ptr &__a)
auto_ptr assignment operator.