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