libstdc++
debug/unordered_map
Go to the documentation of this file.
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(__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(__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(__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(__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(__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(__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(__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(__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(__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(__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 template <typename... _Args>
504 iterator
505 try_emplace(const_iterator __hint, const key_type& __k,
506 _Args&&... __args)
507 {
508 __glibcxx_check_insert(__hint);
509 return { _Base::try_emplace(__hint.base(), __k,
510 std::forward<_Args>(__args)...),
511 this };
512 }
513
514 template <typename... _Args>
515 iterator
516 try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
517 {
518 __glibcxx_check_insert(__hint);
519 return { _Base::try_emplace(__hint.base(), std::move(__k),
520 std::forward<_Args>(__args)...),
521 this };
522 }
523
524 template <typename _Obj>
525 pair<iterator, bool>
526 insert_or_assign(const key_type& __k, _Obj&& __obj)
527 {
528 auto __res = _Base::insert_or_assign(__k,
529 std::forward<_Obj>(__obj));
530 return { { __res.first, this }, __res.second };
531 }
532
533 template <typename _Obj>
534 pair<iterator, bool>
535 insert_or_assign(key_type&& __k, _Obj&& __obj)
536 {
537 auto __res = _Base::insert_or_assign(std::move(__k),
538 std::forward<_Obj>(__obj));
539 return { { __res.first, this }, __res.second };
540 }
541
542 template <typename _Obj>
543 iterator
544 insert_or_assign(const_iterator __hint, const key_type& __k,
545 _Obj&& __obj)
546 {
547 __glibcxx_check_insert(__hint);
548 return { _Base::insert_or_assign(__hint.base(), __k,
549 std::forward<_Obj>(__obj)),
550 this };
551 }
552
553 template <typename _Obj>
554 iterator
555 insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
556 {
557 __glibcxx_check_insert(__hint);
558 return { _Base::insert_or_assign(__hint.base(), std::move(__k),
559 std::forward<_Obj>(__obj)),
560 this };
561 }
562#endif // C++17
563
564#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
565 using node_type = typename _Base::node_type;
566 using insert_return_type = _Node_insert_return<iterator, node_type>;
567
568 node_type
569 extract(const_iterator __position)
570 {
571 __glibcxx_check_erase(__position);
572 return _M_extract(__position.base());
573 }
574
575 node_type
576 extract(const key_type& __key)
577 {
578 const auto __position = _Base::find(__key);
579 if (__position != _Base::end())
580 return _M_extract(__position);
581 return {};
582 }
583
584# ifdef __glibcxx_associative_heterogeneous_erasure
585 template <__heterogeneous_hash_key<unordered_map> _Kt>
586 node_type
587 extract(_Kt&& __key)
588 {
589 const auto __position = _Base::find(__key);
590 if (__position != _Base::end())
591 return _M_extract(__position);
592 return {};
593 }
594#endif
595
596 insert_return_type
597 insert(node_type&& __nh)
598 {
599 auto __ret = _Base::insert(std::move(__nh));
600 return
601 { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };
602 }
603
604 iterator
605 insert(const_iterator __hint, node_type&& __nh)
606 {
607 __glibcxx_check_insert(__hint);
608 return { _Base::insert(__hint.base(), std::move(__nh)), this };
609 }
610
611 template<typename _H2, typename _P2>
612 void
613 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
614 {
615 auto __guard
616 = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
617 _Base::merge(__source);
618 }
619
620 template<typename _H2, typename _P2>
621 void
622 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
623 { merge(__source); }
624
625 template<typename _H2, typename _P2>
626 void
627 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
628 {
629 auto __guard
630 = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
631 _Base::merge(__source);
632 }
633
634 template<typename _H2, typename _P2>
635 void
636 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
637 { merge(__source); }
638#endif // C++17
639
640 using _Base::hash_function;
641 using _Base::key_eq;
642
643 iterator
644 find(const key_type& __key)
645 { return { _Base::find(__key), this }; }
646
647#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
648 template<typename _Kt,
649 typename = std::__has_is_transparent_t<_Hash, _Kt>,
650 typename = std::__has_is_transparent_t<_Pred, _Kt>>
651 iterator
652 find(const _Kt& __k)
653 { return { _Base::find(__k), this }; }
654#endif
655
656 const_iterator
657 find(const key_type& __key) const
658 { return { _Base::find(__key), this }; }
659
660#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
661 template<typename _Kt,
662 typename = std::__has_is_transparent_t<_Hash, _Kt>,
663 typename = std::__has_is_transparent_t<_Pred, _Kt>>
664 const_iterator
665 find(const _Kt& __k) const
666 { return { _Base::find(__k), this }; }
667#endif
668
669 using _Base::count;
670#if __cplusplus > 201703L
671 using _Base::contains;
672#endif
673
674 std::pair<iterator, iterator>
675 equal_range(const key_type& __key)
676 {
677 auto __res = _Base::equal_range(__key);
678 return { { __res.first, this }, { __res.second, this } };
679 }
680
681#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
682 template<typename _Kt,
683 typename = std::__has_is_transparent_t<_Hash, _Kt>,
684 typename = std::__has_is_transparent_t<_Pred, _Kt>>
685 std::pair<iterator, iterator>
686 equal_range(const _Kt& __k)
687 {
688 auto __res = _Base::equal_range(__k);
689 return { { __res.first, this }, { __res.second, this } };
690 }
691#endif
692
693 std::pair<const_iterator, const_iterator>
694 equal_range(const key_type& __key) const
695 {
696 auto __res = _Base::equal_range(__key);
697 return { { __res.first, this }, { __res.second, this } };
698 }
699
700#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
701 template<typename _Kt,
702 typename = std::__has_is_transparent_t<_Hash, _Kt>,
703 typename = std::__has_is_transparent_t<_Pred, _Kt>>
704 std::pair<const_iterator, const_iterator>
705 equal_range(const _Kt& __k) const
706 {
707 auto __res = _Base::equal_range(__k);
708 return { { __res.first, this }, { __res.second, this } };
709 }
710#endif
711
712 using _Base::operator[];
713 using _Base::at;
714
715 size_type
716 erase(const key_type& __key)
717 {
718 size_type __ret(0);
719 auto __victim = _Base::find(__key);
720 if (__victim != _Base::end())
721 {
722 _M_erase(__victim);
723 __ret = 1;
724 }
725 return __ret;
726 }
727
728# ifdef __glibcxx_associative_heterogeneous_erasure
729 template <__heterogeneous_hash_key<unordered_map> _Kt>
730 size_type
731 erase(_Kt&& __key)
732 {
733 auto __victim = _Base::find(__key);
734 if (__victim != _Base::end())
735 return _M_erase(__victim), 1;
736 return 0;
737 }
738#endif
739
740 iterator
741 erase(const_iterator __it)
742 {
743 __glibcxx_check_erase(__it);
744 return { _M_erase(__it.base()), this };
745 }
746
747 _Base_iterator
748 erase(_Base_const_iterator __it)
749 {
750 __glibcxx_check_erase2(__it);
751 return _M_erase(__it);
752 }
753
754 iterator
755 erase(iterator __it)
756 {
757 __glibcxx_check_erase(__it);
758 return { _M_erase(__it.base()), this };
759 }
760
761 iterator
762 erase(const_iterator __first, const_iterator __last)
763 {
764 __glibcxx_check_erase_range(__first, __last);
765 {
766 __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
767 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
768 {
769 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
770 _M_message(__gnu_debug::__msg_valid_range)
771 ._M_iterator(__first, "first")
772 ._M_iterator(__last, "last"));
773 this->_M_invalidate(__tmp, sentry);
774 }
775 }
776
777 auto __next = _Base::erase(__first.base(), __last.base());
778 return { __next, this };
779 }
780
781 using _Base::rehash;
782 using _Base::reserve;
783
784 _Base&
785 _M_base() noexcept { return *this; }
786
787 const _Base&
788 _M_base() const noexcept { return *this; }
789
790 private:
791 const unordered_map*
792 _M_self() const noexcept
793 { return this; }
794
795 void
796 _M_check_rehashed(size_type __prev_count)
797 {
798 if (__prev_count != this->bucket_count())
799 this->_M_invalidate_all();
800 }
801
802 _Base_iterator
803 _M_erase(_Base_const_iterator __victim)
804 {
805 this->_M_invalidate(__victim);
806 return _Base::erase(__victim);
807 }
808
809#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
810 node_type
811 _M_extract(_Base_const_iterator __victim)
812 {
813 this->_M_invalidate(__victim);
814 return _Base::extract(__victim);
815 }
816#endif
817 };
818
819#if __cpp_deduction_guides >= 201606
820
821 template<typename _InputIterator,
822 typename _Hash = hash<__iter_key_t<_InputIterator>>,
823 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
824 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
825 typename = _RequireInputIter<_InputIterator>,
826 typename = _RequireNotAllocatorOrIntegral<_Hash>,
827 typename = _RequireNotAllocator<_Pred>,
828 typename = _RequireAllocator<_Allocator>>
829 unordered_map(_InputIterator, _InputIterator,
830 typename unordered_map<int, int>::size_type = {},
831 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
832 -> unordered_map<__iter_key_t<_InputIterator>,
833 __iter_val_t<_InputIterator>,
834 _Hash, _Pred, _Allocator>;
835
836 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
837 typename _Pred = equal_to<_Key>,
838 typename _Allocator = allocator<pair<const _Key, _Tp>>,
839 typename = _RequireNotAllocatorOrIntegral<_Hash>,
840 typename = _RequireNotAllocator<_Pred>,
841 typename = _RequireAllocator<_Allocator>>
842 unordered_map(initializer_list<pair<_Key, _Tp>>,
843 typename unordered_map<int, int>::size_type = {},
844 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
845 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
846
847 template<typename _InputIterator, typename _Allocator,
848 typename = _RequireInputIter<_InputIterator>,
849 typename = _RequireAllocator<_Allocator>>
850 unordered_map(_InputIterator, _InputIterator,
851 typename unordered_map<int, int>::size_type, _Allocator)
852 -> unordered_map<__iter_key_t<_InputIterator>,
853 __iter_val_t<_InputIterator>,
854 hash<__iter_key_t<_InputIterator>>,
855 equal_to<__iter_key_t<_InputIterator>>,
856 _Allocator>;
857
858 template<typename _InputIterator, typename _Allocator,
859 typename = _RequireInputIter<_InputIterator>,
860 typename = _RequireAllocator<_Allocator>>
861 unordered_map(_InputIterator, _InputIterator, _Allocator)
862 -> unordered_map<__iter_key_t<_InputIterator>,
863 __iter_val_t<_InputIterator>,
864 hash<__iter_key_t<_InputIterator>>,
865 equal_to<__iter_key_t<_InputIterator>>,
866 _Allocator>;
867
868 template<typename _InputIterator, typename _Hash, typename _Allocator,
869 typename = _RequireInputIter<_InputIterator>,
870 typename = _RequireNotAllocatorOrIntegral<_Hash>,
871 typename = _RequireAllocator<_Allocator>>
872 unordered_map(_InputIterator, _InputIterator,
873 typename unordered_map<int, int>::size_type,
874 _Hash, _Allocator)
875 -> unordered_map<__iter_key_t<_InputIterator>,
876 __iter_val_t<_InputIterator>, _Hash,
877 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
878
879 template<typename _Key, typename _Tp, typename _Allocator,
880 typename = _RequireAllocator<_Allocator>>
881 unordered_map(initializer_list<pair<_Key, _Tp>>,
882 typename unordered_map<int, int>::size_type,
883 _Allocator)
884 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
885
886 template<typename _Key, typename _Tp, typename _Allocator,
887 typename = _RequireAllocator<_Allocator>>
888 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
889 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
890
891 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
892 typename = _RequireNotAllocatorOrIntegral<_Hash>,
893 typename = _RequireAllocator<_Allocator>>
894 unordered_map(initializer_list<pair<_Key, _Tp>>,
895 typename unordered_map<int, int>::size_type,
896 _Hash, _Allocator)
897 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
898
899#if __glibcxx_containers_ranges // C++ >= 23
900 template<ranges::input_range _Rg,
901 __not_allocator_like _Hash = hash<__detail::__range_key_type<_Rg>>,
902 __not_allocator_like _Pred = equal_to<__detail::__range_key_type<_Rg>>,
903 __allocator_like _Allocator =
904 allocator<__detail::__range_to_alloc_type<_Rg>>>
905 unordered_map(from_range_t, _Rg&&, unordered_map<int, int>::size_type = {},
906 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
907 -> unordered_map<__detail::__range_key_type<_Rg>,
908 __detail::__range_mapped_type<_Rg>,
909 _Hash, _Pred, _Allocator>;
910
911 template<ranges::input_range _Rg,
912 __allocator_like _Allocator>
913 unordered_map(from_range_t, _Rg&&, unordered_map<int, int>::size_type,
914 _Allocator)
915 -> unordered_map<__detail::__range_key_type<_Rg>,
916 __detail::__range_mapped_type<_Rg>,
917 hash<__detail::__range_key_type<_Rg>>,
918 equal_to<__detail::__range_key_type<_Rg>>,
919 _Allocator>;
920
921 template<ranges::input_range _Rg,
922 __allocator_like _Allocator>
923 unordered_map(from_range_t, _Rg&&, _Allocator)
924 -> unordered_map<__detail::__range_key_type<_Rg>,
925 __detail::__range_mapped_type<_Rg>,
926 hash<__detail::__range_key_type<_Rg>>,
927 equal_to<__detail::__range_key_type<_Rg>>,
928 _Allocator>;
929
930 template<ranges::input_range _Rg,
931 __not_allocator_like _Hash,
932 __allocator_like _Allocator>
933 unordered_map(from_range_t, _Rg&&, unordered_map<int, int>::size_type,
934 _Hash, _Allocator)
935 -> unordered_map<__detail::__range_key_type<_Rg>,
936 __detail::__range_mapped_type<_Rg>,
937 _Hash, equal_to<__detail::__range_key_type<_Rg>>,
938 _Allocator>;
939#endif
940#endif
941
942 template<typename _Key, typename _Tp, typename _Hash,
943 typename _Pred, typename _Alloc>
944 inline void
945 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
946 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
947 noexcept(noexcept(__x.swap(__y)))
948 { __x.swap(__y); }
949
950 template<typename _Key, typename _Tp, typename _Hash,
951 typename _Pred, typename _Alloc>
952 inline bool
953 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
954 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
955 { return __x._M_base() == __y._M_base(); }
956
957#if __cpp_impl_three_way_comparison < 201907L
958 template<typename _Key, typename _Tp, typename _Hash,
959 typename _Pred, typename _Alloc>
960 inline bool
961 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
962 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
963 { return !(__x == __y); }
964#endif
965
966 /// Class std::unordered_multimap with safety/checking/debug instrumentation.
967 template<typename _Key, typename _Tp,
968 typename _Hash = std::hash<_Key>,
969 typename _Pred = std::equal_to<_Key>,
970 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
971 class unordered_multimap
972 : public __gnu_debug::_Safe_container<
973 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
974 __gnu_debug::_Safe_unordered_container>,
975 public _GLIBCXX_STD_C::unordered_multimap<
976 _Key, _Tp, _Hash, _Pred, _Alloc>
977 {
978 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
979 _Pred, _Alloc> _Base;
980 typedef __gnu_debug::_Safe_container<unordered_multimap,
981 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
982 typedef typename _Base::const_iterator _Base_const_iterator;
983 typedef typename _Base::iterator _Base_iterator;
984 typedef typename _Base::const_local_iterator _Base_const_local_iterator;
985 typedef typename _Base::local_iterator _Base_local_iterator;
986
987 template<typename _ItT, typename _SeqT, typename _CatT>
988 friend class ::__gnu_debug::_Safe_iterator;
989 template<typename _ItT, typename _SeqT>
990 friend class ::__gnu_debug::_Safe_local_iterator;
991
992 // Reference wrapper for base class. See PR libstdc++/90102.
993 struct _Base_ref
994 {
995 _Base_ref(const _Base& __r) : _M_ref(__r) { }
996
997 const _Base& _M_ref;
998 };
999
1000 public:
1001 typedef typename _Base::size_type size_type;
1002 typedef typename _Base::hasher hasher;
1003 typedef typename _Base::key_equal key_equal;
1004 typedef typename _Base::allocator_type allocator_type;
1005
1006 typedef typename _Base::key_type key_type;
1007 typedef typename _Base::value_type value_type;
1008 typedef typename _Base::mapped_type mapped_type;
1009
1010 typedef typename _Base::pointer pointer;
1011 typedef typename _Base::const_pointer const_pointer;
1012 typedef typename _Base::reference reference;
1013 typedef typename _Base::const_reference const_reference;
1014 typedef __gnu_debug::_Safe_iterator<
1015 _Base_iterator, unordered_multimap> iterator;
1016 typedef __gnu_debug::_Safe_iterator<
1017 _Base_const_iterator, unordered_multimap> const_iterator;
1018 typedef __gnu_debug::_Safe_local_iterator<
1019 _Base_local_iterator, unordered_multimap> local_iterator;
1020 typedef __gnu_debug::_Safe_local_iterator<
1021 _Base_const_local_iterator, unordered_multimap> const_local_iterator;
1022 typedef typename _Base::difference_type difference_type;
1023
1024 unordered_multimap() = default;
1025
1026 explicit
1027 unordered_multimap(size_type __n,
1028 const hasher& __hf = hasher(),
1029 const key_equal& __eql = key_equal(),
1030 const allocator_type& __a = allocator_type())
1031 : _Base(__n, __hf, __eql, __a) { }
1032
1033 template<typename _InputIterator>
1034 unordered_multimap(_InputIterator __first, _InputIterator __last,
1035 size_type __n = 0,
1036 const hasher& __hf = hasher(),
1037 const key_equal& __eql = key_equal(),
1038 const allocator_type& __a = allocator_type())
1039 : _Base(__gnu_debug::__base(
1040 __glibcxx_check_valid_constructor_range(__first, __last)),
1041 __gnu_debug::__base(__last), __n,
1042 __hf, __eql, __a) { }
1043
1044 unordered_multimap(const unordered_multimap&) = default;
1045
1046 unordered_multimap(_Base_ref __x)
1047 : _Base(__x._M_ref) { }
1048
1049 unordered_multimap(unordered_multimap&&) = default;
1050
1051 explicit
1052 unordered_multimap(const allocator_type& __a)
1053 : _Base(__a) { }
1054
1055 unordered_multimap(const unordered_multimap& __umap,
1056 const allocator_type& __a)
1057 : _Base(__umap, __a) { }
1058
1059 unordered_multimap(unordered_multimap&& __umap,
1060 const allocator_type& __a)
1061 noexcept( noexcept(_Base(std::move(__umap), __a)) )
1062 : _Safe(std::move(__umap), __a),
1063 _Base(std::move(__umap), __a) { }
1064
1065 unordered_multimap(initializer_list<value_type> __l,
1066 size_type __n = 0,
1067 const hasher& __hf = hasher(),
1068 const key_equal& __eql = key_equal(),
1069 const allocator_type& __a = allocator_type())
1070 : _Base(__l, __n, __hf, __eql, __a) { }
1071
1072 unordered_multimap(size_type __n, const allocator_type& __a)
1073 : unordered_multimap(__n, hasher(), key_equal(), __a)
1074 { }
1075
1076 unordered_multimap(size_type __n, const hasher& __hf,
1077 const allocator_type& __a)
1078 : unordered_multimap(__n, __hf, key_equal(), __a)
1079 { }
1080
1081 template<typename _InputIterator>
1082 unordered_multimap(_InputIterator __first, _InputIterator __last,
1083 const allocator_type& __a)
1084 : unordered_multimap(__first, __last, 0, hasher(), key_equal(), __a)
1085 { }
1086
1087 template<typename _InputIterator>
1088 unordered_multimap(_InputIterator __first, _InputIterator __last,
1089 size_type __n,
1090 const allocator_type& __a)
1091 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
1092 { }
1093
1094 template<typename _InputIterator>
1095 unordered_multimap(_InputIterator __first, _InputIterator __last,
1096 size_type __n, const hasher& __hf,
1097 const allocator_type& __a)
1098 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
1099 { }
1100
1101 unordered_multimap(initializer_list<value_type> __l,
1102 const allocator_type& __a)
1103 : unordered_multimap(__l, 0, hasher(), key_equal(), __a)
1104 { }
1105
1106 unordered_multimap(initializer_list<value_type> __l,
1107 size_type __n,
1108 const allocator_type& __a)
1109 : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
1110 { }
1111
1112 unordered_multimap(initializer_list<value_type> __l,
1113 size_type __n, const hasher& __hf,
1114 const allocator_type& __a)
1115 : unordered_multimap(__l, __n, __hf, key_equal(), __a)
1116 { }
1117
1118#if __glibcxx_containers_ranges // C++ >= 23
1119 template<__detail::__container_compatible_range<value_type> _Rg>
1120 unordered_multimap(from_range_t, _Rg&& __rg,
1121 size_type __n = 0,
1122 const hasher& __hf = hasher(),
1123 const key_equal& __eql = key_equal(),
1124 const allocator_type& __a = allocator_type())
1125 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __eql, __a)
1126 { }
1127
1128 template<__detail::__container_compatible_range<value_type> _Rg>
1129 unordered_multimap(from_range_t, _Rg&& __rg, const allocator_type& __a)
1130 : _Base(from_range, std::forward<_Rg>(__rg), __a)
1131 { }
1132
1133 template<__detail::__container_compatible_range<value_type> _Rg>
1134 unordered_multimap(from_range_t, _Rg&& __rg, size_type __n,
1135 const allocator_type& __a)
1136 : _Base(from_range, std::forward<_Rg>(__rg), __n, __a)
1137 { }
1138
1139 template<__detail::__container_compatible_range<value_type> _Rg>
1140 unordered_multimap(from_range_t, _Rg&& __rg, size_type __n,
1141 const hasher& __hf, const allocator_type& __a)
1142 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __a)
1143 { }
1144#endif
1145
1146 ~unordered_multimap() = default;
1147
1148 unordered_multimap&
1149 operator=(const unordered_multimap&) = default;
1150
1151 unordered_multimap&
1152 operator=(unordered_multimap&&) = default;
1153
1154 unordered_multimap&
1155 operator=(initializer_list<value_type> __l)
1156 {
1157 _Base::operator=(__l);
1158 this->_M_invalidate_all();
1159 return *this;
1160 }
1161
1162 using _Base::get_allocator;
1163 using _Base::empty;
1164 using _Base::size;
1165 using _Base::max_size;
1166
1167 void
1168 swap(unordered_multimap& __x)
1169 noexcept( noexcept(declval<_Base&>().swap(__x)) )
1170 {
1171 _Safe::_M_swap(__x);
1172 _Base::swap(__x);
1173 }
1174
1175 void
1176 clear() noexcept
1177 {
1178 _Base::clear();
1179 this->_M_invalidate_all();
1180 }
1181
1182 iterator
1183 begin() noexcept
1184 { return { _Base::begin(), this }; }
1185
1186 const_iterator
1187 begin() const noexcept
1188 { return { _Base::begin(), this }; }
1189
1190 iterator
1191 end() noexcept
1192 { return { _Base::end(), this }; }
1193
1194 const_iterator
1195 end() const noexcept
1196 { return { _Base::end(), this }; }
1197
1198 const_iterator
1199 cbegin() const noexcept
1200 { return { _Base::cbegin(), this }; }
1201
1202 const_iterator
1203 cend() const noexcept
1204 { return { _Base::cend(), this }; }
1205
1206 // local versions
1207 local_iterator
1208 begin(size_type __b)
1209 {
1210 __glibcxx_check_bucket_index(__b);
1211 return { _Base::begin(__b), this };
1212 }
1213
1214 local_iterator
1215 end(size_type __b)
1216 {
1217 __glibcxx_check_bucket_index(__b);
1218 return { _Base::end(__b), this };
1219 }
1220
1221 const_local_iterator
1222 begin(size_type __b) const
1223 {
1224 __glibcxx_check_bucket_index(__b);
1225 return { _Base::begin(__b), this };
1226 }
1227
1228 const_local_iterator
1229 end(size_type __b) const
1230 {
1231 __glibcxx_check_bucket_index(__b);
1232 return { _Base::end(__b), this };
1233 }
1234
1235 const_local_iterator
1236 cbegin(size_type __b) const
1237 {
1238 __glibcxx_check_bucket_index(__b);
1239 return { _Base::cbegin(__b), this };
1240 }
1241
1242 const_local_iterator
1243 cend(size_type __b) const
1244 {
1245 __glibcxx_check_bucket_index(__b);
1246 return { _Base::cend(__b), this };
1247 }
1248
1249 using _Base::bucket_count;
1250 using _Base::max_bucket_count;
1251 using _Base::bucket;
1252
1253 size_type
1254 bucket_size(size_type __b) const
1255 {
1256 __glibcxx_check_bucket_index(__b);
1257 return _Base::bucket_size(__b);
1258 }
1259
1260 float
1261 max_load_factor() const noexcept
1262 { return _Base::max_load_factor(); }
1263
1264 void
1265 max_load_factor(float __f)
1266 {
1267 __glibcxx_check_max_load_factor(__f);
1268 _Base::max_load_factor(__f);
1269 }
1270
1271 template<typename... _Args>
1272 iterator
1273 emplace(_Args&&... __args)
1274 {
1275 size_type __bucket_count = this->bucket_count();
1276 auto __it = _Base::emplace(std::forward<_Args>(__args)...);
1277 _M_check_rehashed(__bucket_count);
1278 return { __it, this };
1279 }
1280
1281 template<typename... _Args>
1282 iterator
1283 emplace_hint(const_iterator __hint, _Args&&... __args)
1284 {
1285 __glibcxx_check_insert(__hint);
1286 size_type __bucket_count = this->bucket_count();
1287 auto __it = _Base::emplace_hint(__hint.base(),
1288 std::forward<_Args>(__args)...);
1289 _M_check_rehashed(__bucket_count);
1290 return { __it, this };
1291 }
1292
1293 iterator
1294 insert(const value_type& __obj)
1295 {
1296 size_type __bucket_count = this->bucket_count();
1297 auto __it = _Base::insert(__obj);
1298 _M_check_rehashed(__bucket_count);
1299 return { __it, this };
1300 }
1301
1302 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1303 // 2354. Unnecessary copying when inserting into maps with braced-init
1304 iterator
1305 insert(value_type&& __x)
1306 {
1307 size_type __bucket_count = this->bucket_count();
1308 auto __it = _Base::insert(std::move(__x));
1309 _M_check_rehashed(__bucket_count);
1310 return { __it, this };
1311 }
1312
1313 iterator
1314 insert(const_iterator __hint, const value_type& __obj)
1315 {
1316 __glibcxx_check_insert(__hint);
1317 size_type __bucket_count = this->bucket_count();
1318 auto __it = _Base::insert(__hint.base(), __obj);
1319 _M_check_rehashed(__bucket_count);
1320 return { __it, this };
1321 }
1322
1323 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1324 // 2354. Unnecessary copying when inserting into maps with braced-init
1325 iterator
1326 insert(const_iterator __hint, value_type&& __x)
1327 {
1328 __glibcxx_check_insert(__hint);
1329 size_type __bucket_count = this->bucket_count();
1330 auto __it = _Base::insert(__hint.base(), std::move(__x));
1331 _M_check_rehashed(__bucket_count);
1332 return { __it, this };
1333 }
1334
1335 template<typename _Pair, typename = typename
1336 std::enable_if<std::is_constructible<value_type,
1337 _Pair&&>::value>::type>
1338 iterator
1339 insert(_Pair&& __obj)
1340 {
1341 size_type __bucket_count = this->bucket_count();
1342 auto __it = _Base::insert(std::forward<_Pair>(__obj));
1343 _M_check_rehashed(__bucket_count);
1344 return { __it, this };
1345 }
1346
1347 template<typename _Pair, typename = typename
1348 std::enable_if<std::is_constructible<value_type,
1349 _Pair&&>::value>::type>
1350 iterator
1351 insert(const_iterator __hint, _Pair&& __obj)
1352 {
1353 __glibcxx_check_insert(__hint);
1354 size_type __bucket_count = this->bucket_count();
1355 auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
1356 _M_check_rehashed(__bucket_count);
1357 return { __it, this };
1358 }
1359
1360 void
1361 insert(std::initializer_list<value_type> __l)
1362 { _Base::insert(__l); }
1363
1364 template<typename _InputIterator>
1365 void
1366 insert(_InputIterator __first, _InputIterator __last)
1367 {
1368 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
1369 __glibcxx_check_valid_range2(__first, __last, __dist);
1370 size_type __bucket_count = this->bucket_count();
1371
1372 if (__dist.second >= __gnu_debug::__dp_sign)
1373 _Base::insert(__gnu_debug::__unsafe(__first),
1374 __gnu_debug::__unsafe(__last));
1375 else
1376 _Base::insert(__first, __last);
1377
1378 _M_check_rehashed(__bucket_count);
1379 }
1380
1381#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1382 using node_type = typename _Base::node_type;
1383
1384 node_type
1385 extract(const_iterator __position)
1386 {
1387 __glibcxx_check_erase(__position);
1388 return _M_extract(__position.base());
1389 }
1390
1391 node_type
1392 extract(const key_type& __key)
1393 {
1394 const auto __position = _Base::find(__key);
1395 if (__position != _Base::end())
1396 return _M_extract(__position);
1397 return {};
1398 }
1399
1400# ifdef __glibcxx_associative_heterogeneous_erasure
1401 template <__heterogeneous_hash_key<unordered_multimap> _Kt>
1402 node_type
1403 extract(_Kt&& __key)
1404 {
1405 const auto __position = _Base::find(__key);
1406 if (__position != _Base::end())
1407 return _M_extract(__position);
1408 return {};
1409 }
1410#endif
1411
1412 iterator
1413 insert(node_type&& __nh)
1414 { return { _Base::insert(std::move(__nh)), this }; }
1415
1416 iterator
1417 insert(const_iterator __hint, node_type&& __nh)
1418 {
1419 __glibcxx_check_insert(__hint);
1420 return { _Base::insert(__hint.base(), std::move(__nh)), this };
1421 }
1422
1423 template<typename _H2, typename _P2>
1424 void
1425 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1426 {
1427 auto __guard
1428 = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
1429 _Base::merge(__source);
1430 }
1431
1432 template<typename _H2, typename _P2>
1433 void
1434 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1435 { merge(__source); }
1436
1437 template<typename _H2, typename _P2>
1438 void
1439 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1440 {
1441 auto __guard
1442 = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
1443 _Base::merge(__source);
1444 }
1445
1446 template<typename _H2, typename _P2>
1447 void
1448 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1449 { merge(__source); }
1450#endif // C++17
1451
1452 using _Base::hash_function;
1453 using _Base::key_eq;
1454
1455 iterator
1456 find(const key_type& __key)
1457 { return { _Base::find(__key), this }; }
1458
1459#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1460 template<typename _Kt,
1461 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1462 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1463 iterator
1464 find(const _Kt& __k)
1465 { return { _Base::find(__k), this }; }
1466#endif
1467
1468 const_iterator
1469 find(const key_type& __key) const
1470 { return { _Base::find(__key), this }; }
1471
1472#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1473 template<typename _Kt,
1474 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1475 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1476 const_iterator
1477 find(const _Kt& __k) const
1478 { return { _Base::find(__k), this }; }
1479#endif
1480
1481 using _Base::count;
1482#if __cplusplus > 201703L
1483 using _Base::contains;
1484#endif
1485
1486 std::pair<iterator, iterator>
1487 equal_range(const key_type& __key)
1488 {
1489 auto __res = _Base::equal_range(__key);
1490 return { { __res.first, this }, { __res.second, this } };
1491 }
1492
1493#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1494 template<typename _Kt,
1495 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1496 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1497 std::pair<iterator, iterator>
1498 equal_range(const _Kt& __k)
1499 {
1500 auto __res = _Base::equal_range(__k);
1501 return { { __res.first, this }, { __res.second, this } };
1502 }
1503#endif
1504
1505 std::pair<const_iterator, const_iterator>
1506 equal_range(const key_type& __key) const
1507 {
1508 auto __res = _Base::equal_range(__key);
1509 return { { __res.first, this }, { __res.second, this } };
1510 }
1511
1512#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1513 template<typename _Kt,
1514 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1515 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1516 std::pair<const_iterator, const_iterator>
1517 equal_range(const _Kt& __k) const
1518 {
1519 auto __res = _Base::equal_range(__k);
1520 return { { __res.first, this }, { __res.second, this } };
1521 }
1522#endif
1523
1524 size_type
1525 erase(const key_type& __key)
1526 {
1527 auto __victims = _Base::equal_range(__key);
1528 return _M_erase(__victims.first, __victims.second);
1529 }
1530
1531# ifdef __glibcxx_associative_heterogeneous_erasure
1532 template <__heterogeneous_hash_key<unordered_multimap> _Kt>
1533 size_type
1534 erase(_Kt&& __key)
1535 {
1536 auto __victims = _Base::equal_range(__key);
1537 return _M_erase(__victims.first, __victims.second);
1538 }
1539#endif
1540
1541 iterator
1542 erase(const_iterator __it)
1543 {
1544 __glibcxx_check_erase(__it);
1545 return { _M_erase(__it.base()), this };
1546 }
1547
1548 _Base_iterator
1549 erase(_Base_const_iterator __it)
1550 {
1551 __glibcxx_check_erase2(__it);
1552 return _M_erase(__it);
1553 }
1554
1555 iterator
1556 erase(iterator __it)
1557 {
1558 __glibcxx_check_erase(__it);
1559 return { _M_erase(__it.base()), this };
1560 }
1561
1562 iterator
1563 erase(const_iterator __first, const_iterator __last)
1564 {
1565 __glibcxx_check_erase_range(__first, __last);
1566 {
1567 __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
1568 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1569 {
1570 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1571 _M_message(__gnu_debug::__msg_valid_range)
1572 ._M_iterator(__first, "first")
1573 ._M_iterator(__last, "last"));
1574 this->_M_invalidate(__tmp, sentry);
1575 }
1576 }
1577
1578 auto __next = _Base::erase(__first.base(), __last.base());
1579 return { __next, this };
1580 }
1581
1582 using _Base::rehash;
1583 using _Base::reserve;
1584
1585 _Base&
1586 _M_base() noexcept { return *this; }
1587
1588 const _Base&
1589 _M_base() const noexcept { return *this; }
1590
1591 private:
1592 const unordered_multimap*
1593 _M_self() const noexcept
1594 { return this; }
1595
1596 void
1597 _M_check_rehashed(size_type __prev_count)
1598 {
1599 if (__prev_count != this->bucket_count())
1600 this->_M_invalidate_all();
1601 }
1602
1603 _Base_iterator
1604 _M_erase(_Base_const_iterator __victim)
1605 {
1606 this->_M_invalidate(__victim);
1607 return _Base::erase(__victim);
1608 }
1609
1610 size_type
1611 _M_erase(_Base_iterator __first, _Base_iterator __last)
1612 {
1613 size_type __ret(0);
1614 {
1615 __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
1616 for (auto __victim = __first; __victim != __last; ++__victim)
1617 {
1618 this->_M_invalidate(__victim, sentry);
1619 ++__ret;
1620 }
1621 }
1622
1623 _Base::erase(__first, __last);
1624 return __ret;
1625 }
1626
1627#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1628 node_type
1629 _M_extract(_Base_const_iterator __victim)
1630 {
1631 this->_M_invalidate(__victim);
1632 return _Base::extract(__victim);
1633 }
1634#endif
1635 };
1636
1637#if __cpp_deduction_guides >= 201606
1638
1639 template<typename _InputIterator,
1640 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1641 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1642 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1643 typename = _RequireInputIter<_InputIterator>,
1644 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1645 typename = _RequireNotAllocator<_Pred>,
1646 typename = _RequireAllocator<_Allocator>>
1647 unordered_multimap(_InputIterator, _InputIterator,
1648 unordered_multimap<int, int>::size_type = {},
1649 _Hash = _Hash(), _Pred = _Pred(),
1650 _Allocator = _Allocator())
1651 -> unordered_multimap<__iter_key_t<_InputIterator>,
1652 __iter_val_t<_InputIterator>, _Hash, _Pred,
1653 _Allocator>;
1654
1655 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
1656 typename _Pred = equal_to<_Key>,
1657 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1658 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1659 typename = _RequireNotAllocator<_Pred>,
1660 typename = _RequireAllocator<_Allocator>>
1661 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1662 unordered_multimap<int, int>::size_type = {},
1663 _Hash = _Hash(), _Pred = _Pred(),
1664 _Allocator = _Allocator())
1665 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
1666
1667 template<typename _InputIterator, typename _Allocator,
1668 typename = _RequireInputIter<_InputIterator>,
1669 typename = _RequireAllocator<_Allocator>>
1670 unordered_multimap(_InputIterator, _InputIterator,
1671 unordered_multimap<int, int>::size_type, _Allocator)
1672 -> unordered_multimap<__iter_key_t<_InputIterator>,
1673 __iter_val_t<_InputIterator>,
1674 hash<__iter_key_t<_InputIterator>>,
1675 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1676
1677 template<typename _InputIterator, typename _Allocator,
1678 typename = _RequireInputIter<_InputIterator>,
1679 typename = _RequireAllocator<_Allocator>>
1680 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
1681 -> unordered_multimap<__iter_key_t<_InputIterator>,
1682 __iter_val_t<_InputIterator>,
1683 hash<__iter_key_t<_InputIterator>>,
1684 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1685
1686 template<typename _InputIterator, typename _Hash, typename _Allocator,
1687 typename = _RequireInputIter<_InputIterator>,
1688 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1689 typename = _RequireAllocator<_Allocator>>
1690 unordered_multimap(_InputIterator, _InputIterator,
1691 unordered_multimap<int, int>::size_type, _Hash,
1692 _Allocator)
1693 -> unordered_multimap<__iter_key_t<_InputIterator>,
1694 __iter_val_t<_InputIterator>, _Hash,
1695 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1696
1697 template<typename _Key, typename _Tp, typename _Allocator,
1698 typename = _RequireAllocator<_Allocator>>
1699 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1700 unordered_multimap<int, int>::size_type,
1701 _Allocator)
1702 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1703
1704 template<typename _Key, typename _Tp, typename _Allocator,
1705 typename = _RequireAllocator<_Allocator>>
1706 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
1707 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1708
1709 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
1710 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1711 typename = _RequireAllocator<_Allocator>>
1712 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1713 unordered_multimap<int, int>::size_type,
1714 _Hash, _Allocator)
1715 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1716
1717#if __glibcxx_containers_ranges // C++ >= 23
1718 template<ranges::input_range _Rg,
1719 __not_allocator_like _Hash = hash<__detail::__range_key_type<_Rg>>,
1720 __not_allocator_like _Pred = equal_to<__detail::__range_key_type<_Rg>>,
1721 __allocator_like _Allocator =
1722 allocator<__detail::__range_to_alloc_type<_Rg>>>
1723 unordered_multimap(from_range_t, _Rg&&,
1724 unordered_multimap<int, int>::size_type = {},
1725 _Hash = _Hash(), _Pred = _Pred(),
1726 _Allocator = _Allocator())
1727 -> unordered_multimap<__detail::__range_key_type<_Rg>,
1728 __detail::__range_mapped_type<_Rg>,
1729 _Hash, _Pred, _Allocator>;
1730
1731 template<ranges::input_range _Rg,
1732 __allocator_like _Allocator>
1733 unordered_multimap(from_range_t, _Rg&&, unordered_multimap<int, int>::size_type,
1734 _Allocator)
1735 -> unordered_multimap<__detail::__range_key_type<_Rg>,
1736 __detail::__range_mapped_type<_Rg>,
1737 hash<__detail::__range_key_type<_Rg>>,
1738 equal_to<__detail::__range_key_type<_Rg>>,
1739 _Allocator>;
1740
1741 template<ranges::input_range _Rg,
1742 __allocator_like _Allocator>
1743 unordered_multimap(from_range_t, _Rg&&, _Allocator)
1744 -> unordered_multimap<__detail::__range_key_type<_Rg>,
1745 __detail::__range_mapped_type<_Rg>,
1746 hash<__detail::__range_key_type<_Rg>>,
1747 equal_to<__detail::__range_key_type<_Rg>>,
1748 _Allocator>;
1749
1750 template<ranges::input_range _Rg,
1751 __not_allocator_like _Hash,
1752 __allocator_like _Allocator>
1753 unordered_multimap(from_range_t, _Rg&&,
1754 unordered_multimap<int, int>::size_type,
1755 _Hash, _Allocator)
1756 -> unordered_multimap<__detail::__range_key_type<_Rg>,
1757 __detail::__range_mapped_type<_Rg>,
1758 _Hash, equal_to<__detail::__range_key_type<_Rg>>,
1759 _Allocator>;
1760#endif
1761#endif
1762
1763 template<typename _Key, typename _Tp, typename _Hash,
1764 typename _Pred, typename _Alloc>
1765 inline void
1766 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1767 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1768 noexcept(noexcept(__x.swap(__y)))
1769 { __x.swap(__y); }
1770
1771 template<typename _Key, typename _Tp, typename _Hash,
1772 typename _Pred, typename _Alloc>
1773 inline bool
1774 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1775 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1776 { return __x._M_base() == __y._M_base(); }
1777
1778#if __cpp_impl_three_way_comparison < 201907L
1779 template<typename _Key, typename _Tp, typename _Hash,
1780 typename _Pred, typename _Alloc>
1781 inline bool
1782 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1783 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1784 { return !(__x == __y); }
1785#endif
1786
1787} // namespace __debug
1788
1789#ifdef __glibcxx_erase_if // C++ >= 20 && HOSTED
1790_GLIBCXX_BEGIN_NAMESPACE_VERSION
1791 template<typename _Key, typename _Tp, typename _Hash, typename _CPred,
1792 typename _Alloc, typename _Predicate>
1793 inline typename __debug::unordered_map<_Key, _Tp, _Hash,
1794 _CPred, _Alloc>::size_type
1795 erase_if(__debug::unordered_map<_Key, _Tp, _Hash, _CPred, _Alloc>& __cont,
1796 _Predicate __pred)
1797 { return __detail::__erase_nodes_if(__cont, __cont._M_base(), __pred); }
1798
1799 template<typename _Key, typename _Tp, typename _Hash, typename _CPred,
1800 typename _Alloc, typename _Predicate>
1801 inline typename __debug::unordered_multimap<_Key, _Tp, _Hash,
1802 _CPred, _Alloc>::size_type
1803 erase_if(__debug::unordered_multimap<_Key, _Tp, _Hash, _CPred, _Alloc>& __cont,
1804 _Predicate __pred)
1805 { return __detail::__erase_nodes_if(__cont, __cont._M_base(), __pred); }
1806_GLIBCXX_END_NAMESPACE_VERSION
1807#endif // __glibcxx_erase_if
1808} // namespace std
1809
1810#endif // C++11
1811
1812#endif
__glibcxx_check_insert
#define __glibcxx_check_insert(_Position)
Definition macros.h:143
__glibcxx_check_erase_range
#define __glibcxx_check_erase_range(_First, _Last)
Definition macros.h:245
__glibcxx_check_erase
#define __glibcxx_check_erase(_Position)
Definition macros.h:209
std::pair::pair
pair(_T1, _T2) -> pair< _T1, _T2 >
Two pairs are equal iff their members are equal.
std::declval
auto declval() noexcept -> decltype(__declval< _Tp >(0))
Definition type_traits:2714
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition move.h:138
std::forward
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition move.h:72
std
ISO C++ entities toplevel namespace is std.
__gnu_debug::__base
constexpr _Iterator __base(_Iterator __it)
Definition helper_functions.h:320
std::__debug
GNU debug code, replaces standard behavior with debug behavior.
std::initializer_list
initializer_list
Definition initializer_list:48
std::hash
Primary class template hash.
Definition functional_hash.h:106
std::enable_if
Define a member typedef type only if a boolean constant is true.
Definition type_traits:137
std::is_constructible
is_constructible
Definition type_traits:1238
std::allocator
The standard allocator, as per C++03 [20.4.1].
Definition allocator.h:134
__gnu_debug::_Safe_iterator
Safe iterator wrapper.
Definition safe_iterator.h:133
__gnu_debug::_Safe_iterator::base
constexpr _Iterator & base() noexcept
Return the underlying iterator.
Definition safe_iterator.h:433
std::equal_to
One of the comparison functors.
Definition stl_function.h:374
std::pair
Struct holding two objects of arbitrary type.
Definition stl_pair.h:304
std::unordered_multimap
A standard container composed of equivalent keys (possibly containing multiple of each key value) tha...
Definition unordered_map.h:1396
std::unordered_multimap::size_type
_Hashtable::size_type size_type
Iterator-related typedefs.
Definition unordered_map.h:1422
std::unordered_map
A standard container composed of unique keys (containing at most one of each key value) that associat...
Definition unordered_map.h:113
std::unordered_map::size_type
_Hashtable::size_type size_type
Iterator-related typedefs.
Definition unordered_map.h:139
__gnu_debug::_Safe_container
Safe class dealing with some allocator dependent operations.
Definition safe_container.h:43
__gnu_debug::_Safe_unordered_container
Base class for constructing a safe unordered container type that tracks iterators that reference it.
Definition safe_unordered_container.h:59
std::__debug::unordered_map
Class std::unordered_map with safety/checking/debug instrumentation.
Definition debug/unordered_map:70
std::__debug::unordered_multimap
Class std::unordered_multimap with safety/checking/debug instrumentation.
Definition debug/unordered_map:977
__gnu_cxx::__scoped_lock
Scoped lock idiom.
Definition concurrence.h:234