libstdc++
debug/unordered_set
Go to the documentation of this file.
1 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2021 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 #pragma GCC system_header
33 
34 #if __cplusplus < 201103L
35 # include <bits/c++0x_warning.h>
36 #else
37 # include <bits/c++config.h>
38 namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug {
39  template<typename _Key, typename _Hash, typename _Pred, typename _Allocator>
40  class unordered_set;
41  template<typename _Key, typename _Hash, typename _Pred, typename _Allocator>
42  class unordered_multiset;
43 } } // namespace std::__debug
44 # include <unordered_set>
45 
46 #include <debug/safe_unordered_container.h>
47 #include <debug/safe_container.h>
48 #include <debug/safe_iterator.h>
49 #include <debug/safe_local_iterator.h>
50 
51 namespace std _GLIBCXX_VISIBILITY(default)
52 {
53 namespace __debug
54 {
55  /// Class std::unordered_set with safety/checking/debug instrumentation.
56  template<typename _Value,
57  typename _Hash = std::hash<_Value>,
58  typename _Pred = std::equal_to<_Value>,
59  typename _Alloc = std::allocator<_Value> >
60  class unordered_set
61  : public __gnu_debug::_Safe_container<
62  unordered_set<_Value, _Hash, _Pred, _Alloc>, _Alloc,
63  __gnu_debug::_Safe_unordered_container>,
64  public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc>
65  {
66  typedef _GLIBCXX_STD_C::unordered_set<
67  _Value, _Hash, _Pred, _Alloc> _Base;
68  typedef __gnu_debug::_Safe_container<
69  unordered_set, _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
70 
71  typedef typename _Base::const_iterator _Base_const_iterator;
72  typedef typename _Base::iterator _Base_iterator;
73  typedef typename _Base::const_local_iterator _Base_const_local_iterator;
74  typedef typename _Base::local_iterator _Base_local_iterator;
75 
76  template<typename _ItT, typename _SeqT, typename _CatT>
77  friend class ::__gnu_debug::_Safe_iterator;
78  template<typename _ItT, typename _SeqT>
79  friend class ::__gnu_debug::_Safe_local_iterator;
80 
81  // Reference wrapper for base class. See PR libstdc++/90102.
82  struct _Base_ref
83  {
84  _Base_ref(const _Base& __r) : _M_ref(__r) { }
85 
86  const _Base& _M_ref;
87  };
88 
89  public:
90  typedef typename _Base::size_type size_type;
91  typedef typename _Base::hasher hasher;
92  typedef typename _Base::key_equal key_equal;
93  typedef typename _Base::allocator_type allocator_type;
94 
95  typedef typename _Base::key_type key_type;
96  typedef typename _Base::value_type value_type;
97 
98  typedef __gnu_debug::_Safe_iterator<
99  _Base_iterator, unordered_set> iterator;
100  typedef __gnu_debug::_Safe_iterator<
101  _Base_const_iterator, unordered_set> const_iterator;
102  typedef __gnu_debug::_Safe_local_iterator<
103  _Base_local_iterator, unordered_set> local_iterator;
104  typedef __gnu_debug::_Safe_local_iterator<
105  _Base_const_local_iterator, unordered_set> const_local_iterator;
106 
107  unordered_set() = default;
108 
109  explicit
110  unordered_set(size_type __n,
111  const hasher& __hf = hasher(),
112  const key_equal& __eql = key_equal(),
113  const allocator_type& __a = allocator_type())
114  : _Base(__n, __hf, __eql, __a) { }
115 
116  template<typename _InputIterator>
117  unordered_set(_InputIterator __first, _InputIterator __last,
118  size_type __n = 0,
119  const hasher& __hf = hasher(),
120  const key_equal& __eql = key_equal(),
121  const allocator_type& __a = allocator_type())
122  : _Base(__gnu_debug::__base(
123  __glibcxx_check_valid_constructor_range(__first, __last)),
124  __gnu_debug::__base(__last), __n,
125  __hf, __eql, __a) { }
126 
127  unordered_set(const unordered_set&) = default;
128 
129  unordered_set(_Base_ref __x)
130  : _Base(__x._M_ref) { }
131 
132  unordered_set(unordered_set&&) = default;
133 
134  explicit
135  unordered_set(const allocator_type& __a)
136  : _Base(__a) { }
137 
138  unordered_set(const unordered_set& __uset,
139  const allocator_type& __a)
140  : _Base(__uset, __a) { }
141 
142  unordered_set(unordered_set&& __uset,
143  const allocator_type& __a)
144  noexcept( noexcept(_Base(std::move(__uset._M_base()), __a)) )
145  : _Safe(std::move(__uset._M_safe()), __a),
146  _Base(std::move(__uset._M_base()), __a) { }
147 
148  unordered_set(initializer_list<value_type> __l,
149  size_type __n = 0,
150  const hasher& __hf = hasher(),
151  const key_equal& __eql = key_equal(),
152  const allocator_type& __a = allocator_type())
153  : _Base(__l, __n, __hf, __eql, __a) { }
154 
155  unordered_set(size_type __n, const allocator_type& __a)
156  : unordered_set(__n, hasher(), key_equal(), __a)
157  { }
158 
159  unordered_set(size_type __n, const hasher& __hf,
160  const allocator_type& __a)
161  : unordered_set(__n, __hf, key_equal(), __a)
162  { }
163 
164  template<typename _InputIterator>
165  unordered_set(_InputIterator __first, _InputIterator __last,
166  size_type __n,
167  const allocator_type& __a)
168  : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
169  { }
170 
171  template<typename _InputIterator>
172  unordered_set(_InputIterator __first, _InputIterator __last,
173  size_type __n, const hasher& __hf,
174  const allocator_type& __a)
175  : unordered_set(__first, __last, __n, __hf, key_equal(), __a)
176  { }
177 
178  unordered_set(initializer_list<value_type> __l,
179  size_type __n,
180  const allocator_type& __a)
181  : unordered_set(__l, __n, hasher(), key_equal(), __a)
182  { }
183 
184  unordered_set(initializer_list<value_type> __l,
185  size_type __n, const hasher& __hf,
186  const allocator_type& __a)
187  : unordered_set(__l, __n, __hf, key_equal(), __a)
188  { }
189 
190  ~unordered_set() = default;
191 
192  unordered_set&
193  operator=(const unordered_set&) = default;
194 
195  unordered_set&
196  operator=(unordered_set&&) = default;
197 
198  unordered_set&
199  operator=(initializer_list<value_type> __l)
200  {
201  _M_base() = __l;
202  this->_M_invalidate_all();
203  return *this;
204  }
205 
206  void
207  swap(unordered_set& __x)
208  noexcept( noexcept(declval<_Base&>().swap(__x)) )
209  {
210  _Safe::_M_swap(__x);
211  _Base::swap(__x);
212  }
213 
214  void
215  clear() noexcept
216  {
217  _Base::clear();
218  this->_M_invalidate_all();
219  }
220 
221  iterator
222  begin() noexcept
223  { return { _Base::begin(), this }; }
224 
225  const_iterator
226  begin() const noexcept
227  { return { _Base::begin(), this }; }
228 
229  iterator
230  end() noexcept
231  { return { _Base::end(), this }; }
232 
233  const_iterator
234  end() const noexcept
235  { return { _Base::end(), this }; }
236 
237  const_iterator
238  cbegin() const noexcept
239  { return { _Base::cbegin(), this }; }
240 
241  const_iterator
242  cend() const noexcept
243  { return { _Base::cend(), this }; }
244 
245  // local versions
246  local_iterator
247  begin(size_type __b)
248  {
249  __glibcxx_check_bucket_index(__b);
250  return { _Base::begin(__b), this };
251  }
252 
253  local_iterator
254  end(size_type __b)
255  {
256  __glibcxx_check_bucket_index(__b);
257  return { _Base::end(__b), this };
258  }
259 
260  const_local_iterator
261  begin(size_type __b) const
262  {
263  __glibcxx_check_bucket_index(__b);
264  return { _Base::begin(__b), this };
265  }
266 
267  const_local_iterator
268  end(size_type __b) const
269  {
270  __glibcxx_check_bucket_index(__b);
271  return { _Base::end(__b), this };
272  }
273 
274  const_local_iterator
275  cbegin(size_type __b) const
276  {
277  __glibcxx_check_bucket_index(__b);
278  return { _Base::cbegin(__b), this };
279  }
280 
281  const_local_iterator
282  cend(size_type __b) const
283  {
284  __glibcxx_check_bucket_index(__b);
285  return { _Base::cend(__b), this };
286  }
287 
288  size_type
289  bucket_size(size_type __b) const
290  {
291  __glibcxx_check_bucket_index(__b);
292  return _Base::bucket_size(__b);
293  }
294 
295  float
296  max_load_factor() const noexcept
297  { return _Base::max_load_factor(); }
298 
299  void
300  max_load_factor(float __f)
301  {
302  __glibcxx_check_max_load_factor(__f);
303  _Base::max_load_factor(__f);
304  }
305 
306  template<typename... _Args>
307  std::pair<iterator, bool>
308  emplace(_Args&&... __args)
309  {
310  size_type __bucket_count = this->bucket_count();
311  auto __res = _Base::emplace(std::forward<_Args>(__args)...);
312  _M_check_rehashed(__bucket_count);
313  return { { __res.first, this }, __res.second };
314  }
315 
316  template<typename... _Args>
317  iterator
318  emplace_hint(const_iterator __hint, _Args&&... __args)
319  {
320  __glibcxx_check_insert(__hint);
321  size_type __bucket_count = this->bucket_count();
322  auto __it = _Base::emplace_hint(__hint.base(),
323  std::forward<_Args>(__args)...);
324  _M_check_rehashed(__bucket_count);
325  return { __it, this };
326  }
327 
328  std::pair<iterator, bool>
329  insert(const value_type& __obj)
330  {
331  size_type __bucket_count = this->bucket_count();
332  auto __res = _Base::insert(__obj);
333  _M_check_rehashed(__bucket_count);
334  return { { __res.first, this }, __res.second };
335  }
336 
337  iterator
338  insert(const_iterator __hint, const value_type& __obj)
339  {
340  __glibcxx_check_insert(__hint);
341  size_type __bucket_count = this->bucket_count();
342  auto __it = _Base::insert(__hint.base(), __obj);
343  _M_check_rehashed(__bucket_count);
344  return { __it, this };
345  }
346 
347  std::pair<iterator, bool>
348  insert(value_type&& __obj)
349  {
350  size_type __bucket_count = this->bucket_count();
351  auto __res = _Base::insert(std::move(__obj));
352  _M_check_rehashed(__bucket_count);
353  return { { __res.first, this }, __res.second };
354  }
355 
356  iterator
357  insert(const_iterator __hint, value_type&& __obj)
358  {
359  __glibcxx_check_insert(__hint);
360  size_type __bucket_count = this->bucket_count();
361  auto __it = _Base::insert(__hint.base(), std::move(__obj));
362  _M_check_rehashed(__bucket_count);
363  return { __it, this };
364  }
365 
366  void
367  insert(std::initializer_list<value_type> __l)
368  {
369  size_type __bucket_count = this->bucket_count();
370  _Base::insert(__l);
371  _M_check_rehashed(__bucket_count);
372  }
373 
374  template<typename _InputIterator>
375  void
376  insert(_InputIterator __first, _InputIterator __last)
377  {
378  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
379  __glibcxx_check_valid_range2(__first, __last, __dist);
380  size_type __bucket_count = this->bucket_count();
381 
382  if (__dist.second >= __gnu_debug::__dp_sign)
383  _Base::insert(__gnu_debug::__unsafe(__first),
384  __gnu_debug::__unsafe(__last));
385  else
386  _Base::insert(__first, __last);
387 
388  _M_check_rehashed(__bucket_count);
389  }
390 
391 #if __cplusplus > 201402L
392  using node_type = typename _Base::node_type;
393  using insert_return_type = _Node_insert_return<iterator, node_type>;
394 
395  node_type
396  extract(const_iterator __position)
397  {
398  __glibcxx_check_erase(__position);
399  return _M_extract(__position.base());
400  }
401 
402  node_type
403  extract(const key_type& __key)
404  {
405  const auto __position = _Base::find(__key);
406  if (__position != _Base::end())
407  return _M_extract(__position);
408  return {};
409  }
410 
411  insert_return_type
412  insert(node_type&& __nh)
413  {
414  auto __ret = _Base::insert(std::move(__nh));
415  return
416  { { __ret.position, this }, __ret.inserted, std::move(__ret.node) };
417  }
418 
419  iterator
420  insert(const_iterator __hint, node_type&& __nh)
421  {
422  __glibcxx_check_insert(__hint);
423  return { _Base::insert(__hint.base(), std::move(__nh)), this };
424  }
425 
426  using _Base::merge;
427 #endif // C++17
428 
429  iterator
430  find(const key_type& __key)
431  { return { _Base::find(__key), this }; }
432 
433  const_iterator
434  find(const key_type& __key) const
435  { return { _Base::find(__key), this }; }
436 
437  std::pair<iterator, iterator>
438  equal_range(const key_type& __key)
439  {
440  auto __res = _Base::equal_range(__key);
441  return { { __res.first, this }, { __res.second, this } };
442  }
443 
444  std::pair<const_iterator, const_iterator>
445  equal_range(const key_type& __key) const
446  {
447  auto __res = _Base::equal_range(__key);
448  return { { __res.first, this }, { __res.second, this } };
449  }
450 
451  size_type
452  erase(const key_type& __key)
453  {
454  size_type __ret(0);
455  auto __victim = _Base::find(__key);
456  if (__victim != _Base::end())
457  {
458  _M_erase(__victim);
459  __ret = 1;
460  }
461  return __ret;
462  }
463 
464  iterator
465  erase(const_iterator __it)
466  {
467  __glibcxx_check_erase(__it);
468  return { _M_erase(__it.base()), this };
469  }
470 
471  iterator
472  erase(iterator __it)
473  {
474  __glibcxx_check_erase(__it);
475  return { _M_erase(__it.base()), this };
476  }
477 
478  iterator
479  erase(const_iterator __first, const_iterator __last)
480  {
481  __glibcxx_check_erase_range(__first, __last);
482  for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
483  {
484  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
485  _M_message(__gnu_debug::__msg_valid_range)
486  ._M_iterator(__first, "first")
487  ._M_iterator(__last, "last"));
488  _M_invalidate(__tmp);
489  }
490 
491  size_type __bucket_count = this->bucket_count();
492  auto __next = _Base::erase(__first.base(), __last.base());
493  _M_check_rehashed(__bucket_count);
494  return { __next, this };
495  }
496 
497  _Base&
498  _M_base() noexcept { return *this; }
499 
500  const _Base&
501  _M_base() const noexcept { return *this; }
502 
503  private:
504  void
505  _M_check_rehashed(size_type __prev_count)
506  {
507  if (__prev_count != this->bucket_count())
508  this->_M_invalidate_all();
509  }
510 
511  void
512  _M_invalidate(_Base_const_iterator __victim)
513  {
514  this->_M_invalidate_if(
515  [__victim](_Base_const_iterator __it) { return __it == __victim; });
516  this->_M_invalidate_local_if(
517  [__victim](_Base_const_local_iterator __it)
518  { return __it == __victim; });
519  }
520 
521  _Base_iterator
522  _M_erase(_Base_const_iterator __victim)
523  {
524  _M_invalidate(__victim);
525  size_type __bucket_count = this->bucket_count();
526  _Base_iterator __next = _Base::erase(__victim);
527  _M_check_rehashed(__bucket_count);
528  return __next;
529  }
530 
531 #if __cplusplus > 201402L
532  node_type
533  _M_extract(_Base_const_iterator __victim)
534  {
535  _M_invalidate(__victim);
536  return _Base::extract(__victim);
537  }
538 #endif
539  };
540 
541 #if __cpp_deduction_guides >= 201606
542 
543  template<typename _InputIterator,
544  typename _Hash =
545  hash<typename iterator_traits<_InputIterator>::value_type>,
546  typename _Pred =
547  equal_to<typename iterator_traits<_InputIterator>::value_type>,
548  typename _Allocator =
549  allocator<typename iterator_traits<_InputIterator>::value_type>,
550  typename = _RequireInputIter<_InputIterator>,
551  typename = _RequireNotAllocatorOrIntegral<_Hash>,
552  typename = _RequireNotAllocator<_Pred>,
553  typename = _RequireAllocator<_Allocator>>
554  unordered_set(_InputIterator, _InputIterator,
555  unordered_set<int>::size_type = {},
556  _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
557  -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
558  _Hash, _Pred, _Allocator>;
559 
560  template<typename _Tp, typename _Hash = hash<_Tp>,
561  typename _Pred = equal_to<_Tp>,
562  typename _Allocator = allocator<_Tp>,
563  typename = _RequireNotAllocatorOrIntegral<_Hash>,
564  typename = _RequireNotAllocator<_Pred>,
565  typename = _RequireAllocator<_Allocator>>
566  unordered_set(initializer_list<_Tp>,
567  unordered_set<int>::size_type = {},
568  _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
569  -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
570 
571  template<typename _InputIterator, typename _Allocator,
572  typename = _RequireInputIter<_InputIterator>,
573  typename = _RequireAllocator<_Allocator>>
574  unordered_set(_InputIterator, _InputIterator,
575  unordered_set<int>::size_type, _Allocator)
576  -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
577  hash<
578  typename iterator_traits<_InputIterator>::value_type>,
579  equal_to<
580  typename iterator_traits<_InputIterator>::value_type>,
581  _Allocator>;
582 
583  template<typename _InputIterator, typename _Hash, typename _Allocator,
584  typename = _RequireInputIter<_InputIterator>,
585  typename = _RequireNotAllocatorOrIntegral<_Hash>,
586  typename = _RequireAllocator<_Allocator>>
587  unordered_set(_InputIterator, _InputIterator,
588  unordered_set<int>::size_type,
589  _Hash, _Allocator)
590  -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
591  _Hash,
592  equal_to<
593  typename iterator_traits<_InputIterator>::value_type>,
594  _Allocator>;
595 
596  template<typename _Tp, typename _Allocator,
597  typename = _RequireAllocator<_Allocator>>
598  unordered_set(initializer_list<_Tp>,
599  unordered_set<int>::size_type, _Allocator)
600  -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
601 
602  template<typename _Tp, typename _Hash, typename _Allocator,
603  typename = _RequireNotAllocatorOrIntegral<_Hash>,
604  typename = _RequireAllocator<_Allocator>>
605  unordered_set(initializer_list<_Tp>,
606  unordered_set<int>::size_type, _Hash, _Allocator)
607  -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
608 
609 #endif
610 
611  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
612  inline void
613  swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
614  unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
615  noexcept(noexcept(__x.swap(__y)))
616  { __x.swap(__y); }
617 
618  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
619  inline bool
620  operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
621  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
622  { return __x._M_base() == __y._M_base(); }
623 
624 #if __cpp_impl_three_way_comparison < 201907L
625  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
626  inline bool
627  operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
628  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
629  { return !(__x == __y); }
630 #endif
631 
632  /// Class std::unordered_multiset with safety/checking/debug instrumentation.
633  template<typename _Value,
634  typename _Hash = std::hash<_Value>,
635  typename _Pred = std::equal_to<_Value>,
636  typename _Alloc = std::allocator<_Value> >
637  class unordered_multiset
638  : public __gnu_debug::_Safe_container<
639  unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
640  __gnu_debug::_Safe_unordered_container>,
641  public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
642  {
643  typedef _GLIBCXX_STD_C::unordered_multiset<
644  _Value, _Hash, _Pred, _Alloc> _Base;
645  typedef __gnu_debug::_Safe_container<unordered_multiset,
646  _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
647  typedef typename _Base::const_iterator _Base_const_iterator;
648  typedef typename _Base::iterator _Base_iterator;
649  typedef typename _Base::const_local_iterator
650  _Base_const_local_iterator;
651  typedef typename _Base::local_iterator _Base_local_iterator;
652 
653  template<typename _ItT, typename _SeqT, typename _CatT>
654  friend class ::__gnu_debug::_Safe_iterator;
655  template<typename _ItT, typename _SeqT>
656  friend class ::__gnu_debug::_Safe_local_iterator;
657 
658  // Reference wrapper for base class. See PR libstdc++/90102.
659  struct _Base_ref
660  {
661  _Base_ref(const _Base& __r) : _M_ref(__r) { }
662 
663  const _Base& _M_ref;
664  };
665 
666  public:
667  typedef typename _Base::size_type size_type;
668  typedef typename _Base::hasher hasher;
669  typedef typename _Base::key_equal key_equal;
670  typedef typename _Base::allocator_type allocator_type;
671 
672  typedef typename _Base::key_type key_type;
673  typedef typename _Base::value_type value_type;
674 
675  typedef __gnu_debug::_Safe_iterator<
676  _Base_iterator, unordered_multiset> iterator;
677  typedef __gnu_debug::_Safe_iterator<
678  _Base_const_iterator, unordered_multiset> const_iterator;
679  typedef __gnu_debug::_Safe_local_iterator<
680  _Base_local_iterator, unordered_multiset> local_iterator;
681  typedef __gnu_debug::_Safe_local_iterator<
682  _Base_const_local_iterator, unordered_multiset> const_local_iterator;
683 
684  unordered_multiset() = default;
685 
686  explicit
687  unordered_multiset(size_type __n,
688  const hasher& __hf = hasher(),
689  const key_equal& __eql = key_equal(),
690  const allocator_type& __a = allocator_type())
691  : _Base(__n, __hf, __eql, __a) { }
692 
693  template<typename _InputIterator>
694  unordered_multiset(_InputIterator __first, _InputIterator __last,
695  size_type __n = 0,
696  const hasher& __hf = hasher(),
697  const key_equal& __eql = key_equal(),
698  const allocator_type& __a = allocator_type())
699  : _Base(__gnu_debug::__base(
700  __glibcxx_check_valid_constructor_range(__first, __last)),
701  __gnu_debug::__base(__last), __n,
702  __hf, __eql, __a) { }
703 
704  unordered_multiset(const unordered_multiset&) = default;
705 
706  unordered_multiset(_Base_ref __x)
707  : _Base(__x._M_ref) { }
708 
709  unordered_multiset(unordered_multiset&&) = default;
710 
711  explicit
712  unordered_multiset(const allocator_type& __a)
713  : _Base(__a) { }
714 
715  unordered_multiset(const unordered_multiset& __uset,
716  const allocator_type& __a)
717  : _Base(__uset, __a) { }
718 
719  unordered_multiset(unordered_multiset&& __uset,
720  const allocator_type& __a)
721  noexcept( noexcept(_Base(std::move(__uset._M_base()), __a)) )
722  : _Safe(std::move(__uset._M_safe()), __a),
723  _Base(std::move(__uset._M_base()), __a) { }
724 
725  unordered_multiset(initializer_list<value_type> __l,
726  size_type __n = 0,
727  const hasher& __hf = hasher(),
728  const key_equal& __eql = key_equal(),
729  const allocator_type& __a = allocator_type())
730  : _Base(__l, __n, __hf, __eql, __a) { }
731 
732  unordered_multiset(size_type __n, const allocator_type& __a)
733  : unordered_multiset(__n, hasher(), key_equal(), __a)
734  { }
735 
736  unordered_multiset(size_type __n, const hasher& __hf,
737  const allocator_type& __a)
738  : unordered_multiset(__n, __hf, key_equal(), __a)
739  { }
740 
741  template<typename _InputIterator>
742  unordered_multiset(_InputIterator __first, _InputIterator __last,
743  size_type __n,
744  const allocator_type& __a)
745  : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
746  { }
747 
748  template<typename _InputIterator>
749  unordered_multiset(_InputIterator __first, _InputIterator __last,
750  size_type __n, const hasher& __hf,
751  const allocator_type& __a)
752  : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
753  { }
754 
755  unordered_multiset(initializer_list<value_type> __l,
756  size_type __n,
757  const allocator_type& __a)
758  : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
759  { }
760 
761  unordered_multiset(initializer_list<value_type> __l,
762  size_type __n, const hasher& __hf,
763  const allocator_type& __a)
764  : unordered_multiset(__l, __n, __hf, key_equal(), __a)
765  { }
766 
767  ~unordered_multiset() = default;
768 
769  unordered_multiset&
770  operator=(const unordered_multiset&) = default;
771 
772  unordered_multiset&
773  operator=(unordered_multiset&&) = default;
774 
775  unordered_multiset&
776  operator=(initializer_list<value_type> __l)
777  {
778  this->_M_base() = __l;
779  this->_M_invalidate_all();
780  return *this;
781  }
782 
783  void
784  swap(unordered_multiset& __x)
785  noexcept( noexcept(declval<_Base&>().swap(__x)) )
786  {
787  _Safe::_M_swap(__x);
788  _Base::swap(__x);
789  }
790 
791  void
792  clear() noexcept
793  {
794  _Base::clear();
795  this->_M_invalidate_all();
796  }
797 
798  iterator
799  begin() noexcept
800  { return { _Base::begin(), this }; }
801 
802  const_iterator
803  begin() const noexcept
804  { return { _Base::begin(), this }; }
805 
806  iterator
807  end() noexcept
808  { return { _Base::end(), this }; }
809 
810  const_iterator
811  end() const noexcept
812  { return { _Base::end(), this }; }
813 
814  const_iterator
815  cbegin() const noexcept
816  { return { _Base::cbegin(), this }; }
817 
818  const_iterator
819  cend() const noexcept
820  { return { _Base::cend(), this }; }
821 
822  // local versions
823  local_iterator
824  begin(size_type __b)
825  {
826  __glibcxx_check_bucket_index(__b);
827  return { _Base::begin(__b), this };
828  }
829 
830  local_iterator
831  end(size_type __b)
832  {
833  __glibcxx_check_bucket_index(__b);
834  return { _Base::end(__b), this };
835  }
836 
837  const_local_iterator
838  begin(size_type __b) const
839  {
840  __glibcxx_check_bucket_index(__b);
841  return { _Base::begin(__b), this };
842  }
843 
844  const_local_iterator
845  end(size_type __b) const
846  {
847  __glibcxx_check_bucket_index(__b);
848  return { _Base::end(__b), this };
849  }
850 
851  const_local_iterator
852  cbegin(size_type __b) const
853  {
854  __glibcxx_check_bucket_index(__b);
855  return { _Base::cbegin(__b), this };
856  }
857 
858  const_local_iterator
859  cend(size_type __b) const
860  {
861  __glibcxx_check_bucket_index(__b);
862  return { _Base::cend(__b), this };
863  }
864 
865  size_type
866  bucket_size(size_type __b) const
867  {
868  __glibcxx_check_bucket_index(__b);
869  return _Base::bucket_size(__b);
870  }
871 
872  float
873  max_load_factor() const noexcept
874  { return _Base::max_load_factor(); }
875 
876  void
877  max_load_factor(float __f)
878  {
879  __glibcxx_check_max_load_factor(__f);
880  _Base::max_load_factor(__f);
881  }
882 
883  template<typename... _Args>
884  iterator
885  emplace(_Args&&... __args)
886  {
887  size_type __bucket_count = this->bucket_count();
888  auto __it = _Base::emplace(std::forward<_Args>(__args)...);
889  _M_check_rehashed(__bucket_count);
890  return { __it, this };
891  }
892 
893  template<typename... _Args>
894  iterator
895  emplace_hint(const_iterator __hint, _Args&&... __args)
896  {
897  __glibcxx_check_insert(__hint);
898  size_type __bucket_count = this->bucket_count();
899  auto __it = _Base::emplace_hint(__hint.base(),
900  std::forward<_Args>(__args)...);
901  _M_check_rehashed(__bucket_count);
902  return { __it, this };
903  }
904 
905  iterator
906  insert(const value_type& __obj)
907  {
908  size_type __bucket_count = this->bucket_count();
909  auto __it = _Base::insert(__obj);
910  _M_check_rehashed(__bucket_count);
911  return { __it, this };
912  }
913 
914  iterator
915  insert(const_iterator __hint, const value_type& __obj)
916  {
917  __glibcxx_check_insert(__hint);
918  size_type __bucket_count = this->bucket_count();
919  auto __it = _Base::insert(__hint.base(), __obj);
920  _M_check_rehashed(__bucket_count);
921  return { __it, this };
922  }
923 
924  iterator
925  insert(value_type&& __obj)
926  {
927  size_type __bucket_count = this->bucket_count();
928  auto __it = _Base::insert(std::move(__obj));
929  _M_check_rehashed(__bucket_count);
930  return { __it, this };
931  }
932 
933  iterator
934  insert(const_iterator __hint, value_type&& __obj)
935  {
936  __glibcxx_check_insert(__hint);
937  size_type __bucket_count = this->bucket_count();
938  auto __it = _Base::insert(__hint.base(), std::move(__obj));
939  _M_check_rehashed(__bucket_count);
940  return { __it, this };
941  }
942 
943  void
944  insert(std::initializer_list<value_type> __l)
945  {
946  size_type __bucket_count = this->bucket_count();
947  _Base::insert(__l);
948  _M_check_rehashed(__bucket_count);
949  }
950 
951  template<typename _InputIterator>
952  void
953  insert(_InputIterator __first, _InputIterator __last)
954  {
955  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
956  __glibcxx_check_valid_range2(__first, __last, __dist);
957  size_type __bucket_count = this->bucket_count();
958 
959  if (__dist.second >= __gnu_debug::__dp_sign)
960  _Base::insert(__gnu_debug::__unsafe(__first),
961  __gnu_debug::__unsafe(__last));
962  else
963  _Base::insert(__first, __last);
964 
965  _M_check_rehashed(__bucket_count);
966  }
967 
968 #if __cplusplus > 201402L
969  using node_type = typename _Base::node_type;
970 
971  node_type
972  extract(const_iterator __position)
973  {
974  __glibcxx_check_erase(__position);
975  return _M_extract(__position.base());
976  }
977 
978  node_type
979  extract(const key_type& __key)
980  {
981  const auto __position = _Base::find(__key);
982  if (__position != _Base::end())
983  return _M_extract(__position);
984  return {};
985  }
986 
987  iterator
988  insert(node_type&& __nh)
989  { return { _Base::insert(std::move(__nh)), this }; }
990 
991  iterator
992  insert(const_iterator __hint, node_type&& __nh)
993  {
994  __glibcxx_check_insert(__hint);
995  return { _Base::insert(__hint.base(), std::move(__nh)), this };
996  }
997 
998  using _Base::merge;
999 #endif // C++17
1000 
1001  iterator
1002  find(const key_type& __key)
1003  { return { _Base::find(__key), this }; }
1004 
1005  const_iterator
1006  find(const key_type& __key) const
1007  { return { _Base::find(__key), this }; }
1008 
1009  std::pair<iterator, iterator>
1010  equal_range(const key_type& __key)
1011  {
1012  auto __res = _Base::equal_range(__key);
1013  return { { __res.first, this }, { __res.second, this } };
1014  }
1015 
1016  std::pair<const_iterator, const_iterator>
1017  equal_range(const key_type& __key) const
1018  {
1019  auto __res = _Base::equal_range(__key);
1020  return { { __res.first, this }, { __res.second, this } };
1021  }
1022 
1023  size_type
1024  erase(const key_type& __key)
1025  {
1026  size_type __ret(0);
1027  auto __pair = _Base::equal_range(__key);
1028  for (auto __victim = __pair.first; __victim != __pair.second;)
1029  {
1030  _M_invalidate(__victim);
1031  __victim = _Base::erase(__victim);
1032  ++__ret;
1033  }
1034 
1035  return __ret;
1036  }
1037 
1038  iterator
1039  erase(const_iterator __it)
1040  {
1041  __glibcxx_check_erase(__it);
1042  return { _M_erase(__it.base()), this };
1043  }
1044 
1045  iterator
1046  erase(iterator __it)
1047  {
1048  __glibcxx_check_erase(__it);
1049  return { _M_erase(__it.base()), this };
1050  }
1051 
1052  iterator
1053  erase(const_iterator __first, const_iterator __last)
1054  {
1055  __glibcxx_check_erase_range(__first, __last);
1056  for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1057  {
1058  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1059  _M_message(__gnu_debug::__msg_valid_range)
1060  ._M_iterator(__first, "first")
1061  ._M_iterator(__last, "last"));
1062  _M_invalidate(__tmp);
1063  }
1064  return { _Base::erase(__first.base(), __last.base()), this };
1065  }
1066 
1067  _Base&
1068  _M_base() noexcept { return *this; }
1069 
1070  const _Base&
1071  _M_base() const noexcept { return *this; }
1072 
1073  private:
1074  void
1075  _M_check_rehashed(size_type __prev_count)
1076  {
1077  if (__prev_count != this->bucket_count())
1078  this->_M_invalidate_all();
1079  }
1080 
1081  void
1082  _M_invalidate(_Base_const_iterator __victim)
1083  {
1084  this->_M_invalidate_if(
1085  [__victim](_Base_const_iterator __it) { return __it == __victim; });
1086  this->_M_invalidate_local_if(
1087  [__victim](_Base_const_local_iterator __it)
1088  { return __it == __victim; });
1089  }
1090 
1091  _Base_iterator
1092  _M_erase(_Base_const_iterator __victim)
1093  {
1094  _M_invalidate(__victim);
1095  size_type __bucket_count = this->bucket_count();
1096  _Base_iterator __next = _Base::erase(__victim);
1097  _M_check_rehashed(__bucket_count);
1098  return __next;
1099  }
1100 
1101 #if __cplusplus > 201402L
1102  node_type
1103  _M_extract(_Base_const_iterator __victim)
1104  {
1105  _M_invalidate(__victim);
1106  return _Base::extract(__victim);
1107  }
1108 #endif
1109  };
1110 
1111 #if __cpp_deduction_guides >= 201606
1112 
1113  template<typename _InputIterator,
1114  typename _Hash =
1115  hash<typename iterator_traits<_InputIterator>::value_type>,
1116  typename _Pred =
1117  equal_to<typename iterator_traits<_InputIterator>::value_type>,
1118  typename _Allocator =
1119  allocator<typename iterator_traits<_InputIterator>::value_type>,
1120  typename = _RequireInputIter<_InputIterator>,
1121  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1122  typename = _RequireNotAllocator<_Pred>,
1123  typename = _RequireAllocator<_Allocator>>
1124  unordered_multiset(_InputIterator, _InputIterator,
1125  unordered_multiset<int>::size_type = {},
1126  _Hash = _Hash(), _Pred = _Pred(),
1127  _Allocator = _Allocator())
1128  -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1129  _Hash, _Pred, _Allocator>;
1130 
1131  template<typename _Tp, typename _Hash = hash<_Tp>,
1132  typename _Pred = equal_to<_Tp>,
1133  typename _Allocator = allocator<_Tp>,
1134  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1135  typename = _RequireNotAllocator<_Pred>,
1136  typename = _RequireAllocator<_Allocator>>
1137  unordered_multiset(initializer_list<_Tp>,
1138  unordered_multiset<int>::size_type = {},
1139  _Hash = _Hash(), _Pred = _Pred(),
1140  _Allocator = _Allocator())
1141  -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1142 
1143  template<typename _InputIterator, typename _Allocator,
1144  typename = _RequireInputIter<_InputIterator>,
1145  typename = _RequireAllocator<_Allocator>>
1146  unordered_multiset(_InputIterator, _InputIterator,
1147  unordered_multiset<int>::size_type, _Allocator)
1148  -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1149  hash<typename
1150  iterator_traits<_InputIterator>::value_type>,
1151  equal_to<typename
1152  iterator_traits<_InputIterator>::value_type>,
1153  _Allocator>;
1154 
1155  template<typename _InputIterator, typename _Hash, typename _Allocator,
1156  typename = _RequireInputIter<_InputIterator>,
1157  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1158  typename = _RequireAllocator<_Allocator>>
1159  unordered_multiset(_InputIterator, _InputIterator,
1160  unordered_multiset<int>::size_type,
1161  _Hash, _Allocator)
1162  -> unordered_multiset<typename
1163  iterator_traits<_InputIterator>::value_type,
1164  _Hash,
1165  equal_to<
1166  typename
1167  iterator_traits<_InputIterator>::value_type>,
1168  _Allocator>;
1169 
1170  template<typename _Tp, typename _Allocator,
1171  typename = _RequireAllocator<_Allocator>>
1172  unordered_multiset(initializer_list<_Tp>,
1173  unordered_multiset<int>::size_type, _Allocator)
1174  -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1175 
1176  template<typename _Tp, typename _Hash, typename _Allocator,
1177  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1178  typename = _RequireAllocator<_Allocator>>
1179  unordered_multiset(initializer_list<_Tp>,
1180  unordered_multiset<int>::size_type, _Hash, _Allocator)
1181  -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1182 
1183 #endif
1184 
1185  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1186  inline void
1187  swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1188  unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1189  noexcept(noexcept(__x.swap(__y)))
1190  { __x.swap(__y); }
1191 
1192  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1193  inline bool
1194  operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1195  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1196  { return __x._M_base() == __y._M_base(); }
1197 
1198 #if __cpp_impl_three_way_comparison < 201907L
1199  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1200  inline bool
1201  operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1202  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1203  { return !(__x == __y); }
1204 #endif
1205 
1206 } // namespace __debug
1207 } // namespace std
1208 
1209 #endif // C++11
1210 
1211 #endif