1 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
3 // Copyright (C) 2003-2020 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 #pragma GCC system_header
34 #if __cplusplus < 201103L
35 # include <bits/c++0x_warning.h>
37 # include <bits/c++config.h>
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,
44 class unordered_multimap;
45 } } // namespace std::__debug
47 # include <unordered_map>
49 #include <debug/safe_unordered_container.h>
50 #include <debug/safe_container.h>
51 #include <debug/safe_iterator.h>
52 #include <debug/safe_local_iterator.h>
54 namespace std _GLIBCXX_VISIBILITY(default)
58 /// Class std::unordered_map with safety/checking/debug instrumentation.
59 template<typename _Key, typename _Tp,
60 typename _Hash = std::hash<_Key>,
61 typename _Pred = std::equal_to<_Key>,
62 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
64 : public __gnu_debug::_Safe_container<
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,
71 typedef __gnu_debug::_Safe_container<unordered_map,
72 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
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;
84 // Reference wrapper for base class. See PR libstdc++/90102.
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;
101 typedef __gnu_debug::_Safe_iterator<
102 _Base_iterator, unordered_map> iterator;
103 typedef __gnu_debug::_Safe_iterator<
104 _Base_const_iterator, unordered_map> const_iterator;
105 typedef __gnu_debug::_Safe_local_iterator<
106 _Base_local_iterator, unordered_map> local_iterator;
107 typedef __gnu_debug::_Safe_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>
313 std::pair<iterator, bool>
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)
326 __glibcxx_check_insert(__hint);
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 };
334 std::pair<iterator, bool>
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 };
343 // _GLIBCXX_RESOLVE_LIB_DEFECTS
344 // 2354. Unnecessary copying when inserting into maps with braced-init
345 std::pair<iterator, bool>
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
355 std::enable_if<std::is_constructible<value_type,
356 _Pair&&>::value>::type>
357 std::pair<iterator, bool>
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)
369 __glibcxx_check_insert(__hint);
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 };
376 // _GLIBCXX_RESOLVE_LIB_DEFECTS
377 // 2354. Unnecessary copying when inserting into maps with braced-init
379 insert(const_iterator __hint, value_type&& __x)
381 __glibcxx_check_insert(__hint);
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
389 std::enable_if<std::is_constructible<value_type,
390 _Pair&&>::value>::type>
392 insert(const_iterator __hint, _Pair&& __obj)
394 __glibcxx_check_insert(__hint);
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 };
402 insert(std::initializer_list<value_type> __l)
404 size_type __bucket_count = this->bucket_count();
406 _M_check_rehashed(__bucket_count);
409 template<typename _InputIterator>
411 insert(_InputIterator __first, _InputIterator __last)
413 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
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,
450 __glibcxx_check_insert(__hint);
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)
460 __glibcxx_check_insert(__hint);
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,
489 __glibcxx_check_insert(__hint);
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)
499 __glibcxx_check_insert(__hint);
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)
513 __glibcxx_check_erase(__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)
537 __glibcxx_check_insert(__hint);
538 return { _Base::insert(__hint.base(), std::move(__nh)), this };
545 find(const key_type& __key)
546 { return { _Base::find(__key), this }; }
549 find(const key_type& __key) const
550 { return { _Base::find(__key), this }; }
552 std::pair<iterator, iterator>
553 equal_range(const key_type& __key)
555 auto __res = _Base::equal_range(__key);
556 return { { __res.first, this }, { __res.second, this } };
559 std::pair<const_iterator, const_iterator>
560 equal_range(const key_type& __key) const
562 auto __res = _Base::equal_range(__key);
563 return { { __res.first, this }, { __res.second, this } };
567 erase(const key_type& __key)
570 auto __victim = _Base::find(__key);
571 if (__victim != _Base::end())
580 erase(const_iterator __it)
582 __glibcxx_check_erase(__it);
583 return { _M_erase(__it.base()), this };
589 __glibcxx_check_erase(__it);
590 return { _M_erase(__it.base()), this };
594 erase(const_iterator __first, const_iterator __last)
596 __glibcxx_check_erase_range(__first, __last);
597 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
599 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
600 _M_message(__gnu_debug::__msg_valid_range)
601 ._M_iterator(__first, "first")
602 ._M_iterator(__last, "last"));
603 _M_invalidate(__tmp);
606 size_type __bucket_count = this->bucket_count();
607 auto __next = _Base::erase(__first.base(), __last.base());
608 _M_check_rehashed(__bucket_count);
609 return { __next, this };
613 _M_base() noexcept { return *this; }
616 _M_base() const noexcept { return *this; }
620 _M_check_rehashed(size_type __prev_count)
622 if (__prev_count != this->bucket_count())
623 this->_M_invalidate_all();
627 _M_invalidate(_Base_const_iterator __victim)
629 this->_M_invalidate_if(
630 [__victim](_Base_const_iterator __it) { return __it == __victim; });
631 this->_M_invalidate_local_if(
632 [__victim](_Base_const_local_iterator __it)
633 { return __it == __victim; });
637 _M_erase(_Base_const_iterator __victim)
639 _M_invalidate(__victim);
640 size_type __bucket_count = this->bucket_count();
641 _Base_iterator __next = _Base::erase(__victim);
642 _M_check_rehashed(__bucket_count);
646 #if __cplusplus > 201402L
648 _M_extract(_Base_const_iterator __victim)
650 _M_invalidate(__victim);
651 return _Base::extract(__victim);
656 #if __cpp_deduction_guides >= 201606
658 template<typename _InputIterator,
659 typename _Hash = hash<__iter_key_t<_InputIterator>>,
660 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
661 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
662 typename = _RequireInputIter<_InputIterator>,
663 typename = _RequireNotAllocatorOrIntegral<_Hash>,
664 typename = _RequireNotAllocator<_Pred>,
665 typename = _RequireAllocator<_Allocator>>
666 unordered_map(_InputIterator, _InputIterator,
667 typename unordered_map<int, int>::size_type = {},
668 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
669 -> unordered_map<__iter_key_t<_InputIterator>,
670 __iter_val_t<_InputIterator>,
671 _Hash, _Pred, _Allocator>;
673 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
674 typename _Pred = equal_to<_Key>,
675 typename _Allocator = allocator<pair<const _Key, _Tp>>,
676 typename = _RequireNotAllocatorOrIntegral<_Hash>,
677 typename = _RequireNotAllocator<_Pred>,
678 typename = _RequireAllocator<_Allocator>>
679 unordered_map(initializer_list<pair<_Key, _Tp>>,
680 typename unordered_map<int, int>::size_type = {},
681 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
682 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
684 template<typename _InputIterator, typename _Allocator,
685 typename = _RequireInputIter<_InputIterator>,
686 typename = _RequireAllocator<_Allocator>>
687 unordered_map(_InputIterator, _InputIterator,
688 typename unordered_map<int, int>::size_type, _Allocator)
689 -> unordered_map<__iter_key_t<_InputIterator>,
690 __iter_val_t<_InputIterator>,
691 hash<__iter_key_t<_InputIterator>>,
692 equal_to<__iter_key_t<_InputIterator>>,
695 template<typename _InputIterator, typename _Allocator,
696 typename = _RequireInputIter<_InputIterator>,
697 typename = _RequireAllocator<_Allocator>>
698 unordered_map(_InputIterator, _InputIterator, _Allocator)
699 -> unordered_map<__iter_key_t<_InputIterator>,
700 __iter_val_t<_InputIterator>,
701 hash<__iter_key_t<_InputIterator>>,
702 equal_to<__iter_key_t<_InputIterator>>,
705 template<typename _InputIterator, typename _Hash, typename _Allocator,
706 typename = _RequireInputIter<_InputIterator>,
707 typename = _RequireNotAllocatorOrIntegral<_Hash>,
708 typename = _RequireAllocator<_Allocator>>
709 unordered_map(_InputIterator, _InputIterator,
710 typename unordered_map<int, int>::size_type,
712 -> unordered_map<__iter_key_t<_InputIterator>,
713 __iter_val_t<_InputIterator>, _Hash,
714 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
716 template<typename _Key, typename _Tp, typename _Allocator,
717 typename = _RequireAllocator<_Allocator>>
718 unordered_map(initializer_list<pair<_Key, _Tp>>,
719 typename unordered_map<int, int>::size_type,
721 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
723 template<typename _Key, typename _Tp, typename _Allocator,
724 typename = _RequireAllocator<_Allocator>>
725 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
726 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
728 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
729 typename = _RequireNotAllocatorOrIntegral<_Hash>,
730 typename = _RequireAllocator<_Allocator>>
731 unordered_map(initializer_list<pair<_Key, _Tp>>,
732 typename unordered_map<int, int>::size_type,
734 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
738 template<typename _Key, typename _Tp, typename _Hash,
739 typename _Pred, typename _Alloc>
741 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
742 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
743 noexcept(noexcept(__x.swap(__y)))
746 template<typename _Key, typename _Tp, typename _Hash,
747 typename _Pred, typename _Alloc>
749 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
750 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
751 { return __x._M_base() == __y._M_base(); }
753 #if __cpp_impl_three_way_comparison < 201907L
754 template<typename _Key, typename _Tp, typename _Hash,
755 typename _Pred, typename _Alloc>
757 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
758 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
759 { return !(__x == __y); }
762 /// Class std::unordered_multimap with safety/checking/debug instrumentation.
763 template<typename _Key, typename _Tp,
764 typename _Hash = std::hash<_Key>,
765 typename _Pred = std::equal_to<_Key>,
766 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
767 class unordered_multimap
768 : public __gnu_debug::_Safe_container<
769 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
770 __gnu_debug::_Safe_unordered_container>,
771 public _GLIBCXX_STD_C::unordered_multimap<
772 _Key, _Tp, _Hash, _Pred, _Alloc>
774 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
775 _Pred, _Alloc> _Base;
776 typedef __gnu_debug::_Safe_container<unordered_multimap,
777 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
778 typedef typename _Base::const_iterator _Base_const_iterator;
779 typedef typename _Base::iterator _Base_iterator;
780 typedef typename _Base::const_local_iterator _Base_const_local_iterator;
781 typedef typename _Base::local_iterator _Base_local_iterator;
783 template<typename _ItT, typename _SeqT, typename _CatT>
784 friend class ::__gnu_debug::_Safe_iterator;
785 template<typename _ItT, typename _SeqT>
786 friend class ::__gnu_debug::_Safe_local_iterator;
788 // Reference wrapper for base class. See PR libstdc++/90102.
791 _Base_ref(const _Base& __r) : _M_ref(__r) { }
797 typedef typename _Base::size_type size_type;
798 typedef typename _Base::hasher hasher;
799 typedef typename _Base::key_equal key_equal;
800 typedef typename _Base::allocator_type allocator_type;
802 typedef typename _Base::key_type key_type;
803 typedef typename _Base::value_type value_type;
805 typedef __gnu_debug::_Safe_iterator<
806 _Base_iterator, unordered_multimap> iterator;
807 typedef __gnu_debug::_Safe_iterator<
808 _Base_const_iterator, unordered_multimap> const_iterator;
809 typedef __gnu_debug::_Safe_local_iterator<
810 _Base_local_iterator, unordered_multimap> local_iterator;
811 typedef __gnu_debug::_Safe_local_iterator<
812 _Base_const_local_iterator, unordered_multimap> const_local_iterator;
814 unordered_multimap() = default;
817 unordered_multimap(size_type __n,
818 const hasher& __hf = hasher(),
819 const key_equal& __eql = key_equal(),
820 const allocator_type& __a = allocator_type())
821 : _Base(__n, __hf, __eql, __a) { }
823 template<typename _InputIterator>
824 unordered_multimap(_InputIterator __first, _InputIterator __last,
826 const hasher& __hf = hasher(),
827 const key_equal& __eql = key_equal(),
828 const allocator_type& __a = allocator_type())
829 : _Base(__gnu_debug::__base(
830 __glibcxx_check_valid_constructor_range(__first, __last)),
831 __gnu_debug::__base(__last), __n,
832 __hf, __eql, __a) { }
834 unordered_multimap(const unordered_multimap&) = default;
836 unordered_multimap(_Base_ref __x)
837 : _Base(__x._M_ref) { }
839 unordered_multimap(unordered_multimap&&) = default;
842 unordered_multimap(const allocator_type& __a)
845 unordered_multimap(const unordered_multimap& __umap,
846 const allocator_type& __a)
847 : _Base(__umap, __a) { }
849 unordered_multimap(unordered_multimap&& __umap,
850 const allocator_type& __a)
851 noexcept( noexcept(_Base(std::move(__umap._M_base()), __a)) )
852 : _Safe(std::move(__umap._M_safe()), __a),
853 _Base(std::move(__umap._M_base()), __a) { }
855 unordered_multimap(initializer_list<value_type> __l,
857 const hasher& __hf = hasher(),
858 const key_equal& __eql = key_equal(),
859 const allocator_type& __a = allocator_type())
860 : _Base(__l, __n, __hf, __eql, __a) { }
862 unordered_multimap(size_type __n, const allocator_type& __a)
863 : unordered_multimap(__n, hasher(), key_equal(), __a)
866 unordered_multimap(size_type __n, const hasher& __hf,
867 const allocator_type& __a)
868 : unordered_multimap(__n, __hf, key_equal(), __a)
871 template<typename _InputIterator>
872 unordered_multimap(_InputIterator __first, _InputIterator __last,
874 const allocator_type& __a)
875 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
878 template<typename _InputIterator>
879 unordered_multimap(_InputIterator __first, _InputIterator __last,
880 size_type __n, const hasher& __hf,
881 const allocator_type& __a)
882 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
885 unordered_multimap(initializer_list<value_type> __l,
887 const allocator_type& __a)
888 : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
891 unordered_multimap(initializer_list<value_type> __l,
892 size_type __n, const hasher& __hf,
893 const allocator_type& __a)
894 : unordered_multimap(__l, __n, __hf, key_equal(), __a)
897 ~unordered_multimap() = default;
900 operator=(const unordered_multimap&) = default;
903 operator=(unordered_multimap&&) = default;
906 operator=(initializer_list<value_type> __l)
908 this->_M_base() = __l;
909 this->_M_invalidate_all();
914 swap(unordered_multimap& __x)
915 noexcept( noexcept(declval<_Base&>().swap(__x)) )
925 this->_M_invalidate_all();
930 { return { _Base::begin(), this }; }
933 begin() const noexcept
934 { return { _Base::begin(), this }; }
938 { return { _Base::end(), this }; }
942 { return { _Base::end(), this }; }
945 cbegin() const noexcept
946 { return { _Base::cbegin(), this }; }
949 cend() const noexcept
950 { return { _Base::cend(), this }; }
956 __glibcxx_check_bucket_index(__b);
957 return { _Base::begin(__b), this };
963 __glibcxx_check_bucket_index(__b);
964 return { _Base::end(__b), this };
968 begin(size_type __b) const
970 __glibcxx_check_bucket_index(__b);
971 return { _Base::begin(__b), this };
975 end(size_type __b) const
977 __glibcxx_check_bucket_index(__b);
978 return { _Base::end(__b), this };
982 cbegin(size_type __b) const
984 __glibcxx_check_bucket_index(__b);
985 return { _Base::cbegin(__b), this };
989 cend(size_type __b) const
991 __glibcxx_check_bucket_index(__b);
992 return { _Base::cend(__b), this };
996 bucket_size(size_type __b) const
998 __glibcxx_check_bucket_index(__b);
999 return _Base::bucket_size(__b);
1003 max_load_factor() const noexcept
1004 { return _Base::max_load_factor(); }
1007 max_load_factor(float __f)
1009 __glibcxx_check_max_load_factor(__f);
1010 _Base::max_load_factor(__f);
1013 template<typename... _Args>
1015 emplace(_Args&&... __args)
1017 size_type __bucket_count = this->bucket_count();
1018 auto __it = _Base::emplace(std::forward<_Args>(__args)...);
1019 _M_check_rehashed(__bucket_count);
1020 return { __it, this };
1023 template<typename... _Args>
1025 emplace_hint(const_iterator __hint, _Args&&... __args)
1027 __glibcxx_check_insert(__hint);
1028 size_type __bucket_count = this->bucket_count();
1029 auto __it = _Base::emplace_hint(__hint.base(),
1030 std::forward<_Args>(__args)...);
1031 _M_check_rehashed(__bucket_count);
1032 return { __it, this };
1036 insert(const value_type& __obj)
1038 size_type __bucket_count = this->bucket_count();
1039 auto __it = _Base::insert(__obj);
1040 _M_check_rehashed(__bucket_count);
1041 return { __it, this };
1044 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1045 // 2354. Unnecessary copying when inserting into maps with braced-init
1047 insert(value_type&& __x)
1049 size_type __bucket_count = this->bucket_count();
1050 auto __it = _Base::insert(std::move(__x));
1051 _M_check_rehashed(__bucket_count);
1052 return { __it, this };
1056 insert(const_iterator __hint, const value_type& __obj)
1058 __glibcxx_check_insert(__hint);
1059 size_type __bucket_count = this->bucket_count();
1060 auto __it = _Base::insert(__hint.base(), __obj);
1061 _M_check_rehashed(__bucket_count);
1062 return { __it, this };
1065 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1066 // 2354. Unnecessary copying when inserting into maps with braced-init
1068 insert(const_iterator __hint, value_type&& __x)
1070 __glibcxx_check_insert(__hint);
1071 size_type __bucket_count = this->bucket_count();
1072 auto __it = _Base::insert(__hint.base(), std::move(__x));
1073 _M_check_rehashed(__bucket_count);
1074 return { __it, this };
1077 template<typename _Pair, typename = typename
1078 std::enable_if<std::is_constructible<value_type,
1079 _Pair&&>::value>::type>
1081 insert(_Pair&& __obj)
1083 size_type __bucket_count = this->bucket_count();
1084 auto __it = _Base::insert(std::forward<_Pair>(__obj));
1085 _M_check_rehashed(__bucket_count);
1086 return { __it, this };
1089 template<typename _Pair, typename = typename
1090 std::enable_if<std::is_constructible<value_type,
1091 _Pair&&>::value>::type>
1093 insert(const_iterator __hint, _Pair&& __obj)
1095 __glibcxx_check_insert(__hint);
1096 size_type __bucket_count = this->bucket_count();
1097 auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
1098 _M_check_rehashed(__bucket_count);
1099 return { __it, this };
1103 insert(std::initializer_list<value_type> __l)
1104 { _Base::insert(__l); }
1106 template<typename _InputIterator>
1108 insert(_InputIterator __first, _InputIterator __last)
1110 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
1111 __glibcxx_check_valid_range2(__first, __last, __dist);
1112 size_type __bucket_count = this->bucket_count();
1114 if (__dist.second >= __gnu_debug::__dp_sign)
1115 _Base::insert(__gnu_debug::__unsafe(__first),
1116 __gnu_debug::__unsafe(__last));
1118 _Base::insert(__first, __last);
1120 _M_check_rehashed(__bucket_count);
1123 #if __cplusplus > 201402L
1124 using node_type = typename _Base::node_type;
1127 extract(const_iterator __position)
1129 __glibcxx_check_erase(__position);
1130 return _M_extract(__position.base());
1134 extract(const key_type& __key)
1136 const auto __position = _Base::find(__key);
1137 if (__position != _Base::end())
1138 return _M_extract(__position);
1143 insert(node_type&& __nh)
1144 { return { _Base::insert(std::move(__nh)), this }; }
1147 insert(const_iterator __hint, node_type&& __nh)
1149 __glibcxx_check_insert(__hint);
1150 return { _Base::insert(__hint.base(), std::move(__nh)), this };
1157 find(const key_type& __key)
1158 { return { _Base::find(__key), this }; }
1161 find(const key_type& __key) const
1162 { return { _Base::find(__key), this }; }
1164 std::pair<iterator, iterator>
1165 equal_range(const key_type& __key)
1167 auto __res = _Base::equal_range(__key);
1168 return { { __res.first, this }, { __res.second, this } };
1171 std::pair<const_iterator, const_iterator>
1172 equal_range(const key_type& __key) const
1174 auto __res = _Base::equal_range(__key);
1175 return { { __res.first, this }, { __res.second, this } };
1179 erase(const key_type& __key)
1182 size_type __bucket_count = this->bucket_count();
1183 auto __pair = _Base::equal_range(__key);
1184 for (auto __victim = __pair.first; __victim != __pair.second;)
1186 _M_invalidate(__victim);
1187 __victim = _Base::erase(__victim);
1191 _M_check_rehashed(__bucket_count);
1196 erase(const_iterator __it)
1198 __glibcxx_check_erase(__it);
1199 return { _M_erase(__it.base()), this };
1203 erase(iterator __it)
1205 __glibcxx_check_erase(__it);
1206 return { _M_erase(__it.base()), this };
1210 erase(const_iterator __first, const_iterator __last)
1212 __glibcxx_check_erase_range(__first, __last);
1213 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1215 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1216 _M_message(__gnu_debug::__msg_valid_range)
1217 ._M_iterator(__first, "first")
1218 ._M_iterator(__last, "last"));
1219 _M_invalidate(__tmp);
1222 size_type __bucket_count = this->bucket_count();
1223 auto __next = _Base::erase(__first.base(), __last.base());
1224 _M_check_rehashed(__bucket_count);
1225 return { __next, this };
1229 _M_base() noexcept { return *this; }
1232 _M_base() const noexcept { return *this; }
1236 _M_check_rehashed(size_type __prev_count)
1238 if (__prev_count != this->bucket_count())
1239 this->_M_invalidate_all();
1243 _M_invalidate(_Base_const_iterator __victim)
1245 this->_M_invalidate_if(
1246 [__victim](_Base_const_iterator __it) { return __it == __victim; });
1247 this->_M_invalidate_local_if(
1248 [__victim](_Base_const_local_iterator __it)
1249 { return __it == __victim; });
1253 _M_erase(_Base_const_iterator __victim)
1255 _M_invalidate(__victim);
1256 size_type __bucket_count = this->bucket_count();
1257 _Base_iterator __next = _Base::erase(__victim);
1258 _M_check_rehashed(__bucket_count);
1262 #if __cplusplus > 201402L
1264 _M_extract(_Base_const_iterator __victim)
1266 _M_invalidate(__victim);
1267 return _Base::extract(__victim);
1272 #if __cpp_deduction_guides >= 201606
1274 template<typename _InputIterator,
1275 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1276 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1277 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1278 typename = _RequireInputIter<_InputIterator>,
1279 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1280 typename = _RequireNotAllocator<_Pred>,
1281 typename = _RequireAllocator<_Allocator>>
1282 unordered_multimap(_InputIterator, _InputIterator,
1283 unordered_multimap<int, int>::size_type = {},
1284 _Hash = _Hash(), _Pred = _Pred(),
1285 _Allocator = _Allocator())
1286 -> unordered_multimap<__iter_key_t<_InputIterator>,
1287 __iter_val_t<_InputIterator>, _Hash, _Pred,
1290 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
1291 typename _Pred = equal_to<_Key>,
1292 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1293 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1294 typename = _RequireNotAllocator<_Pred>,
1295 typename = _RequireAllocator<_Allocator>>
1296 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1297 unordered_multimap<int, int>::size_type = {},
1298 _Hash = _Hash(), _Pred = _Pred(),
1299 _Allocator = _Allocator())
1300 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
1302 template<typename _InputIterator, typename _Allocator,
1303 typename = _RequireInputIter<_InputIterator>,
1304 typename = _RequireAllocator<_Allocator>>
1305 unordered_multimap(_InputIterator, _InputIterator,
1306 unordered_multimap<int, int>::size_type, _Allocator)
1307 -> unordered_multimap<__iter_key_t<_InputIterator>,
1308 __iter_val_t<_InputIterator>,
1309 hash<__iter_key_t<_InputIterator>>,
1310 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1312 template<typename _InputIterator, typename _Allocator,
1313 typename = _RequireInputIter<_InputIterator>,
1314 typename = _RequireAllocator<_Allocator>>
1315 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
1316 -> unordered_multimap<__iter_key_t<_InputIterator>,
1317 __iter_val_t<_InputIterator>,
1318 hash<__iter_key_t<_InputIterator>>,
1319 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1321 template<typename _InputIterator, typename _Hash, typename _Allocator,
1322 typename = _RequireInputIter<_InputIterator>,
1323 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1324 typename = _RequireAllocator<_Allocator>>
1325 unordered_multimap(_InputIterator, _InputIterator,
1326 unordered_multimap<int, int>::size_type, _Hash,
1328 -> unordered_multimap<__iter_key_t<_InputIterator>,
1329 __iter_val_t<_InputIterator>, _Hash,
1330 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1332 template<typename _Key, typename _Tp, typename _Allocator,
1333 typename = _RequireAllocator<_Allocator>>
1334 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1335 unordered_multimap<int, int>::size_type,
1337 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1339 template<typename _Key, typename _Tp, typename _Allocator,
1340 typename = _RequireAllocator<_Allocator>>
1341 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
1342 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1344 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
1345 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1346 typename = _RequireAllocator<_Allocator>>
1347 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1348 unordered_multimap<int, int>::size_type,
1350 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1354 template<typename _Key, typename _Tp, typename _Hash,
1355 typename _Pred, typename _Alloc>
1357 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1358 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1359 noexcept(noexcept(__x.swap(__y)))
1362 template<typename _Key, typename _Tp, typename _Hash,
1363 typename _Pred, typename _Alloc>
1365 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1366 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1367 { return __x._M_base() == __y._M_base(); }
1369 #if __cpp_impl_three_way_comparison < 201907L
1370 template<typename _Key, typename _Tp, typename _Hash,
1371 typename _Pred, typename _Alloc>
1373 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1374 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1375 { return !(__x == __y); }
1378 } // namespace __debug