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>
41  template<typename _Key, typename _Hash, typename _Pred, typename _Allocator>
43 } } // namespace std::__debug
44 # include <unordered_set>
45 
47 #include <debug/safe_container.h>
48 #include <debug/safe_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
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;
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 
99  _Base_iterator, unordered_set> iterator;
101  _Base_const_iterator, unordered_set> const_iterator;
103  _Base_local_iterator, unordered_set> 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>
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 
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 
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
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  {
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 #if __cplusplus > 201703L
434  template<typename _Kt,
435  typename = std::__has_is_transparent_t<_Hash, _Kt>,
436  typename = std::__has_is_transparent_t<_Pred, _Kt>>
437  iterator
438  find(const _Kt& __k)
439  { return { _Base::find(__k), this }; }
440 #endif
441 
442  const_iterator
443  find(const key_type& __key) const
444  { return { _Base::find(__key), this }; }
445 
446 #if __cplusplus > 201703L
447  template<typename _Kt,
448  typename = std::__has_is_transparent_t<_Hash, _Kt>,
449  typename = std::__has_is_transparent_t<_Pred, _Kt>>
450  const_iterator
451  find(const _Kt& __k) const
452  { return { _Base::find(__k), this }; }
453 #endif
454 
456  equal_range(const key_type& __key)
457  {
458  auto __res = _Base::equal_range(__key);
459  return { { __res.first, this }, { __res.second, this } };
460  }
461 
462 #if __cplusplus > 201703L
463  template<typename _Kt,
464  typename = std::__has_is_transparent_t<_Hash, _Kt>,
465  typename = std::__has_is_transparent_t<_Pred, _Kt>>
467  equal_range(const _Kt& __k)
468  {
469  auto __res = _Base::equal_range(__k);
470  return { { __res.first, this }, { __res.second, this } };
471  }
472 #endif
473 
475  equal_range(const key_type& __key) const
476  {
477  auto __res = _Base::equal_range(__key);
478  return { { __res.first, this }, { __res.second, this } };
479  }
480 
481 #if __cplusplus > 201703L
482  template<typename _Kt,
483  typename = std::__has_is_transparent_t<_Hash, _Kt>,
484  typename = std::__has_is_transparent_t<_Pred, _Kt>>
486  equal_range(const _Kt& __k) const
487  {
488  auto __res = _Base::equal_range(__k);
489  return { { __res.first, this }, { __res.second, this } };
490  }
491 #endif
492 
493  size_type
494  erase(const key_type& __key)
495  {
496  size_type __ret(0);
497  auto __victim = _Base::find(__key);
498  if (__victim != _Base::end())
499  {
500  _M_erase(__victim);
501  __ret = 1;
502  }
503  return __ret;
504  }
505 
506  iterator
507  erase(const_iterator __it)
508  {
509  __glibcxx_check_erase(__it);
510  return { _M_erase(__it.base()), this };
511  }
512 
513  iterator
514  erase(iterator __it)
515  {
516  __glibcxx_check_erase(__it);
517  return { _M_erase(__it.base()), this };
518  }
519 
520  iterator
521  erase(const_iterator __first, const_iterator __last)
522  {
523  __glibcxx_check_erase_range(__first, __last);
524  for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
525  {
526  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
527  _M_message(__gnu_debug::__msg_valid_range)
528  ._M_iterator(__first, "first")
529  ._M_iterator(__last, "last"));
530  _M_invalidate(__tmp);
531  }
532 
533  size_type __bucket_count = this->bucket_count();
534  auto __next = _Base::erase(__first.base(), __last.base());
535  _M_check_rehashed(__bucket_count);
536  return { __next, this };
537  }
538 
539  _Base&
540  _M_base() noexcept { return *this; }
541 
542  const _Base&
543  _M_base() const noexcept { return *this; }
544 
545  private:
546  void
547  _M_check_rehashed(size_type __prev_count)
548  {
549  if (__prev_count != this->bucket_count())
550  this->_M_invalidate_all();
551  }
552 
553  void
554  _M_invalidate(_Base_const_iterator __victim)
555  {
556  this->_M_invalidate_if(
557  [__victim](_Base_const_iterator __it) { return __it == __victim; });
559  [__victim](_Base_const_local_iterator __it)
560  { return __it == __victim; });
561  }
562 
563  _Base_iterator
564  _M_erase(_Base_const_iterator __victim)
565  {
566  _M_invalidate(__victim);
567  size_type __bucket_count = this->bucket_count();
568  _Base_iterator __next = _Base::erase(__victim);
569  _M_check_rehashed(__bucket_count);
570  return __next;
571  }
572 
573 #if __cplusplus > 201402L
574  node_type
575  _M_extract(_Base_const_iterator __victim)
576  {
577  _M_invalidate(__victim);
578  return _Base::extract(__victim);
579  }
580 #endif
581  };
582 
583 #if __cpp_deduction_guides >= 201606
584 
585  template<typename _InputIterator,
586  typename _Hash =
587  hash<typename iterator_traits<_InputIterator>::value_type>,
588  typename _Pred =
589  equal_to<typename iterator_traits<_InputIterator>::value_type>,
590  typename _Allocator =
591  allocator<typename iterator_traits<_InputIterator>::value_type>,
592  typename = _RequireInputIter<_InputIterator>,
593  typename = _RequireNotAllocatorOrIntegral<_Hash>,
594  typename = _RequireNotAllocator<_Pred>,
595  typename = _RequireAllocator<_Allocator>>
596  unordered_set(_InputIterator, _InputIterator,
597  unordered_set<int>::size_type = {},
598  _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
599  -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
600  _Hash, _Pred, _Allocator>;
601 
602  template<typename _Tp, typename _Hash = hash<_Tp>,
603  typename _Pred = equal_to<_Tp>,
604  typename _Allocator = allocator<_Tp>,
605  typename = _RequireNotAllocatorOrIntegral<_Hash>,
606  typename = _RequireNotAllocator<_Pred>,
607  typename = _RequireAllocator<_Allocator>>
608  unordered_set(initializer_list<_Tp>,
609  unordered_set<int>::size_type = {},
610  _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
611  -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
612 
613  template<typename _InputIterator, typename _Allocator,
614  typename = _RequireInputIter<_InputIterator>,
615  typename = _RequireAllocator<_Allocator>>
616  unordered_set(_InputIterator, _InputIterator,
617  unordered_set<int>::size_type, _Allocator)
618  -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
619  hash<
620  typename iterator_traits<_InputIterator>::value_type>,
621  equal_to<
622  typename iterator_traits<_InputIterator>::value_type>,
623  _Allocator>;
624 
625  template<typename _InputIterator, typename _Hash, typename _Allocator,
626  typename = _RequireInputIter<_InputIterator>,
627  typename = _RequireNotAllocatorOrIntegral<_Hash>,
628  typename = _RequireAllocator<_Allocator>>
629  unordered_set(_InputIterator, _InputIterator,
630  unordered_set<int>::size_type,
631  _Hash, _Allocator)
632  -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
633  _Hash,
634  equal_to<
635  typename iterator_traits<_InputIterator>::value_type>,
636  _Allocator>;
637 
638  template<typename _Tp, typename _Allocator,
639  typename = _RequireAllocator<_Allocator>>
640  unordered_set(initializer_list<_Tp>,
641  unordered_set<int>::size_type, _Allocator)
642  -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
643 
644  template<typename _Tp, typename _Hash, typename _Allocator,
645  typename = _RequireNotAllocatorOrIntegral<_Hash>,
646  typename = _RequireAllocator<_Allocator>>
647  unordered_set(initializer_list<_Tp>,
648  unordered_set<int>::size_type, _Hash, _Allocator)
649  -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
650 
651 #endif
652 
653  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
654  inline void
655  swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
656  unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
657  noexcept(noexcept(__x.swap(__y)))
658  { __x.swap(__y); }
659 
660  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
661  inline bool
662  operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
663  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
664  { return __x._M_base() == __y._M_base(); }
665 
666 #if __cpp_impl_three_way_comparison < 201907L
667  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
668  inline bool
669  operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
670  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
671  { return !(__x == __y); }
672 #endif
673 
674  /// Class std::unordered_multiset with safety/checking/debug instrumentation.
675  template<typename _Value,
676  typename _Hash = std::hash<_Value>,
677  typename _Pred = std::equal_to<_Value>,
678  typename _Alloc = std::allocator<_Value> >
679  class unordered_multiset
681  unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
682  __gnu_debug::_Safe_unordered_container>,
683  public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
684  {
685  typedef _GLIBCXX_STD_C::unordered_multiset<
686  _Value, _Hash, _Pred, _Alloc> _Base;
687  typedef __gnu_debug::_Safe_container<unordered_multiset,
689  typedef typename _Base::const_iterator _Base_const_iterator;
690  typedef typename _Base::iterator _Base_iterator;
691  typedef typename _Base::const_local_iterator
692  _Base_const_local_iterator;
693  typedef typename _Base::local_iterator _Base_local_iterator;
694 
695  template<typename _ItT, typename _SeqT, typename _CatT>
696  friend class ::__gnu_debug::_Safe_iterator;
697  template<typename _ItT, typename _SeqT>
698  friend class ::__gnu_debug::_Safe_local_iterator;
699 
700  // Reference wrapper for base class. See PR libstdc++/90102.
701  struct _Base_ref
702  {
703  _Base_ref(const _Base& __r) : _M_ref(__r) { }
704 
705  const _Base& _M_ref;
706  };
707 
708  public:
709  typedef typename _Base::size_type size_type;
710  typedef typename _Base::hasher hasher;
711  typedef typename _Base::key_equal key_equal;
712  typedef typename _Base::allocator_type allocator_type;
713 
714  typedef typename _Base::key_type key_type;
715  typedef typename _Base::value_type value_type;
716 
718  _Base_iterator, unordered_multiset> iterator;
720  _Base_const_iterator, unordered_multiset> const_iterator;
722  _Base_local_iterator, unordered_multiset> local_iterator;
724  _Base_const_local_iterator, unordered_multiset> const_local_iterator;
725 
726  unordered_multiset() = default;
727 
728  explicit
729  unordered_multiset(size_type __n,
730  const hasher& __hf = hasher(),
731  const key_equal& __eql = key_equal(),
732  const allocator_type& __a = allocator_type())
733  : _Base(__n, __hf, __eql, __a) { }
734 
735  template<typename _InputIterator>
736  unordered_multiset(_InputIterator __first, _InputIterator __last,
737  size_type __n = 0,
738  const hasher& __hf = hasher(),
739  const key_equal& __eql = key_equal(),
740  const allocator_type& __a = allocator_type())
741  : _Base(__gnu_debug::__base(
742  __glibcxx_check_valid_constructor_range(__first, __last)),
743  __gnu_debug::__base(__last), __n,
744  __hf, __eql, __a) { }
745 
746  unordered_multiset(const unordered_multiset&) = default;
747 
748  unordered_multiset(_Base_ref __x)
749  : _Base(__x._M_ref) { }
750 
751  unordered_multiset(unordered_multiset&&) = default;
752 
753  explicit
754  unordered_multiset(const allocator_type& __a)
755  : _Base(__a) { }
756 
757  unordered_multiset(const unordered_multiset& __uset,
758  const allocator_type& __a)
759  : _Base(__uset, __a) { }
760 
761  unordered_multiset(unordered_multiset&& __uset,
762  const allocator_type& __a)
763  noexcept( noexcept(_Base(std::move(__uset._M_base()), __a)) )
764  : _Safe(std::move(__uset._M_safe()), __a),
765  _Base(std::move(__uset._M_base()), __a) { }
766 
767  unordered_multiset(initializer_list<value_type> __l,
768  size_type __n = 0,
769  const hasher& __hf = hasher(),
770  const key_equal& __eql = key_equal(),
771  const allocator_type& __a = allocator_type())
772  : _Base(__l, __n, __hf, __eql, __a) { }
773 
774  unordered_multiset(size_type __n, const allocator_type& __a)
775  : unordered_multiset(__n, hasher(), key_equal(), __a)
776  { }
777 
778  unordered_multiset(size_type __n, const hasher& __hf,
779  const allocator_type& __a)
780  : unordered_multiset(__n, __hf, key_equal(), __a)
781  { }
782 
783  template<typename _InputIterator>
784  unordered_multiset(_InputIterator __first, _InputIterator __last,
785  size_type __n,
786  const allocator_type& __a)
787  : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
788  { }
789 
790  template<typename _InputIterator>
791  unordered_multiset(_InputIterator __first, _InputIterator __last,
792  size_type __n, const hasher& __hf,
793  const allocator_type& __a)
794  : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
795  { }
796 
797  unordered_multiset(initializer_list<value_type> __l,
798  size_type __n,
799  const allocator_type& __a)
800  : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
801  { }
802 
803  unordered_multiset(initializer_list<value_type> __l,
804  size_type __n, const hasher& __hf,
805  const allocator_type& __a)
806  : unordered_multiset(__l, __n, __hf, key_equal(), __a)
807  { }
808 
809  ~unordered_multiset() = default;
810 
811  unordered_multiset&
812  operator=(const unordered_multiset&) = default;
813 
814  unordered_multiset&
815  operator=(unordered_multiset&&) = default;
816 
817  unordered_multiset&
818  operator=(initializer_list<value_type> __l)
819  {
820  this->_M_base() = __l;
821  this->_M_invalidate_all();
822  return *this;
823  }
824 
825  void
826  swap(unordered_multiset& __x)
827  noexcept( noexcept(declval<_Base&>().swap(__x)) )
828  {
829  _Safe::_M_swap(__x);
830  _Base::swap(__x);
831  }
832 
833  void
834  clear() noexcept
835  {
836  _Base::clear();
837  this->_M_invalidate_all();
838  }
839 
840  iterator
841  begin() noexcept
842  { return { _Base::begin(), this }; }
843 
844  const_iterator
845  begin() const noexcept
846  { return { _Base::begin(), this }; }
847 
848  iterator
849  end() noexcept
850  { return { _Base::end(), this }; }
851 
852  const_iterator
853  end() const noexcept
854  { return { _Base::end(), this }; }
855 
856  const_iterator
857  cbegin() const noexcept
858  { return { _Base::cbegin(), this }; }
859 
860  const_iterator
861  cend() const noexcept
862  { return { _Base::cend(), this }; }
863 
864  // local versions
865  local_iterator
866  begin(size_type __b)
867  {
868  __glibcxx_check_bucket_index(__b);
869  return { _Base::begin(__b), this };
870  }
871 
872  local_iterator
873  end(size_type __b)
874  {
875  __glibcxx_check_bucket_index(__b);
876  return { _Base::end(__b), this };
877  }
878 
879  const_local_iterator
880  begin(size_type __b) const
881  {
882  __glibcxx_check_bucket_index(__b);
883  return { _Base::begin(__b), this };
884  }
885 
886  const_local_iterator
887  end(size_type __b) const
888  {
889  __glibcxx_check_bucket_index(__b);
890  return { _Base::end(__b), this };
891  }
892 
893  const_local_iterator
894  cbegin(size_type __b) const
895  {
896  __glibcxx_check_bucket_index(__b);
897  return { _Base::cbegin(__b), this };
898  }
899 
900  const_local_iterator
901  cend(size_type __b) const
902  {
903  __glibcxx_check_bucket_index(__b);
904  return { _Base::cend(__b), this };
905  }
906 
907  size_type
908  bucket_size(size_type __b) const
909  {
910  __glibcxx_check_bucket_index(__b);
911  return _Base::bucket_size(__b);
912  }
913 
914  float
915  max_load_factor() const noexcept
916  { return _Base::max_load_factor(); }
917 
918  void
919  max_load_factor(float __f)
920  {
921  __glibcxx_check_max_load_factor(__f);
922  _Base::max_load_factor(__f);
923  }
924 
925  template<typename... _Args>
926  iterator
927  emplace(_Args&&... __args)
928  {
929  size_type __bucket_count = this->bucket_count();
930  auto __it = _Base::emplace(std::forward<_Args>(__args)...);
931  _M_check_rehashed(__bucket_count);
932  return { __it, this };
933  }
934 
935  template<typename... _Args>
936  iterator
937  emplace_hint(const_iterator __hint, _Args&&... __args)
938  {
939  __glibcxx_check_insert(__hint);
940  size_type __bucket_count = this->bucket_count();
941  auto __it = _Base::emplace_hint(__hint.base(),
942  std::forward<_Args>(__args)...);
943  _M_check_rehashed(__bucket_count);
944  return { __it, this };
945  }
946 
947  iterator
948  insert(const value_type& __obj)
949  {
950  size_type __bucket_count = this->bucket_count();
951  auto __it = _Base::insert(__obj);
952  _M_check_rehashed(__bucket_count);
953  return { __it, this };
954  }
955 
956  iterator
957  insert(const_iterator __hint, const value_type& __obj)
958  {
959  __glibcxx_check_insert(__hint);
960  size_type __bucket_count = this->bucket_count();
961  auto __it = _Base::insert(__hint.base(), __obj);
962  _M_check_rehashed(__bucket_count);
963  return { __it, this };
964  }
965 
966  iterator
967  insert(value_type&& __obj)
968  {
969  size_type __bucket_count = this->bucket_count();
970  auto __it = _Base::insert(std::move(__obj));
971  _M_check_rehashed(__bucket_count);
972  return { __it, this };
973  }
974 
975  iterator
976  insert(const_iterator __hint, value_type&& __obj)
977  {
978  __glibcxx_check_insert(__hint);
979  size_type __bucket_count = this->bucket_count();
980  auto __it = _Base::insert(__hint.base(), std::move(__obj));
981  _M_check_rehashed(__bucket_count);
982  return { __it, this };
983  }
984 
985  void
987  {
988  size_type __bucket_count = this->bucket_count();
989  _Base::insert(__l);
990  _M_check_rehashed(__bucket_count);
991  }
992 
993  template<typename _InputIterator>
994  void
995  insert(_InputIterator __first, _InputIterator __last)
996  {
998  __glibcxx_check_valid_range2(__first, __last, __dist);
999  size_type __bucket_count = this->bucket_count();
1000 
1001  if (__dist.second >= __gnu_debug::__dp_sign)
1002  _Base::insert(__gnu_debug::__unsafe(__first),
1003  __gnu_debug::__unsafe(__last));
1004  else
1005  _Base::insert(__first, __last);
1006 
1007  _M_check_rehashed(__bucket_count);
1008  }
1009 
1010 #if __cplusplus > 201402L
1011  using node_type = typename _Base::node_type;
1012 
1013  node_type
1014  extract(const_iterator __position)
1015  {
1016  __glibcxx_check_erase(__position);
1017  return _M_extract(__position.base());
1018  }
1019 
1020  node_type
1021  extract(const key_type& __key)
1022  {
1023  const auto __position = _Base::find(__key);
1024  if (__position != _Base::end())
1025  return _M_extract(__position);
1026  return {};
1027  }
1028 
1029  iterator
1030  insert(node_type&& __nh)
1031  { return { _Base::insert(std::move(__nh)), this }; }
1032 
1033  iterator
1034  insert(const_iterator __hint, node_type&& __nh)
1035  {
1036  __glibcxx_check_insert(__hint);
1037  return { _Base::insert(__hint.base(), std::move(__nh)), this };
1038  }
1039 
1040  using _Base::merge;
1041 #endif // C++17
1042 
1043  iterator
1044  find(const key_type& __key)
1045  { return { _Base::find(__key), this }; }
1046 
1047 #if __cplusplus > 201703L
1048  template<typename _Kt,
1049  typename = std::__has_is_transparent_t<_Hash, _Kt>,
1050  typename = std::__has_is_transparent_t<_Pred, _Kt>>
1051  iterator
1052  find(const _Kt& __k)
1053  { return { _Base::find(__k), this }; }
1054 #endif
1055 
1056  const_iterator
1057  find(const key_type& __key) const
1058  { return { _Base::find(__key), this }; }
1059 
1060 #if __cplusplus > 201703L
1061  template<typename _Kt,
1062  typename = std::__has_is_transparent_t<_Hash, _Kt>,
1063  typename = std::__has_is_transparent_t<_Pred, _Kt>>
1064  const_iterator
1065  find(const _Kt& __k) const
1066  { return { _Base::find(__k), this }; }
1067 #endif
1068 
1070  equal_range(const key_type& __key)
1071  {
1072  auto __res = _Base::equal_range(__key);
1073  return { { __res.first, this }, { __res.second, this } };
1074  }
1075 
1076 #if __cplusplus > 201703L
1077  template<typename _Kt,
1078  typename = std::__has_is_transparent_t<_Hash, _Kt>,
1079  typename = std::__has_is_transparent_t<_Pred, _Kt>>
1081  equal_range(const _Kt& __k)
1082  {
1083  auto __res = _Base::equal_range(__k);
1084  return { { __res.first, this }, { __res.second, this } };
1085  }
1086 #endif
1087 
1089  equal_range(const key_type& __key) const
1090  {
1091  auto __res = _Base::equal_range(__key);
1092  return { { __res.first, this }, { __res.second, this } };
1093  }
1094 
1095 #if __cplusplus > 201703L
1096  template<typename _Kt,
1097  typename = std::__has_is_transparent_t<_Hash, _Kt>,
1098  typename = std::__has_is_transparent_t<_Pred, _Kt>>
1100  equal_range(const _Kt& __k) const
1101  {
1102  auto __res = _Base::equal_range(__k);
1103  return { { __res.first, this }, { __res.second, this } };
1104  }
1105 #endif
1106 
1107  size_type
1108  erase(const key_type& __key)
1109  {
1110  size_type __ret(0);
1111  auto __pair = _Base::equal_range(__key);
1112  for (auto __victim = __pair.first; __victim != __pair.second;)
1113  {
1114  _M_invalidate(__victim);
1115  __victim = _Base::erase(__victim);
1116  ++__ret;
1117  }
1118 
1119  return __ret;
1120  }
1121 
1122  iterator
1123  erase(const_iterator __it)
1124  {
1125  __glibcxx_check_erase(__it);
1126  return { _M_erase(__it.base()), this };
1127  }
1128 
1129  iterator
1130  erase(iterator __it)
1131  {
1132  __glibcxx_check_erase(__it);
1133  return { _M_erase(__it.base()), this };
1134  }
1135 
1136  iterator
1137  erase(const_iterator __first, const_iterator __last)
1138  {
1139  __glibcxx_check_erase_range(__first, __last);
1140  for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1141  {
1142  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1143  _M_message(__gnu_debug::__msg_valid_range)
1144  ._M_iterator(__first, "first")
1145  ._M_iterator(__last, "last"));
1146  _M_invalidate(__tmp);
1147  }
1148  return { _Base::erase(__first.base(), __last.base()), this };
1149  }
1150 
1151  _Base&
1152  _M_base() noexcept { return *this; }
1153 
1154  const _Base&
1155  _M_base() const noexcept { return *this; }
1156 
1157  private:
1158  void
1159  _M_check_rehashed(size_type __prev_count)
1160  {
1161  if (__prev_count != this->bucket_count())
1162  this->_M_invalidate_all();
1163  }
1164 
1165  void
1166  _M_invalidate(_Base_const_iterator __victim)
1167  {
1168  this->_M_invalidate_if(
1169  [__victim](_Base_const_iterator __it) { return __it == __victim; });
1170  this->_M_invalidate_local_if(
1171  [__victim](_Base_const_local_iterator __it)
1172  { return __it == __victim; });
1173  }
1174 
1175  _Base_iterator
1176  _M_erase(_Base_const_iterator __victim)
1177  {
1178  _M_invalidate(__victim);
1179  size_type __bucket_count = this->bucket_count();
1180  _Base_iterator __next = _Base::erase(__victim);
1181  _M_check_rehashed(__bucket_count);
1182  return __next;
1183  }
1184 
1185 #if __cplusplus > 201402L
1186  node_type
1187  _M_extract(_Base_const_iterator __victim)
1188  {
1189  _M_invalidate(__victim);
1190  return _Base::extract(__victim);
1191  }
1192 #endif
1193  };
1194 
1195 #if __cpp_deduction_guides >= 201606
1196 
1197  template<typename _InputIterator,
1198  typename _Hash =
1199  hash<typename iterator_traits<_InputIterator>::value_type>,
1200  typename _Pred =
1201  equal_to<typename iterator_traits<_InputIterator>::value_type>,
1202  typename _Allocator =
1203  allocator<typename iterator_traits<_InputIterator>::value_type>,
1204  typename = _RequireInputIter<_InputIterator>,
1205  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1206  typename = _RequireNotAllocator<_Pred>,
1207  typename = _RequireAllocator<_Allocator>>
1208  unordered_multiset(_InputIterator, _InputIterator,
1209  unordered_multiset<int>::size_type = {},
1210  _Hash = _Hash(), _Pred = _Pred(),
1211  _Allocator = _Allocator())
1212  -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1213  _Hash, _Pred, _Allocator>;
1214 
1215  template<typename _Tp, typename _Hash = hash<_Tp>,
1216  typename _Pred = equal_to<_Tp>,
1217  typename _Allocator = allocator<_Tp>,
1218  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1219  typename = _RequireNotAllocator<_Pred>,
1220  typename = _RequireAllocator<_Allocator>>
1221  unordered_multiset(initializer_list<_Tp>,
1222  unordered_multiset<int>::size_type = {},
1223  _Hash = _Hash(), _Pred = _Pred(),
1224  _Allocator = _Allocator())
1225  -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1226 
1227  template<typename _InputIterator, typename _Allocator,
1228  typename = _RequireInputIter<_InputIterator>,
1229  typename = _RequireAllocator<_Allocator>>
1230  unordered_multiset(_InputIterator, _InputIterator,
1231  unordered_multiset<int>::size_type, _Allocator)
1232  -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1233  hash<typename
1234  iterator_traits<_InputIterator>::value_type>,
1235  equal_to<typename
1236  iterator_traits<_InputIterator>::value_type>,
1237  _Allocator>;
1238 
1239  template<typename _InputIterator, typename _Hash, typename _Allocator,
1240  typename = _RequireInputIter<_InputIterator>,
1241  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1242  typename = _RequireAllocator<_Allocator>>
1243  unordered_multiset(_InputIterator, _InputIterator,
1244  unordered_multiset<int>::size_type,
1245  _Hash, _Allocator)
1246  -> unordered_multiset<typename
1247  iterator_traits<_InputIterator>::value_type,
1248  _Hash,
1249  equal_to<
1250  typename
1251  iterator_traits<_InputIterator>::value_type>,
1252  _Allocator>;
1253 
1254  template<typename _Tp, typename _Allocator,
1255  typename = _RequireAllocator<_Allocator>>
1256  unordered_multiset(initializer_list<_Tp>,
1257  unordered_multiset<int>::size_type, _Allocator)
1258  -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1259 
1260  template<typename _Tp, typename _Hash, typename _Allocator,
1261  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1262  typename = _RequireAllocator<_Allocator>>
1263  unordered_multiset(initializer_list<_Tp>,
1264  unordered_multiset<int>::size_type, _Hash, _Allocator)
1265  -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1266 
1267 #endif
1268 
1269  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1270  inline void
1271  swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1272  unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1273  noexcept(noexcept(__x.swap(__y)))
1274  { __x.swap(__y); }
1275 
1276  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1277  inline bool
1278  operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1279  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1280  { return __x._M_base() == __y._M_base(); }
1281 
1282 #if __cpp_impl_three_way_comparison < 201907L
1283  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1284  inline bool
1285  operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1286  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1287  { return !(__x == __y); }
1288 #endif
1289 
1290 } // namespace __debug
1291 } // namespace std
1292 
1293 #endif // C++11
1294 
1295 #endif
constexpr auto cbegin(const _Container &__cont) noexcept(noexcept(std::begin(__cont))) -> decltype(std::begin(__cont))
Return an iterator pointing to the first element of the const container.
Definition: range_access.h:119
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
Definition: move.h:104
Primary class template hash.
Definition: string_view:686
Safe iterator wrapper.
Definition: formatter.h:84
A standard container composed of unique keys (containing at most one of each key value) in which the ...
Definition: unordered_set.h:97
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:211
One of the comparison functors.
Definition: stl_function.h:331
_Tp * begin(valarray< _Tp > &__va)
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1214
Class std::unordered_set with safety/checking/debug instrumentation.
_Tp * end(valarray< _Tp > &__va)
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1234
_Iterator & base() noexcept
Return the underlying iterator.
#define __glibcxx_check_erase(_Position)
Definition: macros.h:212
Base class for constructing a safe unordered container type that tracks iterators that reference it...
The standard allocator, as per C++03 [20.4.1].
Definition: allocator.h:138
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
Definition: range_access.h:130
Safe iterator wrapper.
Definition: debug.h:61
constexpr _Iterator __base(_Iterator __it)
Safe class dealing with some allocator dependent operations.
_T2 second
The second member.
Definition: stl_pair.h:218
#define __glibcxx_check_erase_range(_First, _Last)
Definition: macros.h:240
initializer_list
#define __glibcxx_check_insert(_Position)
Definition: macros.h:146
Class std::unordered_multiset with safety/checking/debug instrumentation.
auto_ptr & operator=(auto_ptr &__a)
auto_ptr assignment operator.
Definition: auto_ptr.h:128