1 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
3 // Copyright (C) 2003-2025 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 /** @file debug/unordered_map
26 * This file is a GNU debug extension to the Standard C++ Library.
29 #ifndef _GLIBCXX_DEBUG_UNORDERED_MAP
30 #define _GLIBCXX_DEBUG_UNORDERED_MAP 1
32 #ifdef _GLIBCXX_SYSHDR
33 #pragma GCC system_header
36 #if __cplusplus < 201103L
37 # include <bits/c++0x_warning.h>
39 # include <bits/c++config.h>
40 namespace 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;
47 } } // namespace std::__debug
49 # include <unordered_map>
51 #include <debug/safe_unordered_container.h>
52 #include <debug/safe_container.h>
53 #include <debug/safe_iterator.h>
54 #include <debug/safe_local_iterator.h>
56 namespace std _GLIBCXX_VISIBILITY(default)
60 /// Class std::unordered_map with safety/checking/debug instrumentation.
61 template<typename _Key, typename _Tp,
62 typename _Hash = std::hash<_Key>,
63 typename _Pred = std::equal_to<_Key>,
64 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
66 : public __gnu_debug::_Safe_container<
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,
73 typedef __gnu_debug::_Safe_container<unordered_map,
74 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
75 typedef typename _Base::const_iterator _Base_const_iterator;
76 typedef typename _Base::iterator _Base_iterator;
77 typedef typename _Base::const_local_iterator
78 _Base_const_local_iterator;
79 typedef typename _Base::local_iterator _Base_local_iterator;
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;
86 // Reference wrapper for base class. See PR libstdc++/90102.
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;
108 typedef __gnu_debug::_Safe_iterator<
109 _Base_iterator, unordered_map> iterator;
110 typedef __gnu_debug::_Safe_iterator<
111 _Base_const_iterator, unordered_map> const_iterator;
112 typedef __gnu_debug::_Safe_local_iterator<
113 _Base_local_iterator, unordered_map> local_iterator;
114 typedef __gnu_debug::_Safe_local_iterator<
115 _Base_const_local_iterator, unordered_map> const_local_iterator;
116 typedef typename _Base::difference_type difference_type;
118 unordered_map() = default;
121 unordered_map(size_type __n,
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>
128 unordered_map(_InputIterator __first, _InputIterator __last,
130 const hasher& __hf = hasher(),
131 const key_equal& __eql = key_equal(),
132 const allocator_type& __a = allocator_type())
133 : _Base(__gnu_debug::__base(
134 __glibcxx_check_valid_constructor_range(__first, __last)),
135 __gnu_debug::__base(__last), __n,
136 __hf, __eql, __a) { }
138 unordered_map(const unordered_map&) = default;
140 unordered_map(_Base_ref __x)
141 : _Base(__x._M_ref) { }
143 unordered_map(unordered_map&&) = default;
146 unordered_map(const allocator_type& __a)
149 unordered_map(const unordered_map& __umap,
150 const allocator_type& __a)
151 : _Base(__umap, __a) { }
153 unordered_map(unordered_map&& __umap,
154 const allocator_type& __a)
155 noexcept( noexcept(_Base(std::move(__umap), __a)) )
156 : _Safe(std::move(__umap), __a),
157 _Base(std::move(__umap), __a) { }
159 unordered_map(initializer_list<value_type> __l,
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) { }
166 unordered_map(size_type __n, const allocator_type& __a)
167 : unordered_map(__n, hasher(), key_equal(), __a)
170 unordered_map(size_type __n,
172 const allocator_type& __a)
173 : unordered_map(__n, __hf, key_equal(), __a)
176 template<typename _InputIterator>
177 unordered_map(_InputIterator __first, _InputIterator __last,
179 const allocator_type& __a)
180 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
183 template<typename _InputIterator>
184 unordered_map(_InputIterator __first, _InputIterator __last,
187 const allocator_type& __a)
188 : unordered_map(__first, __last, __n, __hf, key_equal(), __a)
191 unordered_map(initializer_list<value_type> __l,
193 const allocator_type& __a)
194 : unordered_map(__l, __n, hasher(), key_equal(), __a)
197 unordered_map(initializer_list<value_type> __l,
200 const allocator_type& __a)
201 : unordered_map(__l, __n, __hf, key_equal(), __a)
204 #if __glibcxx_containers_ranges // C++ >= 23
205 template<__detail::__container_compatible_range<value_type> _Rg>
206 unordered_map(from_range_t, _Rg&& __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>
220 unordered_map(from_range_t, _Rg&& __rg, size_type __n,
221 const allocator_type& __a)
222 : _Base(from_range, std::forward<_Rg>(__rg), __n, __a)
225 template<__detail::__container_compatible_range<value_type> _Rg>
226 unordered_map(from_range_t, _Rg&& __rg, size_type __n,
227 const hasher& __hf, const allocator_type& __a)
228 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __a)
232 ~unordered_map() = default;
235 operator=(const unordered_map&) = default;
238 operator=(unordered_map&&) = default;
241 operator=(initializer_list<value_type> __l)
243 _Base::operator=(__l);
244 this->_M_invalidate_all();
248 using _Base::get_allocator;
251 using _Base::max_size;
254 swap(unordered_map& __x)
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>
360 std::pair<iterator, bool>
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>
371 emplace_hint(const_iterator __hint, _Args&&... __args)
373 __glibcxx_check_insert(__hint);
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 };
381 std::pair<iterator, bool>
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 };
390 // _GLIBCXX_RESOLVE_LIB_DEFECTS
391 // 2354. Unnecessary copying when inserting into maps with braced-init
392 std::pair<iterator, bool>
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
402 std::enable_if<std::is_constructible<value_type,
403 _Pair&&>::value>::type>
404 std::pair<iterator, bool>
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 };
414 insert(const_iterator __hint, const value_type& __obj)
416 __glibcxx_check_insert(__hint);
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 };
423 // _GLIBCXX_RESOLVE_LIB_DEFECTS
424 // 2354. Unnecessary copying when inserting into maps with braced-init
426 insert(const_iterator __hint, value_type&& __x)
428 __glibcxx_check_insert(__hint);
429 size_type __bucket_count = this->bucket_count();
430 auto __it = _Base::insert(__hint.base(), std::move(__x));
431 _M_check_rehashed(__bucket_count);
432 return { __it, this };
435 template<typename _Pair, typename = typename
436 std::enable_if<std::is_constructible<value_type,
437 _Pair&&>::value>::type>
439 insert(const_iterator __hint, _Pair&& __obj)
441 __glibcxx_check_insert(__hint);
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 };
449 insert(std::initializer_list<value_type> __l)
451 size_type __bucket_count = this->bucket_count();
453 _M_check_rehashed(__bucket_count);
456 template<typename _InputIterator>
458 insert(_InputIterator __first, _InputIterator __last)
460 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
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 // C++ >= 17 && HOSTED
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>
494 try_emplace(const_iterator __hint, const key_type& __k,
497 __glibcxx_check_insert(__hint);
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)
507 __glibcxx_check_insert(__hint);
508 return { _Base::try_emplace(__hint.base(), std::move(__k),
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>
533 insert_or_assign(const_iterator __hint, const key_type& __k,
536 __glibcxx_check_insert(__hint);
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)
546 __glibcxx_check_insert(__hint);
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;
555 using insert_return_type = _Node_insert_return<iterator, node_type>;
558 extract(const_iterator __position)
560 __glibcxx_check_erase(__position);
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) };
582 insert(const_iterator __hint, node_type&& __nh)
584 __glibcxx_check_insert(__hint);
585 return { _Base::insert(__hint.base(), std::move(__nh)), this };
588 template<typename _H2, typename _P2>
590 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
593 = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
594 _Base::merge(__source);
597 template<typename _H2, typename _P2>
599 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
602 template<typename _H2, typename _P2>
604 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
607 = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
608 _Base::merge(__source);
611 template<typename _H2, typename _P2>
613 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
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;
651 std::pair<iterator, iterator>
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>>
662 std::pair<iterator, iterator>
663 equal_range(const _Kt& __k)
665 auto __res = _Base::equal_range(__k);
666 return { { __res.first, this }, { __res.second, this } };
670 std::pair<const_iterator, const_iterator>
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>>
681 std::pair<const_iterator, const_iterator>
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())
706 erase(const_iterator __it)
708 __glibcxx_check_erase(__it);
709 return { _M_erase(__it.base()), this };
713 erase(_Base_const_iterator __it)
715 __glibcxx_check_erase2(__it);
716 return _M_erase(__it);
722 __glibcxx_check_erase(__it);
723 return { _M_erase(__it.base()), this };
727 erase(const_iterator __first, const_iterator __last)
729 __glibcxx_check_erase_range(__first, __last);
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();
763 _M_invalidate(_Base_const_iterator __victim)
765 this->_M_invalidate_if(
766 [__victim](_Base_const_iterator __it) { return __it == __victim; });
767 this->_M_invalidate_local_if(
768 [__victim](_Base_const_local_iterator __it)
769 { return __it == __victim; });
773 _M_erase(_Base_const_iterator __victim)
775 _M_invalidate(__victim);
776 size_type __bucket_count = this->bucket_count();
777 _Base_iterator __next = _Base::erase(__victim);
778 _M_check_rehashed(__bucket_count);
782 #if __cplusplus > 201402L
784 _M_extract(_Base_const_iterator __victim)
786 _M_invalidate(__victim);
787 return _Base::extract(__victim);
792 #if __cpp_deduction_guides >= 201606
794 template<typename _InputIterator,
795 typename _Hash = hash<__iter_key_t<_InputIterator>>,
796 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
797 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
798 typename = _RequireInputIter<_InputIterator>,
799 typename = _RequireNotAllocatorOrIntegral<_Hash>,
800 typename = _RequireNotAllocator<_Pred>,
801 typename = _RequireAllocator<_Allocator>>
802 unordered_map(_InputIterator, _InputIterator,
803 typename unordered_map<int, int>::size_type = {},
804 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
805 -> unordered_map<__iter_key_t<_InputIterator>,
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>>
815 unordered_map(initializer_list<pair<_Key, _Tp>>,
816 typename unordered_map<int, int>::size_type = {},
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 // C++ >= 23
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); }
939 /// Class std::unordered_multimap with safety/checking/debug instrumentation.
940 template<typename _Key, typename _Tp,
941 typename _Hash = std::hash<_Key>,
942 typename _Pred = std::equal_to<_Key>,
943 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
944 class unordered_multimap
945 : public __gnu_debug::_Safe_container<
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;
953 typedef __gnu_debug::_Safe_container<unordered_multimap,
954 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
955 typedef typename _Base::const_iterator _Base_const_iterator;
956 typedef typename _Base::iterator _Base_iterator;
957 typedef typename _Base::const_local_iterator _Base_const_local_iterator;
958 typedef typename _Base::local_iterator _Base_local_iterator;
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;
965 // Reference wrapper for base class. See PR libstdc++/90102.
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;
987 typedef __gnu_debug::_Safe_iterator<
988 _Base_iterator, unordered_multimap> iterator;
989 typedef __gnu_debug::_Safe_iterator<
990 _Base_const_iterator, unordered_multimap> const_iterator;
991 typedef __gnu_debug::_Safe_local_iterator<
992 _Base_local_iterator, unordered_multimap> local_iterator;
993 typedef __gnu_debug::_Safe_local_iterator<
994 _Base_const_local_iterator, unordered_multimap> const_local_iterator;
995 typedef typename _Base::difference_type difference_type;
997 unordered_multimap() = default;
1000 unordered_multimap(size_type __n,
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>
1007 unordered_multimap(_InputIterator __first, _InputIterator __last,
1009 const hasher& __hf = hasher(),
1010 const key_equal& __eql = key_equal(),
1011 const allocator_type& __a = allocator_type())
1012 : _Base(__gnu_debug::__base(
1013 __glibcxx_check_valid_constructor_range(__first, __last)),
1014 __gnu_debug::__base(__last), __n,
1015 __hf, __eql, __a) { }
1017 unordered_multimap(const unordered_multimap&) = default;
1019 unordered_multimap(_Base_ref __x)
1020 : _Base(__x._M_ref) { }
1022 unordered_multimap(unordered_multimap&&) = default;
1025 unordered_multimap(const allocator_type& __a)
1028 unordered_multimap(const unordered_multimap& __umap,
1029 const allocator_type& __a)
1030 : _Base(__umap, __a) { }
1032 unordered_multimap(unordered_multimap&& __umap,
1033 const allocator_type& __a)
1034 noexcept( noexcept(_Base(std::move(__umap), __a)) )
1035 : _Safe(std::move(__umap), __a),
1036 _Base(std::move(__umap), __a) { }
1038 unordered_multimap(initializer_list<value_type> __l,
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) { }
1045 unordered_multimap(size_type __n, const allocator_type& __a)
1046 : unordered_multimap(__n, hasher(), key_equal(), __a)
1049 unordered_multimap(size_type __n, const hasher& __hf,
1050 const allocator_type& __a)
1051 : unordered_multimap(__n, __hf, key_equal(), __a)
1054 template<typename _InputIterator>
1055 unordered_multimap(_InputIterator __first, _InputIterator __last,
1057 const allocator_type& __a)
1058 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
1061 template<typename _InputIterator>
1062 unordered_multimap(_InputIterator __first, _InputIterator __last,
1063 size_type __n, const hasher& __hf,
1064 const allocator_type& __a)
1065 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
1068 unordered_multimap(initializer_list<value_type> __l,
1070 const allocator_type& __a)
1071 : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
1074 unordered_multimap(initializer_list<value_type> __l,
1075 size_type __n, const hasher& __hf,
1076 const allocator_type& __a)
1077 : unordered_multimap(__l, __n, __hf, key_equal(), __a)
1080 #if __glibcxx_containers_ranges // C++ >= 23
1081 template<__detail::__container_compatible_range<value_type> _Rg>
1082 unordered_multimap(from_range_t, _Rg&& __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>
1091 unordered_multimap(from_range_t, _Rg&& __rg, const allocator_type& __a)
1092 : _Base(from_range, std::forward<_Rg>(__rg), __a)
1095 template<__detail::__container_compatible_range<value_type> _Rg>
1096 unordered_multimap(from_range_t, _Rg&& __rg, size_type __n,
1097 const allocator_type& __a)
1098 : _Base(from_range, std::forward<_Rg>(__rg), __n, __a)
1101 template<__detail::__container_compatible_range<value_type> _Rg>
1102 unordered_multimap(from_range_t, _Rg&& __rg, size_type __n,
1103 const hasher& __hf, const allocator_type& __a)
1104 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __a)
1108 ~unordered_multimap() = default;
1111 operator=(const unordered_multimap&) = default;
1114 operator=(unordered_multimap&&) = default;
1117 operator=(initializer_list<value_type> __l)
1119 _Base::operator=(__l);
1120 this->_M_invalidate_all();
1124 using _Base::get_allocator;
1127 using _Base::max_size;
1130 swap(unordered_multimap& __x)
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 };
1183 const_local_iterator
1184 begin(size_type __b) const
1186 __glibcxx_check_bucket_index(__b);
1187 return { _Base::begin(__b), this };
1190 const_local_iterator
1191 end(size_type __b) const
1193 __glibcxx_check_bucket_index(__b);
1194 return { _Base::end(__b), this };
1197 const_local_iterator
1198 cbegin(size_type __b) const
1200 __glibcxx_check_bucket_index(__b);
1201 return { _Base::cbegin(__b), this };
1204 const_local_iterator
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>
1245 emplace_hint(const_iterator __hint, _Args&&... __args)
1247 __glibcxx_check_insert(__hint);
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 };
1264 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1265 // 2354. Unnecessary copying when inserting into maps with braced-init
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 };
1276 insert(const_iterator __hint, const value_type& __obj)
1278 __glibcxx_check_insert(__hint);
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 };
1285 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1286 // 2354. Unnecessary copying when inserting into maps with braced-init
1288 insert(const_iterator __hint, value_type&& __x)
1290 __glibcxx_check_insert(__hint);
1291 size_type __bucket_count = this->bucket_count();
1292 auto __it = _Base::insert(__hint.base(), std::move(__x));
1293 _M_check_rehashed(__bucket_count);
1294 return { __it, this };
1297 template<typename _Pair, typename = typename
1298 std::enable_if<std::is_constructible<value_type,
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
1310 std::enable_if<std::is_constructible<value_type,
1311 _Pair&&>::value>::type>
1313 insert(const_iterator __hint, _Pair&& __obj)
1315 __glibcxx_check_insert(__hint);
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 };
1323 insert(std::initializer_list<value_type> __l)
1324 { _Base::insert(__l); }
1326 template<typename _InputIterator>
1328 insert(_InputIterator __first, _InputIterator __last)
1330 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
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;
1347 extract(const_iterator __position)
1349 __glibcxx_check_erase(__position);
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 }; }
1367 insert(const_iterator __hint, node_type&& __nh)
1369 __glibcxx_check_insert(__hint);
1370 return { _Base::insert(__hint.base(), std::move(__nh)), this };
1373 template<typename _H2, typename _P2>
1375 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1378 = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
1379 _Base::merge(__source);
1382 template<typename _H2, typename _P2>
1384 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1385 { merge(__source); }
1387 template<typename _H2, typename _P2>
1389 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1392 = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
1393 _Base::merge(__source);
1396 template<typename _H2, typename _P2>
1398 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
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;
1436 std::pair<iterator, iterator>
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>>
1447 std::pair<iterator, iterator>
1448 equal_range(const _Kt& __k)
1450 auto __res = _Base::equal_range(__k);
1451 return { { __res.first, this }, { __res.second, this } };
1455 std::pair<const_iterator, const_iterator>
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>>
1466 std::pair<const_iterator, const_iterator>
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);
1492 erase(const_iterator __it)
1494 __glibcxx_check_erase(__it);
1495 return { _M_erase(__it.base()), this };
1499 erase(_Base_const_iterator __it)
1501 __glibcxx_check_erase2(__it);
1502 return _M_erase(__it);
1506 erase(iterator __it)
1508 __glibcxx_check_erase(__it);
1509 return { _M_erase(__it.base()), this };
1513 erase(const_iterator __first, const_iterator __last)
1515 __glibcxx_check_erase_range(__first, __last);
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();
1549 _M_invalidate(_Base_const_iterator __victim)
1551 this->_M_invalidate_if(
1552 [__victim](_Base_const_iterator __it) { return __it == __victim; });
1553 this->_M_invalidate_local_if(
1554 [__victim](_Base_const_local_iterator __it)
1555 { return __it == __victim; });
1559 _M_erase(_Base_const_iterator __victim)
1561 _M_invalidate(__victim);
1562 size_type __bucket_count = this->bucket_count();
1563 _Base_iterator __next = _Base::erase(__victim);
1564 _M_check_rehashed(__bucket_count);
1568 #if __cplusplus > 201402L
1570 _M_extract(_Base_const_iterator __victim)
1572 _M_invalidate(__victim);
1573 return _Base::extract(__victim);
1578 #if __cpp_deduction_guides >= 201606
1580 template<typename _InputIterator,
1581 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1582 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1583 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1584 typename = _RequireInputIter<_InputIterator>,
1585 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1586 typename = _RequireNotAllocator<_Pred>,
1587 typename = _RequireAllocator<_Allocator>>
1588 unordered_multimap(_InputIterator, _InputIterator,
1589 unordered_multimap<int, int>::size_type = {},
1590 _Hash = _Hash(), _Pred = _Pred(),
1591 _Allocator = _Allocator())
1592 -> unordered_multimap<__iter_key_t<_InputIterator>,
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>>
1602 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1603 unordered_multimap<int, int>::size_type = {},
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 // C++ >= 23
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); }
1728 } // namespace __debug