libstdc++
debug/unordered_map
Go to the documentation of this file.
1 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2022 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>
38 namespace 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 
54 namespace std _GLIBCXX_VISIBILITY(default)
55 {
56 namespace __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 #if __cplusplus > 201402L
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