libstdc++
debug/unordered_map
Go to the documentation of this file.
1// Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
2
3// Copyright (C) 2003-2025 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library. This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 3, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/** @file debug/unordered_map
26 * This file is a GNU debug extension to the Standard C++ Library.
27 */
28
29#ifndef _GLIBCXX_DEBUG_UNORDERED_MAP
30#define _GLIBCXX_DEBUG_UNORDERED_MAP 1
31
32#ifdef _GLIBCXX_SYSHDR
33#pragma GCC system_header
34#endif
35
36#if __cplusplus < 201103L
37# include <bits/c++0x_warning.h>
38#else
39# include <bits/c++config.h>
40namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug {
41 template<typename _Key, typename _Tp, typename _Hash, typename _Pred,
42 typename _Allocator>
43 class unordered_map;
44 template<typename _Key, typename _Tp, typename _Hash, typename _Pred,
45 typename _Allocator>
46 class unordered_multimap;
47} } // namespace std::__debug
48
49# include <unordered_map>
50
51#include <debug/safe_unordered_container.h>
52#include <debug/safe_container.h>
53#include <debug/safe_iterator.h>
54#include <debug/safe_local_iterator.h>
55
56namespace std _GLIBCXX_VISIBILITY(default)
57{
58namespace __debug
59{
60 /// Class std::unordered_map with safety/checking/debug instrumentation.
61 template<typename _Key, typename _Tp,
62 typename _Hash = std::hash<_Key>,
63 typename _Pred = std::equal_to<_Key>,
64 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
65 class unordered_map
66 : public __gnu_debug::_Safe_container<
67 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
68 __gnu_debug::_Safe_unordered_container>,
69 public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
70 {
71 typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
72 _Pred, _Alloc> _Base;
73 typedef __gnu_debug::_Safe_container<unordered_map,
74 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
75 typedef typename _Base::const_iterator _Base_const_iterator;
76 typedef typename _Base::iterator _Base_iterator;
77 typedef typename _Base::const_local_iterator
78 _Base_const_local_iterator;
79 typedef typename _Base::local_iterator _Base_local_iterator;
80
81 template<typename _ItT, typename _SeqT, typename _CatT>
82 friend class ::__gnu_debug::_Safe_iterator;
83 template<typename _ItT, typename _SeqT>
84 friend class ::__gnu_debug::_Safe_local_iterator;
85
86 // Reference wrapper for base class. See PR libstdc++/90102.
87 struct _Base_ref
88 {
89 _Base_ref(const _Base& __r) : _M_ref(__r) { }
90
91 const _Base& _M_ref;
92 };
93
94 public:
95 typedef typename _Base::size_type size_type;
96 typedef typename _Base::hasher hasher;
97 typedef typename _Base::key_equal key_equal;
98 typedef typename _Base::allocator_type allocator_type;
99
100 typedef typename _Base::key_type key_type;
101 typedef typename _Base::value_type value_type;
102 typedef typename _Base::mapped_type mapped_type;
103
104 typedef typename _Base::pointer pointer;
105 typedef typename _Base::const_pointer const_pointer;
106 typedef typename _Base::reference reference;
107 typedef typename _Base::const_reference const_reference;
108 typedef __gnu_debug::_Safe_iterator<
109 _Base_iterator, unordered_map> iterator;
110 typedef __gnu_debug::_Safe_iterator<
111 _Base_const_iterator, unordered_map> const_iterator;
112 typedef __gnu_debug::_Safe_local_iterator<
113 _Base_local_iterator, unordered_map> local_iterator;
114 typedef __gnu_debug::_Safe_local_iterator<
115 _Base_const_local_iterator, unordered_map> const_local_iterator;
116 typedef typename _Base::difference_type difference_type;
117
118 unordered_map() = default;
119
120 explicit
121 unordered_map(size_type __n,
122 const hasher& __hf = hasher(),
123 const key_equal& __eql = key_equal(),
124 const allocator_type& __a = allocator_type())
125 : _Base(__n, __hf, __eql, __a) { }
126
127 template<typename _InputIterator>
128 unordered_map(_InputIterator __first, _InputIterator __last,
129 size_type __n = 0,
130 const hasher& __hf = hasher(),
131 const key_equal& __eql = key_equal(),
132 const allocator_type& __a = allocator_type())
133 : _Base(__gnu_debug::__base(
134 __glibcxx_check_valid_constructor_range(__first, __last)),
135 __gnu_debug::__base(__last), __n,
136 __hf, __eql, __a) { }
137
138 unordered_map(const unordered_map&) = default;
139
140 unordered_map(_Base_ref __x)
141 : _Base(__x._M_ref) { }
142
143 unordered_map(unordered_map&&) = default;
144
145 explicit
146 unordered_map(const allocator_type& __a)
147 : _Base(__a) { }
148
149 unordered_map(const unordered_map& __umap,
150 const allocator_type& __a)
151 : _Base(__umap, __a) { }
152
153 unordered_map(unordered_map&& __umap,
154 const allocator_type& __a)
155 noexcept( noexcept(_Base(std::move(__umap), __a)) )
156 : _Safe(std::move(__umap), __a),
157 _Base(std::move(__umap), __a) { }
158
159 unordered_map(initializer_list<value_type> __l,
160 size_type __n = 0,
161 const hasher& __hf = hasher(),
162 const key_equal& __eql = key_equal(),
163 const allocator_type& __a = allocator_type())
164 : _Base(__l, __n, __hf, __eql, __a) { }
165
166 unordered_map(size_type __n, const allocator_type& __a)
167 : unordered_map(__n, hasher(), key_equal(), __a)
168 { }
169
170 unordered_map(size_type __n,
171 const hasher& __hf,
172 const allocator_type& __a)
173 : unordered_map(__n, __hf, key_equal(), __a)
174 { }
175
176 template<typename _InputIterator>
177 unordered_map(_InputIterator __first, _InputIterator __last,
178 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 insert_return_type
585 insert(node_type&& __nh)
586 {
587 auto __ret = _Base::insert(std::move(__nh));
588 return
589 { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };
590 }
591
592 iterator
593 insert(const_iterator __hint, node_type&& __nh)
594 {
595 __glibcxx_check_insert(__hint);
596 return { _Base::insert(__hint.base(), std::move(__nh)), this };
597 }
598
599 template<typename _H2, typename _P2>
600 void
601 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
602 {
603 auto __guard
604 = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
605 _Base::merge(__source);
606 }
607
608 template<typename _H2, typename _P2>
609 void
610 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
611 { merge(__source); }
612
613 template<typename _H2, typename _P2>
614 void
615 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
616 {
617 auto __guard
618 = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
619 _Base::merge(__source);
620 }
621
622 template<typename _H2, typename _P2>
623 void
624 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
625 { merge(__source); }
626#endif // C++17
627
628 using _Base::hash_function;
629 using _Base::key_eq;
630
631 iterator
632 find(const key_type& __key)
633 { return { _Base::find(__key), this }; }
634
635#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
636 template<typename _Kt,
637 typename = std::__has_is_transparent_t<_Hash, _Kt>,
638 typename = std::__has_is_transparent_t<_Pred, _Kt>>
639 iterator
640 find(const _Kt& __k)
641 { return { _Base::find(__k), this }; }
642#endif
643
644 const_iterator
645 find(const key_type& __key) const
646 { return { _Base::find(__key), this }; }
647
648#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
649 template<typename _Kt,
650 typename = std::__has_is_transparent_t<_Hash, _Kt>,
651 typename = std::__has_is_transparent_t<_Pred, _Kt>>
652 const_iterator
653 find(const _Kt& __k) const
654 { return { _Base::find(__k), this }; }
655#endif
656
657 using _Base::count;
658#if __cplusplus > 201703L
659 using _Base::contains;
660#endif
661
662 std::pair<iterator, iterator>
663 equal_range(const key_type& __key)
664 {
665 auto __res = _Base::equal_range(__key);
666 return { { __res.first, this }, { __res.second, this } };
667 }
668
669#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
670 template<typename _Kt,
671 typename = std::__has_is_transparent_t<_Hash, _Kt>,
672 typename = std::__has_is_transparent_t<_Pred, _Kt>>
673 std::pair<iterator, iterator>
674 equal_range(const _Kt& __k)
675 {
676 auto __res = _Base::equal_range(__k);
677 return { { __res.first, this }, { __res.second, this } };
678 }
679#endif
680
681 std::pair<const_iterator, const_iterator>
682 equal_range(const key_type& __key) const
683 {
684 auto __res = _Base::equal_range(__key);
685 return { { __res.first, this }, { __res.second, this } };
686 }
687
688#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
689 template<typename _Kt,
690 typename = std::__has_is_transparent_t<_Hash, _Kt>,
691 typename = std::__has_is_transparent_t<_Pred, _Kt>>
692 std::pair<const_iterator, const_iterator>
693 equal_range(const _Kt& __k) const
694 {
695 auto __res = _Base::equal_range(__k);
696 return { { __res.first, this }, { __res.second, this } };
697 }
698#endif
699
700 using _Base::operator[];
701 using _Base::at;
702
703 size_type
704 erase(const key_type& __key)
705 {
706 size_type __ret(0);
707 auto __victim = _Base::find(__key);
708 if (__victim != _Base::end())
709 {
710 _M_erase(__victim);
711 __ret = 1;
712 }
713 return __ret;
714 }
715
716 iterator
717 erase(const_iterator __it)
718 {
719 __glibcxx_check_erase(__it);
720 return { _M_erase(__it.base()), this };
721 }
722
723 _Base_iterator
724 erase(_Base_const_iterator __it)
725 {
726 __glibcxx_check_erase2(__it);
727 return _M_erase(__it);
728 }
729
730 iterator
731 erase(iterator __it)
732 {
733 __glibcxx_check_erase(__it);
734 return { _M_erase(__it.base()), this };
735 }
736
737 iterator
738 erase(const_iterator __first, const_iterator __last)
739 {
740 __glibcxx_check_erase_range(__first, __last);
741 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
742 {
743 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
744 _M_message(__gnu_debug::__msg_valid_range)
745 ._M_iterator(__first, "first")
746 ._M_iterator(__last, "last"));
747 _M_invalidate(__tmp);
748 }
749
750 size_type __bucket_count = this->bucket_count();
751 auto __next = _Base::erase(__first.base(), __last.base());
752 _M_check_rehashed(__bucket_count);
753 return { __next, this };
754 }
755
756 using _Base::rehash;
757 using _Base::reserve;
758
759 _Base&
760 _M_base() noexcept { return *this; }
761
762 const _Base&
763 _M_base() const noexcept { return *this; }
764
765 private:
766 void
767 _M_check_rehashed(size_type __prev_count)
768 {
769 if (__prev_count != this->bucket_count())
770 this->_M_invalidate_all();
771 }
772
773 void
774 _M_invalidate(_Base_const_iterator __victim)
775 {
776 this->_M_invalidate_if(
777 [__victim](_Base_const_iterator __it) { return __it == __victim; });
778 this->_M_invalidate_local_if(
779 [__victim](_Base_const_local_iterator __it)
780 { return __it == __victim; });
781 }
782
783 _Base_iterator
784 _M_erase(_Base_const_iterator __victim)
785 {
786 _M_invalidate(__victim);
787 size_type __bucket_count = this->bucket_count();
788 _Base_iterator __next = _Base::erase(__victim);
789 _M_check_rehashed(__bucket_count);
790 return __next;
791 }
792
793#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
794 node_type
795 _M_extract(_Base_const_iterator __victim)
796 {
797 _M_invalidate(__victim);
798 return _Base::extract(__victim);
799 }
800#endif
801 };
802
803#if __cpp_deduction_guides >= 201606
804
805 template<typename _InputIterator,
806 typename _Hash = hash<__iter_key_t<_InputIterator>>,
807 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
808 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
809 typename = _RequireInputIter<_InputIterator>,
810 typename = _RequireNotAllocatorOrIntegral<_Hash>,
811 typename = _RequireNotAllocator<_Pred>,
812 typename = _RequireAllocator<_Allocator>>
813 unordered_map(_InputIterator, _InputIterator,
814 typename unordered_map<int, int>::size_type = {},
815 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
816 -> unordered_map<__iter_key_t<_InputIterator>,
817 __iter_val_t<_InputIterator>,
818 _Hash, _Pred, _Allocator>;
819
820 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
821 typename _Pred = equal_to<_Key>,
822 typename _Allocator = allocator<pair<const _Key, _Tp>>,
823 typename = _RequireNotAllocatorOrIntegral<_Hash>,
824 typename = _RequireNotAllocator<_Pred>,
825 typename = _RequireAllocator<_Allocator>>
826 unordered_map(initializer_list<pair<_Key, _Tp>>,
827 typename unordered_map<int, int>::size_type = {},
828 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
829 -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
830
831 template<typename _InputIterator, typename _Allocator,
832 typename = _RequireInputIter<_InputIterator>,
833 typename = _RequireAllocator<_Allocator>>
834 unordered_map(_InputIterator, _InputIterator,
835 typename unordered_map<int, int>::size_type, _Allocator)
836 -> unordered_map<__iter_key_t<_InputIterator>,
837 __iter_val_t<_InputIterator>,
838 hash<__iter_key_t<_InputIterator>>,
839 equal_to<__iter_key_t<_InputIterator>>,
840 _Allocator>;
841
842 template<typename _InputIterator, typename _Allocator,
843 typename = _RequireInputIter<_InputIterator>,
844 typename = _RequireAllocator<_Allocator>>
845 unordered_map(_InputIterator, _InputIterator, _Allocator)
846 -> unordered_map<__iter_key_t<_InputIterator>,
847 __iter_val_t<_InputIterator>,
848 hash<__iter_key_t<_InputIterator>>,
849 equal_to<__iter_key_t<_InputIterator>>,
850 _Allocator>;
851
852 template<typename _InputIterator, typename _Hash, typename _Allocator,
853 typename = _RequireInputIter<_InputIterator>,
854 typename = _RequireNotAllocatorOrIntegral<_Hash>,
855 typename = _RequireAllocator<_Allocator>>
856 unordered_map(_InputIterator, _InputIterator,
857 typename unordered_map<int, int>::size_type,
858 _Hash, _Allocator)
859 -> unordered_map<__iter_key_t<_InputIterator>,
860 __iter_val_t<_InputIterator>, _Hash,
861 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
862
863 template<typename _Key, typename _Tp, typename _Allocator,
864 typename = _RequireAllocator<_Allocator>>
865 unordered_map(initializer_list<pair<_Key, _Tp>>,
866 typename unordered_map<int, int>::size_type,
867 _Allocator)
868 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
869
870 template<typename _Key, typename _Tp, typename _Allocator,
871 typename = _RequireAllocator<_Allocator>>
872 unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
873 -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
874
875 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
876 typename = _RequireNotAllocatorOrIntegral<_Hash>,
877 typename = _RequireAllocator<_Allocator>>
878 unordered_map(initializer_list<pair<_Key, _Tp>>,
879 typename unordered_map<int, int>::size_type,
880 _Hash, _Allocator)
881 -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
882
883#if __glibcxx_containers_ranges // C++ >= 23
884 template<ranges::input_range _Rg,
885 __not_allocator_like _Hash = hash<__detail::__range_key_type<_Rg>>,
886 __not_allocator_like _Pred = equal_to<__detail::__range_key_type<_Rg>>,
887 __allocator_like _Allocator =
888 allocator<__detail::__range_to_alloc_type<_Rg>>>
889 unordered_map(from_range_t, _Rg&&, unordered_map<int, int>::size_type = {},
890 _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
891 -> unordered_map<__detail::__range_key_type<_Rg>,
892 __detail::__range_mapped_type<_Rg>,
893 _Hash, _Pred, _Allocator>;
894
895 template<ranges::input_range _Rg,
896 __allocator_like _Allocator>
897 unordered_map(from_range_t, _Rg&&, unordered_map<int, int>::size_type,
898 _Allocator)
899 -> unordered_map<__detail::__range_key_type<_Rg>,
900 __detail::__range_mapped_type<_Rg>,
901 hash<__detail::__range_key_type<_Rg>>,
902 equal_to<__detail::__range_key_type<_Rg>>,
903 _Allocator>;
904
905 template<ranges::input_range _Rg,
906 __allocator_like _Allocator>
907 unordered_map(from_range_t, _Rg&&, _Allocator)
908 -> unordered_map<__detail::__range_key_type<_Rg>,
909 __detail::__range_mapped_type<_Rg>,
910 hash<__detail::__range_key_type<_Rg>>,
911 equal_to<__detail::__range_key_type<_Rg>>,
912 _Allocator>;
913
914 template<ranges::input_range _Rg,
915 __not_allocator_like _Hash,
916 __allocator_like _Allocator>
917 unordered_map(from_range_t, _Rg&&, unordered_map<int, int>::size_type,
918 _Hash, _Allocator)
919 -> unordered_map<__detail::__range_key_type<_Rg>,
920 __detail::__range_mapped_type<_Rg>,
921 _Hash, equal_to<__detail::__range_key_type<_Rg>>,
922 _Allocator>;
923#endif
924#endif
925
926 template<typename _Key, typename _Tp, typename _Hash,
927 typename _Pred, typename _Alloc>
928 inline void
929 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
930 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
931 noexcept(noexcept(__x.swap(__y)))
932 { __x.swap(__y); }
933
934 template<typename _Key, typename _Tp, typename _Hash,
935 typename _Pred, typename _Alloc>
936 inline bool
937 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
938 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
939 { return __x._M_base() == __y._M_base(); }
940
941#if __cpp_impl_three_way_comparison < 201907L
942 template<typename _Key, typename _Tp, typename _Hash,
943 typename _Pred, typename _Alloc>
944 inline bool
945 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
946 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
947 { return !(__x == __y); }
948#endif
949
950 /// Class std::unordered_multimap with safety/checking/debug instrumentation.
951 template<typename _Key, typename _Tp,
952 typename _Hash = std::hash<_Key>,
953 typename _Pred = std::equal_to<_Key>,
954 typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
955 class unordered_multimap
956 : public __gnu_debug::_Safe_container<
957 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
958 __gnu_debug::_Safe_unordered_container>,
959 public _GLIBCXX_STD_C::unordered_multimap<
960 _Key, _Tp, _Hash, _Pred, _Alloc>
961 {
962 typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
963 _Pred, _Alloc> _Base;
964 typedef __gnu_debug::_Safe_container<unordered_multimap,
965 _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
966 typedef typename _Base::const_iterator _Base_const_iterator;
967 typedef typename _Base::iterator _Base_iterator;
968 typedef typename _Base::const_local_iterator _Base_const_local_iterator;
969 typedef typename _Base::local_iterator _Base_local_iterator;
970
971 template<typename _ItT, typename _SeqT, typename _CatT>
972 friend class ::__gnu_debug::_Safe_iterator;
973 template<typename _ItT, typename _SeqT>
974 friend class ::__gnu_debug::_Safe_local_iterator;
975
976 // Reference wrapper for base class. See PR libstdc++/90102.
977 struct _Base_ref
978 {
979 _Base_ref(const _Base& __r) : _M_ref(__r) { }
980
981 const _Base& _M_ref;
982 };
983
984 public:
985 typedef typename _Base::size_type size_type;
986 typedef typename _Base::hasher hasher;
987 typedef typename _Base::key_equal key_equal;
988 typedef typename _Base::allocator_type allocator_type;
989
990 typedef typename _Base::key_type key_type;
991 typedef typename _Base::value_type value_type;
992 typedef typename _Base::mapped_type mapped_type;
993
994 typedef typename _Base::pointer pointer;
995 typedef typename _Base::const_pointer const_pointer;
996 typedef typename _Base::reference reference;
997 typedef typename _Base::const_reference const_reference;
998 typedef __gnu_debug::_Safe_iterator<
999 _Base_iterator, unordered_multimap> iterator;
1000 typedef __gnu_debug::_Safe_iterator<
1001 _Base_const_iterator, unordered_multimap> const_iterator;
1002 typedef __gnu_debug::_Safe_local_iterator<
1003 _Base_local_iterator, unordered_multimap> local_iterator;
1004 typedef __gnu_debug::_Safe_local_iterator<
1005 _Base_const_local_iterator, unordered_multimap> const_local_iterator;
1006 typedef typename _Base::difference_type difference_type;
1007
1008 unordered_multimap() = default;
1009
1010 explicit
1011 unordered_multimap(size_type __n,
1012 const hasher& __hf = hasher(),
1013 const key_equal& __eql = key_equal(),
1014 const allocator_type& __a = allocator_type())
1015 : _Base(__n, __hf, __eql, __a) { }
1016
1017 template<typename _InputIterator>
1018 unordered_multimap(_InputIterator __first, _InputIterator __last,
1019 size_type __n = 0,
1020 const hasher& __hf = hasher(),
1021 const key_equal& __eql = key_equal(),
1022 const allocator_type& __a = allocator_type())
1023 : _Base(__gnu_debug::__base(
1024 __glibcxx_check_valid_constructor_range(__first, __last)),
1025 __gnu_debug::__base(__last), __n,
1026 __hf, __eql, __a) { }
1027
1028 unordered_multimap(const unordered_multimap&) = default;
1029
1030 unordered_multimap(_Base_ref __x)
1031 : _Base(__x._M_ref) { }
1032
1033 unordered_multimap(unordered_multimap&&) = default;
1034
1035 explicit
1036 unordered_multimap(const allocator_type& __a)
1037 : _Base(__a) { }
1038
1039 unordered_multimap(const unordered_multimap& __umap,
1040 const allocator_type& __a)
1041 : _Base(__umap, __a) { }
1042
1043 unordered_multimap(unordered_multimap&& __umap,
1044 const allocator_type& __a)
1045 noexcept( noexcept(_Base(std::move(__umap), __a)) )
1046 : _Safe(std::move(__umap), __a),
1047 _Base(std::move(__umap), __a) { }
1048
1049 unordered_multimap(initializer_list<value_type> __l,
1050 size_type __n = 0,
1051 const hasher& __hf = hasher(),
1052 const key_equal& __eql = key_equal(),
1053 const allocator_type& __a = allocator_type())
1054 : _Base(__l, __n, __hf, __eql, __a) { }
1055
1056 unordered_multimap(size_type __n, const allocator_type& __a)
1057 : unordered_multimap(__n, hasher(), key_equal(), __a)
1058 { }
1059
1060 unordered_multimap(size_type __n, const hasher& __hf,
1061 const allocator_type& __a)
1062 : unordered_multimap(__n, __hf, key_equal(), __a)
1063 { }
1064
1065 template<typename _InputIterator>
1066 unordered_multimap(_InputIterator __first, _InputIterator __last,
1067 const allocator_type& __a)
1068 : unordered_multimap(__first, __last, 0, hasher(), key_equal(), __a)
1069 { }
1070
1071 template<typename _InputIterator>
1072 unordered_multimap(_InputIterator __first, _InputIterator __last,
1073 size_type __n,
1074 const allocator_type& __a)
1075 : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
1076 { }
1077
1078 template<typename _InputIterator>
1079 unordered_multimap(_InputIterator __first, _InputIterator __last,
1080 size_type __n, const hasher& __hf,
1081 const allocator_type& __a)
1082 : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
1083 { }
1084
1085 unordered_multimap(initializer_list<value_type> __l,
1086 const allocator_type& __a)
1087 : unordered_multimap(__l, 0, hasher(), key_equal(), __a)
1088 { }
1089
1090 unordered_multimap(initializer_list<value_type> __l,
1091 size_type __n,
1092 const allocator_type& __a)
1093 : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
1094 { }
1095
1096 unordered_multimap(initializer_list<value_type> __l,
1097 size_type __n, const hasher& __hf,
1098 const allocator_type& __a)
1099 : unordered_multimap(__l, __n, __hf, key_equal(), __a)
1100 { }
1101
1102#if __glibcxx_containers_ranges // C++ >= 23
1103 template<__detail::__container_compatible_range<value_type> _Rg>
1104 unordered_multimap(from_range_t, _Rg&& __rg,
1105 size_type __n = 0,
1106 const hasher& __hf = hasher(),
1107 const key_equal& __eql = key_equal(),
1108 const allocator_type& __a = allocator_type())
1109 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __eql, __a)
1110 { }
1111
1112 template<__detail::__container_compatible_range<value_type> _Rg>
1113 unordered_multimap(from_range_t, _Rg&& __rg, const allocator_type& __a)
1114 : _Base(from_range, std::forward<_Rg>(__rg), __a)
1115 { }
1116
1117 template<__detail::__container_compatible_range<value_type> _Rg>
1118 unordered_multimap(from_range_t, _Rg&& __rg, size_type __n,
1119 const allocator_type& __a)
1120 : _Base(from_range, std::forward<_Rg>(__rg), __n, __a)
1121 { }
1122
1123 template<__detail::__container_compatible_range<value_type> _Rg>
1124 unordered_multimap(from_range_t, _Rg&& __rg, size_type __n,
1125 const hasher& __hf, const allocator_type& __a)
1126 : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __a)
1127 { }
1128#endif
1129
1130 ~unordered_multimap() = default;
1131
1132 unordered_multimap&
1133 operator=(const unordered_multimap&) = default;
1134
1135 unordered_multimap&
1136 operator=(unordered_multimap&&) = default;
1137
1138 unordered_multimap&
1139 operator=(initializer_list<value_type> __l)
1140 {
1141 _Base::operator=(__l);
1142 this->_M_invalidate_all();
1143 return *this;
1144 }
1145
1146 using _Base::get_allocator;
1147 using _Base::empty;
1148 using _Base::size;
1149 using _Base::max_size;
1150
1151 void
1152 swap(unordered_multimap& __x)
1153 noexcept( noexcept(declval<_Base&>().swap(__x)) )
1154 {
1155 _Safe::_M_swap(__x);
1156 _Base::swap(__x);
1157 }
1158
1159 void
1160 clear() noexcept
1161 {
1162 _Base::clear();
1163 this->_M_invalidate_all();
1164 }
1165
1166 iterator
1167 begin() noexcept
1168 { return { _Base::begin(), this }; }
1169
1170 const_iterator
1171 begin() const noexcept
1172 { return { _Base::begin(), this }; }
1173
1174 iterator
1175 end() noexcept
1176 { return { _Base::end(), this }; }
1177
1178 const_iterator
1179 end() const noexcept
1180 { return { _Base::end(), this }; }
1181
1182 const_iterator
1183 cbegin() const noexcept
1184 { return { _Base::cbegin(), this }; }
1185
1186 const_iterator
1187 cend() const noexcept
1188 { return { _Base::cend(), this }; }
1189
1190 // local versions
1191 local_iterator
1192 begin(size_type __b)
1193 {
1194 __glibcxx_check_bucket_index(__b);
1195 return { _Base::begin(__b), this };
1196 }
1197
1198 local_iterator
1199 end(size_type __b)
1200 {
1201 __glibcxx_check_bucket_index(__b);
1202 return { _Base::end(__b), this };
1203 }
1204
1205 const_local_iterator
1206 begin(size_type __b) const
1207 {
1208 __glibcxx_check_bucket_index(__b);
1209 return { _Base::begin(__b), this };
1210 }
1211
1212 const_local_iterator
1213 end(size_type __b) const
1214 {
1215 __glibcxx_check_bucket_index(__b);
1216 return { _Base::end(__b), this };
1217 }
1218
1219 const_local_iterator
1220 cbegin(size_type __b) const
1221 {
1222 __glibcxx_check_bucket_index(__b);
1223 return { _Base::cbegin(__b), this };
1224 }
1225
1226 const_local_iterator
1227 cend(size_type __b) const
1228 {
1229 __glibcxx_check_bucket_index(__b);
1230 return { _Base::cend(__b), this };
1231 }
1232
1233 using _Base::bucket_count;
1234 using _Base::max_bucket_count;
1235 using _Base::bucket;
1236
1237 size_type
1238 bucket_size(size_type __b) const
1239 {
1240 __glibcxx_check_bucket_index(__b);
1241 return _Base::bucket_size(__b);
1242 }
1243
1244 float
1245 max_load_factor() const noexcept
1246 { return _Base::max_load_factor(); }
1247
1248 void
1249 max_load_factor(float __f)
1250 {
1251 __glibcxx_check_max_load_factor(__f);
1252 _Base::max_load_factor(__f);
1253 }
1254
1255 template<typename... _Args>
1256 iterator
1257 emplace(_Args&&... __args)
1258 {
1259 size_type __bucket_count = this->bucket_count();
1260 auto __it = _Base::emplace(std::forward<_Args>(__args)...);
1261 _M_check_rehashed(__bucket_count);
1262 return { __it, this };
1263 }
1264
1265 template<typename... _Args>
1266 iterator
1267 emplace_hint(const_iterator __hint, _Args&&... __args)
1268 {
1269 __glibcxx_check_insert(__hint);
1270 size_type __bucket_count = this->bucket_count();
1271 auto __it = _Base::emplace_hint(__hint.base(),
1272 std::forward<_Args>(__args)...);
1273 _M_check_rehashed(__bucket_count);
1274 return { __it, this };
1275 }
1276
1277 iterator
1278 insert(const value_type& __obj)
1279 {
1280 size_type __bucket_count = this->bucket_count();
1281 auto __it = _Base::insert(__obj);
1282 _M_check_rehashed(__bucket_count);
1283 return { __it, this };
1284 }
1285
1286 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1287 // 2354. Unnecessary copying when inserting into maps with braced-init
1288 iterator
1289 insert(value_type&& __x)
1290 {
1291 size_type __bucket_count = this->bucket_count();
1292 auto __it = _Base::insert(std::move(__x));
1293 _M_check_rehashed(__bucket_count);
1294 return { __it, this };
1295 }
1296
1297 iterator
1298 insert(const_iterator __hint, const value_type& __obj)
1299 {
1300 __glibcxx_check_insert(__hint);
1301 size_type __bucket_count = this->bucket_count();
1302 auto __it = _Base::insert(__hint.base(), __obj);
1303 _M_check_rehashed(__bucket_count);
1304 return { __it, this };
1305 }
1306
1307 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1308 // 2354. Unnecessary copying when inserting into maps with braced-init
1309 iterator
1310 insert(const_iterator __hint, value_type&& __x)
1311 {
1312 __glibcxx_check_insert(__hint);
1313 size_type __bucket_count = this->bucket_count();
1314 auto __it = _Base::insert(__hint.base(), std::move(__x));
1315 _M_check_rehashed(__bucket_count);
1316 return { __it, this };
1317 }
1318
1319 template<typename _Pair, typename = typename
1320 std::enable_if<std::is_constructible<value_type,
1321 _Pair&&>::value>::type>
1322 iterator
1323 insert(_Pair&& __obj)
1324 {
1325 size_type __bucket_count = this->bucket_count();
1326 auto __it = _Base::insert(std::forward<_Pair>(__obj));
1327 _M_check_rehashed(__bucket_count);
1328 return { __it, this };
1329 }
1330
1331 template<typename _Pair, typename = typename
1332 std::enable_if<std::is_constructible<value_type,
1333 _Pair&&>::value>::type>
1334 iterator
1335 insert(const_iterator __hint, _Pair&& __obj)
1336 {
1337 __glibcxx_check_insert(__hint);
1338 size_type __bucket_count = this->bucket_count();
1339 auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
1340 _M_check_rehashed(__bucket_count);
1341 return { __it, this };
1342 }
1343
1344 void
1345 insert(std::initializer_list<value_type> __l)
1346 { _Base::insert(__l); }
1347
1348 template<typename _InputIterator>
1349 void
1350 insert(_InputIterator __first, _InputIterator __last)
1351 {
1352 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
1353 __glibcxx_check_valid_range2(__first, __last, __dist);
1354 size_type __bucket_count = this->bucket_count();
1355
1356 if (__dist.second >= __gnu_debug::__dp_sign)
1357 _Base::insert(__gnu_debug::__unsafe(__first),
1358 __gnu_debug::__unsafe(__last));
1359 else
1360 _Base::insert(__first, __last);
1361
1362 _M_check_rehashed(__bucket_count);
1363 }
1364
1365#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1366 using node_type = typename _Base::node_type;
1367
1368 node_type
1369 extract(const_iterator __position)
1370 {
1371 __glibcxx_check_erase(__position);
1372 return _M_extract(__position.base());
1373 }
1374
1375 node_type
1376 extract(const key_type& __key)
1377 {
1378 const auto __position = _Base::find(__key);
1379 if (__position != _Base::end())
1380 return _M_extract(__position);
1381 return {};
1382 }
1383
1384 iterator
1385 insert(node_type&& __nh)
1386 { return { _Base::insert(std::move(__nh)), this }; }
1387
1388 iterator
1389 insert(const_iterator __hint, node_type&& __nh)
1390 {
1391 __glibcxx_check_insert(__hint);
1392 return { _Base::insert(__hint.base(), std::move(__nh)), this };
1393 }
1394
1395 template<typename _H2, typename _P2>
1396 void
1397 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1398 {
1399 auto __guard
1400 = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
1401 _Base::merge(__source);
1402 }
1403
1404 template<typename _H2, typename _P2>
1405 void
1406 merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1407 { merge(__source); }
1408
1409 template<typename _H2, typename _P2>
1410 void
1411 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1412 {
1413 auto __guard
1414 = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
1415 _Base::merge(__source);
1416 }
1417
1418 template<typename _H2, typename _P2>
1419 void
1420 merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1421 { merge(__source); }
1422#endif // C++17
1423
1424 using _Base::hash_function;
1425 using _Base::key_eq;
1426
1427 iterator
1428 find(const key_type& __key)
1429 { return { _Base::find(__key), this }; }
1430
1431#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1432 template<typename _Kt,
1433 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1434 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1435 iterator
1436 find(const _Kt& __k)
1437 { return { _Base::find(__k), this }; }
1438#endif
1439
1440 const_iterator
1441 find(const key_type& __key) const
1442 { return { _Base::find(__key), this }; }
1443
1444#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1445 template<typename _Kt,
1446 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1447 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1448 const_iterator
1449 find(const _Kt& __k) const
1450 { return { _Base::find(__k), this }; }
1451#endif
1452
1453 using _Base::count;
1454#if __cplusplus > 201703L
1455 using _Base::contains;
1456#endif
1457
1458 std::pair<iterator, iterator>
1459 equal_range(const key_type& __key)
1460 {
1461 auto __res = _Base::equal_range(__key);
1462 return { { __res.first, this }, { __res.second, this } };
1463 }
1464
1465#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1466 template<typename _Kt,
1467 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1468 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1469 std::pair<iterator, iterator>
1470 equal_range(const _Kt& __k)
1471 {
1472 auto __res = _Base::equal_range(__k);
1473 return { { __res.first, this }, { __res.second, this } };
1474 }
1475#endif
1476
1477 std::pair<const_iterator, const_iterator>
1478 equal_range(const key_type& __key) const
1479 {
1480 auto __res = _Base::equal_range(__key);
1481 return { { __res.first, this }, { __res.second, this } };
1482 }
1483
1484#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1485 template<typename _Kt,
1486 typename = std::__has_is_transparent_t<_Hash, _Kt>,
1487 typename = std::__has_is_transparent_t<_Pred, _Kt>>
1488 std::pair<const_iterator, const_iterator>
1489 equal_range(const _Kt& __k) const
1490 {
1491 auto __res = _Base::equal_range(__k);
1492 return { { __res.first, this }, { __res.second, this } };
1493 }
1494#endif
1495
1496 size_type
1497 erase(const key_type& __key)
1498 {
1499 size_type __ret(0);
1500 size_type __bucket_count = this->bucket_count();
1501 auto __pair = _Base::equal_range(__key);
1502 for (auto __victim = __pair.first; __victim != __pair.second;)
1503 {
1504 _M_invalidate(__victim);
1505 __victim = _Base::erase(__victim);
1506 ++__ret;
1507 }
1508
1509 _M_check_rehashed(__bucket_count);
1510 return __ret;
1511 }
1512
1513 iterator
1514 erase(const_iterator __it)
1515 {
1516 __glibcxx_check_erase(__it);
1517 return { _M_erase(__it.base()), this };
1518 }
1519
1520 _Base_iterator
1521 erase(_Base_const_iterator __it)
1522 {
1523 __glibcxx_check_erase2(__it);
1524 return _M_erase(__it);
1525 }
1526
1527 iterator
1528 erase(iterator __it)
1529 {
1530 __glibcxx_check_erase(__it);
1531 return { _M_erase(__it.base()), this };
1532 }
1533
1534 iterator
1535 erase(const_iterator __first, const_iterator __last)
1536 {
1537 __glibcxx_check_erase_range(__first, __last);
1538 for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1539 {
1540 _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1541 _M_message(__gnu_debug::__msg_valid_range)
1542 ._M_iterator(__first, "first")
1543 ._M_iterator(__last, "last"));
1544 _M_invalidate(__tmp);
1545 }
1546
1547 size_type __bucket_count = this->bucket_count();
1548 auto __next = _Base::erase(__first.base(), __last.base());
1549 _M_check_rehashed(__bucket_count);
1550 return { __next, this };
1551 }
1552
1553 using _Base::rehash;
1554 using _Base::reserve;
1555
1556 _Base&
1557 _M_base() noexcept { return *this; }
1558
1559 const _Base&
1560 _M_base() const noexcept { return *this; }
1561
1562 private:
1563 void
1564 _M_check_rehashed(size_type __prev_count)
1565 {
1566 if (__prev_count != this->bucket_count())
1567 this->_M_invalidate_all();
1568 }
1569
1570 void
1571 _M_invalidate(_Base_const_iterator __victim)
1572 {
1573 this->_M_invalidate_if(
1574 [__victim](_Base_const_iterator __it) { return __it == __victim; });
1575 this->_M_invalidate_local_if(
1576 [__victim](_Base_const_local_iterator __it)
1577 { return __it == __victim; });
1578 }
1579
1580 _Base_iterator
1581 _M_erase(_Base_const_iterator __victim)
1582 {
1583 _M_invalidate(__victim);
1584 size_type __bucket_count = this->bucket_count();
1585 _Base_iterator __next = _Base::erase(__victim);
1586 _M_check_rehashed(__bucket_count);
1587 return __next;
1588 }
1589
1590#ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1591 node_type
1592 _M_extract(_Base_const_iterator __victim)
1593 {
1594 _M_invalidate(__victim);
1595 return _Base::extract(__victim);
1596 }
1597#endif
1598 };
1599
1600#if __cpp_deduction_guides >= 201606
1601
1602 template<typename _InputIterator,
1603 typename _Hash = hash<__iter_key_t<_InputIterator>>,
1604 typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1605 typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1606 typename = _RequireInputIter<_InputIterator>,
1607 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1608 typename = _RequireNotAllocator<_Pred>,
1609 typename = _RequireAllocator<_Allocator>>
1610 unordered_multimap(_InputIterator, _InputIterator,
1611 unordered_multimap<int, int>::size_type = {},
1612 _Hash = _Hash(), _Pred = _Pred(),
1613 _Allocator = _Allocator())
1614 -> unordered_multimap<__iter_key_t<_InputIterator>,
1615 __iter_val_t<_InputIterator>, _Hash, _Pred,
1616 _Allocator>;
1617
1618 template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
1619 typename _Pred = equal_to<_Key>,
1620 typename _Allocator = allocator<pair<const _Key, _Tp>>,
1621 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1622 typename = _RequireNotAllocator<_Pred>,
1623 typename = _RequireAllocator<_Allocator>>
1624 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1625 unordered_multimap<int, int>::size_type = {},
1626 _Hash = _Hash(), _Pred = _Pred(),
1627 _Allocator = _Allocator())
1628 -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
1629
1630 template<typename _InputIterator, typename _Allocator,
1631 typename = _RequireInputIter<_InputIterator>,
1632 typename = _RequireAllocator<_Allocator>>
1633 unordered_multimap(_InputIterator, _InputIterator,
1634 unordered_multimap<int, int>::size_type, _Allocator)
1635 -> unordered_multimap<__iter_key_t<_InputIterator>,
1636 __iter_val_t<_InputIterator>,
1637 hash<__iter_key_t<_InputIterator>>,
1638 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1639
1640 template<typename _InputIterator, typename _Allocator,
1641 typename = _RequireInputIter<_InputIterator>,
1642 typename = _RequireAllocator<_Allocator>>
1643 unordered_multimap(_InputIterator, _InputIterator, _Allocator)
1644 -> unordered_multimap<__iter_key_t<_InputIterator>,
1645 __iter_val_t<_InputIterator>,
1646 hash<__iter_key_t<_InputIterator>>,
1647 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1648
1649 template<typename _InputIterator, typename _Hash, typename _Allocator,
1650 typename = _RequireInputIter<_InputIterator>,
1651 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1652 typename = _RequireAllocator<_Allocator>>
1653 unordered_multimap(_InputIterator, _InputIterator,
1654 unordered_multimap<int, int>::size_type, _Hash,
1655 _Allocator)
1656 -> unordered_multimap<__iter_key_t<_InputIterator>,
1657 __iter_val_t<_InputIterator>, _Hash,
1658 equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1659
1660 template<typename _Key, typename _Tp, typename _Allocator,
1661 typename = _RequireAllocator<_Allocator>>
1662 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1663 unordered_multimap<int, int>::size_type,
1664 _Allocator)
1665 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1666
1667 template<typename _Key, typename _Tp, typename _Allocator,
1668 typename = _RequireAllocator<_Allocator>>
1669 unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
1670 -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1671
1672 template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
1673 typename = _RequireNotAllocatorOrIntegral<_Hash>,
1674 typename = _RequireAllocator<_Allocator>>
1675 unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1676 unordered_multimap<int, int>::size_type,
1677 _Hash, _Allocator)
1678 -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1679
1680#if __glibcxx_containers_ranges // C++ >= 23
1681 template<ranges::input_range _Rg,
1682 __not_allocator_like _Hash = hash<__detail::__range_key_type<_Rg>>,
1683 __not_allocator_like _Pred = equal_to<__detail::__range_key_type<_Rg>>,
1684 __allocator_like _Allocator =
1685 allocator<__detail::__range_to_alloc_type<_Rg>>>
1686 unordered_multimap(from_range_t, _Rg&&,
1687 unordered_multimap<int, int>::size_type = {},
1688 _Hash = _Hash(), _Pred = _Pred(),
1689 _Allocator = _Allocator())
1690 -> unordered_multimap<__detail::__range_key_type<_Rg>,
1691 __detail::__range_mapped_type<_Rg>,
1692 _Hash, _Pred, _Allocator>;
1693
1694 template<ranges::input_range _Rg,
1695 __allocator_like _Allocator>
1696 unordered_multimap(from_range_t, _Rg&&, unordered_multimap<int, int>::size_type,
1697 _Allocator)
1698 -> unordered_multimap<__detail::__range_key_type<_Rg>,
1699 __detail::__range_mapped_type<_Rg>,
1700 hash<__detail::__range_key_type<_Rg>>,
1701 equal_to<__detail::__range_key_type<_Rg>>,
1702 _Allocator>;
1703
1704 template<ranges::input_range _Rg,
1705 __allocator_like _Allocator>
1706 unordered_multimap(from_range_t, _Rg&&, _Allocator)
1707 -> unordered_multimap<__detail::__range_key_type<_Rg>,
1708 __detail::__range_mapped_type<_Rg>,
1709 hash<__detail::__range_key_type<_Rg>>,
1710 equal_to<__detail::__range_key_type<_Rg>>,
1711 _Allocator>;
1712
1713 template<ranges::input_range _Rg,
1714 __not_allocator_like _Hash,
1715 __allocator_like _Allocator>
1716 unordered_multimap(from_range_t, _Rg&&,
1717 unordered_multimap<int, int>::size_type,
1718 _Hash, _Allocator)
1719 -> unordered_multimap<__detail::__range_key_type<_Rg>,
1720 __detail::__range_mapped_type<_Rg>,
1721 _Hash, equal_to<__detail::__range_key_type<_Rg>>,
1722 _Allocator>;
1723#endif
1724#endif
1725
1726 template<typename _Key, typename _Tp, typename _Hash,
1727 typename _Pred, typename _Alloc>
1728 inline void
1729 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1730 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1731 noexcept(noexcept(__x.swap(__y)))
1732 { __x.swap(__y); }
1733
1734 template<typename _Key, typename _Tp, typename _Hash,
1735 typename _Pred, typename _Alloc>
1736 inline bool
1737 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1738 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1739 { return __x._M_base() == __y._M_base(); }
1740
1741#if __cpp_impl_three_way_comparison < 201907L
1742 template<typename _Key, typename _Tp, typename _Hash,
1743 typename _Pred, typename _Alloc>
1744 inline bool
1745 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1746 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1747 { return !(__x == __y); }
1748#endif
1749
1750} // namespace __debug
1751} // namespace std
1752
1753#endif // C++11
1754
1755#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:2672
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:136
std::is_constructible
is_constructible
Definition type_traits:1196
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:371
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:1382
std::unordered_multimap::size_type
_Hashtable::size_type size_type
Iterator-related typedefs.
Definition unordered_map.h:1408
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:961