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