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