libstdc++
debug/unordered_map
Go to the documentation of this file.
1 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2026 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  const allocator_type& __a)
179  : unordered_map(__first, __last, 0, hasher(), key_equal(), __a)
180  { }
181 
182  template<typename _InputIterator>
183  unordered_map(_InputIterator __first, _InputIterator __last,
184  size_type __n,
185  const allocator_type& __a)
186  : unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
187  { }
188 
189  template<typename _InputIterator>
190  unordered_map(_InputIterator __first, _InputIterator __last,
191  size_type __n,
192  const hasher& __hf,
193  const allocator_type& __a)
194  : unordered_map(__first, __last, __n, __hf, key_equal(), __a)
195  { }
196 
197  unordered_map(initializer_list<value_type> __l,
198  const allocator_type& __a)
199  : unordered_map(__l, 0, hasher(), key_equal(), __a)
200  { }
201 
202  unordered_map(initializer_list<value_type> __l,
203  size_type __n,
204  const allocator_type& __a)
205  : unordered_map(__l, __n, hasher(), key_equal(), __a)
206  { }
207 
208  unordered_map(initializer_list<value_type> __l,
209  size_type __n,
210  const hasher& __hf,
211  const allocator_type& __a)
212  : unordered_map(__l, __n, __hf, key_equal(), __a)
213  { }
214 
215 #if __glibcxx_containers_ranges // C++ >= 23
216  template<__detail::__container_compatible_range<value_type> _Rg>
217  unordered_map(from_range_t, _Rg&& __rg,
218  size_type __n = 0,
219  const hasher& __hf = hasher(),
220  const key_equal& __eql = key_equal(),
221  const allocator_type& __a = allocator_type())
222  : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __eql, __a)
223  { }
224 
225  template<__detail::__container_compatible_range<value_type> _Rg>
226  unordered_map(from_range_t, _Rg&& __rg, const allocator_type& __a)
227  : _Base(from_range, std::forward<_Rg>(__rg), __a)
228  { }
229 
230  template<__detail::__container_compatible_range<value_type> _Rg>
231  unordered_map(from_range_t, _Rg&& __rg, size_type __n,
232  const allocator_type& __a)
233  : _Base(from_range, std::forward<_Rg>(__rg), __n, __a)
234  { }
235 
236  template<__detail::__container_compatible_range<value_type> _Rg>
237  unordered_map(from_range_t, _Rg&& __rg, size_type __n,
238  const hasher& __hf, const allocator_type& __a)
239  : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __a)
240  { }
241 #endif
242 
243  ~unordered_map() = default;
244 
245  unordered_map&
246  operator=(const unordered_map&) = default;
247 
248  unordered_map&
249  operator=(unordered_map&&) = default;
250 
251  unordered_map&
252  operator=(initializer_list<value_type> __l)
253  {
254  _Base::operator=(__l);
255  this->_M_invalidate_all();
256  return *this;
257  }
258 
259  using _Base::get_allocator;
260  using _Base::empty;
261  using _Base::size;
262  using _Base::max_size;
263 
264  void
265  swap(unordered_map& __x)
266  noexcept( noexcept(declval<_Base&>().swap(__x)) )
267  {
268  _Safe::_M_swap(__x);
269  _Base::swap(__x);
270  }
271 
272  void
273  clear() noexcept
274  {
275  _Base::clear();
276  this->_M_invalidate_all();
277  }
278 
279  iterator
280  begin() noexcept
281  { return { _Base::begin(), this }; }
282 
283  const_iterator
284  begin() const noexcept
285  { return { _Base::begin(), this }; }
286 
287  iterator
288  end() noexcept
289  { return { _Base::end(), this }; }
290 
291  const_iterator
292  end() const noexcept
293  { return { _Base::end(), this }; }
294 
295  const_iterator
296  cbegin() const noexcept
297  { return { _Base::cbegin(), this }; }
298 
299  const_iterator
300  cend() const noexcept
301  { return { _Base::cend(), this }; }
302 
303  // local versions
304  local_iterator
305  begin(size_type __b)
306  {
307  __glibcxx_check_bucket_index(__b);
308  return { _Base::begin(__b), this };
309  }
310 
311  local_iterator
312  end(size_type __b)
313  {
314  __glibcxx_check_bucket_index(__b);
315  return { _Base::end(__b), this };
316  }
317 
318  const_local_iterator
319  begin(size_type __b) const
320  {
321  __glibcxx_check_bucket_index(__b);
322  return { _Base::begin(__b), this };
323  }
324 
325  const_local_iterator
326  end(size_type __b) const
327  {
328  __glibcxx_check_bucket_index(__b);
329  return { _Base::end(__b), this };
330  }
331 
332  const_local_iterator
333  cbegin(size_type __b) const
334  {
335  __glibcxx_check_bucket_index(__b);
336  return { _Base::cbegin(__b), this };
337  }
338 
339  const_local_iterator
340  cend(size_type __b) const
341  {
342  __glibcxx_check_bucket_index(__b);
343  return { _Base::cend(__b), this };
344  }
345 
346  using _Base::bucket_count;
347  using _Base::max_bucket_count;
348  using _Base::bucket;
349 
350  size_type
351  bucket_size(size_type __b) const
352  {
353  __glibcxx_check_bucket_index(__b);
354  return _Base::bucket_size(__b);
355  }
356 
357  using _Base::load_factor;
358 
359  float
360  max_load_factor() const noexcept
361  { return _Base::max_load_factor(); }
362 
363  void
364  max_load_factor(float __f)
365  {
366  __glibcxx_check_max_load_factor(__f);
367  _Base::max_load_factor(__f);
368  }
369 
370  template<typename... _Args>
371  std::pair<iterator, bool>
372  emplace(_Args&&... __args)
373  {
374  size_type __bucket_count = this->bucket_count();
375  auto __res = _Base::emplace(std::forward<_Args>(__args)...);
376  _M_check_rehashed(__bucket_count);
377  return { { __res.first, this }, __res.second };
378  }
379 
380  template<typename... _Args>
381  iterator
382  emplace_hint(const_iterator __hint, _Args&&... __args)
383  {
384  __glibcxx_check_insert(__hint);
385  size_type __bucket_count = this->bucket_count();
386  auto __it = _Base::emplace_hint(__hint.base(),
387  std::forward<_Args>(__args)...);
388  _M_check_rehashed(__bucket_count);
389  return { __it, this };
390  }
391 
392  std::pair<iterator, bool>
393  insert(const value_type& __obj)
394  {
395  size_type __bucket_count = this->bucket_count();
396  auto __res = _Base::insert(__obj);
397  _M_check_rehashed(__bucket_count);
398  return { { __res.first, this }, __res.second };
399  }
400 
401  // _GLIBCXX_RESOLVE_LIB_DEFECTS
402  // 2354. Unnecessary copying when inserting into maps with braced-init
403  std::pair<iterator, bool>
404  insert(value_type&& __x)
405  {
406  size_type __bucket_count = this->bucket_count();
407  auto __res = _Base::insert(std::move(__x));
408  _M_check_rehashed(__bucket_count);
409  return { { __res.first, this }, __res.second };
410  }
411 
412  template<typename _Pair, typename = typename
413  std::enable_if<std::is_constructible<value_type,
414  _Pair&&>::value>::type>
415  std::pair<iterator, bool>
416  insert(_Pair&& __obj)
417  {
418  size_type __bucket_count = this->bucket_count();
419  auto __res = _Base::insert(std::forward<_Pair>(__obj));
420  _M_check_rehashed(__bucket_count);
421  return { { __res.first, this }, __res.second };
422  }
423 
424  iterator
425  insert(const_iterator __hint, const value_type& __obj)
426  {
427  __glibcxx_check_insert(__hint);
428  size_type __bucket_count = this->bucket_count();
429  auto __it = _Base::insert(__hint.base(), __obj);
430  _M_check_rehashed(__bucket_count);
431  return { __it, this };
432  }
433 
434  // _GLIBCXX_RESOLVE_LIB_DEFECTS
435  // 2354. Unnecessary copying when inserting into maps with braced-init
436  iterator
437  insert(const_iterator __hint, value_type&& __x)
438  {
439  __glibcxx_check_insert(__hint);
440  size_type __bucket_count = this->bucket_count();
441  auto __it = _Base::insert(__hint.base(), std::move(__x));
442  _M_check_rehashed(__bucket_count);
443  return { __it, this };
444  }
445 
446  template<typename _Pair, typename = typename
447  std::enable_if<std::is_constructible<value_type,
448  _Pair&&>::value>::type>
449  iterator
450  insert(const_iterator __hint, _Pair&& __obj)
451  {
452  __glibcxx_check_insert(__hint);
453  size_type __bucket_count = this->bucket_count();
454  auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
455  _M_check_rehashed(__bucket_count);
456  return { __it, this };
457  }
458 
459  void
460  insert(std::initializer_list<value_type> __l)
461  {
462  size_type __bucket_count = this->bucket_count();
463  _Base::insert(__l);
464  _M_check_rehashed(__bucket_count);
465  }
466 
467  template<typename _InputIterator>
468  void
469  insert(_InputIterator __first, _InputIterator __last)
470  {
471  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
472  __glibcxx_check_valid_range2(__first, __last, __dist);
473  size_type __bucket_count = this->bucket_count();
474 
475  if (__dist.second >= __gnu_debug::__dp_sign)
476  _Base::insert(__gnu_debug::__unsafe(__first),
477  __gnu_debug::__unsafe(__last));
478  else
479  _Base::insert(__first, __last);
480 
481  _M_check_rehashed(__bucket_count);
482  }
483 
484 #ifdef __glibcxx_unordered_map_try_emplace // C++ >= 17 && HOSTED
485  template <typename... _Args>
486  pair<iterator, bool>
487  try_emplace(const key_type& __k, _Args&&... __args)
488  {
489  auto __res = _Base::try_emplace(__k,
490  std::forward<_Args>(__args)...);
491  return { { __res.first, this }, __res.second };
492  }
493 
494  template <typename... _Args>
495  pair<iterator, bool>
496  try_emplace(key_type&& __k, _Args&&... __args)
497  {
498  auto __res = _Base::try_emplace(std::move(__k),
499  std::forward<_Args>(__args)...);
500  return { { __res.first, this }, __res.second };
501  }
502 
503 # ifdef __glibcxx_associative_heterogeneous_insertion
504  template <__heterogeneous_hash_key<unordered_map> _Kt, typename... _Args>
505  pair<iterator, bool>
506  try_emplace(_Kt&& __k, _Args&&... __args)
507  {
508  auto __res = _Base::try_emplace(std::forward<_Kt>(__k),
509  std::forward<_Args>(__args)...);
510  return { { __res.first, this }, __res.second };
511  }
512 # endif
513 
514  template <typename... _Args>
515  iterator
516  try_emplace(const_iterator __hint, const key_type& __k,
517  _Args&&... __args)
518  {
519  __glibcxx_check_insert(__hint);
520  return { _Base::try_emplace(__hint.base(), __k,
521  std::forward<_Args>(__args)...),
522  this };
523  }
524 
525  template <typename... _Args>
526  iterator
527  try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
528  {
529  __glibcxx_check_insert(__hint);
530  auto __it = _Base::try_emplace(__hint.base(), std::move(__k),
531  std::forward<_Args>(__args)...);
532  return { __it, this };
533  }
534 # ifdef __glibcxx_associative_heterogeneous_insertion
535  template <__heterogeneous_hash_key<unordered_map> _Kt, typename... _Args>
536  iterator
537  try_emplace(const_iterator __hint, _Kt&& __k, _Args&&... __args)
538  {
539  __glibcxx_check_insert(__hint);
540  auto __it = _Base::try_emplace(__hint.base(),
541  std::forward<_Kt>(__k), std::forward<_Args>(__args)...);
542  return { __it, this };
543  }
544 # endif
545 
546  template <typename _Obj>
547  pair<iterator, bool>
548  insert_or_assign(const key_type& __k, _Obj&& __obj)
549  {
550  auto __res = _Base::insert_or_assign(__k,
551  std::forward<_Obj>(__obj));
552  return { { __res.first, this }, __res.second };
553  }
554 
555  template <typename _Obj>
556  pair<iterator, bool>
557  insert_or_assign(key_type&& __k, _Obj&& __obj)
558  {
559  auto __res = _Base::insert_or_assign(std::move(__k),
560  std::forward<_Obj>(__obj));
561  return { { __res.first, this }, __res.second };
562  }
563 
564 # ifdef __glibcxx_associative_heterogeneous_insertion
565  template <__heterogeneous_hash_key<unordered_map> _Kt, typename _Obj>
566  pair<iterator, bool>
567  insert_or_assign(_Kt&& __k, _Obj&& __obj)
568  {
569  auto __res = _Base::insert_or_assign(
570  std::forward<_Kt>(__k), std::forward<_Obj>(__obj));
571  return { { __res.first, this }, __res.second };
572  }
573 # endif
574 
575  template <typename _Obj>
576  iterator
577  insert_or_assign(const_iterator __hint, const key_type& __k,
578  _Obj&& __obj)
579  {
580  __glibcxx_check_insert(__hint);
581  auto __it = _Base::insert_or_assign(__hint.base(), __k,
582  std::forward<_Obj>(__obj));
583  return { __it, this };
584  }
585 
586  template <typename _Obj>
587  iterator
588  insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
589  {
590  __glibcxx_check_insert(__hint);
591  auto __it = _Base::insert_or_assign(__hint.base(), std::move(__k),
592  std::forward<_Obj>(__obj));
593  return { __it, this };
594  }
595 
596 # ifdef __glibcxx_associative_heterogeneous_insertion
597  template <__heterogeneous_hash_key<unordered_map> _Kt, typename _Obj>
598  iterator
599  insert_or_assign(const_iterator __hint, _Kt&& __k, _Obj&& __obj)
600  {
601  __glibcxx_check_insert(__hint);
602  auto __it = _Base::insert_or_assign(__hint.base(),
603  std::forward<_Kt>(__k), std::forward<_Obj>(__obj));
604  return { __it, this };
605  }
606 # endif
607 
608 #endif // C++17
609 
610 #ifdef __glibcxx_node_extract // >= C++17 && HOSTED
611  using node_type = typename _Base::node_type;
612  using insert_return_type = _Node_insert_return<iterator, node_type>;
613 
614  node_type
615  extract(const_iterator __position)
616  {
617  __glibcxx_check_erase(__position);
618  return _M_extract(__position.base());
619  }
620 
621  node_type
622  extract(const key_type& __key)
623  {
624  const auto __position = _Base::find(__key);
625  if (__position != _Base::end())
626  return _M_extract(__position);
627  return {};
628  }
629 
630 # ifdef __glibcxx_associative_heterogeneous_erasure
631  template <__heterogeneous_hash_key<unordered_map> _Kt>
632  node_type
633  extract(_Kt&& __key)
634  {
635  const auto __position = _Base::find(__key);
636  if (__position != _Base::end())
637  return _M_extract(__position);
638  return {};
639  }
640 #endif
641 
642  insert_return_type
643  insert(node_type&& __nh)
644  {
645  auto __ret = _Base::insert(std::move(__nh));
646  return
647  { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };
648  }
649 
650  iterator
651  insert(const_iterator __hint, node_type&& __nh)
652  {
653  __glibcxx_check_insert(__hint);
654  return { _Base::insert(__hint.base(), std::move(__nh)), this };
655  }
656 
657  template<typename _H2, typename _P2>
658  void
659  merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
660  {
661  auto __guard
662  = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
663  _Base::merge(__source);
664  }
665 
666  template<typename _H2, typename _P2>
667  void
668  merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
669  { merge(__source); }
670 
671  template<typename _H2, typename _P2>
672  void
673  merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
674  {
675  auto __guard
676  = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
677  _Base::merge(__source);
678  }
679 
680  template<typename _H2, typename _P2>
681  void
682  merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
683  { merge(__source); }
684 #endif // C++17
685 
686  using _Base::hash_function;
687  using _Base::key_eq;
688 
689  iterator
690  find(const key_type& __key)
691  { return { _Base::find(__key), this }; }
692 
693 #ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
694  template<typename _Kt,
695  typename = std::__has_is_transparent_t<_Hash, _Kt>,
696  typename = std::__has_is_transparent_t<_Pred, _Kt>>
697  iterator
698  find(const _Kt& __k)
699  { return { _Base::find(__k), this }; }
700 #endif
701 
702  const_iterator
703  find(const key_type& __key) const
704  { return { _Base::find(__key), this }; }
705 
706 #ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
707  template<typename _Kt,
708  typename = std::__has_is_transparent_t<_Hash, _Kt>,
709  typename = std::__has_is_transparent_t<_Pred, _Kt>>
710  const_iterator
711  find(const _Kt& __k) const
712  { return { _Base::find(__k), this }; }
713 #endif
714 
715  using _Base::count;
716 #if __cplusplus > 201703L
717  using _Base::contains;
718 #endif
719 
720  std::pair<iterator, iterator>
721  equal_range(const key_type& __key)
722  {
723  auto __res = _Base::equal_range(__key);
724  return { { __res.first, this }, { __res.second, this } };
725  }
726 
727 #ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
728  template<typename _Kt,
729  typename = std::__has_is_transparent_t<_Hash, _Kt>,
730  typename = std::__has_is_transparent_t<_Pred, _Kt>>
731  std::pair<iterator, iterator>
732  equal_range(const _Kt& __k)
733  {
734  auto __res = _Base::equal_range(__k);
735  return { { __res.first, this }, { __res.second, this } };
736  }
737 #endif
738 
739  std::pair<const_iterator, const_iterator>
740  equal_range(const key_type& __key) const
741  {
742  auto __res = _Base::equal_range(__key);
743  return { { __res.first, this }, { __res.second, this } };
744  }
745 
746 #ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
747  template<typename _Kt,
748  typename = std::__has_is_transparent_t<_Hash, _Kt>,
749  typename = std::__has_is_transparent_t<_Pred, _Kt>>
750  std::pair<const_iterator, const_iterator>
751  equal_range(const _Kt& __k) const
752  {
753  auto __res = _Base::equal_range(__k);
754  return { { __res.first, this }, { __res.second, this } };
755  }
756 #endif
757 
758  using _Base::operator[];
759  using _Base::at;
760 
761  size_type
762  erase(const key_type& __key)
763  {
764  size_type __ret(0);
765  auto __victim = _Base::find(__key);
766  if (__victim != _Base::end())
767  {
768  _M_erase(__victim);
769  __ret = 1;
770  }
771  return __ret;
772  }
773 
774 # ifdef __glibcxx_associative_heterogeneous_erasure
775  template <__heterogeneous_hash_key<unordered_map> _Kt>
776  size_type
777  erase(_Kt&& __key)
778  {
779  auto __victim = _Base::find(__key);
780  if (__victim != _Base::end())
781  return _M_erase(__victim), 1;
782  return 0;
783  }
784 #endif
785 
786  iterator
787  erase(const_iterator __it)
788  {
789  __glibcxx_check_erase(__it);
790  return { _M_erase(__it.base()), this };
791  }
792 
793  _Base_iterator
794  erase(_Base_const_iterator __it)
795  {
796  __glibcxx_check_erase2(__it);
797  return _M_erase(__it);
798  }
799 
800  iterator
801  erase(iterator __it)
802  {
803  __glibcxx_check_erase(__it);
804  return { _M_erase(__it.base()), this };
805  }
806 
807  iterator
808  erase(const_iterator __first, const_iterator __last)
809  {
810  __glibcxx_check_erase_range(__first, __last);
811  {
812  __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
813  for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
814  {
815  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
816  _M_message(__gnu_debug::__msg_valid_range)
817  ._M_iterator(__first, "first")
818  ._M_iterator(__last, "last"));
819  this->_M_invalidate(__tmp, sentry);
820  }
821  }
822 
823  auto __next = _Base::erase(__first.base(), __last.base());
824  return { __next, this };
825  }
826 
827  using _Base::rehash;
828  using _Base::reserve;
829 
830  _Base&
831  _M_base() noexcept { return *this; }
832 
833  const _Base&
834  _M_base() const noexcept { return *this; }
835 
836  private:
837  const unordered_map*
838  _M_self() const noexcept
839  { return this; }
840 
841  void
842  _M_check_rehashed(size_type __prev_count)
843  {
844  if (__prev_count != this->bucket_count())
845  this->_M_invalidate_all();
846  }
847 
848  _Base_iterator
849  _M_erase(_Base_const_iterator __victim)
850  {
851  this->_M_invalidate(__victim);
852  return _Base::erase(__victim);
853  }
854 
855 #ifdef __glibcxx_node_extract // >= C++17 && HOSTED
856  node_type
857  _M_extract(_Base_const_iterator __victim)
858  {
859  this->_M_invalidate(__victim);
860  return _Base::extract(__victim);
861  }
862 #endif
863  };
864 
865 #if __cpp_deduction_guides >= 201606
866 
867  template<typename _InputIterator,
868  typename _Hash = hash<__iter_key_t<_InputIterator>>,
869  typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
870  typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
871  typename = _RequireInputIter<_InputIterator>,
872  typename = _RequireNotAllocatorOrIntegral<_Hash>,
873  typename = _RequireNotAllocator<_Pred>,
874  typename = _RequireAllocator<_Allocator>>
875  unordered_map(_InputIterator, _InputIterator,
876  typename unordered_map<int, int>::size_type = {},
877  _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
878  -> unordered_map<__iter_key_t<_InputIterator>,
879  __iter_val_t<_InputIterator>,
880  _Hash, _Pred, _Allocator>;
881 
882  template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
883  typename _Pred = equal_to<_Key>,
884  typename _Allocator = allocator<pair<const _Key, _Tp>>,
885  typename = _RequireNotAllocatorOrIntegral<_Hash>,
886  typename = _RequireNotAllocator<_Pred>,
887  typename = _RequireAllocator<_Allocator>>
888  unordered_map(initializer_list<pair<_Key, _Tp>>,
889  typename unordered_map<int, int>::size_type = {},
890  _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
891  -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
892 
893  template<typename _InputIterator, typename _Allocator,
894  typename = _RequireInputIter<_InputIterator>,
895  typename = _RequireAllocator<_Allocator>>
896  unordered_map(_InputIterator, _InputIterator,
897  typename unordered_map<int, int>::size_type, _Allocator)
898  -> unordered_map<__iter_key_t<_InputIterator>,
899  __iter_val_t<_InputIterator>,
900  hash<__iter_key_t<_InputIterator>>,
901  equal_to<__iter_key_t<_InputIterator>>,
902  _Allocator>;
903 
904  template<typename _InputIterator, typename _Allocator,
905  typename = _RequireInputIter<_InputIterator>,
906  typename = _RequireAllocator<_Allocator>>
907  unordered_map(_InputIterator, _InputIterator, _Allocator)
908  -> unordered_map<__iter_key_t<_InputIterator>,
909  __iter_val_t<_InputIterator>,
910  hash<__iter_key_t<_InputIterator>>,
911  equal_to<__iter_key_t<_InputIterator>>,
912  _Allocator>;
913 
914  template<typename _InputIterator, typename _Hash, typename _Allocator,
915  typename = _RequireInputIter<_InputIterator>,
916  typename = _RequireNotAllocatorOrIntegral<_Hash>,
917  typename = _RequireAllocator<_Allocator>>
918  unordered_map(_InputIterator, _InputIterator,
919  typename unordered_map<int, int>::size_type,
920  _Hash, _Allocator)
921  -> unordered_map<__iter_key_t<_InputIterator>,
922  __iter_val_t<_InputIterator>, _Hash,
923  equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
924 
925  template<typename _Key, typename _Tp, typename _Allocator,
926  typename = _RequireAllocator<_Allocator>>
927  unordered_map(initializer_list<pair<_Key, _Tp>>,
928  typename unordered_map<int, int>::size_type,
929  _Allocator)
930  -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
931 
932  template<typename _Key, typename _Tp, typename _Allocator,
933  typename = _RequireAllocator<_Allocator>>
934  unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
935  -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
936 
937  template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
938  typename = _RequireNotAllocatorOrIntegral<_Hash>,
939  typename = _RequireAllocator<_Allocator>>
940  unordered_map(initializer_list<pair<_Key, _Tp>>,
941  typename unordered_map<int, int>::size_type,
942  _Hash, _Allocator)
943  -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
944 
945 #if __glibcxx_containers_ranges // C++ >= 23
946  template<ranges::input_range _Rg,
947  __not_allocator_like _Hash = hash<__detail::__range_key_type<_Rg>>,
948  __not_allocator_like _Pred = equal_to<__detail::__range_key_type<_Rg>>,
949  __allocator_like _Allocator =
950  allocator<__detail::__range_to_alloc_type<_Rg>>>
951  unordered_map(from_range_t, _Rg&&, unordered_map<int, int>::size_type = {},
952  _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
953  -> unordered_map<__detail::__range_key_type<_Rg>,
954  __detail::__range_mapped_type<_Rg>,
955  _Hash, _Pred, _Allocator>;
956 
957  template<ranges::input_range _Rg,
958  __allocator_like _Allocator>
959  unordered_map(from_range_t, _Rg&&, unordered_map<int, int>::size_type,
960  _Allocator)
961  -> unordered_map<__detail::__range_key_type<_Rg>,
962  __detail::__range_mapped_type<_Rg>,
963  hash<__detail::__range_key_type<_Rg>>,
964  equal_to<__detail::__range_key_type<_Rg>>,
965  _Allocator>;
966 
967  template<ranges::input_range _Rg,
968  __allocator_like _Allocator>
969  unordered_map(from_range_t, _Rg&&, _Allocator)
970  -> unordered_map<__detail::__range_key_type<_Rg>,
971  __detail::__range_mapped_type<_Rg>,
972  hash<__detail::__range_key_type<_Rg>>,
973  equal_to<__detail::__range_key_type<_Rg>>,
974  _Allocator>;
975 
976  template<ranges::input_range _Rg,
977  __not_allocator_like _Hash,
978  __allocator_like _Allocator>
979  unordered_map(from_range_t, _Rg&&, unordered_map<int, int>::size_type,
980  _Hash, _Allocator)
981  -> unordered_map<__detail::__range_key_type<_Rg>,
982  __detail::__range_mapped_type<_Rg>,
983  _Hash, equal_to<__detail::__range_key_type<_Rg>>,
984  _Allocator>;
985 #endif
986 #endif
987 
988  template<typename _Key, typename _Tp, typename _Hash,
989  typename _Pred, typename _Alloc>
990  inline void
991  swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
992  unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
993  noexcept(noexcept(__x.swap(__y)))
994  { __x.swap(__y); }
995 
996  template<typename _Key, typename _Tp, typename _Hash,
997  typename _Pred, typename _Alloc>
998  inline bool
999  operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1000  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1001  { return __x._M_base() == __y._M_base(); }
1002 
1003 #if __cpp_impl_three_way_comparison < 201907L
1004  template<typename _Key, typename _Tp, typename _Hash,
1005  typename _Pred, typename _Alloc>
1006  inline bool
1007  operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1008  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1009  { return !(__x == __y); }
1010 #endif
1011 
1012  /// Class std::unordered_multimap with safety/checking/debug instrumentation.
1013  template<typename _Key, typename _Tp,
1014  typename _Hash = std::hash<_Key>,
1015  typename _Pred = std::equal_to<_Key>,
1016  typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
1017  class unordered_multimap
1018  : public __gnu_debug::_Safe_container<
1019  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
1020  __gnu_debug::_Safe_unordered_container>,
1021  public _GLIBCXX_STD_C::unordered_multimap<
1022  _Key, _Tp, _Hash, _Pred, _Alloc>
1023  {
1024  typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
1025  _Pred, _Alloc> _Base;
1026  typedef __gnu_debug::_Safe_container<unordered_multimap,
1027  _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
1028  typedef typename _Base::const_iterator _Base_const_iterator;
1029  typedef typename _Base::iterator _Base_iterator;
1030  typedef typename _Base::const_local_iterator _Base_const_local_iterator;
1031  typedef typename _Base::local_iterator _Base_local_iterator;
1032 
1033  template<typename _ItT, typename _SeqT, typename _CatT>
1034  friend class ::__gnu_debug::_Safe_iterator;
1035  template<typename _ItT, typename _SeqT>
1036  friend class ::__gnu_debug::_Safe_local_iterator;
1037 
1038  // Reference wrapper for base class. See PR libstdc++/90102.
1039  struct _Base_ref
1040  {
1041  _Base_ref(const _Base& __r) : _M_ref(__r) { }
1042 
1043  const _Base& _M_ref;
1044  };
1045 
1046  public:
1047  typedef typename _Base::size_type size_type;
1048  typedef typename _Base::hasher hasher;
1049  typedef typename _Base::key_equal key_equal;
1050  typedef typename _Base::allocator_type allocator_type;
1051 
1052  typedef typename _Base::key_type key_type;
1053  typedef typename _Base::value_type value_type;
1054  typedef typename _Base::mapped_type mapped_type;
1055 
1056  typedef typename _Base::pointer pointer;
1057  typedef typename _Base::const_pointer const_pointer;
1058  typedef typename _Base::reference reference;
1059  typedef typename _Base::const_reference const_reference;
1060  typedef __gnu_debug::_Safe_iterator<
1061  _Base_iterator, unordered_multimap> iterator;
1062  typedef __gnu_debug::_Safe_iterator<
1063  _Base_const_iterator, unordered_multimap> const_iterator;
1064  typedef __gnu_debug::_Safe_local_iterator<
1065  _Base_local_iterator, unordered_multimap> local_iterator;
1066  typedef __gnu_debug::_Safe_local_iterator<
1067  _Base_const_local_iterator, unordered_multimap> const_local_iterator;
1068  typedef typename _Base::difference_type difference_type;
1069 
1070  unordered_multimap() = default;
1071 
1072  explicit
1073  unordered_multimap(size_type __n,
1074  const hasher& __hf = hasher(),
1075  const key_equal& __eql = key_equal(),
1076  const allocator_type& __a = allocator_type())
1077  : _Base(__n, __hf, __eql, __a) { }
1078 
1079  template<typename _InputIterator>
1080  unordered_multimap(_InputIterator __first, _InputIterator __last,
1081  size_type __n = 0,
1082  const hasher& __hf = hasher(),
1083  const key_equal& __eql = key_equal(),
1084  const allocator_type& __a = allocator_type())
1085  : _Base(__gnu_debug::__base(
1086  __glibcxx_check_valid_constructor_range(__first, __last)),
1087  __gnu_debug::__base(__last), __n,
1088  __hf, __eql, __a) { }
1089 
1090  unordered_multimap(const unordered_multimap&) = default;
1091 
1092  unordered_multimap(_Base_ref __x)
1093  : _Base(__x._M_ref) { }
1094 
1095  unordered_multimap(unordered_multimap&&) = default;
1096 
1097  explicit
1098  unordered_multimap(const allocator_type& __a)
1099  : _Base(__a) { }
1100 
1101  unordered_multimap(const unordered_multimap& __umap,
1102  const allocator_type& __a)
1103  : _Base(__umap, __a) { }
1104 
1105  unordered_multimap(unordered_multimap&& __umap,
1106  const allocator_type& __a)
1107  noexcept( noexcept(_Base(std::move(__umap), __a)) )
1108  : _Safe(std::move(__umap), __a),
1109  _Base(std::move(__umap), __a) { }
1110 
1111  unordered_multimap(initializer_list<value_type> __l,
1112  size_type __n = 0,
1113  const hasher& __hf = hasher(),
1114  const key_equal& __eql = key_equal(),
1115  const allocator_type& __a = allocator_type())
1116  : _Base(__l, __n, __hf, __eql, __a) { }
1117 
1118  unordered_multimap(size_type __n, const allocator_type& __a)
1119  : unordered_multimap(__n, hasher(), key_equal(), __a)
1120  { }
1121 
1122  unordered_multimap(size_type __n, const hasher& __hf,
1123  const allocator_type& __a)
1124  : unordered_multimap(__n, __hf, key_equal(), __a)
1125  { }
1126 
1127  template<typename _InputIterator>
1128  unordered_multimap(_InputIterator __first, _InputIterator __last,
1129  const allocator_type& __a)
1130  : unordered_multimap(__first, __last, 0, hasher(), key_equal(), __a)
1131  { }
1132 
1133  template<typename _InputIterator>
1134  unordered_multimap(_InputIterator __first, _InputIterator __last,
1135  size_type __n,
1136  const allocator_type& __a)
1137  : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
1138  { }
1139 
1140  template<typename _InputIterator>
1141  unordered_multimap(_InputIterator __first, _InputIterator __last,
1142  size_type __n, const hasher& __hf,
1143  const allocator_type& __a)
1144  : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
1145  { }
1146 
1147  unordered_multimap(initializer_list<value_type> __l,
1148  const allocator_type& __a)
1149  : unordered_multimap(__l, 0, hasher(), key_equal(), __a)
1150  { }
1151 
1152  unordered_multimap(initializer_list<value_type> __l,
1153  size_type __n,
1154  const allocator_type& __a)
1155  : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
1156  { }
1157 
1158  unordered_multimap(initializer_list<value_type> __l,
1159  size_type __n, const hasher& __hf,
1160  const allocator_type& __a)
1161  : unordered_multimap(__l, __n, __hf, key_equal(), __a)
1162  { }
1163 
1164 #if __glibcxx_containers_ranges // C++ >= 23
1165  template<__detail::__container_compatible_range<value_type> _Rg>
1166  unordered_multimap(from_range_t, _Rg&& __rg,
1167  size_type __n = 0,
1168  const hasher& __hf = hasher(),
1169  const key_equal& __eql = key_equal(),
1170  const allocator_type& __a = allocator_type())
1171  : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __eql, __a)
1172  { }
1173 
1174  template<__detail::__container_compatible_range<value_type> _Rg>
1175  unordered_multimap(from_range_t, _Rg&& __rg, const allocator_type& __a)
1176  : _Base(from_range, std::forward<_Rg>(__rg), __a)
1177  { }
1178 
1179  template<__detail::__container_compatible_range<value_type> _Rg>
1180  unordered_multimap(from_range_t, _Rg&& __rg, size_type __n,
1181  const allocator_type& __a)
1182  : _Base(from_range, std::forward<_Rg>(__rg), __n, __a)
1183  { }
1184 
1185  template<__detail::__container_compatible_range<value_type> _Rg>
1186  unordered_multimap(from_range_t, _Rg&& __rg, size_type __n,
1187  const hasher& __hf, const allocator_type& __a)
1188  : _Base(from_range, std::forward<_Rg>(__rg), __n, __hf, __a)
1189  { }
1190 #endif
1191 
1192  ~unordered_multimap() = default;
1193 
1194  unordered_multimap&
1195  operator=(const unordered_multimap&) = default;
1196 
1197  unordered_multimap&
1198  operator=(unordered_multimap&&) = default;
1199 
1200  unordered_multimap&
1201  operator=(initializer_list<value_type> __l)
1202  {
1203  _Base::operator=(__l);
1204  this->_M_invalidate_all();
1205  return *this;
1206  }
1207 
1208  using _Base::get_allocator;
1209  using _Base::empty;
1210  using _Base::size;
1211  using _Base::max_size;
1212 
1213  void
1214  swap(unordered_multimap& __x)
1215  noexcept( noexcept(declval<_Base&>().swap(__x)) )
1216  {
1217  _Safe::_M_swap(__x);
1218  _Base::swap(__x);
1219  }
1220 
1221  void
1222  clear() noexcept
1223  {
1224  _Base::clear();
1225  this->_M_invalidate_all();
1226  }
1227 
1228  iterator
1229  begin() noexcept
1230  { return { _Base::begin(), this }; }
1231 
1232  const_iterator
1233  begin() const noexcept
1234  { return { _Base::begin(), this }; }
1235 
1236  iterator
1237  end() noexcept
1238  { return { _Base::end(), this }; }
1239 
1240  const_iterator
1241  end() const noexcept
1242  { return { _Base::end(), this }; }
1243 
1244  const_iterator
1245  cbegin() const noexcept
1246  { return { _Base::cbegin(), this }; }
1247 
1248  const_iterator
1249  cend() const noexcept
1250  { return { _Base::cend(), this }; }
1251 
1252  // local versions
1253  local_iterator
1254  begin(size_type __b)
1255  {
1256  __glibcxx_check_bucket_index(__b);
1257  return { _Base::begin(__b), this };
1258  }
1259 
1260  local_iterator
1261  end(size_type __b)
1262  {
1263  __glibcxx_check_bucket_index(__b);
1264  return { _Base::end(__b), this };
1265  }
1266 
1267  const_local_iterator
1268  begin(size_type __b) const
1269  {
1270  __glibcxx_check_bucket_index(__b);
1271  return { _Base::begin(__b), this };
1272  }
1273 
1274  const_local_iterator
1275  end(size_type __b) const
1276  {
1277  __glibcxx_check_bucket_index(__b);
1278  return { _Base::end(__b), this };
1279  }
1280 
1281  const_local_iterator
1282  cbegin(size_type __b) const
1283  {
1284  __glibcxx_check_bucket_index(__b);
1285  return { _Base::cbegin(__b), this };
1286  }
1287 
1288  const_local_iterator
1289  cend(size_type __b) const
1290  {
1291  __glibcxx_check_bucket_index(__b);
1292  return { _Base::cend(__b), this };
1293  }
1294 
1295  using _Base::bucket_count;
1296  using _Base::max_bucket_count;
1297  using _Base::bucket;
1298 
1299  size_type
1300  bucket_size(size_type __b) const
1301  {
1302  __glibcxx_check_bucket_index(__b);
1303  return _Base::bucket_size(__b);
1304  }
1305 
1306  float
1307  max_load_factor() const noexcept
1308  { return _Base::max_load_factor(); }
1309 
1310  void
1311  max_load_factor(float __f)
1312  {
1313  __glibcxx_check_max_load_factor(__f);
1314  _Base::max_load_factor(__f);
1315  }
1316 
1317  template<typename... _Args>
1318  iterator
1319  emplace(_Args&&... __args)
1320  {
1321  size_type __bucket_count = this->bucket_count();
1322  auto __it = _Base::emplace(std::forward<_Args>(__args)...);
1323  _M_check_rehashed(__bucket_count);
1324  return { __it, this };
1325  }
1326 
1327  template<typename... _Args>
1328  iterator
1329  emplace_hint(const_iterator __hint, _Args&&... __args)
1330  {
1331  __glibcxx_check_insert(__hint);
1332  size_type __bucket_count = this->bucket_count();
1333  auto __it = _Base::emplace_hint(__hint.base(),
1334  std::forward<_Args>(__args)...);
1335  _M_check_rehashed(__bucket_count);
1336  return { __it, this };
1337  }
1338 
1339  iterator
1340  insert(const value_type& __obj)
1341  {
1342  size_type __bucket_count = this->bucket_count();
1343  auto __it = _Base::insert(__obj);
1344  _M_check_rehashed(__bucket_count);
1345  return { __it, this };
1346  }
1347 
1348  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1349  // 2354. Unnecessary copying when inserting into maps with braced-init
1350  iterator
1351  insert(value_type&& __x)
1352  {
1353  size_type __bucket_count = this->bucket_count();
1354  auto __it = _Base::insert(std::move(__x));
1355  _M_check_rehashed(__bucket_count);
1356  return { __it, this };
1357  }
1358 
1359  iterator
1360  insert(const_iterator __hint, const value_type& __obj)
1361  {
1362  __glibcxx_check_insert(__hint);
1363  size_type __bucket_count = this->bucket_count();
1364  auto __it = _Base::insert(__hint.base(), __obj);
1365  _M_check_rehashed(__bucket_count);
1366  return { __it, this };
1367  }
1368 
1369  // _GLIBCXX_RESOLVE_LIB_DEFECTS
1370  // 2354. Unnecessary copying when inserting into maps with braced-init
1371  iterator
1372  insert(const_iterator __hint, value_type&& __x)
1373  {
1374  __glibcxx_check_insert(__hint);
1375  size_type __bucket_count = this->bucket_count();
1376  auto __it = _Base::insert(__hint.base(), std::move(__x));
1377  _M_check_rehashed(__bucket_count);
1378  return { __it, this };
1379  }
1380 
1381  template<typename _Pair, typename = typename
1382  std::enable_if<std::is_constructible<value_type,
1383  _Pair&&>::value>::type>
1384  iterator
1385  insert(_Pair&& __obj)
1386  {
1387  size_type __bucket_count = this->bucket_count();
1388  auto __it = _Base::insert(std::forward<_Pair>(__obj));
1389  _M_check_rehashed(__bucket_count);
1390  return { __it, this };
1391  }
1392 
1393  template<typename _Pair, typename = typename
1394  std::enable_if<std::is_constructible<value_type,
1395  _Pair&&>::value>::type>
1396  iterator
1397  insert(const_iterator __hint, _Pair&& __obj)
1398  {
1399  __glibcxx_check_insert(__hint);
1400  size_type __bucket_count = this->bucket_count();
1401  auto __it = _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
1402  _M_check_rehashed(__bucket_count);
1403  return { __it, this };
1404  }
1405 
1406  void
1407  insert(std::initializer_list<value_type> __l)
1408  { _Base::insert(__l); }
1409 
1410  template<typename _InputIterator>
1411  void
1412  insert(_InputIterator __first, _InputIterator __last)
1413  {
1414  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
1415  __glibcxx_check_valid_range2(__first, __last, __dist);
1416  size_type __bucket_count = this->bucket_count();
1417 
1418  if (__dist.second >= __gnu_debug::__dp_sign)
1419  _Base::insert(__gnu_debug::__unsafe(__first),
1420  __gnu_debug::__unsafe(__last));
1421  else
1422  _Base::insert(__first, __last);
1423 
1424  _M_check_rehashed(__bucket_count);
1425  }
1426 
1427 #ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1428  using node_type = typename _Base::node_type;
1429 
1430  node_type
1431  extract(const_iterator __position)
1432  {
1433  __glibcxx_check_erase(__position);
1434  return _M_extract(__position.base());
1435  }
1436 
1437  node_type
1438  extract(const key_type& __key)
1439  {
1440  const auto __position = _Base::find(__key);
1441  if (__position != _Base::end())
1442  return _M_extract(__position);
1443  return {};
1444  }
1445 
1446 # ifdef __glibcxx_associative_heterogeneous_erasure
1447  template <__heterogeneous_hash_key<unordered_multimap> _Kt>
1448  node_type
1449  extract(_Kt&& __key)
1450  {
1451  const auto __position = _Base::find(__key);
1452  if (__position != _Base::end())
1453  return _M_extract(__position);
1454  return {};
1455  }
1456 #endif
1457 
1458  iterator
1459  insert(node_type&& __nh)
1460  { return { _Base::insert(std::move(__nh)), this }; }
1461 
1462  iterator
1463  insert(const_iterator __hint, node_type&& __nh)
1464  {
1465  __glibcxx_check_insert(__hint);
1466  return { _Base::insert(__hint.base(), std::move(__nh)), this };
1467  }
1468 
1469  template<typename _H2, typename _P2>
1470  void
1471  merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1472  {
1473  auto __guard
1474  = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
1475  _Base::merge(__source);
1476  }
1477 
1478  template<typename _H2, typename _P2>
1479  void
1480  merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1481  { merge(__source); }
1482 
1483  template<typename _H2, typename _P2>
1484  void
1485  merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
1486  {
1487  auto __guard
1488  = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
1489  _Base::merge(__source);
1490  }
1491 
1492  template<typename _H2, typename _P2>
1493  void
1494  merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
1495  { merge(__source); }
1496 #endif // C++17
1497 
1498  using _Base::hash_function;
1499  using _Base::key_eq;
1500 
1501  iterator
1502  find(const key_type& __key)
1503  { return { _Base::find(__key), this }; }
1504 
1505 #ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1506  template<typename _Kt,
1507  typename = std::__has_is_transparent_t<_Hash, _Kt>,
1508  typename = std::__has_is_transparent_t<_Pred, _Kt>>
1509  iterator
1510  find(const _Kt& __k)
1511  { return { _Base::find(__k), this }; }
1512 #endif
1513 
1514  const_iterator
1515  find(const key_type& __key) const
1516  { return { _Base::find(__key), this }; }
1517 
1518 #ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1519  template<typename _Kt,
1520  typename = std::__has_is_transparent_t<_Hash, _Kt>,
1521  typename = std::__has_is_transparent_t<_Pred, _Kt>>
1522  const_iterator
1523  find(const _Kt& __k) const
1524  { return { _Base::find(__k), this }; }
1525 #endif
1526 
1527  using _Base::count;
1528 #if __cplusplus > 201703L
1529  using _Base::contains;
1530 #endif
1531 
1532  std::pair<iterator, iterator>
1533  equal_range(const key_type& __key)
1534  {
1535  auto __res = _Base::equal_range(__key);
1536  return { { __res.first, this }, { __res.second, this } };
1537  }
1538 
1539 #ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1540  template<typename _Kt,
1541  typename = std::__has_is_transparent_t<_Hash, _Kt>,
1542  typename = std::__has_is_transparent_t<_Pred, _Kt>>
1543  std::pair<iterator, iterator>
1544  equal_range(const _Kt& __k)
1545  {
1546  auto __res = _Base::equal_range(__k);
1547  return { { __res.first, this }, { __res.second, this } };
1548  }
1549 #endif
1550 
1551  std::pair<const_iterator, const_iterator>
1552  equal_range(const key_type& __key) const
1553  {
1554  auto __res = _Base::equal_range(__key);
1555  return { { __res.first, this }, { __res.second, this } };
1556  }
1557 
1558 #ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
1559  template<typename _Kt,
1560  typename = std::__has_is_transparent_t<_Hash, _Kt>,
1561  typename = std::__has_is_transparent_t<_Pred, _Kt>>
1562  std::pair<const_iterator, const_iterator>
1563  equal_range(const _Kt& __k) const
1564  {
1565  auto __res = _Base::equal_range(__k);
1566  return { { __res.first, this }, { __res.second, this } };
1567  }
1568 #endif
1569 
1570  size_type
1571  erase(const key_type& __key)
1572  {
1573  auto __victims = _Base::equal_range(__key);
1574  return _M_erase(__victims.first, __victims.second);
1575  }
1576 
1577 # ifdef __glibcxx_associative_heterogeneous_erasure
1578  template <__heterogeneous_hash_key<unordered_multimap> _Kt>
1579  size_type
1580  erase(_Kt&& __key)
1581  {
1582  auto __victims = _Base::equal_range(__key);
1583  return _M_erase(__victims.first, __victims.second);
1584  }
1585 #endif
1586 
1587  iterator
1588  erase(const_iterator __it)
1589  {
1590  __glibcxx_check_erase(__it);
1591  return { _M_erase(__it.base()), this };
1592  }
1593 
1594  _Base_iterator
1595  erase(_Base_const_iterator __it)
1596  {
1597  __glibcxx_check_erase2(__it);
1598  return _M_erase(__it);
1599  }
1600 
1601  iterator
1602  erase(iterator __it)
1603  {
1604  __glibcxx_check_erase(__it);
1605  return { _M_erase(__it.base()), this };
1606  }
1607 
1608  iterator
1609  erase(const_iterator __first, const_iterator __last)
1610  {
1611  __glibcxx_check_erase_range(__first, __last);
1612  {
1613  __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
1614  for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1615  {
1616  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1617  _M_message(__gnu_debug::__msg_valid_range)
1618  ._M_iterator(__first, "first")
1619  ._M_iterator(__last, "last"));
1620  this->_M_invalidate(__tmp, sentry);
1621  }
1622  }
1623 
1624  auto __next = _Base::erase(__first.base(), __last.base());
1625  return { __next, this };
1626  }
1627 
1628  using _Base::rehash;
1629  using _Base::reserve;
1630 
1631  _Base&
1632  _M_base() noexcept { return *this; }
1633 
1634  const _Base&
1635  _M_base() const noexcept { return *this; }
1636 
1637  private:
1638  const unordered_multimap*
1639  _M_self() const noexcept
1640  { return this; }
1641 
1642  void
1643  _M_check_rehashed(size_type __prev_count)
1644  {
1645  if (__prev_count != this->bucket_count())
1646  this->_M_invalidate_all();
1647  }
1648 
1649  _Base_iterator
1650  _M_erase(_Base_const_iterator __victim)
1651  {
1652  this->_M_invalidate(__victim);
1653  return _Base::erase(__victim);
1654  }
1655 
1656  size_type
1657  _M_erase(_Base_iterator __first, _Base_iterator __last)
1658  {
1659  size_type __ret(0);
1660  {
1661  __gnu_cxx::__scoped_lock sentry(_M_self()->_M_get_mutex());
1662  for (auto __victim = __first; __victim != __last; ++__victim)
1663  {
1664  this->_M_invalidate(__victim, sentry);
1665  ++__ret;
1666  }
1667  }
1668 
1669  _Base::erase(__first, __last);
1670  return __ret;
1671  }
1672 
1673 #ifdef __glibcxx_node_extract // >= C++17 && HOSTED
1674  node_type
1675  _M_extract(_Base_const_iterator __victim)
1676  {
1677  this->_M_invalidate(__victim);
1678  return _Base::extract(__victim);
1679  }
1680 #endif
1681  };
1682 
1683 #if __cpp_deduction_guides >= 201606
1684 
1685  template<typename _InputIterator,
1686  typename _Hash = hash<__iter_key_t<_InputIterator>>,
1687  typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
1688  typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
1689  typename = _RequireInputIter<_InputIterator>,
1690  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1691  typename = _RequireNotAllocator<_Pred>,
1692  typename = _RequireAllocator<_Allocator>>
1693  unordered_multimap(_InputIterator, _InputIterator,
1694  unordered_multimap<int, int>::size_type = {},
1695  _Hash = _Hash(), _Pred = _Pred(),
1696  _Allocator = _Allocator())
1697  -> unordered_multimap<__iter_key_t<_InputIterator>,
1698  __iter_val_t<_InputIterator>, _Hash, _Pred,
1699  _Allocator>;
1700 
1701  template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
1702  typename _Pred = equal_to<_Key>,
1703  typename _Allocator = allocator<pair<const _Key, _Tp>>,
1704  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1705  typename = _RequireNotAllocator<_Pred>,
1706  typename = _RequireAllocator<_Allocator>>
1707  unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1708  unordered_multimap<int, int>::size_type = {},
1709  _Hash = _Hash(), _Pred = _Pred(),
1710  _Allocator = _Allocator())
1711  -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
1712 
1713  template<typename _InputIterator, typename _Allocator,
1714  typename = _RequireInputIter<_InputIterator>,
1715  typename = _RequireAllocator<_Allocator>>
1716  unordered_multimap(_InputIterator, _InputIterator,
1717  unordered_multimap<int, int>::size_type, _Allocator)
1718  -> unordered_multimap<__iter_key_t<_InputIterator>,
1719  __iter_val_t<_InputIterator>,
1720  hash<__iter_key_t<_InputIterator>>,
1721  equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1722 
1723  template<typename _InputIterator, typename _Allocator,
1724  typename = _RequireInputIter<_InputIterator>,
1725  typename = _RequireAllocator<_Allocator>>
1726  unordered_multimap(_InputIterator, _InputIterator, _Allocator)
1727  -> unordered_multimap<__iter_key_t<_InputIterator>,
1728  __iter_val_t<_InputIterator>,
1729  hash<__iter_key_t<_InputIterator>>,
1730  equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1731 
1732  template<typename _InputIterator, typename _Hash, typename _Allocator,
1733  typename = _RequireInputIter<_InputIterator>,
1734  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1735  typename = _RequireAllocator<_Allocator>>
1736  unordered_multimap(_InputIterator, _InputIterator,
1737  unordered_multimap<int, int>::size_type, _Hash,
1738  _Allocator)
1739  -> unordered_multimap<__iter_key_t<_InputIterator>,
1740  __iter_val_t<_InputIterator>, _Hash,
1741  equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
1742 
1743  template<typename _Key, typename _Tp, typename _Allocator,
1744  typename = _RequireAllocator<_Allocator>>
1745  unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1746  unordered_multimap<int, int>::size_type,
1747  _Allocator)
1748  -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1749 
1750  template<typename _Key, typename _Tp, typename _Allocator,
1751  typename = _RequireAllocator<_Allocator>>
1752  unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
1753  -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
1754 
1755  template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
1756  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1757  typename = _RequireAllocator<_Allocator>>
1758  unordered_multimap(initializer_list<pair<_Key, _Tp>>,
1759  unordered_multimap<int, int>::size_type,
1760  _Hash, _Allocator)
1761  -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
1762 
1763 #if __glibcxx_containers_ranges // C++ >= 23
1764  template<ranges::input_range _Rg,
1765  __not_allocator_like _Hash = hash<__detail::__range_key_type<_Rg>>,
1766  __not_allocator_like _Pred = equal_to<__detail::__range_key_type<_Rg>>,
1767  __allocator_like _Allocator =
1768  allocator<__detail::__range_to_alloc_type<_Rg>>>
1769  unordered_multimap(from_range_t, _Rg&&,
1770  unordered_multimap<int, int>::size_type = {},
1771  _Hash = _Hash(), _Pred = _Pred(),
1772  _Allocator = _Allocator())
1773  -> unordered_multimap<__detail::__range_key_type<_Rg>,
1774  __detail::__range_mapped_type<_Rg>,
1775  _Hash, _Pred, _Allocator>;
1776 
1777  template<ranges::input_range _Rg,
1778  __allocator_like _Allocator>
1779  unordered_multimap(from_range_t, _Rg&&, unordered_multimap<int, int>::size_type,
1780  _Allocator)
1781  -> unordered_multimap<__detail::__range_key_type<_Rg>,
1782  __detail::__range_mapped_type<_Rg>,
1783  hash<__detail::__range_key_type<_Rg>>,
1784  equal_to<__detail::__range_key_type<_Rg>>,
1785  _Allocator>;
1786 
1787  template<ranges::input_range _Rg,
1788  __allocator_like _Allocator>
1789  unordered_multimap(from_range_t, _Rg&&, _Allocator)
1790  -> unordered_multimap<__detail::__range_key_type<_Rg>,
1791  __detail::__range_mapped_type<_Rg>,
1792  hash<__detail::__range_key_type<_Rg>>,
1793  equal_to<__detail::__range_key_type<_Rg>>,
1794  _Allocator>;
1795 
1796  template<ranges::input_range _Rg,
1797  __not_allocator_like _Hash,
1798  __allocator_like _Allocator>
1799  unordered_multimap(from_range_t, _Rg&&,
1800  unordered_multimap<int, int>::size_type,
1801  _Hash, _Allocator)
1802  -> unordered_multimap<__detail::__range_key_type<_Rg>,
1803  __detail::__range_mapped_type<_Rg>,
1804  _Hash, equal_to<__detail::__range_key_type<_Rg>>,
1805  _Allocator>;
1806 #endif
1807 #endif
1808 
1809  template<typename _Key, typename _Tp, typename _Hash,
1810  typename _Pred, typename _Alloc>
1811  inline void
1812  swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1813  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1814  noexcept(noexcept(__x.swap(__y)))
1815  { __x.swap(__y); }
1816 
1817  template<typename _Key, typename _Tp, typename _Hash,
1818  typename _Pred, typename _Alloc>
1819  inline bool
1820  operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1821  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1822  { return __x._M_base() == __y._M_base(); }
1823 
1824 #if __cpp_impl_three_way_comparison < 201907L
1825  template<typename _Key, typename _Tp, typename _Hash,
1826  typename _Pred, typename _Alloc>
1827  inline bool
1828  operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
1829  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
1830  { return !(__x == __y); }
1831 #endif
1832 
1833 } // namespace __debug
1834 
1835 #ifdef __glibcxx_erase_if // C++ >= 20 && HOSTED
1836 _GLIBCXX_BEGIN_NAMESPACE_VERSION
1837  template<typename _Key, typename _Tp, typename _Hash, typename _CPred,
1838  typename _Alloc, typename _Predicate>
1839  inline typename __debug::unordered_map<_Key, _Tp, _Hash,
1840  _CPred, _Alloc>::size_type
1841  erase_if(__debug::unordered_map<_Key, _Tp, _Hash, _CPred, _Alloc>& __cont,
1842  _Predicate __pred)
1843  { return __detail::__erase_nodes_if(__cont, __cont._M_base(), __pred); }
1844 
1845  template<typename _Key, typename _Tp, typename _Hash, typename _CPred,
1846  typename _Alloc, typename _Predicate>
1847  inline typename __debug::unordered_multimap<_Key, _Tp, _Hash,
1848  _CPred, _Alloc>::size_type
1849  erase_if(__debug::unordered_multimap<_Key, _Tp, _Hash, _CPred, _Alloc>& __cont,
1850  _Predicate __pred)
1851  { return __detail::__erase_nodes_if(__cont, __cont._M_base(), __pred); }
1852 _GLIBCXX_END_NAMESPACE_VERSION
1853 #endif // __glibcxx_erase_if
1854 } // namespace std
1855 
1856 #endif // C++11
1857 
1858 #endif
__glibcxx_check_insert
#define __glibcxx_check_insert(_Position)
Definition: macros.h:143
__glibcxx_check_erase_range
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:245
__glibcxx_check_erase
#define __glibcxx_check_erase(_Position)
Definition: macros.h:209
std::move
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:138
std
ISO C++ entities toplevel namespace is std.
__gnu_debug::__base
constexpr _Iterator __base(_Iterator __it)
Definition: helper_functions.h:339
std::initializer_list
initializer_list
Definition: initializer_list:48
std::hash
Primary class template hash.
Definition: functional_hash.h:106
std::enable_if
Define a member typedef type only if a boolean constant is true.
Definition: type_traits:137
std::is_constructible
is_constructible
Definition: type_traits:1239
std::allocator
The standard allocator, as per C++03 [20.4.1].
Definition: allocator.h:134
__gnu_debug::_Safe_iterator
Safe iterator wrapper.
Definition: safe_iterator.h:133
__gnu_debug::_Safe_iterator::base
constexpr _Iterator & base() noexcept
Return the underlying iterator.
Definition: safe_iterator.h:433
std::_Node_insert_return
Return type of insert(node_handle&&) on unique maps/sets.
Definition: node_handle.h:398
std::equal_to
One of the comparison functors.
Definition: stl_function.h:374
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:304
std::pair::second
_T2 second
The second member.
Definition: stl_pair.h:309
std::unordered_multimap
A standard container composed of equivalent keys (possibly containing multiple of each key value) tha...
Definition: unordered_map.h:1485
std::unordered_multimap::size_type
_Hashtable::size_type size_type
Iterator-related typedefs.
Definition: unordered_map.h:1511
std::unordered_map
A standard container composed of unique keys (containing at most one of each key value) that associat...
Definition: unordered_map.h:113
std::unordered_map::size_type
_Hashtable::size_type size_type
Iterator-related typedefs.
Definition: unordered_map.h:139
__gnu_debug::_Safe_sequence_base
Base class that supports tracking of iterators that reference a sequence.
Definition: safe_base.h:219
__gnu_debug::_Safe_sequence_base::_M_get_mutex
__gnu_cxx::__mutex & _M_get_mutex() const noexcept
__gnu_debug::_Safe_container
Safe class dealing with some allocator dependent operations.
Definition: safe_container.h:43
__gnu_debug::_Safe_unordered_container
Base class for constructing a safe unordered container type that tracks iterators that reference it.
Definition: safe_unordered_container.h:130
std::__debug::unordered_map
Class std::unordered_map with safety/checking/debug instrumentation.
Definition: debug/unordered_map:70
std::__debug::unordered_multimap
Class std::unordered_multimap with safety/checking/debug instrumentation.
Definition: debug/unordered_map:1023
__gnu_cxx::__scoped_lock
Scoped lock idiom.
Definition: concurrence.h:234