libstdc++
debug/unordered_map
Go to the documentation of this file.
1// Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
2
3// Copyright (C) 2003-2025 Free Software Foundation, Inc.
4//
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)
9// any later version.
10
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.
15
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.
19
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/>.
24
25/** @file debug/unordered_map
26 * This file is a GNU debug extension to the Standard C++ Library.
27 */
28
29#ifndef _GLIBCXX_DEBUG_UNORDERED_MAP
30#define _GLIBCXX_DEBUG_UNORDERED_MAP 1
31
32#ifdef _GLIBCXX_SYSHDR
33#pragma GCC system_header
34#endif
35
36#if __cplusplus < 201103L
37# include <bits/c++0x_warning.h>
38#else
39# include <bits/c++config.h>
40namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug {
41 template<typename _Key, typename _Tp, typename _Hash, typename _Pred,
42 typename _Allocator>
43 class unordered_map;
44 template<typename _Key, typename _Tp, typename _Hash, typename _Pred,
45 typename _Allocator>
46 class unordered_multimap;
47} } // namespace std::__debug
48
49# include <unordered_map>
50
53#include <debug/safe_iterator.h>
55
56namespace std _GLIBCXX_VISIBILITY(default)
57{
58namespace __debug
59{
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>,
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>
70 {
71 typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
72 _Pred, _Alloc> _Base;
76 typedef typename _Base::iterator _Base_iterator;
77 typedef typename _Base::const_local_iterator
80
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;
85
86 // Reference wrapper for base class. See PR libstdc++/90102.
87 struct _Base_ref
88 {
89 _Base_ref(const _Base& __r) : _M_ref(__r) { }
90
91 const _Base& _M_ref;
92 };
93
94 public:
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;
99
100 typedef typename _Base::key_type key_type;
101 typedef typename _Base::value_type value_type;
102 typedef typename _Base::mapped_type mapped_type;
103
104 typedef typename _Base::pointer pointer;
105 typedef typename _Base::const_pointer const_pointer;
106 typedef typename _Base::reference reference;
107 typedef typename _Base::const_reference const_reference;
116 typedef typename _Base::difference_type difference_type;
117
118 unordered_map() = default;
119
120 explicit
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) { }
126
127 template<typename _InputIterator>
128 unordered_map(_InputIterator __first, _InputIterator __last,
129 size_type __n = 0,
130 const hasher& __hf = hasher(),
131 const key_equal& __eql = key_equal(),
132 const allocator_type& __a = allocator_type())
134 __glibcxx_check_valid_constructor_range(__first, __last)),
135 __gnu_debug::__base(__last), __n,
136 __hf, __eql, __a) { }
137
138 unordered_map(const unordered_map&) = default;
139
140 unordered_map(_Base_ref __x)
141 : _Base(__x._M_ref) { }
142
143 unordered_map(unordered_map&&) = default;
144
145 explicit
146 unordered_map(const allocator_type& __a)
147 : _Base(__a) { }
148
149 unordered_map(const unordered_map& __umap,
150 const allocator_type& __a)
151 : _Base(__umap, __a) { }
152
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) { }
158
160 size_type __n = 0,
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) { }
165
166 unordered_map(size_type __n, const allocator_type& __a)
167 : unordered_map(__n, hasher(), key_equal(), __a)
168 { }
169
170 unordered_map(size_type __n,
171 const hasher& __hf,
172 const allocator_type& __a)
173 : unordered_map(__n, __hf, key_equal(), __a)
174 { }
175
176 template<typename _InputIterator>
177 unordered_map(_InputIterator __first, _InputIterator __last,
178 size_type __n,
179 const allocator_type& __a)
180 : unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
181 { }
182
183 template<typename _InputIterator>
184 unordered_map(_InputIterator __first, _InputIterator __last,
185 size_type __n,
186 const hasher& __hf,
187 const allocator_type& __a)
188 : unordered_map(__first, __last, __n, __hf, key_equal(), __a)
189 { }
190
192 size_type __n,
193 const allocator_type& __a)
194 : unordered_map(__l, __n, hasher(), key_equal(), __a)
195 { }
196
198 size_type __n,
199 const hasher& __hf,
200 const allocator_type& __a)
201 : unordered_map(__l, __n, __hf, key_equal(), __a)
202 { }
203
204 ~unordered_map() = default;
205
207 operator=(const unordered_map&) = default;
208
210 operator=(unordered_map&&) = default;
211
213 operator=(initializer_list<value_type> __l)
214 {
215 _Base::operator=(__l);
216 this->_M_invalidate_all();
217 return *this;
218 }
219
220 using _Base::get_allocator;
221 using _Base::empty;
222 using _Base::size;
223 using _Base::max_size;
224
225 void
226 swap(unordered_map& __x)
227 noexcept( noexcept(declval<_Base&>().swap(__x)) )
228 {
229 _Safe::_M_swap(__x);
230 _Base::swap(__x);
231 }
232
233 void
234 clear() noexcept
235 {
236 _Base::clear();
237 this->_M_invalidate_all();
238 }
239
241 begin() noexcept
242 { return { _Base::begin(), this }; }
243
245 begin() const noexcept
246 { return { _Base::begin(), this }; }
247
249 end() noexcept
250 { return { _Base::end(), this }; }
251
253 end() const noexcept
254 { return { _Base::end(), this }; }
255
257 cbegin() const noexcept
258 { return { _Base::cbegin(), this }; }
259
261 cend() const noexcept
262 { return { _Base::cend(), this }; }
263
264 // local versions
266 begin(size_type __b)
267 {
268 __glibcxx_check_bucket_index(__b);
269 return { _Base::begin(__b), this };
270 }
271
273 end(size_type __b)
274 {
275 __glibcxx_check_bucket_index(__b);
276 return { _Base::end(__b), this };
277 }
278
280 begin(size_type __b) const
281 {
282 __glibcxx_check_bucket_index(__b);
283 return { _Base::begin(__b), this };
284 }
285
287 end(size_type __b) const
288 {
289 __glibcxx_check_bucket_index(__b);
290 return { _Base::end(__b), this };
291 }
292
294 cbegin(size_type __b) const
295 {
296 __glibcxx_check_bucket_index(__b);
297 return { _Base::cbegin(__b), this };
298 }
299
301 cend(size_type __b) const
302 {
303 __glibcxx_check_bucket_index(__b);
304 return { _Base::cend(__b), this };
305 }
306
307 using _Base::bucket_count;
308 using _Base::max_bucket_count;
309 using _Base::bucket;
310
311 size_type
312 bucket_size(size_type __b) const
313 {
314 __glibcxx_check_bucket_index(__b);
315 return _Base::bucket_size(__b);
316 }
317
318 using _Base::load_factor;
319
320 float
321 max_load_factor() const noexcept
322 { return _Base::max_load_factor(); }
323
324 void
325 max_load_factor(float __f)
326 {
327 __glibcxx_check_max_load_factor(__f);
328 _Base::max_load_factor(__f);
329 }
330
331 template<typename... _Args>
333 emplace(_Args&&... __args)
334 {
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 };
339 }
340
341 template<typename... _Args>
343 emplace_hint(const_iterator __hint, _Args&&... __args)
344 {
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 };
351 }
352
354 insert(const value_type& __obj)
355 {
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 };
360 }
361
362 // _GLIBCXX_RESOLVE_LIB_DEFECTS
363 // 2354. Unnecessary copying when inserting into maps with braced-init
365 insert(value_type&& __x)
366 {
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 };
371 }
372
373 template<typename _Pair, typename = typename
375 _Pair&&>::value>::type>
377 insert(_Pair&& __obj)
378 {
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 };
383 }
384
386 insert(const_iterator __hint, const value_type& __obj)
387 {
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 };
393 }
394
395 // _GLIBCXX_RESOLVE_LIB_DEFECTS
396 // 2354. Unnecessary copying when inserting into maps with braced-init
398 insert(const_iterator __hint, value_type&& __x)
399 {
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 };
405 }
406
407 template<typename _Pair, typename = typename
409 _Pair&&>::value>::type>
411 insert(const_iterator __hint, _Pair&& __obj)
412 {
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 };
418 }
419
420 void
422 {
423 size_type __bucket_count = this->bucket_count();
424 _Base::insert(__l);
425 _M_check_rehashed(__bucket_count);
426 }
427
428 template<typename _InputIterator>
429 void
430 insert(_InputIterator __first, _InputIterator __last)
431 {
433 __glibcxx_check_valid_range2(__first, __last, __dist);
434 size_type __bucket_count = this->bucket_count();
435
436 if (__dist.second >= __gnu_debug::__dp_sign)
437 _Base::insert(__gnu_debug::__unsafe(__first),
438 __gnu_debug::__unsafe(__last));
439 else
440 _Base::insert(__first, __last);
441
442 _M_check_rehashed(__bucket_count);
443 }
444
445#ifdef __glibcxx_unordered_map_try_emplace // C++ >= 17 && HOSTED
446 template <typename... _Args>
448 try_emplace(const key_type& __k, _Args&&... __args)
449 {
450 auto __res = _Base::try_emplace(__k,
451 std::forward<_Args>(__args)...);
452 return { { __res.first, this }, __res.second };
453 }
454
455 template <typename... _Args>
457 try_emplace(key_type&& __k, _Args&&... __args)
458 {
459 auto __res = _Base::try_emplace(std::move(__k),
460 std::forward<_Args>(__args)...);
461 return { { __res.first, this }, __res.second };
462 }
463
464 template <typename... _Args>
466 try_emplace(const_iterator __hint, const key_type& __k,
467 _Args&&... __args)
468 {
470 return { _Base::try_emplace(__hint.base(), __k,
471 std::forward<_Args>(__args)...),
472 this };
473 }
474
475 template <typename... _Args>
477 try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
478 {
480 return { _Base::try_emplace(__hint.base(), std::move(__k),
481 std::forward<_Args>(__args)...),
482 this };
483 }
484
485 template <typename _Obj>
487 insert_or_assign(const key_type& __k, _Obj&& __obj)
488 {
489 auto __res = _Base::insert_or_assign(__k,
490 std::forward<_Obj>(__obj));
491 return { { __res.first, this }, __res.second };
492 }
493
494 template <typename _Obj>
496 insert_or_assign(key_type&& __k, _Obj&& __obj)
497 {
498 auto __res = _Base::insert_or_assign(std::move(__k),
499 std::forward<_Obj>(__obj));
500 return { { __res.first, this }, __res.second };
501 }
502
503 template <typename _Obj>
505 insert_or_assign(const_iterator __hint, const key_type& __k,
506 _Obj&& __obj)
507 {
509 return { _Base::insert_or_assign(__hint.base(), __k,
510 std::forward<_Obj>(__obj)),
511 this };
512 }
513
514 template <typename _Obj>
516 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
517 {
519 return { _Base::insert_or_assign(__hint.base(), std::move(__k),
520 std::forward<_Obj>(__obj)),
521 this };
522 }
523#endif // C++17
524
525#if __cplusplus > 201402L
526 using node_type = typename _Base::node_type;
527 using insert_return_type = _Node_insert_return<iterator, node_type>;
528
529 node_type
530 extract(const_iterator __position)
531 {
532 __glibcxx_check_erase(__position);
533 return _M_extract(__position.base());
534 }
535
536 node_type
537 extract(const key_type& __key)
538 {
539 const auto __position = _Base::find(__key);
540 if (__position != _Base::end())
541 return _M_extract(__position);
542 return {};
543 }
544
545 insert_return_type
546 insert(node_type&& __nh)
547 {
548 auto __ret = _Base::insert(std::move(__nh));
549 return
550 { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };
551 }
552
554 insert(const_iterator __hint, node_type&& __nh)
555 {
557 return { _Base::insert(__hint.base(), std::move(__nh)), this };
558 }
559
560 template<typename _H2, typename _P2>
561 void
563 {
564 auto __guard
565 = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
566 _Base::merge(__source);
567 }
568
569 template<typename _H2, typename _P2>
570 void
572 { merge(__source); }
573
574 template<typename _H2, typename _P2>
575 void
577 {
578 auto __guard
579 = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
580 _Base::merge(__source);
581 }
582
583 template<typename _H2, typename _P2>
584 void
586 { merge(__source); }
587#endif // C++17
588
589 using _Base::hash_function;
590 using _Base::key_eq;
591
593 find(const key_type& __key)
594 { return { _Base::find(__key), this }; }
595
596#if __cplusplus > 201703L
597 template<typename _Kt,
598 typename = std::__has_is_transparent_t<_Hash, _Kt>,
599 typename = std::__has_is_transparent_t<_Pred, _Kt>>
601 find(const _Kt& __k)
602 { return { _Base::find(__k), this }; }
603#endif
604
606 find(const key_type& __key) const
607 { return { _Base::find(__key), this }; }
608
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 }; }
616#endif
617
618 using _Base::count;
619#if __cplusplus > 201703L
620 using _Base::contains;
621#endif
622
624 equal_range(const key_type& __key)
625 {
626 auto __res = _Base::equal_range(__key);
627 return { { __res.first, this }, { __res.second, this } };
628 }
629
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>>
635 equal_range(const _Kt& __k)
636 {
637 auto __res = _Base::equal_range(__k);
638 return { { __res.first, this }, { __res.second, this } };
639 }
640#endif
641
643 equal_range(const key_type& __key) const
644 {
645 auto __res = _Base::equal_range(__key);
646 return { { __res.first, this }, { __res.second, this } };
647 }
648
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>>
654 equal_range(const _Kt& __k) const
655 {
656 auto __res = _Base::equal_range(__k);
657 return { { __res.first, this }, { __res.second, this } };
658 }
659#endif
660
661 using _Base::operator[];
662 using _Base::at;
663
664 size_type
665 erase(const key_type& __key)
666 {
667 size_type __ret(0);
668 auto __victim = _Base::find(__key);
669 if (__victim != _Base::end())
670 {
671 _M_erase(__victim);
672 __ret = 1;
673 }
674 return __ret;
675 }
676
678 erase(const_iterator __it)
679 {
681 return { _M_erase(__it.base()), this };
682 }
683
685 erase(_Base_const_iterator __it)
686 {
687 __glibcxx_check_erase2(__it);
688 return _M_erase(__it);
689 }
690
692 erase(iterator __it)
693 {
695 return { _M_erase(__it.base()), this };
696 }
697
699 erase(const_iterator __first, const_iterator __last)
700 {
701 __glibcxx_check_erase_range(__first, __last);
702 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
703 {
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);
709 }
710
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 };
715 }
716
717 using _Base::rehash;
718 using _Base::reserve;
719
720 _Base&
721 _M_base() noexcept { return *this; }
722
723 const _Base&
724 _M_base() const noexcept { return *this; }
725
726 private:
727 void
728 _M_check_rehashed(size_type __prev_count)
729 {
730 if (__prev_count != this->bucket_count())
731 this->_M_invalidate_all();
732 }
733
734 void
735 _M_invalidate(_Base_const_iterator __victim)
736 {
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; });
742 }
743
745 _M_erase(_Base_const_iterator __victim)
746 {
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);
751 return __next;
752 }
753
754#if __cplusplus > 201402L
755 node_type
756 _M_extract(_Base_const_iterator __victim)
757 {
758 _M_invalidate(__victim);
759 return _Base::extract(__victim);
760 }
761#endif
762 };
763
764#if __cpp_deduction_guides >= 201606
765
766 template<typename _InputIterator,
767 typename _Hash = hash<__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>;
780
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>>
789 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
790 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
791
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>>,
801 _Allocator>;
802
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>>,
811 _Allocator>;
812
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,
819 _Hash, _Allocator)
820 -> unordered_map<__iter_key_t<_InputIterator>,
821 __iter_val_t<_InputIterator>, _Hash,
822 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
823
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,
828 _Allocator)
829 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
830
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>;
835
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,
841 _Hash, _Allocator)
842 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
843
844#endif
845
846 template<typename _Key, typename _Tp, typename _Hash,
847 typename _Pred, typename _Alloc>
848 inline void
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)))
852 { __x.swap(__y); }
853
854 template<typename _Key, typename _Tp, typename _Hash,
855 typename _Pred, typename _Alloc>
856 inline bool
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(); }
860
861#if __cpp_impl_three_way_comparison < 201907L
862 template<typename _Key, typename _Tp, typename _Hash,
863 typename _Pred, typename _Alloc>
864 inline bool
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); }
868#endif
869
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>,
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>
881 {
882 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
883 _Pred, _Alloc> _Base;
887 typedef typename _Base::iterator _Base_iterator;
890
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;
895
896 // Reference wrapper for base class. See PR libstdc++/90102.
897 struct _Base_ref
898 {
899 _Base_ref(const _Base& __r) : _M_ref(__r) { }
900
901 const _Base& _M_ref;
902 };
903
904 public:
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;
909
910 typedef typename _Base::key_type key_type;
911 typedef typename _Base::value_type value_type;
912 typedef typename _Base::mapped_type mapped_type;
913
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;
926 typedef typename _Base::difference_type difference_type;
927
928 unordered_multimap() = default;
929
930 explicit
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) { }
936
937 template<typename _InputIterator>
938 unordered_multimap(_InputIterator __first, _InputIterator __last,
939 size_type __n = 0,
940 const hasher& __hf = hasher(),
941 const key_equal& __eql = key_equal(),
942 const allocator_type& __a = allocator_type())
944 __glibcxx_check_valid_constructor_range(__first, __last)),
945 __gnu_debug::__base(__last), __n,
946 __hf, __eql, __a) { }
947
948 unordered_multimap(const unordered_multimap&) = default;
949
950 unordered_multimap(_Base_ref __x)
951 : _Base(__x._M_ref) { }
952
954
955 explicit
956 unordered_multimap(const allocator_type& __a)
957 : _Base(__a) { }
958
960 const allocator_type& __a)
961 : _Base(__umap, __a) { }
962
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) { }
968
970 size_type __n = 0,
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) { }
975
976 unordered_multimap(size_type __n, const allocator_type& __a)
977 : unordered_multimap(__n, hasher(), key_equal(), __a)
978 { }
979
980 unordered_multimap(size_type __n, const hasher& __hf,
981 const allocator_type& __a)
982 : unordered_multimap(__n, __hf, key_equal(), __a)
983 { }
984
985 template<typename _InputIterator>
986 unordered_multimap(_InputIterator __first, _InputIterator __last,
987 size_type __n,
988 const allocator_type& __a)
989 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
990 { }
991
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)
997 { }
998
1000 size_type __n,
1001 const allocator_type& __a)
1002 : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
1003 { }
1004
1006 size_type __n, const hasher& __hf,
1007 const allocator_type& __a)
1008 : unordered_multimap(__l, __n, __hf, key_equal(), __a)
1009 { }
1010
1011 ~unordered_multimap() = default;
1012
1014 operator=(const unordered_multimap&) = default;
1015
1017 operator=(unordered_multimap&&) = default;
1018
1020 operator=(initializer_list<value_type> __l)
1021 {
1022 _Base::operator=(__l);
1023 this->_M_invalidate_all();
1024 return *this;
1025 }
1026
1027 using _Base::get_allocator;
1028 using _Base::empty;
1029 using _Base::size;
1030 using _Base::max_size;
1031
1032 void
1033 swap(unordered_multimap& __x)
1034 noexcept( noexcept(declval<_Base&>().swap(__x)) )
1035 {
1036 _Safe::_M_swap(__x);
1037 _Base::swap(__x);
1038 }
1039
1040 void
1041 clear() noexcept
1042 {
1043 _Base::clear();
1044 this->_M_invalidate_all();
1045 }
1046
1047 iterator
1048 begin() noexcept
1049 { return { _Base::begin(), this }; }
1050
1052 begin() const noexcept
1053 { return { _Base::begin(), this }; }
1054
1055 iterator
1056 end() noexcept
1057 { return { _Base::end(), this }; }
1058
1060 end() const noexcept
1061 { return { _Base::end(), this }; }
1062
1064 cbegin() const noexcept
1065 { return { _Base::cbegin(), this }; }
1066
1068 cend() const noexcept
1069 { return { _Base::cend(), this }; }
1070
1071 // local versions
1073 begin(size_type __b)
1074 {
1075 __glibcxx_check_bucket_index(__b);
1076 return { _Base::begin(__b), this };
1077 }
1078
1080 end(size_type __b)
1081 {
1082 __glibcxx_check_bucket_index(__b);
1083 return { _Base::end(__b), this };
1084 }
1085
1087 begin(size_type __b) const
1088 {
1089 __glibcxx_check_bucket_index(__b);
1090 return { _Base::begin(__b), this };
1091 }
1092
1094 end(size_type __b) const
1095 {
1096 __glibcxx_check_bucket_index(__b);
1097 return { _Base::end(__b), this };
1098 }
1099
1101 cbegin(size_type __b) const
1102 {
1103 __glibcxx_check_bucket_index(__b);
1104 return { _Base::cbegin(__b), this };
1105 }
1106
1108 cend(size_type __b) const
1109 {
1110 __glibcxx_check_bucket_index(__b);
1111 return { _Base::cend(__b), this };
1112 }
1113
1114 using _Base::bucket_count;
1115 using _Base::max_bucket_count;
1116 using _Base::bucket;
1117
1118 size_type
1119 bucket_size(size_type __b) const
1120 {
1121 __glibcxx_check_bucket_index(__b);
1122 return _Base::bucket_size(__b);
1123 }
1124
1125 float
1126 max_load_factor() const noexcept
1127 { return _Base::max_load_factor(); }
1128
1129 void
1130 max_load_factor(float __f)
1131 {
1132 __glibcxx_check_max_load_factor(__f);
1133 _Base::max_load_factor(__f);
1134 }
1135
1136 template<typename... _Args>
1137 iterator
1138 emplace(_Args&&... __args)
1139 {
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 };
1144 }
1145
1146 template<typename... _Args>
1147 iterator
1148 emplace_hint(const_iterator __hint, _Args&&... __args)
1149 {
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 };
1156 }
1157
1158 iterator
1159 insert(const value_type& __obj)
1160 {
1161 size_type __bucket_count = this->bucket_count();
1162 auto __it = _Base::insert(__obj);
1163 _M_check_rehashed(__bucket_count);
1164 return { __it, this };
1165 }
1166
1167 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1168 // 2354. Unnecessary copying when inserting into maps with braced-init
1169 iterator
1170 insert(value_type&& __x)
1171 {
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 };
1176 }
1177
1178 iterator
1179 insert(const_iterator __hint, const value_type& __obj)
1180 {
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 };
1186 }
1187
1188 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1189 // 2354. Unnecessary copying when inserting into maps with braced-init
1190 iterator
1191 insert(const_iterator __hint, value_type&& __x)
1192 {
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 };
1198 }
1199
1200 template<typename _Pair, typename = typename
1202 _Pair&&>::value>::type>
1203 iterator
1204 insert(_Pair&& __obj)
1205 {
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 };
1210 }
1211
1212 template<typename _Pair, typename = typename
1214 _Pair&&>::value>::type>
1215 iterator
1216 insert(const_iterator __hint, _Pair&& __obj)
1217 {
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 };
1223 }
1224
1225 void
1227 { _Base::insert(__l); }
1228
1229 template<typename _InputIterator>
1230 void
1231 insert(_InputIterator __first, _InputIterator __last)
1232 {
1234 __glibcxx_check_valid_range2(__first, __last, __dist);
1235 size_type __bucket_count = this->bucket_count();
1236
1237 if (__dist.second >= __gnu_debug::__dp_sign)
1238 _Base::insert(__gnu_debug::__unsafe(__first),
1239 __gnu_debug::__unsafe(__last));
1240 else
1241 _Base::insert(__first, __last);
1242
1243 _M_check_rehashed(__bucket_count);
1244 }
1245
1246#if __cplusplus > 201402L
1247 using node_type = typename _Base::node_type;
1248
1249 node_type
1250 extract(const_iterator __position)
1251 {
1252 __glibcxx_check_erase(__position);
1253 return _M_extract(__position.base());
1254 }
1255
1256 node_type
1257 extract(const key_type& __key)
1258 {
1259 const auto __position = _Base::find(__key);
1260 if (__position != _Base::end())
1261 return _M_extract(__position);
1262 return {};
1263 }
1264
1265 iterator
1266 insert(node_type&& __nh)
1267 { return { _Base::insert(std::move(__nh)), this }; }
1268
1269 iterator
1270 insert(const_iterator __hint, node_type&& __nh)
1271 {
1272 __glibcxx_check_insert(__hint);
1273 return { _Base::insert(__hint.base(), std::move(__nh)), this };
1274 }
1275
1276 template<typename _H2, typename _P2>
1277 void
1279 {
1280 auto __guard
1281 = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
1282 _Base::merge(__source);
1283 }
1284
1285 template<typename _H2, typename _P2>
1286 void
1288 { merge(__source); }
1289
1290 template<typename _H2, typename _P2>
1291 void
1293 {
1294 auto __guard
1295 = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
1296 _Base::merge(__source);
1297 }
1298
1299 template<typename _H2, typename _P2>
1300 void
1302 { merge(__source); }
1303#endif // C++17
1304
1305 using _Base::hash_function;
1306 using _Base::key_eq;
1307
1308 iterator
1309 find(const key_type& __key)
1310 { return { _Base::find(__key), this }; }
1311
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>>
1316 iterator
1317 find(const _Kt& __k)
1318 { return { _Base::find(__k), this }; }
1319#endif
1320
1322 find(const key_type& __key) const
1323 { return { _Base::find(__key), this }; }
1324
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 }; }
1332#endif
1333
1334 using _Base::count;
1335#if __cplusplus > 201703L
1336 using _Base::contains;
1337#endif
1338
1340 equal_range(const key_type& __key)
1341 {
1342 auto __res = _Base::equal_range(__key);
1343 return { { __res.first, this }, { __res.second, this } };
1344 }
1345
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>>
1351 equal_range(const _Kt& __k)
1352 {
1353 auto __res = _Base::equal_range(__k);
1354 return { { __res.first, this }, { __res.second, this } };
1355 }
1356#endif
1357
1359 equal_range(const key_type& __key) const
1360 {
1361 auto __res = _Base::equal_range(__key);
1362 return { { __res.first, this }, { __res.second, this } };
1363 }
1364
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>>
1370 equal_range(const _Kt& __k) const
1371 {
1372 auto __res = _Base::equal_range(__k);
1373 return { { __res.first, this }, { __res.second, this } };
1374 }
1375#endif
1376
1377 size_type
1378 erase(const key_type& __key)
1379 {
1380 size_type __ret(0);
1381 size_type __bucket_count = this->bucket_count();
1382 auto __pair = _Base::equal_range(__key);
1383 for (auto __victim = __pair.first; __victim != __pair.second;)
1384 {
1385 _M_invalidate(__victim);
1386 __victim = _Base::erase(__victim);
1387 ++__ret;
1388 }
1389
1390 _M_check_rehashed(__bucket_count);
1391 return __ret;
1392 }
1393
1394 iterator
1395 erase(const_iterator __it)
1396 {
1398 return { _M_erase(__it.base()), this };
1399 }
1400
1402 erase(_Base_const_iterator __it)
1403 {
1404 __glibcxx_check_erase2(__it);
1405 return _M_erase(__it);
1406 }
1407
1408 iterator
1409 erase(iterator __it)
1410 {
1412 return { _M_erase(__it.base()), this };
1413 }
1414
1415 iterator
1416 erase(const_iterator __first, const_iterator __last)
1417 {
1418 __glibcxx_check_erase_range(__first, __last);
1419 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1420 {
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);
1426 }
1427
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 };
1432 }
1433
1434 using _Base::rehash;
1435 using _Base::reserve;
1436
1437 _Base&
1438 _M_base() noexcept { return *this; }
1439
1440 const _Base&
1441 _M_base() const noexcept { return *this; }
1442
1443 private:
1444 void
1445 _M_check_rehashed(size_type __prev_count)
1446 {
1447 if (__prev_count != this->bucket_count())
1448 this->_M_invalidate_all();
1449 }
1450
1451 void
1452 _M_invalidate(_Base_const_iterator __victim)
1453 {
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; });
1459 }
1460
1462 _M_erase(_Base_const_iterator __victim)
1463 {
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);
1468 return __next;
1469 }
1470
1471#if __cplusplus > 201402L
1472 node_type
1473 _M_extract(_Base_const_iterator __victim)
1474 {
1475 _M_invalidate(__victim);
1476 return _Base::extract(__victim);
1477 }
1478#endif
1479 };
1480
1481#if __cpp_deduction_guides >= 201606
1482
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,
1497 _Allocator>;
1498
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>>
1507 _Hash = _Hash(), _Pred = _Pred(),
1508 _Allocator = _Allocator())
1509 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
1510
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>;
1520
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>;
1529
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,
1536 _Allocator)
1537 -> unordered_multimap<__iter_key_t<_InputIterator>,
1538 __iter_val_t<_InputIterator>, _Hash,
1539 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1540
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,
1545 _Allocator)
1546 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1547
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>;
1552
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,
1558 _Hash, _Allocator)
1559 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1560
1561#endif
1562
1563 template<typename _Key, typename _Tp, typename _Hash,
1564 typename _Pred, typename _Alloc>
1565 inline void
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)))
1569 { __x.swap(__y); }
1570
1571 template<typename _Key, typename _Tp, typename _Hash,
1572 typename _Pred, typename _Alloc>
1573 inline bool
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(); }
1577
1578#if __cpp_impl_three_way_comparison < 201907L
1579 template<typename _Key, typename _Tp, typename _Hash,
1580 typename _Pred, typename _Alloc>
1581 inline bool
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); }
1585#endif
1586
1587} // namespace __debug
1588} // namespace std
1589
1590#endif // C++11
1591
1592#endif
#define __glibcxx_check_insert(_Position)
Definition macros.h:143
#define __glibcxx_check_erase_range(_First, _Last)
Definition macros.h:245
#define __glibcxx_check_erase(_Position)
Definition macros.h:209
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:138
ISO C++ entities toplevel namespace is std.
constexpr _Iterator __base(_Iterator __it)
initializer_list
Primary class template hash.
Define a member typedef type only if a boolean constant is true.
Definition type_traits:134
is_constructible
Definition type_traits:1158
The standard allocator, as per C++03 [20.4.1].
Definition allocator.h:134
Safe iterator wrapper.
constexpr _Iterator & base() noexcept
Return the underlying iterator.
Return type of insert(node_handle&&) on unique maps/sets.
One of the comparison functors.
Struct holding two objects of arbitrary type.
Definition stl_pair.h:304
_T2 second
The second member.
Definition stl_pair.h:309
A standard container composed of equivalent keys (possibly containing multiple of each key value) tha...
_Hashtable::size_type size_type
Iterator-related typedefs.
A standard container composed of unique keys (containing at most one of each key value) that associat...
_Hashtable::size_type size_type
Iterator-related typedefs.
Safe class dealing with some allocator dependent operations.
Base class for constructing a safe unordered container type that tracks iterators that reference it.
Class std::unordered_map with safety/checking/debug instrumentation.
Class std::unordered_multimap with safety/checking/debug instrumentation.