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 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
766 {
767 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
768 _M_message(__gnu_debug::__msg_valid_range)
769 ._M_iterator(__first, "first")
770 ._M_iterator(__last, "last"));
771 _M_invalidate(__tmp);
772 }
773
774 size_type __bucket_count = this->bucket_count();
775 auto __next = _Base::erase(__first.base(), __last.base());
776 _M_check_rehashed(__bucket_count);
777 return { __next, this };
778 }
779
780 using _Base::rehash;
781 using _Base::reserve;
782
783 _Base&
784 _M_base() noexcept { return *this; }
785
786 const _Base&
787 _M_base() const noexcept { return *this; }
788
789 private:
790 void
791 _M_check_rehashed(size_type __prev_count)
792 {
793 if (__prev_count != this->bucket_count())
794 this->_M_invalidate_all();
795 }
796
797 void
798 _M_invalidate(_Base_const_iterator __victim)
799 {
800 this->_M_invalidate_if(
801 [__victim](_Base_const_iterator __it) { return __it == __victim; });
802 this->_M_invalidate_local_if(
803 [__victim](_Base_const_local_iterator __it)
804 { return __it == __victim; });
805 }
806
807 _Base_iterator
808 _M_erase(_Base_const_iterator __victim)
809 {
810 _M_invalidate(__victim);
811 size_type __bucket_count = this->bucket_count();
812 _Base_iterator __next = _Base::erase(__victim);
813 _M_check_rehashed(__bucket_count);
814 return __next;
815 }
816
817#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
818 node_type
819 _M_extract(_Base_const_iterator __victim)
820 {
821 _M_invalidate(__victim);
822 return _Base::extract(__victim);
823 }
824#endif
825 };
826
827#if __cpp_deduction_guides >= 201606
828
829 template<typename _InputIterator,
830 typename _Hash = hash<__iter_key_t<_InputIterator>>,
831 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
832 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
833 typename = _RequireInputIter<_InputIterator>,
834 typename = _RequireNotAllocatorOrIntegral<_Hash>,
835 typename = _RequireNotAllocator<_Pred>,
836 typename = _RequireAllocator<_Allocator>>
837 unordered_map(_InputIterator, _InputIterator,
838 typename unordered_map<int, int>::size_type = {},
839 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
840 -> unordered_map<__iter_key_t<_InputIterator>,
841 __iter_val_t<_InputIterator>,
842 _Hash, _Pred, _Allocator>;
843
844 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
845 typename _Pred = equal_to<_Key>,
846 typename _Allocator = allocator<pair<const _Key, _Tp>>,
847 typename = _RequireNotAllocatorOrIntegral<_Hash>,
848 typename = _RequireNotAllocator<_Pred>,
849 typename = _RequireAllocator<_Allocator>>
850 unordered_map(initializer_list<pair<_Key, _Tp>>,
851 typename unordered_map<int, int>::size_type = {},
852 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
853 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
854
855 template<typename _InputIterator, typename _Allocator,
856 typename = _RequireInputIter<_InputIterator>,
857 typename = _RequireAllocator<_Allocator>>
858 unordered_map(_InputIterator, _InputIterator,
859 typename unordered_map<int, int>::size_type, _Allocator)
860 -> unordered_map<__iter_key_t<_InputIterator>,
861 __iter_val_t<_InputIterator>,
862 hash<__iter_key_t<_InputIterator>>,
863 equal_to<__iter_key_t<_InputIterator>>,
864 _Allocator>;
865
866 template<typename _InputIterator, typename _Allocator,
867 typename = _RequireInputIter<_InputIterator>,
868 typename = _RequireAllocator<_Allocator>>
869 unordered_map(_InputIterator, _InputIterator, _Allocator)
870 -> unordered_map<__iter_key_t<_InputIterator>,
871 __iter_val_t<_InputIterator>,
872 hash<__iter_key_t<_InputIterator>>,
873 equal_to<__iter_key_t<_InputIterator>>,
874 _Allocator>;
875
876 template<typename _InputIterator, typename _Hash, typename _Allocator,
877 typename = _RequireInputIter<_InputIterator>,
878 typename = _RequireNotAllocatorOrIntegral<_Hash>,
879 typename = _RequireAllocator<_Allocator>>
880 unordered_map(_InputIterator, _InputIterator,
881 typename unordered_map<int, int>::size_type,
882 _Hash, _Allocator)
883 -> unordered_map<__iter_key_t<_InputIterator>,
884 __iter_val_t<_InputIterator>, _Hash,
885 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
886
887 template<typename _Key, typename _Tp, typename _Allocator,
888 typename = _RequireAllocator<_Allocator>>
889 unordered_map(initializer_list<pair<_Key, _Tp>>,
890 typename unordered_map<int, int>::size_type,
891 _Allocator)
892 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
893
894 template<typename _Key, typename _Tp, typename _Allocator,
895 typename = _RequireAllocator<_Allocator>>
896 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
897 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
898
899 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
900 typename = _RequireNotAllocatorOrIntegral<_Hash>,
901 typename = _RequireAllocator<_Allocator>>
902 unordered_map(initializer_list<pair<_Key, _Tp>>,
903 typename unordered_map<int, int>::size_type,
904 _Hash, _Allocator)
905 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
906
907#if __glibcxx_containers_ranges // C++ >= 23
908 template<ranges::input_range _Rg,
909 __not_allocator_like _Hash = hash<__detail::__range_key_type<_Rg>>,
910 __not_allocator_like _Pred = equal_to<__detail::__range_key_type<_Rg>>,
911 __allocator_like _Allocator =
912 allocator<__detail::__range_to_alloc_type<_Rg>>>
913 unordered_map(from_range_t, _Rg&&, unordered_map<int, int>::size_type = {},
914 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
915 -> unordered_map<__detail::__range_key_type<_Rg>,
916 __detail::__range_mapped_type<_Rg>,
917 _Hash, _Pred, _Allocator>;
918
919 template<ranges::input_range _Rg,
920 __allocator_like _Allocator>
921 unordered_map(from_range_t, _Rg&&, unordered_map<int, int>::size_type,
922 _Allocator)
923 -> unordered_map<__detail::__range_key_type<_Rg>,
924 __detail::__range_mapped_type<_Rg>,
925 hash<__detail::__range_key_type<_Rg>>,
926 equal_to<__detail::__range_key_type<_Rg>>,
927 _Allocator>;
928
929 template<ranges::input_range _Rg,
930 __allocator_like _Allocator>
931 unordered_map(from_range_t, _Rg&&, _Allocator)
932 -> unordered_map<__detail::__range_key_type<_Rg>,
933 __detail::__range_mapped_type<_Rg>,
934 hash<__detail::__range_key_type<_Rg>>,
935 equal_to<__detail::__range_key_type<_Rg>>,
936 _Allocator>;
937
938 template<ranges::input_range _Rg,
939 __not_allocator_like _Hash,
940 __allocator_like _Allocator>
941 unordered_map(from_range_t, _Rg&&, unordered_map<int, int>::size_type,
942 _Hash, _Allocator)
943 -> unordered_map<__detail::__range_key_type<_Rg>,
944 __detail::__range_mapped_type<_Rg>,
945 _Hash, equal_to<__detail::__range_key_type<_Rg>>,
946 _Allocator>;
947#endif
948#endif
949
950 template<typename _Key, typename _Tp, typename _Hash,
951 typename _Pred, typename _Alloc>
952 inline void
953 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
954 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
955 noexcept(noexcept(__x.swap(__y)))
956 { __x.swap(__y); }
957
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._M_base() == __y._M_base(); }
964
965#if __cpp_impl_three_way_comparison < 201907L
966 template<typename _Key, typename _Tp, typename _Hash,
967 typename _Pred, typename _Alloc>
968 inline bool
969 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
970 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
971 { return !(__x == __y); }
972#endif
973
974 /// Class std::unordered_multimap with safety/checking/debug instrumentation.
975 template<typename _Key, typename _Tp,
976 typename _Hash = std::hash<_Key>,
977 typename _Pred = std::equal_to<_Key>,
978 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
979 class unordered_multimap
980 : public __gnu_debug::_Safe_container<
981 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
982 __gnu_debug::_Safe_unordered_container>,
983 public _GLIBCXX_STD_C::unordered_multimap<
984 _Key, _Tp, _Hash, _Pred, _Alloc>
985 {
986 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
987 _Pred, _Alloc> _Base;
988 typedef __gnu_debug::_Safe_container<unordered_multimap,
989 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
990 typedef typename _Base::const_iterator _Base_const_iterator;
991 typedef typename _Base::iterator _Base_iterator;
992 typedef typename _Base::const_local_iterator _Base_const_local_iterator;
993 typedef typename _Base::local_iterator _Base_local_iterator;
994
995 template<typename _ItT, typename _SeqT, typename _CatT>
996 friend class ::__gnu_debug::_Safe_iterator;
997 template<typename _ItT, typename _SeqT>
998 friend class ::__gnu_debug::_Safe_local_iterator;
999
1000 // Reference wrapper for base class. See PR libstdc++/90102.
1001 struct _Base_ref
1002 {
1003 _Base_ref(const _Base& __r) : _M_ref(__r) { }
1004
1005 const _Base& _M_ref;
1006 };
1007
1008 public:
1009 typedef typename _Base::size_type size_type;
1010 typedef typename _Base::hasher hasher;
1011 typedef typename _Base::key_equal key_equal;
1012 typedef typename _Base::allocator_type allocator_type;
1013
1014 typedef typename _Base::key_type key_type;
1015 typedef typename _Base::value_type value_type;
1016 typedef typename _Base::mapped_type mapped_type;
1017
1018 typedef typename _Base::pointer pointer;
1019 typedef typename _Base::const_pointer const_pointer;
1020 typedef typename _Base::reference reference;
1021 typedef typename _Base::const_reference const_reference;
1022 typedef __gnu_debug::_Safe_iterator<
1023 _Base_iterator, unordered_multimap> iterator;
1024 typedef __gnu_debug::_Safe_iterator<
1025 _Base_const_iterator, unordered_multimap> const_iterator;
1026 typedef __gnu_debug::_Safe_local_iterator<
1027 _Base_local_iterator, unordered_multimap> local_iterator;
1028 typedef __gnu_debug::_Safe_local_iterator<
1029 _Base_const_local_iterator, unordered_multimap> const_local_iterator;
1030 typedef typename _Base::difference_type difference_type;
1031
1032 unordered_multimap() = default;
1033
1034 explicit
1035 unordered_multimap(size_type __n,
1036 const hasher& __hf = hasher(),
1037 const key_equal& __eql = key_equal(),
1038 const allocator_type& __a = allocator_type())
1039 : _Base(__n, __hf, __eql, __a) { }
1040
1041 template<typename _InputIterator>
1042 unordered_multimap(_InputIterator __first, _InputIterator __last,
1043 size_type __n = 0,
1044 const hasher& __hf = hasher(),
1045 const key_equal& __eql = key_equal(),
1046 const allocator_type& __a = allocator_type())
1047 : _Base(__gnu_debug::__base(
1048 __glibcxx_check_valid_constructor_range(__first, __last)),
1049 __gnu_debug::__base(__last), __n,
1050 __hf, __eql, __a) { }
1051
1052 unordered_multimap(const unordered_multimap&) = default;
1053
1054 unordered_multimap(_Base_ref __x)
1055 : _Base(__x._M_ref) { }
1056
1057 unordered_multimap(unordered_multimap&&) = default;
1058
1059 explicit
1060 unordered_multimap(const allocator_type& __a)
1061 : _Base(__a) { }
1062
1063 unordered_multimap(const unordered_multimap& __umap,
1064 const allocator_type& __a)
1065 : _Base(__umap, __a) { }
1066
1067 unordered_multimap(unordered_multimap&& __umap,
1068 const allocator_type& __a)
1069 noexcept( noexcept(_Base(std::move(__umap), __a)) )
1070 : _Safe(std::move(__umap), __a),
1071 _Base(std::move(__umap), __a) { }
1072
1073 unordered_multimap(initializer_list<value_type> __l,
1074 size_type __n = 0,
1075 const hasher& __hf = hasher(),
1076 const key_equal& __eql = key_equal(),
1077 const allocator_type& __a = allocator_type())
1078 : _Base(__l, __n, __hf, __eql, __a) { }
1079
1080 unordered_multimap(size_type __n, const allocator_type& __a)
1081 : unordered_multimap(__n, hasher(), key_equal(), __a)
1082 { }
1083
1084 unordered_multimap(size_type __n, const hasher& __hf,
1085 const allocator_type& __a)
1086 : unordered_multimap(__n, __hf, key_equal(), __a)
1087 { }
1088
1089 template<typename _InputIterator>
1090 unordered_multimap(_InputIterator __first, _InputIterator __last,
1091 const allocator_type& __a)
1092 : unordered_multimap(__first, __last, 0, hasher(), key_equal(), __a)
1093 { }
1094
1095 template<typename _InputIterator>
1096 unordered_multimap(_InputIterator __first, _InputIterator __last,
1097 size_type __n,
1098 const allocator_type& __a)
1099 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
1100 { }
1101
1102 template<typename _InputIterator>
1103 unordered_multimap(_InputIterator __first, _InputIterator __last,
1104 size_type __n, const hasher& __hf,
1105 const allocator_type& __a)
1106 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
1107 { }
1108
1109 unordered_multimap(initializer_list<value_type> __l,
1110 const allocator_type& __a)
1111 : unordered_multimap(__l, 0, hasher(), key_equal(), __a)
1112 { }
1113
1114 unordered_multimap(initializer_list<value_type> __l,
1115 size_type __n,
1116 const allocator_type& __a)
1117 : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
1118 { }
1119
1120 unordered_multimap(initializer_list<value_type> __l,
1121 size_type __n, const hasher& __hf,
1122 const allocator_type& __a)
1123 : unordered_multimap(__l, __n, __hf, key_equal(), __a)
1124 { }
1125
1126#if __glibcxx_containers_ranges // C++ >= 23
1127 template<__detail::__container_compatible_range<value_type> _Rg>
1128 unordered_multimap(from_range_t, _Rg&& __rg,
1129 size_type __n = 0,
1130 const hasher& __hf = hasher(),
1131 const key_equal& __eql = key_equal(),
1132 const allocator_type& __a = allocator_type())
1133 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __eql, __a)
1134 { }
1135
1136 template<__detail::__container_compatible_range<value_type> _Rg>
1137 unordered_multimap(from_range_t, _Rg&& __rg, const allocator_type& __a)
1138 : _Base(from_range, std::forward<_Rg>(__rg), __a)
1139 { }
1140
1141 template<__detail::__container_compatible_range<value_type> _Rg>
1142 unordered_multimap(from_range_t, _Rg&& __rg, size_type __n,
1143 const allocator_type& __a)
1144 : _Base(from_range, std::forward<_Rg>(__rg), __n, __a)
1145 { }
1146
1147 template<__detail::__container_compatible_range<value_type> _Rg>
1148 unordered_multimap(from_range_t, _Rg&& __rg, size_type __n,
1149 const hasher& __hf, const allocator_type& __a)
1150 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __a)
1151 { }
1152#endif
1153
1154 ~unordered_multimap() = default;
1155
1156 unordered_multimap&
1157 operator=(const unordered_multimap&) = default;
1158
1159 unordered_multimap&
1160 operator=(unordered_multimap&&) = default;
1161
1162 unordered_multimap&
1163 operator=(initializer_list<value_type> __l)
1164 {
1165 _Base::operator=(__l);
1166 this->_M_invalidate_all();
1167 return *this;
1168 }
1169
1170 using _Base::get_allocator;
1171 using _Base::empty;
1172 using _Base::size;
1173 using _Base::max_size;
1174
1175 void
1176 swap(unordered_multimap& __x)
1177 noexcept( noexcept(declval<_Base&>().swap(__x)) )
1178 {
1179 _Safe::_M_swap(__x);
1180 _Base::swap(__x);
1181 }
1182
1183 void
1184 clear() noexcept
1185 {
1186 _Base::clear();
1187 this->_M_invalidate_all();
1188 }
1189
1190 iterator
1191 begin() noexcept
1192 { return { _Base::begin(), this }; }
1193
1194 const_iterator
1195 begin() const noexcept
1196 { return { _Base::begin(), this }; }
1197
1198 iterator
1199 end() noexcept
1200 { return { _Base::end(), this }; }
1201
1202 const_iterator
1203 end() const noexcept
1204 { return { _Base::end(), this }; }
1205
1206 const_iterator
1207 cbegin() const noexcept
1208 { return { _Base::cbegin(), this }; }
1209
1210 const_iterator
1211 cend() const noexcept
1212 { return { _Base::cend(), this }; }
1213
1214 // local versions
1215 local_iterator
1216 begin(size_type __b)
1217 {
1218 __glibcxx_check_bucket_index(__b);
1219 return { _Base::begin(__b), this };
1220 }
1221
1222 local_iterator
1223 end(size_type __b)
1224 {
1225 __glibcxx_check_bucket_index(__b);
1226 return { _Base::end(__b), this };
1227 }
1228
1229 const_local_iterator
1230 begin(size_type __b) const
1231 {
1232 __glibcxx_check_bucket_index(__b);
1233 return { _Base::begin(__b), this };
1234 }
1235
1236 const_local_iterator
1237 end(size_type __b) const
1238 {
1239 __glibcxx_check_bucket_index(__b);
1240 return { _Base::end(__b), this };
1241 }
1242
1243 const_local_iterator
1244 cbegin(size_type __b) const
1245 {
1246 __glibcxx_check_bucket_index(__b);
1247 return { _Base::cbegin(__b), this };
1248 }
1249
1250 const_local_iterator
1251 cend(size_type __b) const
1252 {
1253 __glibcxx_check_bucket_index(__b);
1254 return { _Base::cend(__b), this };
1255 }
1256
1257 using _Base::bucket_count;
1258 using _Base::max_bucket_count;
1259 using _Base::bucket;
1260
1261 size_type
1262 bucket_size(size_type __b) const
1263 {
1264 __glibcxx_check_bucket_index(__b);
1265 return _Base::bucket_size(__b);
1266 }
1267
1268 float
1269 max_load_factor() const noexcept
1270 { return _Base::max_load_factor(); }
1271
1272 void
1273 max_load_factor(float __f)
1274 {
1275 __glibcxx_check_max_load_factor(__f);
1276 _Base::max_load_factor(__f);
1277 }
1278
1279 template<typename... _Args>
1280 iterator
1281 emplace(_Args&&... __args)
1282 {
1283 size_type __bucket_count = this->bucket_count();
1284 auto __it = _Base::emplace(std::forward<_Args>(__args)...);
1285 _M_check_rehashed(__bucket_count);
1286 return { __it, this };
1287 }
1288
1289 template<typename... _Args>
1290 iterator
1291 emplace_hint(const_iterator __hint, _Args&&... __args)
1292 {
1293 __glibcxx_check_insert(__hint);
1294 size_type __bucket_count = this->bucket_count();
1295 auto __it = _Base::emplace_hint(__hint.base(),
1296 std::forward<_Args>(__args)...);
1297 _M_check_rehashed(__bucket_count);
1298 return { __it, this };
1299 }
1300
1301 iterator
1302 insert(const value_type& __obj)
1303 {
1304 size_type __bucket_count = this->bucket_count();
1305 auto __it = _Base::insert(__obj);
1306 _M_check_rehashed(__bucket_count);
1307 return { __it, this };
1308 }
1309
1310 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1311 // 2354. Unnecessary copying when inserting into maps with braced-init
1312 iterator
1313 insert(value_type&& __x)
1314 {
1315 size_type __bucket_count = this->bucket_count();
1316 auto __it = _Base::insert(std::move(__x));
1317 _M_check_rehashed(__bucket_count);
1318 return { __it, this };
1319 }
1320
1321 iterator
1322 insert(const_iterator __hint, const value_type& __obj)
1323 {
1324 __glibcxx_check_insert(__hint);
1325 size_type __bucket_count = this->bucket_count();
1326 auto __it = _Base::insert(__hint.base(), __obj);
1327 _M_check_rehashed(__bucket_count);
1328 return { __it, this };
1329 }
1330
1331 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1332 // 2354. Unnecessary copying when inserting into maps with braced-init
1333 iterator
1334 insert(const_iterator __hint, value_type&& __x)
1335 {
1336 __glibcxx_check_insert(__hint);
1337 size_type __bucket_count = this->bucket_count();
1338 auto __it = _Base::insert(__hint.base(), std::move(__x));
1339 _M_check_rehashed(__bucket_count);
1340 return { __it, this };
1341 }
1342
1343 template<typename _Pair, typename = typename
1344 std::enable_if<std::is_constructible<value_type,
1345 _Pair&&>::value>::type>
1346 iterator
1347 insert(_Pair&& __obj)
1348 {
1349 size_type __bucket_count = this->bucket_count();
1350 auto __it = _Base::insert(std::forward<_Pair>(__obj));
1351 _M_check_rehashed(__bucket_count);
1352 return { __it, this };
1353 }
1354
1355 template<typename _Pair, typename = typename
1356 std::enable_if<std::is_constructible<value_type,
1357 _Pair&&>::value>::type>
1358 iterator
1359 insert(const_iterator __hint, _Pair&& __obj)
1360 {
1361 __glibcxx_check_insert(__hint);
1362 size_type __bucket_count = this->bucket_count();
1363 auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
1364 _M_check_rehashed(__bucket_count);
1365 return { __it, this };
1366 }
1367
1368 void
1369 insert(std::initializer_list<value_type> __l)
1370 { _Base::insert(__l); }
1371
1372 template<typename _InputIterator>
1373 void
1374 insert(_InputIterator __first, _InputIterator __last)
1375 {
1376 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
1377 __glibcxx_check_valid_range2(__first, __last, __dist);
1378 size_type __bucket_count = this->bucket_count();
1379
1380 if (__dist.second >= __gnu_debug::__dp_sign)
1381 _Base::insert(__gnu_debug::__unsafe(__first),
1382 __gnu_debug::__unsafe(__last));
1383 else
1384 _Base::insert(__first, __last);
1385
1386 _M_check_rehashed(__bucket_count);
1387 }
1388
1389#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1390 using node_type = typename _Base::node_type;
1391
1392 node_type
1393 extract(const_iterator __position)
1394 {
1395 __glibcxx_check_erase(__position);
1396 return _M_extract(__position.base());
1397 }
1398
1399 node_type
1400 extract(const key_type& __key)
1401 {
1402 const auto __position = _Base::find(__key);
1403 if (__position != _Base::end())
1404 return _M_extract(__position);
1405 return {};
1406 }
1407
1408# ifdef __glibcxx_associative_heterogeneous_erasure
1409 template <__heterogeneous_hash_key<unordered_multimap> _Kt>
1410 node_type
1411 extract(_Kt&& __key)
1412 {
1413 const auto __position = _Base::find(__key);
1414 if (__position != _Base::end())
1415 return _M_extract(__position);
1416 return {};
1417 }
1418#endif
1419
1420 iterator
1421 insert(node_type&& __nh)
1422 { return { _Base::insert(std::move(__nh)), this }; }
1423
1424 iterator
1425 insert(const_iterator __hint, node_type&& __nh)
1426 {
1427 __glibcxx_check_insert(__hint);
1428 return { _Base::insert(__hint.base(), std::move(__nh)), this };
1429 }
1430
1431 template<typename _H2, typename _P2>
1432 void
1433 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1434 {
1435 auto __guard
1436 = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
1437 _Base::merge(__source);
1438 }
1439
1440 template<typename _H2, typename _P2>
1441 void
1442 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1443 { merge(__source); }
1444
1445 template<typename _H2, typename _P2>
1446 void
1447 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1448 {
1449 auto __guard
1450 = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
1451 _Base::merge(__source);
1452 }
1453
1454 template<typename _H2, typename _P2>
1455 void
1456 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1457 { merge(__source); }
1458#endif // C++17
1459
1460 using _Base::hash_function;
1461 using _Base::key_eq;
1462
1463 iterator
1464 find(const key_type& __key)
1465 { return { _Base::find(__key), this }; }
1466
1467#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1468 template<typename _Kt,
1469 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1470 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1471 iterator
1472 find(const _Kt& __k)
1473 { return { _Base::find(__k), this }; }
1474#endif
1475
1476 const_iterator
1477 find(const key_type& __key) const
1478 { return { _Base::find(__key), this }; }
1479
1480#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1481 template<typename _Kt,
1482 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1483 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1484 const_iterator
1485 find(const _Kt& __k) const
1486 { return { _Base::find(__k), this }; }
1487#endif
1488
1489 using _Base::count;
1490#if __cplusplus > 201703L
1491 using _Base::contains;
1492#endif
1493
1494 std::pair<iterator, iterator>
1495 equal_range(const key_type& __key)
1496 {
1497 auto __res = _Base::equal_range(__key);
1498 return { { __res.first, this }, { __res.second, this } };
1499 }
1500
1501#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1502 template<typename _Kt,
1503 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1504 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1505 std::pair<iterator, iterator>
1506 equal_range(const _Kt& __k)
1507 {
1508 auto __res = _Base::equal_range(__k);
1509 return { { __res.first, this }, { __res.second, this } };
1510 }
1511#endif
1512
1513 std::pair<const_iterator, const_iterator>
1514 equal_range(const key_type& __key) const
1515 {
1516 auto __res = _Base::equal_range(__key);
1517 return { { __res.first, this }, { __res.second, this } };
1518 }
1519
1520#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1521 template<typename _Kt,
1522 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1523 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1524 std::pair<const_iterator, const_iterator>
1525 equal_range(const _Kt& __k) const
1526 {
1527 auto __res = _Base::equal_range(__k);
1528 return { { __res.first, this }, { __res.second, this } };
1529 }
1530#endif
1531
1532 size_type
1533 erase(const key_type& __key)
1534 {
1535 size_type __ret(0);
1536 size_type __bucket_count = this->bucket_count();
1537 auto __pair = _Base::equal_range(__key);
1538 for (auto __victim = __pair.first; __victim != __pair.second;)
1539 {
1540 _M_invalidate(__victim);
1541 __victim = _Base::erase(__victim);
1542 ++__ret;
1543 }
1544
1545 _M_check_rehashed(__bucket_count);
1546 return __ret;
1547 }
1548
1549# ifdef __glibcxx_associative_heterogeneous_erasure
1550 template <__heterogeneous_hash_key<unordered_multimap> _Kt>
1551 size_type
1552 erase(_Kt&& __key)
1553 {
1554 size_type __count(0);
1555 auto __victims = _Base::equal_range(__key);
1556 for (auto __victim = __victims.first; __victim != __victims.second;)
1557 {
1558 _M_invalidate(__victim);
1559 __victim = _Base::erase(__victim);
1560 ++__count;
1561 }
1562 return __count;
1563 }
1564#endif
1565
1566 iterator
1567 erase(const_iterator __it)
1568 {
1569 __glibcxx_check_erase(__it);
1570 return { _M_erase(__it.base()), this };
1571 }
1572
1573 _Base_iterator
1574 erase(_Base_const_iterator __it)
1575 {
1576 __glibcxx_check_erase2(__it);
1577 return _M_erase(__it);
1578 }
1579
1580 iterator
1581 erase(iterator __it)
1582 {
1583 __glibcxx_check_erase(__it);
1584 return { _M_erase(__it.base()), this };
1585 }
1586
1587 iterator
1588 erase(const_iterator __first, const_iterator __last)
1589 {
1590 __glibcxx_check_erase_range(__first, __last);
1591 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1592 {
1593 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1594 _M_message(__gnu_debug::__msg_valid_range)
1595 ._M_iterator(__first, "first")
1596 ._M_iterator(__last, "last"));
1597 _M_invalidate(__tmp);
1598 }
1599
1600 size_type __bucket_count = this->bucket_count();
1601 auto __next = _Base::erase(__first.base(), __last.base());
1602 _M_check_rehashed(__bucket_count);
1603 return { __next, this };
1604 }
1605
1606 using _Base::rehash;
1607 using _Base::reserve;
1608
1609 _Base&
1610 _M_base() noexcept { return *this; }
1611
1612 const _Base&
1613 _M_base() const noexcept { return *this; }
1614
1615 private:
1616 void
1617 _M_check_rehashed(size_type __prev_count)
1618 {
1619 if (__prev_count != this->bucket_count())
1620 this->_M_invalidate_all();
1621 }
1622
1623 void
1624 _M_invalidate(_Base_const_iterator __victim)
1625 {
1626 this->_M_invalidate_if(
1627 [__victim](_Base_const_iterator __it) { return __it == __victim; });
1628 this->_M_invalidate_local_if(
1629 [__victim](_Base_const_local_iterator __it)
1630 { return __it == __victim; });
1631 }
1632
1633 _Base_iterator
1634 _M_erase(_Base_const_iterator __victim)
1635 {
1636 _M_invalidate(__victim);
1637 size_type __bucket_count = this->bucket_count();
1638 _Base_iterator __next = _Base::erase(__victim);
1639 _M_check_rehashed(__bucket_count);
1640 return __next;
1641 }
1642
1643#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1644 node_type
1645 _M_extract(_Base_const_iterator __victim)
1646 {
1647 _M_invalidate(__victim);
1648 return _Base::extract(__victim);
1649 }
1650#endif
1651 };
1652
1653#if __cpp_deduction_guides >= 201606
1654
1655 template<typename _InputIterator,
1656 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1657 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1658 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1659 typename = _RequireInputIter<_InputIterator>,
1660 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1661 typename = _RequireNotAllocator<_Pred>,
1662 typename = _RequireAllocator<_Allocator>>
1663 unordered_multimap(_InputIterator, _InputIterator,
1664 unordered_multimap<int, int>::size_type = {},
1665 _Hash = _Hash(), _Pred = _Pred(),
1666 _Allocator = _Allocator())
1667 -> unordered_multimap<__iter_key_t<_InputIterator>,
1668 __iter_val_t<_InputIterator>, _Hash, _Pred,
1669 _Allocator>;
1670
1671 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
1672 typename _Pred = equal_to<_Key>,
1673 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1674 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1675 typename = _RequireNotAllocator<_Pred>,
1676 typename = _RequireAllocator<_Allocator>>
1677 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1678 unordered_multimap<int, int>::size_type = {},
1679 _Hash = _Hash(), _Pred = _Pred(),
1680 _Allocator = _Allocator())
1681 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
1682
1683 template<typename _InputIterator, typename _Allocator,
1684 typename = _RequireInputIter<_InputIterator>,
1685 typename = _RequireAllocator<_Allocator>>
1686 unordered_multimap(_InputIterator, _InputIterator,
1687 unordered_multimap<int, int>::size_type, _Allocator)
1688 -> unordered_multimap<__iter_key_t<_InputIterator>,
1689 __iter_val_t<_InputIterator>,
1690 hash<__iter_key_t<_InputIterator>>,
1691 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1692
1693 template<typename _InputIterator, typename _Allocator,
1694 typename = _RequireInputIter<_InputIterator>,
1695 typename = _RequireAllocator<_Allocator>>
1696 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
1697 -> unordered_multimap<__iter_key_t<_InputIterator>,
1698 __iter_val_t<_InputIterator>,
1699 hash<__iter_key_t<_InputIterator>>,
1700 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1701
1702 template<typename _InputIterator, typename _Hash, typename _Allocator,
1703 typename = _RequireInputIter<_InputIterator>,
1704 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1705 typename = _RequireAllocator<_Allocator>>
1706 unordered_multimap(_InputIterator, _InputIterator,
1707 unordered_multimap<int, int>::size_type, _Hash,
1708 _Allocator)
1709 -> unordered_multimap<__iter_key_t<_InputIterator>,
1710 __iter_val_t<_InputIterator>, _Hash,
1711 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1712
1713 template<typename _Key, typename _Tp, typename _Allocator,
1714 typename = _RequireAllocator<_Allocator>>
1715 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1716 unordered_multimap<int, int>::size_type,
1717 _Allocator)
1718 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1719
1720 template<typename _Key, typename _Tp, typename _Allocator,
1721 typename = _RequireAllocator<_Allocator>>
1722 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
1723 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1724
1725 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
1726 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1727 typename = _RequireAllocator<_Allocator>>
1728 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1729 unordered_multimap<int, int>::size_type,
1730 _Hash, _Allocator)
1731 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1732
1733#if __glibcxx_containers_ranges // C++ >= 23
1734 template<ranges::input_range _Rg,
1735 __not_allocator_like _Hash = hash<__detail::__range_key_type<_Rg>>,
1736 __not_allocator_like _Pred = equal_to<__detail::__range_key_type<_Rg>>,
1737 __allocator_like _Allocator =
1738 allocator<__detail::__range_to_alloc_type<_Rg>>>
1739 unordered_multimap(from_range_t, _Rg&&,
1740 unordered_multimap<int, int>::size_type = {},
1741 _Hash = _Hash(), _Pred = _Pred(),
1742 _Allocator = _Allocator())
1743 -> unordered_multimap<__detail::__range_key_type<_Rg>,
1744 __detail::__range_mapped_type<_Rg>,
1745 _Hash, _Pred, _Allocator>;
1746
1747 template<ranges::input_range _Rg,
1748 __allocator_like _Allocator>
1749 unordered_multimap(from_range_t, _Rg&&, unordered_multimap<int, int>::size_type,
1750 _Allocator)
1751 -> unordered_multimap<__detail::__range_key_type<_Rg>,
1752 __detail::__range_mapped_type<_Rg>,
1753 hash<__detail::__range_key_type<_Rg>>,
1754 equal_to<__detail::__range_key_type<_Rg>>,
1755 _Allocator>;
1756
1757 template<ranges::input_range _Rg,
1758 __allocator_like _Allocator>
1759 unordered_multimap(from_range_t, _Rg&&, _Allocator)
1760 -> unordered_multimap<__detail::__range_key_type<_Rg>,
1761 __detail::__range_mapped_type<_Rg>,
1762 hash<__detail::__range_key_type<_Rg>>,
1763 equal_to<__detail::__range_key_type<_Rg>>,
1764 _Allocator>;
1765
1766 template<ranges::input_range _Rg,
1767 __not_allocator_like _Hash,
1768 __allocator_like _Allocator>
1769 unordered_multimap(from_range_t, _Rg&&,
1770 unordered_multimap<int, int>::size_type,
1771 _Hash, _Allocator)
1772 -> unordered_multimap<__detail::__range_key_type<_Rg>,
1773 __detail::__range_mapped_type<_Rg>,
1774 _Hash, equal_to<__detail::__range_key_type<_Rg>>,
1775 _Allocator>;
1776#endif
1777#endif
1778
1779 template<typename _Key, typename _Tp, typename _Hash,
1780 typename _Pred, typename _Alloc>
1781 inline void
1782 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1783 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1784 noexcept(noexcept(__x.swap(__y)))
1785 { __x.swap(__y); }
1786
1787 template<typename _Key, typename _Tp, typename _Hash,
1788 typename _Pred, typename _Alloc>
1789 inline bool
1790 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1791 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1792 { return __x._M_base() == __y._M_base(); }
1793
1794#if __cpp_impl_three_way_comparison < 201907L
1795 template<typename _Key, typename _Tp, typename _Hash,
1796 typename _Pred, typename _Alloc>
1797 inline bool
1798 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1799 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1800 { return !(__x == __y); }
1801#endif
1802
1803} // namespace __debug
1804
1805#ifdef __glibcxx_erase_if // C++ >= 20 && HOSTED
1806_GLIBCXX_BEGIN_NAMESPACE_VERSION
1807 template<typename _Key, typename _Tp, typename _Hash, typename _CPred,
1808 typename _Alloc, typename _Predicate>
1809 inline typename __debug::unordered_map<_Key, _Tp, _Hash,
1810 _CPred, _Alloc>::size_type
1811 erase_if(__debug::unordered_map<_Key, _Tp, _Hash, _CPred, _Alloc>& __cont,
1812 _Predicate __pred)
1813 { return __detail::__erase_nodes_if(__cont, __cont._M_base(), __pred); }
1814
1815 template<typename _Key, typename _Tp, typename _Hash, typename _CPred,
1816 typename _Alloc, typename _Predicate>
1817 inline typename __debug::unordered_multimap<_Key, _Tp, _Hash,
1818 _CPred, _Alloc>::size_type
1819 erase_if(__debug::unordered_multimap<_Key, _Tp, _Hash, _CPred, _Alloc>& __cont,
1820 _Predicate __pred)
1821 { return __detail::__erase_nodes_if(__cont, __cont._M_base(), __pred); }
1822_GLIBCXX_END_NAMESPACE_VERSION
1823#endif // __glibcxx_erase_if
1824} // namespace std
1825
1826#endif // C++11
1827
1828#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:985