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