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