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
33#pragma GCC system_header
36#if __cplusplus < 201103L
37# include <bits/c++0x_warning.h>
39# include <bits/c++config.h>
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;
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>
56namespace 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 ~unordered_map() = default;
207 operator=(const unordered_map&) = default;
210 operator=(unordered_map&&) = default;
213 operator=(initializer_list<value_type> __l)
215 _Base::operator=(__l);
216 this->_M_invalidate_all();
220 using _Base::get_allocator;
223 using _Base::max_size;
226 swap(unordered_map& __x)
227 noexcept( noexcept(declval<_Base&>().swap(__x)) )
237 this->_M_invalidate_all();
242 { return { _Base::begin(), this }; }
245 begin() const noexcept
246 { return { _Base::begin(), this }; }
250 { return { _Base::end(), this }; }
254 { return { _Base::end(), this }; }
257 cbegin() const noexcept
258 { return { _Base::cbegin(), this }; }
261 cend() const noexcept
262 { return { _Base::cend(), this }; }
268 __glibcxx_check_bucket_index(__b);
269 return { _Base::begin(__b), this };
275 __glibcxx_check_bucket_index(__b);
276 return { _Base::end(__b), this };
280 begin(size_type __b) const
282 __glibcxx_check_bucket_index(__b);
283 return { _Base::begin(__b), this };
287 end(size_type __b) const
289 __glibcxx_check_bucket_index(__b);
290 return { _Base::end(__b), this };
294 cbegin(size_type __b) const
296 __glibcxx_check_bucket_index(__b);
297 return { _Base::cbegin(__b), this };
301 cend(size_type __b) const
303 __glibcxx_check_bucket_index(__b);
304 return { _Base::cend(__b), this };
307 using _Base::bucket_count;
308 using _Base::max_bucket_count;
312 bucket_size(size_type __b) const
314 __glibcxx_check_bucket_index(__b);
315 return _Base::bucket_size(__b);
318 using _Base::load_factor;
321 max_load_factor() const noexcept
322 { return _Base::max_load_factor(); }
325 max_load_factor(float __f)
327 __glibcxx_check_max_load_factor(__f);
328 _Base::max_load_factor(__f);
331 template<typename... _Args>
332 std::pair<iterator, bool>
333 emplace(_Args&&... __args)
335 size_type __bucket_count = this->bucket_count();
336 auto __res = _Base::emplace(std::forward<_Args>(__args)...);
337 _M_check_rehashed(__bucket_count);
338 return { { __res.first, this }, __res.second };
341 template<typename... _Args>
343 emplace_hint(const_iterator __hint, _Args&&... __args)
345 __glibcxx_check_insert(__hint);
346 size_type __bucket_count = this->bucket_count();
347 auto __it = _Base::emplace_hint(__hint.base(),
348 std::forward<_Args>(__args)...);
349 _M_check_rehashed(__bucket_count);
350 return { __it, this };
353 std::pair<iterator, bool>
354 insert(const value_type& __obj)
356 size_type __bucket_count = this->bucket_count();
357 auto __res = _Base::insert(__obj);
358 _M_check_rehashed(__bucket_count);
359 return { { __res.first, this }, __res.second };
362 // _GLIBCXX_RESOLVE_LIB_DEFECTS
363 // 2354. Unnecessary copying when inserting into maps with braced-init
364 std::pair<iterator, bool>
365 insert(value_type&& __x)
367 size_type __bucket_count = this->bucket_count();
368 auto __res = _Base::insert(std::move(__x));
369 _M_check_rehashed(__bucket_count);
370 return { { __res.first, this }, __res.second };
373 template<typename _Pair, typename = typename
374 std::enable_if<std::is_constructible<value_type,
375 _Pair&&>::value>::type>
376 std::pair<iterator, bool>
377 insert(_Pair&& __obj)
379 size_type __bucket_count = this->bucket_count();
380 auto __res = _Base::insert(std::forward<_Pair>(__obj));
381 _M_check_rehashed(__bucket_count);
382 return { { __res.first, this }, __res.second };
386 insert(const_iterator __hint, const value_type& __obj)
388 __glibcxx_check_insert(__hint);
389 size_type __bucket_count = this->bucket_count();
390 auto __it = _Base::insert(__hint.base(), __obj);
391 _M_check_rehashed(__bucket_count);
392 return { __it, this };
395 // _GLIBCXX_RESOLVE_LIB_DEFECTS
396 // 2354. Unnecessary copying when inserting into maps with braced-init
398 insert(const_iterator __hint, value_type&& __x)
400 __glibcxx_check_insert(__hint);
401 size_type __bucket_count = this->bucket_count();
402 auto __it = _Base::insert(__hint.base(), std::move(__x));
403 _M_check_rehashed(__bucket_count);
404 return { __it, this };
407 template<typename _Pair, typename = typename
408 std::enable_if<std::is_constructible<value_type,
409 _Pair&&>::value>::type>
411 insert(const_iterator __hint, _Pair&& __obj)
413 __glibcxx_check_insert(__hint);
414 size_type __bucket_count = this->bucket_count();
415 auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
416 _M_check_rehashed(__bucket_count);
417 return { __it, this };
421 insert(std::initializer_list<value_type> __l)
423 size_type __bucket_count = this->bucket_count();
425 _M_check_rehashed(__bucket_count);
428 template<typename _InputIterator>
430 insert(_InputIterator __first, _InputIterator __last)
432 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
433 __glibcxx_check_valid_range2(__first, __last, __dist);
434 size_type __bucket_count = this->bucket_count();
436 if (__dist.second >= __gnu_debug::__dp_sign)
437 _Base::insert(__gnu_debug::__unsafe(__first),
438 __gnu_debug::__unsafe(__last));
440 _Base::insert(__first, __last);
442 _M_check_rehashed(__bucket_count);
445#ifdef __glibcxx_unordered_map_try_emplace // C++ >= 17 && HOSTED
446 template <typename... _Args>
448 try_emplace(const key_type& __k, _Args&&... __args)
450 auto __res = _Base::try_emplace(__k,
451 std::forward<_Args>(__args)...);
452 return { { __res.first, this }, __res.second };
455 template <typename... _Args>
457 try_emplace(key_type&& __k, _Args&&... __args)
459 auto __res = _Base::try_emplace(std::move(__k),
460 std::forward<_Args>(__args)...);
461 return { { __res.first, this }, __res.second };
464 template <typename... _Args>
466 try_emplace(const_iterator __hint, const key_type& __k,
469 __glibcxx_check_insert(__hint);
470 return { _Base::try_emplace(__hint.base(), __k,
471 std::forward<_Args>(__args)...),
475 template <typename... _Args>
477 try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
479 __glibcxx_check_insert(__hint);
480 return { _Base::try_emplace(__hint.base(), std::move(__k),
481 std::forward<_Args>(__args)...),
485 template <typename _Obj>
487 insert_or_assign(const key_type& __k, _Obj&& __obj)
489 auto __res = _Base::insert_or_assign(__k,
490 std::forward<_Obj>(__obj));
491 return { { __res.first, this }, __res.second };
494 template <typename _Obj>
496 insert_or_assign(key_type&& __k, _Obj&& __obj)
498 auto __res = _Base::insert_or_assign(std::move(__k),
499 std::forward<_Obj>(__obj));
500 return { { __res.first, this }, __res.second };
503 template <typename _Obj>
505 insert_or_assign(const_iterator __hint, const key_type& __k,
508 __glibcxx_check_insert(__hint);
509 return { _Base::insert_or_assign(__hint.base(), __k,
510 std::forward<_Obj>(__obj)),
514 template <typename _Obj>
516 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
518 __glibcxx_check_insert(__hint);
519 return { _Base::insert_or_assign(__hint.base(), std::move(__k),
520 std::forward<_Obj>(__obj)),
525#if __cplusplus > 201402L
526 using node_type = typename _Base::node_type;
527 using insert_return_type = _Node_insert_return<iterator, node_type>;
530 extract(const_iterator __position)
532 __glibcxx_check_erase(__position);
533 return _M_extract(__position.base());
537 extract(const key_type& __key)
539 const auto __position = _Base::find(__key);
540 if (__position != _Base::end())
541 return _M_extract(__position);
546 insert(node_type&& __nh)
548 auto __ret = _Base::insert(std::move(__nh));
550 { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };
554 insert(const_iterator __hint, node_type&& __nh)
556 __glibcxx_check_insert(__hint);
557 return { _Base::insert(__hint.base(), std::move(__nh)), this };
560 template<typename _H2, typename _P2>
562 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
565 = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
566 _Base::merge(__source);
569 template<typename _H2, typename _P2>
571 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
574 template<typename _H2, typename _P2>
576 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
579 = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
580 _Base::merge(__source);
583 template<typename _H2, typename _P2>
585 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
589 using _Base::hash_function;
593 find(const key_type& __key)
594 { return { _Base::find(__key), this }; }
596#if __cplusplus > 201703L
597 template<typename _Kt,
598 typename = std::__has_is_transparent_t<_Hash, _Kt>,
599 typename = std::__has_is_transparent_t<_Pred, _Kt>>
602 { return { _Base::find(__k), this }; }
606 find(const key_type& __key) const
607 { return { _Base::find(__key), this }; }
609#if __cplusplus > 201703L
610 template<typename _Kt,
611 typename = std::__has_is_transparent_t<_Hash, _Kt>,
612 typename = std::__has_is_transparent_t<_Pred, _Kt>>
614 find(const _Kt& __k) const
615 { return { _Base::find(__k), this }; }
619#if __cplusplus > 201703L
620 using _Base::contains;
623 std::pair<iterator, iterator>
624 equal_range(const key_type& __key)
626 auto __res = _Base::equal_range(__key);
627 return { { __res.first, this }, { __res.second, this } };
630#if __cplusplus > 201703L
631 template<typename _Kt,
632 typename = std::__has_is_transparent_t<_Hash, _Kt>,
633 typename = std::__has_is_transparent_t<_Pred, _Kt>>
634 std::pair<iterator, iterator>
635 equal_range(const _Kt& __k)
637 auto __res = _Base::equal_range(__k);
638 return { { __res.first, this }, { __res.second, this } };
642 std::pair<const_iterator, const_iterator>
643 equal_range(const key_type& __key) const
645 auto __res = _Base::equal_range(__key);
646 return { { __res.first, this }, { __res.second, this } };
649#if __cplusplus > 201703L
650 template<typename _Kt,
651 typename = std::__has_is_transparent_t<_Hash, _Kt>,
652 typename = std::__has_is_transparent_t<_Pred, _Kt>>
653 std::pair<const_iterator, const_iterator>
654 equal_range(const _Kt& __k) const
656 auto __res = _Base::equal_range(__k);
657 return { { __res.first, this }, { __res.second, this } };
661 using _Base::operator[];
665 erase(const key_type& __key)
668 auto __victim = _Base::find(__key);
669 if (__victim != _Base::end())
678 erase(const_iterator __it)
680 __glibcxx_check_erase(__it);
681 return { _M_erase(__it.base()), this };
685 erase(_Base_const_iterator __it)
687 __glibcxx_check_erase2(__it);
688 return _M_erase(__it);
694 __glibcxx_check_erase(__it);
695 return { _M_erase(__it.base()), this };
699 erase(const_iterator __first, const_iterator __last)
701 __glibcxx_check_erase_range(__first, __last);
702 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
704 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
705 _M_message(__gnu_debug::__msg_valid_range)
706 ._M_iterator(__first, "first")
707 ._M_iterator(__last, "last"));
708 _M_invalidate(__tmp);
711 size_type __bucket_count = this->bucket_count();
712 auto __next = _Base::erase(__first.base(), __last.base());
713 _M_check_rehashed(__bucket_count);
714 return { __next, this };
718 using _Base::reserve;
721 _M_base() noexcept { return *this; }
724 _M_base() const noexcept { return *this; }
728 _M_check_rehashed(size_type __prev_count)
730 if (__prev_count != this->bucket_count())
731 this->_M_invalidate_all();
735 _M_invalidate(_Base_const_iterator __victim)
737 this->_M_invalidate_if(
738 [__victim](_Base_const_iterator __it) { return __it == __victim; });
739 this->_M_invalidate_local_if(
740 [__victim](_Base_const_local_iterator __it)
741 { return __it == __victim; });
745 _M_erase(_Base_const_iterator __victim)
747 _M_invalidate(__victim);
748 size_type __bucket_count = this->bucket_count();
749 _Base_iterator __next = _Base::erase(__victim);
750 _M_check_rehashed(__bucket_count);
754#if __cplusplus > 201402L
756 _M_extract(_Base_const_iterator __victim)
758 _M_invalidate(__victim);
759 return _Base::extract(__victim);
764#if __cpp_deduction_guides >= 201606
766 template<typename _InputIterator,
767 typename _Hash = hash<__iter_key_t<_InputIterator>>,
768 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
769 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
770 typename = _RequireInputIter<_InputIterator>,
771 typename = _RequireNotAllocatorOrIntegral<_Hash>,
772 typename = _RequireNotAllocator<_Pred>,
773 typename = _RequireAllocator<_Allocator>>
774 unordered_map(_InputIterator, _InputIterator,
775 typename unordered_map<int, int>::size_type = {},
776 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
777 -> unordered_map<__iter_key_t<_InputIterator>,
778 __iter_val_t<_InputIterator>,
779 _Hash, _Pred, _Allocator>;
781 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
782 typename _Pred = equal_to<_Key>,
783 typename _Allocator = allocator<pair<const _Key, _Tp>>,
784 typename = _RequireNotAllocatorOrIntegral<_Hash>,
785 typename = _RequireNotAllocator<_Pred>,
786 typename = _RequireAllocator<_Allocator>>
787 unordered_map(initializer_list<pair<_Key, _Tp>>,
788 typename unordered_map<int, int>::size_type = {},
789 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
790 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
792 template<typename _InputIterator, typename _Allocator,
793 typename = _RequireInputIter<_InputIterator>,
794 typename = _RequireAllocator<_Allocator>>
795 unordered_map(_InputIterator, _InputIterator,
796 typename unordered_map<int, int>::size_type, _Allocator)
797 -> unordered_map<__iter_key_t<_InputIterator>,
798 __iter_val_t<_InputIterator>,
799 hash<__iter_key_t<_InputIterator>>,
800 equal_to<__iter_key_t<_InputIterator>>,
803 template<typename _InputIterator, typename _Allocator,
804 typename = _RequireInputIter<_InputIterator>,
805 typename = _RequireAllocator<_Allocator>>
806 unordered_map(_InputIterator, _InputIterator, _Allocator)
807 -> unordered_map<__iter_key_t<_InputIterator>,
808 __iter_val_t<_InputIterator>,
809 hash<__iter_key_t<_InputIterator>>,
810 equal_to<__iter_key_t<_InputIterator>>,
813 template<typename _InputIterator, typename _Hash, typename _Allocator,
814 typename = _RequireInputIter<_InputIterator>,
815 typename = _RequireNotAllocatorOrIntegral<_Hash>,
816 typename = _RequireAllocator<_Allocator>>
817 unordered_map(_InputIterator, _InputIterator,
818 typename unordered_map<int, int>::size_type,
820 -> unordered_map<__iter_key_t<_InputIterator>,
821 __iter_val_t<_InputIterator>, _Hash,
822 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
824 template<typename _Key, typename _Tp, typename _Allocator,
825 typename = _RequireAllocator<_Allocator>>
826 unordered_map(initializer_list<pair<_Key, _Tp>>,
827 typename unordered_map<int, int>::size_type,
829 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
831 template<typename _Key, typename _Tp, typename _Allocator,
832 typename = _RequireAllocator<_Allocator>>
833 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
834 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
836 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
837 typename = _RequireNotAllocatorOrIntegral<_Hash>,
838 typename = _RequireAllocator<_Allocator>>
839 unordered_map(initializer_list<pair<_Key, _Tp>>,
840 typename unordered_map<int, int>::size_type,
842 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
846 template<typename _Key, typename _Tp, typename _Hash,
847 typename _Pred, typename _Alloc>
849 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
850 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
851 noexcept(noexcept(__x.swap(__y)))
854 template<typename _Key, typename _Tp, typename _Hash,
855 typename _Pred, typename _Alloc>
857 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
858 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
859 { return __x._M_base() == __y._M_base(); }
861#if __cpp_impl_three_way_comparison < 201907L
862 template<typename _Key, typename _Tp, typename _Hash,
863 typename _Pred, typename _Alloc>
865 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
866 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
867 { return !(__x == __y); }
870 /// Class std::unordered_multimap with safety/checking/debug instrumentation.
871 template<typename _Key, typename _Tp,
872 typename _Hash = std::hash<_Key>,
873 typename _Pred = std::equal_to<_Key>,
874 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
875 class unordered_multimap
876 : public __gnu_debug::_Safe_container<
877 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
878 __gnu_debug::_Safe_unordered_container>,
879 public _GLIBCXX_STD_C::unordered_multimap<
880 _Key, _Tp, _Hash, _Pred, _Alloc>
882 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
883 _Pred, _Alloc> _Base;
884 typedef __gnu_debug::_Safe_container<unordered_multimap,
885 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
886 typedef typename _Base::const_iterator _Base_const_iterator;
887 typedef typename _Base::iterator _Base_iterator;
888 typedef typename _Base::const_local_iterator _Base_const_local_iterator;
889 typedef typename _Base::local_iterator _Base_local_iterator;
891 template<typename _ItT, typename _SeqT, typename _CatT>
892 friend class ::__gnu_debug::_Safe_iterator;
893 template<typename _ItT, typename _SeqT>
894 friend class ::__gnu_debug::_Safe_local_iterator;
896 // Reference wrapper for base class. See PR libstdc++/90102.
899 _Base_ref(const _Base& __r) : _M_ref(__r) { }
905 typedef typename _Base::size_type size_type;
906 typedef typename _Base::hasher hasher;
907 typedef typename _Base::key_equal key_equal;
908 typedef typename _Base::allocator_type allocator_type;
910 typedef typename _Base::key_type key_type;
911 typedef typename _Base::value_type value_type;
912 typedef typename _Base::mapped_type mapped_type;
914 typedef typename _Base::pointer pointer;
915 typedef typename _Base::const_pointer const_pointer;
916 typedef typename _Base::reference reference;
917 typedef typename _Base::const_reference const_reference;
918 typedef __gnu_debug::_Safe_iterator<
919 _Base_iterator, unordered_multimap> iterator;
920 typedef __gnu_debug::_Safe_iterator<
921 _Base_const_iterator, unordered_multimap> const_iterator;
922 typedef __gnu_debug::_Safe_local_iterator<
923 _Base_local_iterator, unordered_multimap> local_iterator;
924 typedef __gnu_debug::_Safe_local_iterator<
925 _Base_const_local_iterator, unordered_multimap> const_local_iterator;
926 typedef typename _Base::difference_type difference_type;
928 unordered_multimap() = default;
931 unordered_multimap(size_type __n,
932 const hasher& __hf = hasher(),
933 const key_equal& __eql = key_equal(),
934 const allocator_type& __a = allocator_type())
935 : _Base(__n, __hf, __eql, __a) { }
937 template<typename _InputIterator>
938 unordered_multimap(_InputIterator __first, _InputIterator __last,
940 const hasher& __hf = hasher(),
941 const key_equal& __eql = key_equal(),
942 const allocator_type& __a = allocator_type())
943 : _Base(__gnu_debug::__base(
944 __glibcxx_check_valid_constructor_range(__first, __last)),
945 __gnu_debug::__base(__last), __n,
946 __hf, __eql, __a) { }
948 unordered_multimap(const unordered_multimap&) = default;
950 unordered_multimap(_Base_ref __x)
951 : _Base(__x._M_ref) { }
953 unordered_multimap(unordered_multimap&&) = default;
956 unordered_multimap(const allocator_type& __a)
959 unordered_multimap(const unordered_multimap& __umap,
960 const allocator_type& __a)
961 : _Base(__umap, __a) { }
963 unordered_multimap(unordered_multimap&& __umap,
964 const allocator_type& __a)
965 noexcept( noexcept(_Base(std::move(__umap), __a)) )
966 : _Safe(std::move(__umap), __a),
967 _Base(std::move(__umap), __a) { }
969 unordered_multimap(initializer_list<value_type> __l,
971 const hasher& __hf = hasher(),
972 const key_equal& __eql = key_equal(),
973 const allocator_type& __a = allocator_type())
974 : _Base(__l, __n, __hf, __eql, __a) { }
976 unordered_multimap(size_type __n, const allocator_type& __a)
977 : unordered_multimap(__n, hasher(), key_equal(), __a)
980 unordered_multimap(size_type __n, const hasher& __hf,
981 const allocator_type& __a)
982 : unordered_multimap(__n, __hf, key_equal(), __a)
985 template<typename _InputIterator>
986 unordered_multimap(_InputIterator __first, _InputIterator __last,
988 const allocator_type& __a)
989 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
992 template<typename _InputIterator>
993 unordered_multimap(_InputIterator __first, _InputIterator __last,
994 size_type __n, const hasher& __hf,
995 const allocator_type& __a)
996 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
999 unordered_multimap(initializer_list<value_type> __l,
1001 const allocator_type& __a)
1002 : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
1005 unordered_multimap(initializer_list<value_type> __l,
1006 size_type __n, const hasher& __hf,
1007 const allocator_type& __a)
1008 : unordered_multimap(__l, __n, __hf, key_equal(), __a)
1011 ~unordered_multimap() = default;
1014 operator=(const unordered_multimap&) = default;
1017 operator=(unordered_multimap&&) = default;
1020 operator=(initializer_list<value_type> __l)
1022 _Base::operator=(__l);
1023 this->_M_invalidate_all();
1027 using _Base::get_allocator;
1030 using _Base::max_size;
1033 swap(unordered_multimap& __x)
1034 noexcept( noexcept(declval<_Base&>().swap(__x)) )
1036 _Safe::_M_swap(__x);
1044 this->_M_invalidate_all();
1049 { return { _Base::begin(), this }; }
1052 begin() const noexcept
1053 { return { _Base::begin(), this }; }
1057 { return { _Base::end(), this }; }
1060 end() const noexcept
1061 { return { _Base::end(), this }; }
1064 cbegin() const noexcept
1065 { return { _Base::cbegin(), this }; }
1068 cend() const noexcept
1069 { return { _Base::cend(), this }; }
1073 begin(size_type __b)
1075 __glibcxx_check_bucket_index(__b);
1076 return { _Base::begin(__b), this };
1082 __glibcxx_check_bucket_index(__b);
1083 return { _Base::end(__b), this };
1086 const_local_iterator
1087 begin(size_type __b) const
1089 __glibcxx_check_bucket_index(__b);
1090 return { _Base::begin(__b), this };
1093 const_local_iterator
1094 end(size_type __b) const
1096 __glibcxx_check_bucket_index(__b);
1097 return { _Base::end(__b), this };
1100 const_local_iterator
1101 cbegin(size_type __b) const
1103 __glibcxx_check_bucket_index(__b);
1104 return { _Base::cbegin(__b), this };
1107 const_local_iterator
1108 cend(size_type __b) const
1110 __glibcxx_check_bucket_index(__b);
1111 return { _Base::cend(__b), this };
1114 using _Base::bucket_count;
1115 using _Base::max_bucket_count;
1116 using _Base::bucket;
1119 bucket_size(size_type __b) const
1121 __glibcxx_check_bucket_index(__b);
1122 return _Base::bucket_size(__b);
1126 max_load_factor() const noexcept
1127 { return _Base::max_load_factor(); }
1130 max_load_factor(float __f)
1132 __glibcxx_check_max_load_factor(__f);
1133 _Base::max_load_factor(__f);
1136 template<typename... _Args>
1138 emplace(_Args&&... __args)
1140 size_type __bucket_count = this->bucket_count();
1141 auto __it = _Base::emplace(std::forward<_Args>(__args)...);
1142 _M_check_rehashed(__bucket_count);
1143 return { __it, this };
1146 template<typename... _Args>
1148 emplace_hint(const_iterator __hint, _Args&&... __args)
1150 __glibcxx_check_insert(__hint);
1151 size_type __bucket_count = this->bucket_count();
1152 auto __it = _Base::emplace_hint(__hint.base(),
1153 std::forward<_Args>(__args)...);
1154 _M_check_rehashed(__bucket_count);
1155 return { __it, this };
1159 insert(const value_type& __obj)
1161 size_type __bucket_count = this->bucket_count();
1162 auto __it = _Base::insert(__obj);
1163 _M_check_rehashed(__bucket_count);
1164 return { __it, this };
1167 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1168 // 2354. Unnecessary copying when inserting into maps with braced-init
1170 insert(value_type&& __x)
1172 size_type __bucket_count = this->bucket_count();
1173 auto __it = _Base::insert(std::move(__x));
1174 _M_check_rehashed(__bucket_count);
1175 return { __it, this };
1179 insert(const_iterator __hint, const value_type& __obj)
1181 __glibcxx_check_insert(__hint);
1182 size_type __bucket_count = this->bucket_count();
1183 auto __it = _Base::insert(__hint.base(), __obj);
1184 _M_check_rehashed(__bucket_count);
1185 return { __it, this };
1188 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1189 // 2354. Unnecessary copying when inserting into maps with braced-init
1191 insert(const_iterator __hint, value_type&& __x)
1193 __glibcxx_check_insert(__hint);
1194 size_type __bucket_count = this->bucket_count();
1195 auto __it = _Base::insert(__hint.base(), std::move(__x));
1196 _M_check_rehashed(__bucket_count);
1197 return { __it, this };
1200 template<typename _Pair, typename = typename
1201 std::enable_if<std::is_constructible<value_type,
1202 _Pair&&>::value>::type>
1204 insert(_Pair&& __obj)
1206 size_type __bucket_count = this->bucket_count();
1207 auto __it = _Base::insert(std::forward<_Pair>(__obj));
1208 _M_check_rehashed(__bucket_count);
1209 return { __it, this };
1212 template<typename _Pair, typename = typename
1213 std::enable_if<std::is_constructible<value_type,
1214 _Pair&&>::value>::type>
1216 insert(const_iterator __hint, _Pair&& __obj)
1218 __glibcxx_check_insert(__hint);
1219 size_type __bucket_count = this->bucket_count();
1220 auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
1221 _M_check_rehashed(__bucket_count);
1222 return { __it, this };
1226 insert(std::initializer_list<value_type> __l)
1227 { _Base::insert(__l); }
1229 template<typename _InputIterator>
1231 insert(_InputIterator __first, _InputIterator __last)
1233 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
1234 __glibcxx_check_valid_range2(__first, __last, __dist);
1235 size_type __bucket_count = this->bucket_count();
1237 if (__dist.second >= __gnu_debug::__dp_sign)
1238 _Base::insert(__gnu_debug::__unsafe(__first),
1239 __gnu_debug::__unsafe(__last));
1241 _Base::insert(__first, __last);
1243 _M_check_rehashed(__bucket_count);
1246#if __cplusplus > 201402L
1247 using node_type = typename _Base::node_type;
1250 extract(const_iterator __position)
1252 __glibcxx_check_erase(__position);
1253 return _M_extract(__position.base());
1257 extract(const key_type& __key)
1259 const auto __position = _Base::find(__key);
1260 if (__position != _Base::end())
1261 return _M_extract(__position);
1266 insert(node_type&& __nh)
1267 { return { _Base::insert(std::move(__nh)), this }; }
1270 insert(const_iterator __hint, node_type&& __nh)
1272 __glibcxx_check_insert(__hint);
1273 return { _Base::insert(__hint.base(), std::move(__nh)), this };
1276 template<typename _H2, typename _P2>
1278 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1281 = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
1282 _Base::merge(__source);
1285 template<typename _H2, typename _P2>
1287 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1288 { merge(__source); }
1290 template<typename _H2, typename _P2>
1292 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1295 = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
1296 _Base::merge(__source);
1299 template<typename _H2, typename _P2>
1301 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1302 { merge(__source); }
1305 using _Base::hash_function;
1306 using _Base::key_eq;
1309 find(const key_type& __key)
1310 { return { _Base::find(__key), this }; }
1312#if __cplusplus > 201703L
1313 template<typename _Kt,
1314 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1315 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1317 find(const _Kt& __k)
1318 { return { _Base::find(__k), this }; }
1322 find(const key_type& __key) const
1323 { return { _Base::find(__key), this }; }
1325#if __cplusplus > 201703L
1326 template<typename _Kt,
1327 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1328 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1330 find(const _Kt& __k) const
1331 { return { _Base::find(__k), this }; }
1335#if __cplusplus > 201703L
1336 using _Base::contains;
1339 std::pair<iterator, iterator>
1340 equal_range(const key_type& __key)
1342 auto __res = _Base::equal_range(__key);
1343 return { { __res.first, this }, { __res.second, this } };
1346#if __cplusplus > 201703L
1347 template<typename _Kt,
1348 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1349 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1350 std::pair<iterator, iterator>
1351 equal_range(const _Kt& __k)
1353 auto __res = _Base::equal_range(__k);
1354 return { { __res.first, this }, { __res.second, this } };
1358 std::pair<const_iterator, const_iterator>
1359 equal_range(const key_type& __key) const
1361 auto __res = _Base::equal_range(__key);
1362 return { { __res.first, this }, { __res.second, this } };
1365#if __cplusplus > 201703L
1366 template<typename _Kt,
1367 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1368 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1369 std::pair<const_iterator, const_iterator>
1370 equal_range(const _Kt& __k) const
1372 auto __res = _Base::equal_range(__k);
1373 return { { __res.first, this }, { __res.second, this } };
1378 erase(const key_type& __key)
1381 size_type __bucket_count = this->bucket_count();
1382 auto __pair = _Base::equal_range(__key);
1383 for (auto __victim = __pair.first; __victim != __pair.second;)
1385 _M_invalidate(__victim);
1386 __victim = _Base::erase(__victim);
1390 _M_check_rehashed(__bucket_count);
1395 erase(const_iterator __it)
1397 __glibcxx_check_erase(__it);
1398 return { _M_erase(__it.base()), this };
1402 erase(_Base_const_iterator __it)
1404 __glibcxx_check_erase2(__it);
1405 return _M_erase(__it);
1409 erase(iterator __it)
1411 __glibcxx_check_erase(__it);
1412 return { _M_erase(__it.base()), this };
1416 erase(const_iterator __first, const_iterator __last)
1418 __glibcxx_check_erase_range(__first, __last);
1419 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1421 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1422 _M_message(__gnu_debug::__msg_valid_range)
1423 ._M_iterator(__first, "first")
1424 ._M_iterator(__last, "last"));
1425 _M_invalidate(__tmp);
1428 size_type __bucket_count = this->bucket_count();
1429 auto __next = _Base::erase(__first.base(), __last.base());
1430 _M_check_rehashed(__bucket_count);
1431 return { __next, this };
1434 using _Base::rehash;
1435 using _Base::reserve;
1438 _M_base() noexcept { return *this; }
1441 _M_base() const noexcept { return *this; }
1445 _M_check_rehashed(size_type __prev_count)
1447 if (__prev_count != this->bucket_count())
1448 this->_M_invalidate_all();
1452 _M_invalidate(_Base_const_iterator __victim)
1454 this->_M_invalidate_if(
1455 [__victim](_Base_const_iterator __it) { return __it == __victim; });
1456 this->_M_invalidate_local_if(
1457 [__victim](_Base_const_local_iterator __it)
1458 { return __it == __victim; });
1462 _M_erase(_Base_const_iterator __victim)
1464 _M_invalidate(__victim);
1465 size_type __bucket_count = this->bucket_count();
1466 _Base_iterator __next = _Base::erase(__victim);
1467 _M_check_rehashed(__bucket_count);
1471#if __cplusplus > 201402L
1473 _M_extract(_Base_const_iterator __victim)
1475 _M_invalidate(__victim);
1476 return _Base::extract(__victim);
1481#if __cpp_deduction_guides >= 201606
1483 template<typename _InputIterator,
1484 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1485 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1486 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1487 typename = _RequireInputIter<_InputIterator>,
1488 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1489 typename = _RequireNotAllocator<_Pred>,
1490 typename = _RequireAllocator<_Allocator>>
1491 unordered_multimap(_InputIterator, _InputIterator,
1492 unordered_multimap<int, int>::size_type = {},
1493 _Hash = _Hash(), _Pred = _Pred(),
1494 _Allocator = _Allocator())
1495 -> unordered_multimap<__iter_key_t<_InputIterator>,
1496 __iter_val_t<_InputIterator>, _Hash, _Pred,
1499 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
1500 typename _Pred = equal_to<_Key>,
1501 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1502 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1503 typename = _RequireNotAllocator<_Pred>,
1504 typename = _RequireAllocator<_Allocator>>
1505 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1506 unordered_multimap<int, int>::size_type = {},
1507 _Hash = _Hash(), _Pred = _Pred(),
1508 _Allocator = _Allocator())
1509 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
1511 template<typename _InputIterator, typename _Allocator,
1512 typename = _RequireInputIter<_InputIterator>,
1513 typename = _RequireAllocator<_Allocator>>
1514 unordered_multimap(_InputIterator, _InputIterator,
1515 unordered_multimap<int, int>::size_type, _Allocator)
1516 -> unordered_multimap<__iter_key_t<_InputIterator>,
1517 __iter_val_t<_InputIterator>,
1518 hash<__iter_key_t<_InputIterator>>,
1519 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1521 template<typename _InputIterator, typename _Allocator,
1522 typename = _RequireInputIter<_InputIterator>,
1523 typename = _RequireAllocator<_Allocator>>
1524 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
1525 -> unordered_multimap<__iter_key_t<_InputIterator>,
1526 __iter_val_t<_InputIterator>,
1527 hash<__iter_key_t<_InputIterator>>,
1528 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1530 template<typename _InputIterator, typename _Hash, typename _Allocator,
1531 typename = _RequireInputIter<_InputIterator>,
1532 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1533 typename = _RequireAllocator<_Allocator>>
1534 unordered_multimap(_InputIterator, _InputIterator,
1535 unordered_multimap<int, int>::size_type, _Hash,
1537 -> unordered_multimap<__iter_key_t<_InputIterator>,
1538 __iter_val_t<_InputIterator>, _Hash,
1539 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1541 template<typename _Key, typename _Tp, typename _Allocator,
1542 typename = _RequireAllocator<_Allocator>>
1543 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1544 unordered_multimap<int, int>::size_type,
1546 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1548 template<typename _Key, typename _Tp, typename _Allocator,
1549 typename = _RequireAllocator<_Allocator>>
1550 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
1551 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1553 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
1554 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1555 typename = _RequireAllocator<_Allocator>>
1556 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1557 unordered_multimap<int, int>::size_type,
1559 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1563 template<typename _Key, typename _Tp, typename _Hash,
1564 typename _Pred, typename _Alloc>
1566 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1567 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1568 noexcept(noexcept(__x.swap(__y)))
1571 template<typename _Key, typename _Tp, typename _Hash,
1572 typename _Pred, typename _Alloc>
1574 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1575 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1576 { return __x._M_base() == __y._M_base(); }
1578#if __cpp_impl_three_way_comparison < 201907L
1579 template<typename _Key, typename _Tp, typename _Hash,
1580 typename _Pred, typename _Alloc>
1582 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1583 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1584 { return !(__x == __y); }
1587} // namespace __debug