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
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>
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>,
64 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
65 class unordered_map
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>
70 {
71 typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
72 _Pred, _Alloc> _Base;
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;
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;
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;
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())
133 : _Base(__gnu_debug::__base(
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
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) { }
158
159 unordered_map(initializer_list<value_type> __l,
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
191 unordered_map(initializer_list<value_type> __l,
192 size_type __n,
193 const allocator_type& __a)
194 : unordered_map(__l, __n, hasher(), key_equal(), __a)
195 { }
196
197 unordered_map(initializer_list<value_type> __l,
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#if __glibcxx_containers_ranges // C++ >= 23
205 template<__detail::__container_compatible_range<value_type> _Rg>
206 unordered_map(from_range_t, _Rg&& __rg,
207 size_type __n = 0,
208 const hasher& __hf = hasher(),
209 const key_equal& __eql = key_equal(),
210 const allocator_type& __a = allocator_type())
211 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __eql, __a)
212 { }
213
214 template<__detail::__container_compatible_range<value_type> _Rg>
215 unordered_map(from_range_t, _Rg&& __rg, const allocator_type& __a)
216 : _Base(from_range, std::forward<_Rg>(__rg), __a)
217 { }
218
219 template<__detail::__container_compatible_range<value_type> _Rg>
220 unordered_map(from_range_t, _Rg&& __rg, size_type __n,
221 const allocator_type& __a)
222 : _Base(from_range, std::forward<_Rg>(__rg), __n, __a)
223 { }
224
225 template<__detail::__container_compatible_range<value_type> _Rg>
226 unordered_map(from_range_t, _Rg&& __rg, size_type __n,
227 const hasher& __hf, const allocator_type& __a)
228 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __a)
229 { }
230#endif
231
232 ~unordered_map() = default;
233
234 unordered_map&
235 operator=(const unordered_map&) = default;
236
237 unordered_map&
238 operator=(unordered_map&&) = default;
239
240 unordered_map&
241 operator=(initializer_list<value_type> __l)
242 {
243 _Base::operator=(__l);
244 this->_M_invalidate_all();
245 return *this;
246 }
247
248 using _Base::get_allocator;
249 using _Base::empty;
250 using _Base::size;
251 using _Base::max_size;
252
253 void
254 swap(unordered_map& __x)
255 noexcept( noexcept(declval<_Base&>().swap(__x)) )
256 {
257 _Safe::_M_swap(__x);
258 _Base::swap(__x);
259 }
260
261 void
262 clear() noexcept
263 {
264 _Base::clear();
265 this->_M_invalidate_all();
266 }
267
268 iterator
269 begin() noexcept
270 { return { _Base::begin(), this }; }
271
272 const_iterator
273 begin() const noexcept
274 { return { _Base::begin(), this }; }
275
276 iterator
277 end() noexcept
278 { return { _Base::end(), this }; }
279
280 const_iterator
281 end() const noexcept
282 { return { _Base::end(), this }; }
283
284 const_iterator
285 cbegin() const noexcept
286 { return { _Base::cbegin(), this }; }
287
288 const_iterator
289 cend() const noexcept
290 { return { _Base::cend(), this }; }
291
292 // local versions
293 local_iterator
294 begin(size_type __b)
295 {
296 __glibcxx_check_bucket_index(__b);
297 return { _Base::begin(__b), this };
298 }
299
300 local_iterator
301 end(size_type __b)
302 {
303 __glibcxx_check_bucket_index(__b);
304 return { _Base::end(__b), this };
305 }
306
307 const_local_iterator
308 begin(size_type __b) const
309 {
310 __glibcxx_check_bucket_index(__b);
311 return { _Base::begin(__b), this };
312 }
313
314 const_local_iterator
315 end(size_type __b) const
316 {
317 __glibcxx_check_bucket_index(__b);
318 return { _Base::end(__b), this };
319 }
320
321 const_local_iterator
322 cbegin(size_type __b) const
323 {
324 __glibcxx_check_bucket_index(__b);
325 return { _Base::cbegin(__b), this };
326 }
327
328 const_local_iterator
329 cend(size_type __b) const
330 {
331 __glibcxx_check_bucket_index(__b);
332 return { _Base::cend(__b), this };
333 }
334
335 using _Base::bucket_count;
336 using _Base::max_bucket_count;
337 using _Base::bucket;
338
339 size_type
340 bucket_size(size_type __b) const
341 {
342 __glibcxx_check_bucket_index(__b);
343 return _Base::bucket_size(__b);
344 }
345
346 using _Base::load_factor;
347
348 float
349 max_load_factor() const noexcept
350 { return _Base::max_load_factor(); }
351
352 void
353 max_load_factor(float __f)
354 {
355 __glibcxx_check_max_load_factor(__f);
356 _Base::max_load_factor(__f);
357 }
358
359 template<typename... _Args>
360 std::pair<iterator, bool>
361 emplace(_Args&&... __args)
362 {
363 size_type __bucket_count = this->bucket_count();
364 auto __res = _Base::emplace(std::forward<_Args>(__args)...);
365 _M_check_rehashed(__bucket_count);
366 return { { __res.first, this }, __res.second };
367 }
368
369 template<typename... _Args>
370 iterator
371 emplace_hint(const_iterator __hint, _Args&&... __args)
372 {
373 __glibcxx_check_insert(__hint);
374 size_type __bucket_count = this->bucket_count();
375 auto __it = _Base::emplace_hint(__hint.base(),
376 std::forward<_Args>(__args)...);
377 _M_check_rehashed(__bucket_count);
378 return { __it, this };
379 }
380
381 std::pair<iterator, bool>
382 insert(const value_type& __obj)
383 {
384 size_type __bucket_count = this->bucket_count();
385 auto __res = _Base::insert(__obj);
386 _M_check_rehashed(__bucket_count);
387 return { { __res.first, this }, __res.second };
388 }
389
390 // _GLIBCXX_RESOLVE_LIB_DEFECTS
391 // 2354. Unnecessary copying when inserting into maps with braced-init
392 std::pair<iterator, bool>
393 insert(value_type&& __x)
394 {
395 size_type __bucket_count = this->bucket_count();
396 auto __res = _Base::insert(std::move(__x));
397 _M_check_rehashed(__bucket_count);
398 return { { __res.first, this }, __res.second };
399 }
400
401 template<typename _Pair, typename = typename
402 std::enable_if<std::is_constructible<value_type,
403 _Pair&&>::value>::type>
404 std::pair<iterator, bool>
405 insert(_Pair&& __obj)
406 {
407 size_type __bucket_count = this->bucket_count();
408 auto __res = _Base::insert(std::forward<_Pair>(__obj));
409 _M_check_rehashed(__bucket_count);
410 return { { __res.first, this }, __res.second };
411 }
412
413 iterator
414 insert(const_iterator __hint, const value_type& __obj)
415 {
416 __glibcxx_check_insert(__hint);
417 size_type __bucket_count = this->bucket_count();
418 auto __it = _Base::insert(__hint.base(), __obj);
419 _M_check_rehashed(__bucket_count);
420 return { __it, this };
421 }
422
423 // _GLIBCXX_RESOLVE_LIB_DEFECTS
424 // 2354. Unnecessary copying when inserting into maps with braced-init
425 iterator
426 insert(const_iterator __hint, value_type&& __x)
427 {
428 __glibcxx_check_insert(__hint);
429 size_type __bucket_count = this->bucket_count();
430 auto __it = _Base::insert(__hint.base(), std::move(__x));
431 _M_check_rehashed(__bucket_count);
432 return { __it, this };
433 }
434
435 template<typename _Pair, typename = typename
436 std::enable_if<std::is_constructible<value_type,
437 _Pair&&>::value>::type>
438 iterator
439 insert(const_iterator __hint, _Pair&& __obj)
440 {
441 __glibcxx_check_insert(__hint);
442 size_type __bucket_count = this->bucket_count();
443 auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
444 _M_check_rehashed(__bucket_count);
445 return { __it, this };
446 }
447
448 void
449 insert(std::initializer_list<value_type> __l)
450 {
451 size_type __bucket_count = this->bucket_count();
452 _Base::insert(__l);
453 _M_check_rehashed(__bucket_count);
454 }
455
456 template<typename _InputIterator>
457 void
458 insert(_InputIterator __first, _InputIterator __last)
459 {
460 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
461 __glibcxx_check_valid_range2(__first, __last, __dist);
462 size_type __bucket_count = this->bucket_count();
463
464 if (__dist.second >= __gnu_debug::__dp_sign)
465 _Base::insert(__gnu_debug::__unsafe(__first),
466 __gnu_debug::__unsafe(__last));
467 else
468 _Base::insert(__first, __last);
469
470 _M_check_rehashed(__bucket_count);
471 }
472
473#ifdef __glibcxx_unordered_map_try_emplace // C++ >= 17 && HOSTED
474 template <typename... _Args>
475 pair<iterator, bool>
476 try_emplace(const key_type& __k, _Args&&... __args)
477 {
478 auto __res = _Base::try_emplace(__k,
479 std::forward<_Args>(__args)...);
480 return { { __res.first, this }, __res.second };
481 }
482
483 template <typename... _Args>
484 pair<iterator, bool>
485 try_emplace(key_type&& __k, _Args&&... __args)
486 {
487 auto __res = _Base::try_emplace(std::move(__k),
488 std::forward<_Args>(__args)...);
489 return { { __res.first, this }, __res.second };
490 }
491
492 template <typename... _Args>
493 iterator
494 try_emplace(const_iterator __hint, const key_type& __k,
495 _Args&&... __args)
496 {
497 __glibcxx_check_insert(__hint);
498 return { _Base::try_emplace(__hint.base(), __k,
499 std::forward<_Args>(__args)...),
500 this };
501 }
502
503 template <typename... _Args>
504 iterator
505 try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
506 {
507 __glibcxx_check_insert(__hint);
508 return { _Base::try_emplace(__hint.base(), std::move(__k),
509 std::forward<_Args>(__args)...),
510 this };
511 }
512
513 template <typename _Obj>
514 pair<iterator, bool>
515 insert_or_assign(const key_type& __k, _Obj&& __obj)
516 {
517 auto __res = _Base::insert_or_assign(__k,
518 std::forward<_Obj>(__obj));
519 return { { __res.first, this }, __res.second };
520 }
521
522 template <typename _Obj>
523 pair<iterator, bool>
524 insert_or_assign(key_type&& __k, _Obj&& __obj)
525 {
526 auto __res = _Base::insert_or_assign(std::move(__k),
527 std::forward<_Obj>(__obj));
528 return { { __res.first, this }, __res.second };
529 }
530
531 template <typename _Obj>
532 iterator
533 insert_or_assign(const_iterator __hint, const key_type& __k,
534 _Obj&& __obj)
535 {
536 __glibcxx_check_insert(__hint);
537 return { _Base::insert_or_assign(__hint.base(), __k,
538 std::forward<_Obj>(__obj)),
539 this };
540 }
541
542 template <typename _Obj>
543 iterator
544 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
545 {
546 __glibcxx_check_insert(__hint);
547 return { _Base::insert_or_assign(__hint.base(), std::move(__k),
548 std::forward<_Obj>(__obj)),
549 this };
550 }
551#endif // C++17
552
553#if __cplusplus > 201402L
554 using node_type = typename _Base::node_type;
555 using insert_return_type = _Node_insert_return<iterator, node_type>;
556
557 node_type
558 extract(const_iterator __position)
559 {
560 __glibcxx_check_erase(__position);
561 return _M_extract(__position.base());
562 }
563
564 node_type
565 extract(const key_type& __key)
566 {
567 const auto __position = _Base::find(__key);
568 if (__position != _Base::end())
569 return _M_extract(__position);
570 return {};
571 }
572
573 insert_return_type
574 insert(node_type&& __nh)
575 {
576 auto __ret = _Base::insert(std::move(__nh));
577 return
578 { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };
579 }
580
581 iterator
582 insert(const_iterator __hint, node_type&& __nh)
583 {
584 __glibcxx_check_insert(__hint);
585 return { _Base::insert(__hint.base(), std::move(__nh)), this };
586 }
587
588 template<typename _H2, typename _P2>
589 void
590 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
591 {
592 auto __guard
593 = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
594 _Base::merge(__source);
595 }
596
597 template<typename _H2, typename _P2>
598 void
599 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
600 { merge(__source); }
601
602 template<typename _H2, typename _P2>
603 void
604 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
605 {
606 auto __guard
607 = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
608 _Base::merge(__source);
609 }
610
611 template<typename _H2, typename _P2>
612 void
613 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
614 { merge(__source); }
615#endif // C++17
616
617 using _Base::hash_function;
618 using _Base::key_eq;
619
620 iterator
621 find(const key_type& __key)
622 { return { _Base::find(__key), this }; }
623
624#if __cplusplus > 201703L
625 template<typename _Kt,
626 typename = std::__has_is_transparent_t<_Hash, _Kt>,
627 typename = std::__has_is_transparent_t<_Pred, _Kt>>
628 iterator
629 find(const _Kt& __k)
630 { return { _Base::find(__k), this }; }
631#endif
632
633 const_iterator
634 find(const key_type& __key) const
635 { return { _Base::find(__key), this }; }
636
637#if __cplusplus > 201703L
638 template<typename _Kt,
639 typename = std::__has_is_transparent_t<_Hash, _Kt>,
640 typename = std::__has_is_transparent_t<_Pred, _Kt>>
641 const_iterator
642 find(const _Kt& __k) const
643 { return { _Base::find(__k), this }; }
644#endif
645
646 using _Base::count;
647#if __cplusplus > 201703L
648 using _Base::contains;
649#endif
650
651 std::pair<iterator, iterator>
652 equal_range(const key_type& __key)
653 {
654 auto __res = _Base::equal_range(__key);
655 return { { __res.first, this }, { __res.second, this } };
656 }
657
658#if __cplusplus > 201703L
659 template<typename _Kt,
660 typename = std::__has_is_transparent_t<_Hash, _Kt>,
661 typename = std::__has_is_transparent_t<_Pred, _Kt>>
662 std::pair<iterator, iterator>
663 equal_range(const _Kt& __k)
664 {
665 auto __res = _Base::equal_range(__k);
666 return { { __res.first, this }, { __res.second, this } };
667 }
668#endif
669
670 std::pair<const_iterator, const_iterator>
671 equal_range(const key_type& __key) const
672 {
673 auto __res = _Base::equal_range(__key);
674 return { { __res.first, this }, { __res.second, this } };
675 }
676
677#if __cplusplus > 201703L
678 template<typename _Kt,
679 typename = std::__has_is_transparent_t<_Hash, _Kt>,
680 typename = std::__has_is_transparent_t<_Pred, _Kt>>
681 std::pair<const_iterator, const_iterator>
682 equal_range(const _Kt& __k) const
683 {
684 auto __res = _Base::equal_range(__k);
685 return { { __res.first, this }, { __res.second, this } };
686 }
687#endif
688
689 using _Base::operator[];
690 using _Base::at;
691
692 size_type
693 erase(const key_type& __key)
694 {
695 size_type __ret(0);
696 auto __victim = _Base::find(__key);
697 if (__victim != _Base::end())
698 {
699 _M_erase(__victim);
700 __ret = 1;
701 }
702 return __ret;
703 }
704
705 iterator
706 erase(const_iterator __it)
707 {
708 __glibcxx_check_erase(__it);
709 return { _M_erase(__it.base()), this };
710 }
711
712 _Base_iterator
713 erase(_Base_const_iterator __it)
714 {
715 __glibcxx_check_erase2(__it);
716 return _M_erase(__it);
717 }
718
719 iterator
720 erase(iterator __it)
721 {
722 __glibcxx_check_erase(__it);
723 return { _M_erase(__it.base()), this };
724 }
725
726 iterator
727 erase(const_iterator __first, const_iterator __last)
728 {
729 __glibcxx_check_erase_range(__first, __last);
730 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
731 {
732 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
733 _M_message(__gnu_debug::__msg_valid_range)
734 ._M_iterator(__first, "first")
735 ._M_iterator(__last, "last"));
736 _M_invalidate(__tmp);
737 }
738
739 size_type __bucket_count = this->bucket_count();
740 auto __next = _Base::erase(__first.base(), __last.base());
741 _M_check_rehashed(__bucket_count);
742 return { __next, this };
743 }
744
745 using _Base::rehash;
746 using _Base::reserve;
747
748 _Base&
749 _M_base() noexcept { return *this; }
750
751 const _Base&
752 _M_base() const noexcept { return *this; }
753
754 private:
755 void
756 _M_check_rehashed(size_type __prev_count)
757 {
758 if (__prev_count != this->bucket_count())
759 this->_M_invalidate_all();
760 }
761
762 void
763 _M_invalidate(_Base_const_iterator __victim)
764 {
765 this->_M_invalidate_if(
766 [__victim](_Base_const_iterator __it) { return __it == __victim; });
767 this->_M_invalidate_local_if(
768 [__victim](_Base_const_local_iterator __it)
769 { return __it == __victim; });
770 }
771
772 _Base_iterator
773 _M_erase(_Base_const_iterator __victim)
774 {
775 _M_invalidate(__victim);
776 size_type __bucket_count = this->bucket_count();
777 _Base_iterator __next = _Base::erase(__victim);
778 _M_check_rehashed(__bucket_count);
779 return __next;
780 }
781
782#if __cplusplus > 201402L
783 node_type
784 _M_extract(_Base_const_iterator __victim)
785 {
786 _M_invalidate(__victim);
787 return _Base::extract(__victim);
788 }
789#endif
790 };
791
792#if __cpp_deduction_guides >= 201606
793
794 template<typename _InputIterator,
795 typename _Hash = hash<__iter_key_t<_InputIterator>>,
796 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
797 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
798 typename = _RequireInputIter<_InputIterator>,
799 typename = _RequireNotAllocatorOrIntegral<_Hash>,
800 typename = _RequireNotAllocator<_Pred>,
801 typename = _RequireAllocator<_Allocator>>
802 unordered_map(_InputIterator, _InputIterator,
803 typename unordered_map<int, int>::size_type = {},
804 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
805 -> unordered_map<__iter_key_t<_InputIterator>,
806 __iter_val_t<_InputIterator>,
807 _Hash, _Pred, _Allocator>;
808
809 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
810 typename _Pred = equal_to<_Key>,
811 typename _Allocator = allocator<pair<const _Key, _Tp>>,
812 typename = _RequireNotAllocatorOrIntegral<_Hash>,
813 typename = _RequireNotAllocator<_Pred>,
814 typename = _RequireAllocator<_Allocator>>
815 unordered_map(initializer_list<pair<_Key, _Tp>>,
816 typename unordered_map<int, int>::size_type = {},
817 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
818 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
819
820 template<typename _InputIterator, typename _Allocator,
821 typename = _RequireInputIter<_InputIterator>,
822 typename = _RequireAllocator<_Allocator>>
823 unordered_map(_InputIterator, _InputIterator,
824 typename unordered_map<int, int>::size_type, _Allocator)
825 -> unordered_map<__iter_key_t<_InputIterator>,
826 __iter_val_t<_InputIterator>,
827 hash<__iter_key_t<_InputIterator>>,
828 equal_to<__iter_key_t<_InputIterator>>,
829 _Allocator>;
830
831 template<typename _InputIterator, typename _Allocator,
832 typename = _RequireInputIter<_InputIterator>,
833 typename = _RequireAllocator<_Allocator>>
834 unordered_map(_InputIterator, _InputIterator, _Allocator)
835 -> unordered_map<__iter_key_t<_InputIterator>,
836 __iter_val_t<_InputIterator>,
837 hash<__iter_key_t<_InputIterator>>,
838 equal_to<__iter_key_t<_InputIterator>>,
839 _Allocator>;
840
841 template<typename _InputIterator, typename _Hash, typename _Allocator,
842 typename = _RequireInputIter<_InputIterator>,
843 typename = _RequireNotAllocatorOrIntegral<_Hash>,
844 typename = _RequireAllocator<_Allocator>>
845 unordered_map(_InputIterator, _InputIterator,
846 typename unordered_map<int, int>::size_type,
847 _Hash, _Allocator)
848 -> unordered_map<__iter_key_t<_InputIterator>,
849 __iter_val_t<_InputIterator>, _Hash,
850 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
851
852 template<typename _Key, typename _Tp, typename _Allocator,
853 typename = _RequireAllocator<_Allocator>>
854 unordered_map(initializer_list<pair<_Key, _Tp>>,
855 typename unordered_map<int, int>::size_type,
856 _Allocator)
857 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
858
859 template<typename _Key, typename _Tp, typename _Allocator,
860 typename = _RequireAllocator<_Allocator>>
861 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
862 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
863
864 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
865 typename = _RequireNotAllocatorOrIntegral<_Hash>,
866 typename = _RequireAllocator<_Allocator>>
867 unordered_map(initializer_list<pair<_Key, _Tp>>,
868 typename unordered_map<int, int>::size_type,
869 _Hash, _Allocator)
870 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
871
872#if __glibcxx_containers_ranges // C++ >= 23
873 template<ranges::input_range _Rg,
874 __not_allocator_like _Hash = hash<__detail::__range_key_type<_Rg>>,
875 __not_allocator_like _Pred = equal_to<__detail::__range_key_type<_Rg>>,
876 __allocator_like _Allocator =
877 allocator<__detail::__range_to_alloc_type<_Rg>>>
878 unordered_map(from_range_t, _Rg&&, unordered_map<int, int>::size_type = {},
879 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
880 -> unordered_map<__detail::__range_key_type<_Rg>,
881 __detail::__range_mapped_type<_Rg>,
882 _Hash, _Pred, _Allocator>;
883
884 template<ranges::input_range _Rg,
885 __allocator_like _Allocator>
886 unordered_map(from_range_t, _Rg&&, unordered_map<int, int>::size_type,
887 _Allocator)
888 -> unordered_map<__detail::__range_key_type<_Rg>,
889 __detail::__range_mapped_type<_Rg>,
890 hash<__detail::__range_key_type<_Rg>>,
891 equal_to<__detail::__range_key_type<_Rg>>,
892 _Allocator>;
893
894 template<ranges::input_range _Rg,
895 __allocator_like _Allocator>
896 unordered_map(from_range_t, _Rg&&, _Allocator)
897 -> unordered_map<__detail::__range_key_type<_Rg>,
898 __detail::__range_mapped_type<_Rg>,
899 hash<__detail::__range_key_type<_Rg>>,
900 equal_to<__detail::__range_key_type<_Rg>>,
901 _Allocator>;
902
903 template<ranges::input_range _Rg,
904 __not_allocator_like _Hash,
905 __allocator_like _Allocator>
906 unordered_map(from_range_t, _Rg&&, unordered_map<int, int>::size_type,
907 _Hash, _Allocator)
908 -> unordered_map<__detail::__range_key_type<_Rg>,
909 __detail::__range_mapped_type<_Rg>,
910 _Hash, equal_to<__detail::__range_key_type<_Rg>>,
911 _Allocator>;
912#endif
913#endif
914
915 template<typename _Key, typename _Tp, typename _Hash,
916 typename _Pred, typename _Alloc>
917 inline void
918 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
919 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
920 noexcept(noexcept(__x.swap(__y)))
921 { __x.swap(__y); }
922
923 template<typename _Key, typename _Tp, typename _Hash,
924 typename _Pred, typename _Alloc>
925 inline bool
926 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
927 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
928 { return __x._M_base() == __y._M_base(); }
929
930#if __cpp_impl_three_way_comparison < 201907L
931 template<typename _Key, typename _Tp, typename _Hash,
932 typename _Pred, typename _Alloc>
933 inline bool
934 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
935 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
936 { return !(__x == __y); }
937#endif
938
939 /// Class std::unordered_multimap with safety/checking/debug instrumentation.
940 template<typename _Key, typename _Tp,
941 typename _Hash = std::hash<_Key>,
942 typename _Pred = std::equal_to<_Key>,
943 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
944 class unordered_multimap
945 : public __gnu_debug::_Safe_container<
946 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
947 __gnu_debug::_Safe_unordered_container>,
948 public _GLIBCXX_STD_C::unordered_multimap<
949 _Key, _Tp, _Hash, _Pred, _Alloc>
950 {
951 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
952 _Pred, _Alloc> _Base;
953 typedef __gnu_debug::_Safe_container<unordered_multimap,
954 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
955 typedef typename _Base::const_iterator _Base_const_iterator;
956 typedef typename _Base::iterator _Base_iterator;
957 typedef typename _Base::const_local_iterator _Base_const_local_iterator;
958 typedef typename _Base::local_iterator _Base_local_iterator;
959
960 template<typename _ItT, typename _SeqT, typename _CatT>
961 friend class ::__gnu_debug::_Safe_iterator;
962 template<typename _ItT, typename _SeqT>
963 friend class ::__gnu_debug::_Safe_local_iterator;
964
965 // Reference wrapper for base class. See PR libstdc++/90102.
966 struct _Base_ref
967 {
968 _Base_ref(const _Base& __r) : _M_ref(__r) { }
969
970 const _Base& _M_ref;
971 };
972
973 public:
974 typedef typename _Base::size_type size_type;
975 typedef typename _Base::hasher hasher;
976 typedef typename _Base::key_equal key_equal;
977 typedef typename _Base::allocator_type allocator_type;
978
979 typedef typename _Base::key_type key_type;
980 typedef typename _Base::value_type value_type;
981 typedef typename _Base::mapped_type mapped_type;
982
983 typedef typename _Base::pointer pointer;
984 typedef typename _Base::const_pointer const_pointer;
985 typedef typename _Base::reference reference;
986 typedef typename _Base::const_reference const_reference;
987 typedef __gnu_debug::_Safe_iterator<
988 _Base_iterator, unordered_multimap> iterator;
989 typedef __gnu_debug::_Safe_iterator<
990 _Base_const_iterator, unordered_multimap> const_iterator;
991 typedef __gnu_debug::_Safe_local_iterator<
992 _Base_local_iterator, unordered_multimap> local_iterator;
993 typedef __gnu_debug::_Safe_local_iterator<
994 _Base_const_local_iterator, unordered_multimap> const_local_iterator;
995 typedef typename _Base::difference_type difference_type;
996
997 unordered_multimap() = default;
998
999 explicit
1000 unordered_multimap(size_type __n,
1001 const hasher& __hf = hasher(),
1002 const key_equal& __eql = key_equal(),
1003 const allocator_type& __a = allocator_type())
1004 : _Base(__n, __hf, __eql, __a) { }
1005
1006 template<typename _InputIterator>
1007 unordered_multimap(_InputIterator __first, _InputIterator __last,
1008 size_type __n = 0,
1009 const hasher& __hf = hasher(),
1010 const key_equal& __eql = key_equal(),
1011 const allocator_type& __a = allocator_type())
1012 : _Base(__gnu_debug::__base(
1013 __glibcxx_check_valid_constructor_range(__first, __last)),
1014 __gnu_debug::__base(__last), __n,
1015 __hf, __eql, __a) { }
1016
1017 unordered_multimap(const unordered_multimap&) = default;
1018
1019 unordered_multimap(_Base_ref __x)
1020 : _Base(__x._M_ref) { }
1021
1022 unordered_multimap(unordered_multimap&&) = default;
1023
1024 explicit
1025 unordered_multimap(const allocator_type& __a)
1026 : _Base(__a) { }
1027
1028 unordered_multimap(const unordered_multimap& __umap,
1029 const allocator_type& __a)
1030 : _Base(__umap, __a) { }
1031
1032 unordered_multimap(unordered_multimap&& __umap,
1033 const allocator_type& __a)
1034 noexcept( noexcept(_Base(std::move(__umap), __a)) )
1035 : _Safe(std::move(__umap), __a),
1036 _Base(std::move(__umap), __a) { }
1037
1038 unordered_multimap(initializer_list<value_type> __l,
1039 size_type __n = 0,
1040 const hasher& __hf = hasher(),
1041 const key_equal& __eql = key_equal(),
1042 const allocator_type& __a = allocator_type())
1043 : _Base(__l, __n, __hf, __eql, __a) { }
1044
1045 unordered_multimap(size_type __n, const allocator_type& __a)
1046 : unordered_multimap(__n, hasher(), key_equal(), __a)
1047 { }
1048
1049 unordered_multimap(size_type __n, const hasher& __hf,
1050 const allocator_type& __a)
1051 : unordered_multimap(__n, __hf, key_equal(), __a)
1052 { }
1053
1054 template<typename _InputIterator>
1055 unordered_multimap(_InputIterator __first, _InputIterator __last,
1056 size_type __n,
1057 const allocator_type& __a)
1058 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
1059 { }
1060
1061 template<typename _InputIterator>
1062 unordered_multimap(_InputIterator __first, _InputIterator __last,
1063 size_type __n, const hasher& __hf,
1064 const allocator_type& __a)
1065 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
1066 { }
1067
1068 unordered_multimap(initializer_list<value_type> __l,
1069 size_type __n,
1070 const allocator_type& __a)
1071 : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
1072 { }
1073
1074 unordered_multimap(initializer_list<value_type> __l,
1075 size_type __n, const hasher& __hf,
1076 const allocator_type& __a)
1077 : unordered_multimap(__l, __n, __hf, key_equal(), __a)
1078 { }
1079
1080#if __glibcxx_containers_ranges // C++ >= 23
1081 template<__detail::__container_compatible_range<value_type> _Rg>
1082 unordered_multimap(from_range_t, _Rg&& __rg,
1083 size_type __n = 0,
1084 const hasher& __hf = hasher(),
1085 const key_equal& __eql = key_equal(),
1086 const allocator_type& __a = allocator_type())
1087 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __eql, __a)
1088 { }
1089
1090 template<__detail::__container_compatible_range<value_type> _Rg>
1091 unordered_multimap(from_range_t, _Rg&& __rg, const allocator_type& __a)
1092 : _Base(from_range, std::forward<_Rg>(__rg), __a)
1093 { }
1094
1095 template<__detail::__container_compatible_range<value_type> _Rg>
1096 unordered_multimap(from_range_t, _Rg&& __rg, size_type __n,
1097 const allocator_type& __a)
1098 : _Base(from_range, std::forward<_Rg>(__rg), __n, __a)
1099 { }
1100
1101 template<__detail::__container_compatible_range<value_type> _Rg>
1102 unordered_multimap(from_range_t, _Rg&& __rg, size_type __n,
1103 const hasher& __hf, const allocator_type& __a)
1104 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __a)
1105 { }
1106#endif
1107
1108 ~unordered_multimap() = default;
1109
1110 unordered_multimap&
1111 operator=(const unordered_multimap&) = default;
1112
1113 unordered_multimap&
1114 operator=(unordered_multimap&&) = default;
1115
1116 unordered_multimap&
1117 operator=(initializer_list<value_type> __l)
1118 {
1119 _Base::operator=(__l);
1120 this->_M_invalidate_all();
1121 return *this;
1122 }
1123
1124 using _Base::get_allocator;
1125 using _Base::empty;
1126 using _Base::size;
1127 using _Base::max_size;
1128
1129 void
1130 swap(unordered_multimap& __x)
1131 noexcept( noexcept(declval<_Base&>().swap(__x)) )
1132 {
1133 _Safe::_M_swap(__x);
1134 _Base::swap(__x);
1135 }
1136
1137 void
1138 clear() noexcept
1139 {
1140 _Base::clear();
1141 this->_M_invalidate_all();
1142 }
1143
1144 iterator
1145 begin() noexcept
1146 { return { _Base::begin(), this }; }
1147
1148 const_iterator
1149 begin() const noexcept
1150 { return { _Base::begin(), this }; }
1151
1152 iterator
1153 end() noexcept
1154 { return { _Base::end(), this }; }
1155
1156 const_iterator
1157 end() const noexcept
1158 { return { _Base::end(), this }; }
1159
1160 const_iterator
1161 cbegin() const noexcept
1162 { return { _Base::cbegin(), this }; }
1163
1164 const_iterator
1165 cend() const noexcept
1166 { return { _Base::cend(), this }; }
1167
1168 // local versions
1169 local_iterator
1170 begin(size_type __b)
1171 {
1172 __glibcxx_check_bucket_index(__b);
1173 return { _Base::begin(__b), this };
1174 }
1175
1176 local_iterator
1177 end(size_type __b)
1178 {
1179 __glibcxx_check_bucket_index(__b);
1180 return { _Base::end(__b), this };
1181 }
1182
1183 const_local_iterator
1184 begin(size_type __b) const
1185 {
1186 __glibcxx_check_bucket_index(__b);
1187 return { _Base::begin(__b), this };
1188 }
1189
1190 const_local_iterator
1191 end(size_type __b) const
1192 {
1193 __glibcxx_check_bucket_index(__b);
1194 return { _Base::end(__b), this };
1195 }
1196
1197 const_local_iterator
1198 cbegin(size_type __b) const
1199 {
1200 __glibcxx_check_bucket_index(__b);
1201 return { _Base::cbegin(__b), this };
1202 }
1203
1204 const_local_iterator
1205 cend(size_type __b) const
1206 {
1207 __glibcxx_check_bucket_index(__b);
1208 return { _Base::cend(__b), this };
1209 }
1210
1211 using _Base::bucket_count;
1212 using _Base::max_bucket_count;
1213 using _Base::bucket;
1214
1215 size_type
1216 bucket_size(size_type __b) const
1217 {
1218 __glibcxx_check_bucket_index(__b);
1219 return _Base::bucket_size(__b);
1220 }
1221
1222 float
1223 max_load_factor() const noexcept
1224 { return _Base::max_load_factor(); }
1225
1226 void
1227 max_load_factor(float __f)
1228 {
1229 __glibcxx_check_max_load_factor(__f);
1230 _Base::max_load_factor(__f);
1231 }
1232
1233 template<typename... _Args>
1234 iterator
1235 emplace(_Args&&... __args)
1236 {
1237 size_type __bucket_count = this->bucket_count();
1238 auto __it = _Base::emplace(std::forward<_Args>(__args)...);
1239 _M_check_rehashed(__bucket_count);
1240 return { __it, this };
1241 }
1242
1243 template<typename... _Args>
1244 iterator
1245 emplace_hint(const_iterator __hint, _Args&&... __args)
1246 {
1247 __glibcxx_check_insert(__hint);
1248 size_type __bucket_count = this->bucket_count();
1249 auto __it = _Base::emplace_hint(__hint.base(),
1250 std::forward<_Args>(__args)...);
1251 _M_check_rehashed(__bucket_count);
1252 return { __it, this };
1253 }
1254
1255 iterator
1256 insert(const value_type& __obj)
1257 {
1258 size_type __bucket_count = this->bucket_count();
1259 auto __it = _Base::insert(__obj);
1260 _M_check_rehashed(__bucket_count);
1261 return { __it, this };
1262 }
1263
1264 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1265 // 2354. Unnecessary copying when inserting into maps with braced-init
1266 iterator
1267 insert(value_type&& __x)
1268 {
1269 size_type __bucket_count = this->bucket_count();
1270 auto __it = _Base::insert(std::move(__x));
1271 _M_check_rehashed(__bucket_count);
1272 return { __it, this };
1273 }
1274
1275 iterator
1276 insert(const_iterator __hint, const value_type& __obj)
1277 {
1278 __glibcxx_check_insert(__hint);
1279 size_type __bucket_count = this->bucket_count();
1280 auto __it = _Base::insert(__hint.base(), __obj);
1281 _M_check_rehashed(__bucket_count);
1282 return { __it, this };
1283 }
1284
1285 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1286 // 2354. Unnecessary copying when inserting into maps with braced-init
1287 iterator
1288 insert(const_iterator __hint, value_type&& __x)
1289 {
1290 __glibcxx_check_insert(__hint);
1291 size_type __bucket_count = this->bucket_count();
1292 auto __it = _Base::insert(__hint.base(), std::move(__x));
1293 _M_check_rehashed(__bucket_count);
1294 return { __it, this };
1295 }
1296
1297 template<typename _Pair, typename = typename
1298 std::enable_if<std::is_constructible<value_type,
1299 _Pair&&>::value>::type>
1300 iterator
1301 insert(_Pair&& __obj)
1302 {
1303 size_type __bucket_count = this->bucket_count();
1304 auto __it = _Base::insert(std::forward<_Pair>(__obj));
1305 _M_check_rehashed(__bucket_count);
1306 return { __it, this };
1307 }
1308
1309 template<typename _Pair, typename = typename
1310 std::enable_if<std::is_constructible<value_type,
1311 _Pair&&>::value>::type>
1312 iterator
1313 insert(const_iterator __hint, _Pair&& __obj)
1314 {
1315 __glibcxx_check_insert(__hint);
1316 size_type __bucket_count = this->bucket_count();
1317 auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
1318 _M_check_rehashed(__bucket_count);
1319 return { __it, this };
1320 }
1321
1322 void
1323 insert(std::initializer_list<value_type> __l)
1324 { _Base::insert(__l); }
1325
1326 template<typename _InputIterator>
1327 void
1328 insert(_InputIterator __first, _InputIterator __last)
1329 {
1330 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
1331 __glibcxx_check_valid_range2(__first, __last, __dist);
1332 size_type __bucket_count = this->bucket_count();
1333
1334 if (__dist.second >= __gnu_debug::__dp_sign)
1335 _Base::insert(__gnu_debug::__unsafe(__first),
1336 __gnu_debug::__unsafe(__last));
1337 else
1338 _Base::insert(__first, __last);
1339
1340 _M_check_rehashed(__bucket_count);
1341 }
1342
1343#if __cplusplus > 201402L
1344 using node_type = typename _Base::node_type;
1345
1346 node_type
1347 extract(const_iterator __position)
1348 {
1349 __glibcxx_check_erase(__position);
1350 return _M_extract(__position.base());
1351 }
1352
1353 node_type
1354 extract(const key_type& __key)
1355 {
1356 const auto __position = _Base::find(__key);
1357 if (__position != _Base::end())
1358 return _M_extract(__position);
1359 return {};
1360 }
1361
1362 iterator
1363 insert(node_type&& __nh)
1364 { return { _Base::insert(std::move(__nh)), this }; }
1365
1366 iterator
1367 insert(const_iterator __hint, node_type&& __nh)
1368 {
1369 __glibcxx_check_insert(__hint);
1370 return { _Base::insert(__hint.base(), std::move(__nh)), this };
1371 }
1372
1373 template<typename _H2, typename _P2>
1374 void
1375 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1376 {
1377 auto __guard
1378 = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
1379 _Base::merge(__source);
1380 }
1381
1382 template<typename _H2, typename _P2>
1383 void
1384 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1385 { merge(__source); }
1386
1387 template<typename _H2, typename _P2>
1388 void
1389 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1390 {
1391 auto __guard
1392 = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
1393 _Base::merge(__source);
1394 }
1395
1396 template<typename _H2, typename _P2>
1397 void
1398 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1399 { merge(__source); }
1400#endif // C++17
1401
1402 using _Base::hash_function;
1403 using _Base::key_eq;
1404
1405 iterator
1406 find(const key_type& __key)
1407 { return { _Base::find(__key), this }; }
1408
1409#if __cplusplus > 201703L
1410 template<typename _Kt,
1411 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1412 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1413 iterator
1414 find(const _Kt& __k)
1415 { return { _Base::find(__k), this }; }
1416#endif
1417
1418 const_iterator
1419 find(const key_type& __key) const
1420 { return { _Base::find(__key), this }; }
1421
1422#if __cplusplus > 201703L
1423 template<typename _Kt,
1424 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1425 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1426 const_iterator
1427 find(const _Kt& __k) const
1428 { return { _Base::find(__k), this }; }
1429#endif
1430
1431 using _Base::count;
1432#if __cplusplus > 201703L
1433 using _Base::contains;
1434#endif
1435
1436 std::pair<iterator, iterator>
1437 equal_range(const key_type& __key)
1438 {
1439 auto __res = _Base::equal_range(__key);
1440 return { { __res.first, this }, { __res.second, this } };
1441 }
1442
1443#if __cplusplus > 201703L
1444 template<typename _Kt,
1445 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1446 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1447 std::pair<iterator, iterator>
1448 equal_range(const _Kt& __k)
1449 {
1450 auto __res = _Base::equal_range(__k);
1451 return { { __res.first, this }, { __res.second, this } };
1452 }
1453#endif
1454
1455 std::pair<const_iterator, const_iterator>
1456 equal_range(const key_type& __key) const
1457 {
1458 auto __res = _Base::equal_range(__key);
1459 return { { __res.first, this }, { __res.second, this } };
1460 }
1461
1462#if __cplusplus > 201703L
1463 template<typename _Kt,
1464 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1465 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1466 std::pair<const_iterator, const_iterator>
1467 equal_range(const _Kt& __k) const
1468 {
1469 auto __res = _Base::equal_range(__k);
1470 return { { __res.first, this }, { __res.second, this } };
1471 }
1472#endif
1473
1474 size_type
1475 erase(const key_type& __key)
1476 {
1477 size_type __ret(0);
1478 size_type __bucket_count = this->bucket_count();
1479 auto __pair = _Base::equal_range(__key);
1480 for (auto __victim = __pair.first; __victim != __pair.second;)
1481 {
1482 _M_invalidate(__victim);
1483 __victim = _Base::erase(__victim);
1484 ++__ret;
1485 }
1486
1487 _M_check_rehashed(__bucket_count);
1488 return __ret;
1489 }
1490
1491 iterator
1492 erase(const_iterator __it)
1493 {
1494 __glibcxx_check_erase(__it);
1495 return { _M_erase(__it.base()), this };
1496 }
1497
1498 _Base_iterator
1499 erase(_Base_const_iterator __it)
1500 {
1501 __glibcxx_check_erase2(__it);
1502 return _M_erase(__it);
1503 }
1504
1505 iterator
1506 erase(iterator __it)
1507 {
1508 __glibcxx_check_erase(__it);
1509 return { _M_erase(__it.base()), this };
1510 }
1511
1512 iterator
1513 erase(const_iterator __first, const_iterator __last)
1514 {
1515 __glibcxx_check_erase_range(__first, __last);
1516 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1517 {
1518 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1519 _M_message(__gnu_debug::__msg_valid_range)
1520 ._M_iterator(__first, "first")
1521 ._M_iterator(__last, "last"));
1522 _M_invalidate(__tmp);
1523 }
1524
1525 size_type __bucket_count = this->bucket_count();
1526 auto __next = _Base::erase(__first.base(), __last.base());
1527 _M_check_rehashed(__bucket_count);
1528 return { __next, this };
1529 }
1530
1531 using _Base::rehash;
1532 using _Base::reserve;
1533
1534 _Base&
1535 _M_base() noexcept { return *this; }
1536
1537 const _Base&
1538 _M_base() const noexcept { return *this; }
1539
1540 private:
1541 void
1542 _M_check_rehashed(size_type __prev_count)
1543 {
1544 if (__prev_count != this->bucket_count())
1545 this->_M_invalidate_all();
1546 }
1547
1548 void
1549 _M_invalidate(_Base_const_iterator __victim)
1550 {
1551 this->_M_invalidate_if(
1552 [__victim](_Base_const_iterator __it) { return __it == __victim; });
1553 this->_M_invalidate_local_if(
1554 [__victim](_Base_const_local_iterator __it)
1555 { return __it == __victim; });
1556 }
1557
1558 _Base_iterator
1559 _M_erase(_Base_const_iterator __victim)
1560 {
1561 _M_invalidate(__victim);
1562 size_type __bucket_count = this->bucket_count();
1563 _Base_iterator __next = _Base::erase(__victim);
1564 _M_check_rehashed(__bucket_count);
1565 return __next;
1566 }
1567
1568#if __cplusplus > 201402L
1569 node_type
1570 _M_extract(_Base_const_iterator __victim)
1571 {
1572 _M_invalidate(__victim);
1573 return _Base::extract(__victim);
1574 }
1575#endif
1576 };
1577
1578#if __cpp_deduction_guides >= 201606
1579
1580 template<typename _InputIterator,
1581 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1582 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1583 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1584 typename = _RequireInputIter<_InputIterator>,
1585 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1586 typename = _RequireNotAllocator<_Pred>,
1587 typename = _RequireAllocator<_Allocator>>
1588 unordered_multimap(_InputIterator, _InputIterator,
1589 unordered_multimap<int, int>::size_type = {},
1590 _Hash = _Hash(), _Pred = _Pred(),
1591 _Allocator = _Allocator())
1592 -> unordered_multimap<__iter_key_t<_InputIterator>,
1593 __iter_val_t<_InputIterator>, _Hash, _Pred,
1594 _Allocator>;
1595
1596 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
1597 typename _Pred = equal_to<_Key>,
1598 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1599 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1600 typename = _RequireNotAllocator<_Pred>,
1601 typename = _RequireAllocator<_Allocator>>
1602 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1603 unordered_multimap<int, int>::size_type = {},
1604 _Hash = _Hash(), _Pred = _Pred(),
1605 _Allocator = _Allocator())
1606 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
1607
1608 template<typename _InputIterator, typename _Allocator,
1609 typename = _RequireInputIter<_InputIterator>,
1610 typename = _RequireAllocator<_Allocator>>
1611 unordered_multimap(_InputIterator, _InputIterator,
1612 unordered_multimap<int, int>::size_type, _Allocator)
1613 -> unordered_multimap<__iter_key_t<_InputIterator>,
1614 __iter_val_t<_InputIterator>,
1615 hash<__iter_key_t<_InputIterator>>,
1616 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1617
1618 template<typename _InputIterator, typename _Allocator,
1619 typename = _RequireInputIter<_InputIterator>,
1620 typename = _RequireAllocator<_Allocator>>
1621 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
1622 -> unordered_multimap<__iter_key_t<_InputIterator>,
1623 __iter_val_t<_InputIterator>,
1624 hash<__iter_key_t<_InputIterator>>,
1625 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1626
1627 template<typename _InputIterator, typename _Hash, typename _Allocator,
1628 typename = _RequireInputIter<_InputIterator>,
1629 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1630 typename = _RequireAllocator<_Allocator>>
1631 unordered_multimap(_InputIterator, _InputIterator,
1632 unordered_multimap<int, int>::size_type, _Hash,
1633 _Allocator)
1634 -> unordered_multimap<__iter_key_t<_InputIterator>,
1635 __iter_val_t<_InputIterator>, _Hash,
1636 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1637
1638 template<typename _Key, typename _Tp, typename _Allocator,
1639 typename = _RequireAllocator<_Allocator>>
1640 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1641 unordered_multimap<int, int>::size_type,
1642 _Allocator)
1643 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1644
1645 template<typename _Key, typename _Tp, typename _Allocator,
1646 typename = _RequireAllocator<_Allocator>>
1647 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
1648 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1649
1650 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
1651 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1652 typename = _RequireAllocator<_Allocator>>
1653 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1654 unordered_multimap<int, int>::size_type,
1655 _Hash, _Allocator)
1656 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1657
1658#if __glibcxx_containers_ranges // C++ >= 23
1659 template<ranges::input_range _Rg,
1660 __not_allocator_like _Hash = hash<__detail::__range_key_type<_Rg>>,
1661 __not_allocator_like _Pred = equal_to<__detail::__range_key_type<_Rg>>,
1662 __allocator_like _Allocator =
1663 allocator<__detail::__range_to_alloc_type<_Rg>>>
1664 unordered_multimap(from_range_t, _Rg&&,
1665 unordered_multimap<int, int>::size_type = {},
1666 _Hash = _Hash(), _Pred = _Pred(),
1667 _Allocator = _Allocator())
1668 -> unordered_multimap<__detail::__range_key_type<_Rg>,
1669 __detail::__range_mapped_type<_Rg>,
1670 _Hash, _Pred, _Allocator>;
1671
1672 template<ranges::input_range _Rg,
1673 __allocator_like _Allocator>
1674 unordered_multimap(from_range_t, _Rg&&, unordered_multimap<int, int>::size_type,
1675 _Allocator)
1676 -> unordered_multimap<__detail::__range_key_type<_Rg>,
1677 __detail::__range_mapped_type<_Rg>,
1678 hash<__detail::__range_key_type<_Rg>>,
1679 equal_to<__detail::__range_key_type<_Rg>>,
1680 _Allocator>;
1681
1682 template<ranges::input_range _Rg,
1683 __allocator_like _Allocator>
1684 unordered_multimap(from_range_t, _Rg&&, _Allocator)
1685 -> unordered_multimap<__detail::__range_key_type<_Rg>,
1686 __detail::__range_mapped_type<_Rg>,
1687 hash<__detail::__range_key_type<_Rg>>,
1688 equal_to<__detail::__range_key_type<_Rg>>,
1689 _Allocator>;
1690
1691 template<ranges::input_range _Rg,
1692 __not_allocator_like _Hash,
1693 __allocator_like _Allocator>
1694 unordered_multimap(from_range_t, _Rg&&,
1695 unordered_multimap<int, int>::size_type,
1696 _Hash, _Allocator)
1697 -> unordered_multimap<__detail::__range_key_type<_Rg>,
1698 __detail::__range_mapped_type<_Rg>,
1699 _Hash, equal_to<__detail::__range_key_type<_Rg>>,
1700 _Allocator>;
1701#endif
1702#endif
1703
1704 template<typename _Key, typename _Tp, typename _Hash,
1705 typename _Pred, typename _Alloc>
1706 inline void
1707 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1708 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1709 noexcept(noexcept(__x.swap(__y)))
1710 { __x.swap(__y); }
1711
1712 template<typename _Key, typename _Tp, typename _Hash,
1713 typename _Pred, typename _Alloc>
1714 inline bool
1715 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1716 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1717 { return __x._M_base() == __y._M_base(); }
1718
1719#if __cpp_impl_three_way_comparison < 201907L
1720 template<typename _Key, typename _Tp, typename _Hash,
1721 typename _Pred, typename _Alloc>
1722 inline bool
1723 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1724 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1725 { return !(__x == __y); }
1726#endif
1727
1728} // namespace __debug
1729} // namespace std
1730
1731#endif // C++11
1732
1733#endif