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