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