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