libstdc++
debug/unordered_set
Go to the documentation of this file.
1 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2019 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  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 
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
629  : public __gnu_debug::_Safe_container<
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,
637  _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
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 
658  typedef __gnu_debug::_Safe_iterator<
659  _Base_iterator, unordered_multiset> iterator;
660  typedef __gnu_debug::_Safe_iterator<
661  _Base_const_iterator, unordered_multiset> const_iterator;
662  typedef __gnu_debug::_Safe_local_iterator<
663  _Base_local_iterator, unordered_multiset> local_iterator;
664  typedef __gnu_debug::_Safe_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  noexcept( noexcept(_Base(std::move(__uset._M_base()), __a)) )
705  : _Safe(std::move(__uset._M_safe()), __a),
706  _Base(std::move(__uset._M_base()), __a) { }
707 
708  unordered_multiset(initializer_list<value_type> __l,
709  size_type __n = 0,
710  const hasher& __hf = hasher(),
711  const key_equal& __eql = key_equal(),
712  const allocator_type& __a = allocator_type())
713  : _Base(__l, __n, __hf, __eql, __a) { }
714 
715  unordered_multiset(size_type __n, const allocator_type& __a)
716  : unordered_multiset(__n, hasher(), key_equal(), __a)
717  { }
718 
719  unordered_multiset(size_type __n, const hasher& __hf,
720  const allocator_type& __a)
721  : unordered_multiset(__n, __hf, key_equal(), __a)
722  { }
723 
724  template<typename _InputIterator>
725  unordered_multiset(_InputIterator __first, _InputIterator __last,
726  size_type __n,
727  const allocator_type& __a)
728  : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
729  { }
730 
731  template<typename _InputIterator>
732  unordered_multiset(_InputIterator __first, _InputIterator __last,
733  size_type __n, const hasher& __hf,
734  const allocator_type& __a)
735  : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
736  { }
737 
738  unordered_multiset(initializer_list<value_type> __l,
739  size_type __n,
740  const allocator_type& __a)
741  : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
742  { }
743 
744  unordered_multiset(initializer_list<value_type> __l,
745  size_type __n, const hasher& __hf,
746  const allocator_type& __a)
747  : unordered_multiset(__l, __n, __hf, key_equal(), __a)
748  { }
749 
750  ~unordered_multiset() = default;
751 
752  unordered_multiset&
753  operator=(const unordered_multiset&) = default;
754 
755  unordered_multiset&
756  operator=(unordered_multiset&&) = default;
757 
758  unordered_multiset&
759  operator=(initializer_list<value_type> __l)
760  {
761  this->_M_base() = __l;
762  this->_M_invalidate_all();
763  return *this;
764  }
765 
766  void
767  swap(unordered_multiset& __x)
768  noexcept( noexcept(declval<_Base&>().swap(__x)) )
769  {
770  _Safe::_M_swap(__x);
771  _Base::swap(__x);
772  }
773 
774  void
775  clear() noexcept
776  {
777  _Base::clear();
778  this->_M_invalidate_all();
779  }
780 
781  iterator
782  begin() noexcept
783  { return { _Base::begin(), this }; }
784 
785  const_iterator
786  begin() const noexcept
787  { return { _Base::begin(), this }; }
788 
789  iterator
790  end() noexcept
791  { return { _Base::end(), this }; }
792 
793  const_iterator
794  end() const noexcept
795  { return { _Base::end(), this }; }
796 
797  const_iterator
798  cbegin() const noexcept
799  { return { _Base::cbegin(), this }; }
800 
801  const_iterator
802  cend() const noexcept
803  { return { _Base::cend(), this }; }
804 
805  // local versions
806  local_iterator
807  begin(size_type __b)
808  {
809  __glibcxx_check_bucket_index(__b);
810  return { _Base::begin(__b), this };
811  }
812 
813  local_iterator
814  end(size_type __b)
815  {
816  __glibcxx_check_bucket_index(__b);
817  return { _Base::end(__b), this };
818  }
819 
820  const_local_iterator
821  begin(size_type __b) const
822  {
823  __glibcxx_check_bucket_index(__b);
824  return { _Base::begin(__b), this };
825  }
826 
827  const_local_iterator
828  end(size_type __b) const
829  {
830  __glibcxx_check_bucket_index(__b);
831  return { _Base::end(__b), this };
832  }
833 
834  const_local_iterator
835  cbegin(size_type __b) const
836  {
837  __glibcxx_check_bucket_index(__b);
838  return { _Base::cbegin(__b), this };
839  }
840 
841  const_local_iterator
842  cend(size_type __b) const
843  {
844  __glibcxx_check_bucket_index(__b);
845  return { _Base::cend(__b), this };
846  }
847 
848  size_type
849  bucket_size(size_type __b) const
850  {
851  __glibcxx_check_bucket_index(__b);
852  return _Base::bucket_size(__b);
853  }
854 
855  float
856  max_load_factor() const noexcept
857  { return _Base::max_load_factor(); }
858 
859  void
860  max_load_factor(float __f)
861  {
862  __glibcxx_check_max_load_factor(__f);
863  _Base::max_load_factor(__f);
864  }
865 
866  template<typename... _Args>
867  iterator
868  emplace(_Args&&... __args)
869  {
870  size_type __bucket_count = this->bucket_count();
871  auto __it = _Base::emplace(std::forward<_Args>(__args)...);
872  _M_check_rehashed(__bucket_count);
873  return { __it, this };
874  }
875 
876  template<typename... _Args>
877  iterator
878  emplace_hint(const_iterator __hint, _Args&&... __args)
879  {
880  __glibcxx_check_insert(__hint);
881  size_type __bucket_count = this->bucket_count();
882  auto __it = _Base::emplace_hint(__hint.base(),
883  std::forward<_Args>(__args)...);
884  _M_check_rehashed(__bucket_count);
885  return { __it, this };
886  }
887 
888  iterator
889  insert(const value_type& __obj)
890  {
891  size_type __bucket_count = this->bucket_count();
892  auto __it = _Base::insert(__obj);
893  _M_check_rehashed(__bucket_count);
894  return { __it, this };
895  }
896 
897  iterator
898  insert(const_iterator __hint, const value_type& __obj)
899  {
900  __glibcxx_check_insert(__hint);
901  size_type __bucket_count = this->bucket_count();
902  auto __it = _Base::insert(__hint.base(), __obj);
903  _M_check_rehashed(__bucket_count);
904  return { __it, this };
905  }
906 
907  iterator
908  insert(value_type&& __obj)
909  {
910  size_type __bucket_count = this->bucket_count();
911  auto __it = _Base::insert(std::move(__obj));
912  _M_check_rehashed(__bucket_count);
913  return { __it, this };
914  }
915 
916  iterator
917  insert(const_iterator __hint, value_type&& __obj)
918  {
919  __glibcxx_check_insert(__hint);
920  size_type __bucket_count = this->bucket_count();
921  auto __it = _Base::insert(__hint.base(), std::move(__obj));
922  _M_check_rehashed(__bucket_count);
923  return { __it, this };
924  }
925 
926  void
927  insert(std::initializer_list<value_type> __l)
928  {
929  size_type __bucket_count = this->bucket_count();
930  _Base::insert(__l);
931  _M_check_rehashed(__bucket_count);
932  }
933 
934  template<typename _InputIterator>
935  void
936  insert(_InputIterator __first, _InputIterator __last)
937  {
938  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
939  __glibcxx_check_valid_range2(__first, __last, __dist);
940  size_type __bucket_count = this->bucket_count();
941 
942  if (__dist.second >= __gnu_debug::__dp_sign)
943  _Base::insert(__gnu_debug::__unsafe(__first),
944  __gnu_debug::__unsafe(__last));
945  else
946  _Base::insert(__first, __last);
947 
948  _M_check_rehashed(__bucket_count);
949  }
950 
951 #if __cplusplus > 201402L
952  using node_type = typename _Base::node_type;
953 
954  node_type
955  extract(const_iterator __position)
956  {
957  __glibcxx_check_erase(__position);
958  return _M_extract(__position.base());
959  }
960 
961  node_type
962  extract(const key_type& __key)
963  {
964  const auto __position = _Base::find(__key);
965  if (__position != _Base::end())
966  return _M_extract(__position);
967  return {};
968  }
969 
970  iterator
971  insert(node_type&& __nh)
972  { return { _Base::insert(std::move(__nh)), this }; }
973 
974  iterator
975  insert(const_iterator __hint, node_type&& __nh)
976  {
977  __glibcxx_check_insert(__hint);
978  return { _Base::insert(__hint.base(), std::move(__nh)), this };
979  }
980 
981  using _Base::merge;
982 #endif // C++17
983 
984  iterator
985  find(const key_type& __key)
986  { return { _Base::find(__key), this }; }
987 
988  const_iterator
989  find(const key_type& __key) const
990  { return { _Base::find(__key), this }; }
991 
992  std::pair<iterator, iterator>
993  equal_range(const key_type& __key)
994  {
995  auto __res = _Base::equal_range(__key);
996  return { { __res.first, this }, { __res.second, this } };
997  }
998 
999  std::pair<const_iterator, const_iterator>
1000  equal_range(const key_type& __key) const
1001  {
1002  auto __res = _Base::equal_range(__key);
1003  return { { __res.first, this }, { __res.second, this } };
1004  }
1005 
1006  size_type
1007  erase(const key_type& __key)
1008  {
1009  size_type __ret(0);
1010  auto __pair = _Base::equal_range(__key);
1011  for (auto __victim = __pair.first; __victim != __pair.second;)
1012  {
1013  _M_invalidate(__victim);
1014  __victim = _Base::erase(__victim);
1015  ++__ret;
1016  }
1017 
1018  return __ret;
1019  }
1020 
1021  iterator
1022  erase(const_iterator __it)
1023  {
1024  __glibcxx_check_erase(__it);
1025  return { _M_erase(__it.base()), this };
1026  }
1027 
1028  iterator
1029  erase(iterator __it)
1030  {
1031  __glibcxx_check_erase(__it);
1032  return { _M_erase(__it.base()), this };
1033  }
1034 
1035  iterator
1036  erase(const_iterator __first, const_iterator __last)
1037  {
1038  __glibcxx_check_erase_range(__first, __last);
1039  for (auto __tmp = __first.base(); __tmp != __last.base(); ++__tmp)
1040  {
1041  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::cend(),
1042  _M_message(__gnu_debug::__msg_valid_range)
1043  ._M_iterator(__first, "first")
1044  ._M_iterator(__last, "last"));
1045  _M_invalidate(__tmp);
1046  }
1047  return { _Base::erase(__first.base(), __last.base()), this };
1048  }
1049 
1050  _Base&
1051  _M_base() noexcept { return *this; }
1052 
1053  const _Base&
1054  _M_base() const noexcept { return *this; }
1055 
1056  private:
1057  void
1058  _M_check_rehashed(size_type __prev_count)
1059  {
1060  if (__prev_count != this->bucket_count())
1061  this->_M_invalidate_all();
1062  }
1063 
1064  void
1065  _M_invalidate(_Base_const_iterator __victim)
1066  {
1067  this->_M_invalidate_if(
1068  [__victim](_Base_const_iterator __it) { return __it == __victim; });
1069  this->_M_invalidate_local_if(
1070  [__victim](_Base_const_local_iterator __it)
1071  { return __it._M_curr() == __victim._M_cur; });
1072  }
1073 
1074  _Base_iterator
1075  _M_erase(_Base_const_iterator __victim)
1076  {
1077  _M_invalidate(__victim);
1078  size_type __bucket_count = this->bucket_count();
1079  _Base_iterator __next = _Base::erase(__victim);
1080  _M_check_rehashed(__bucket_count);
1081  return __next;
1082  }
1083 
1084 #if __cplusplus > 201402L
1085  node_type
1086  _M_extract(_Base_const_iterator __victim)
1087  {
1088  _M_invalidate(__victim);
1089  return _Base::extract(__victim);
1090  }
1091 #endif
1092  };
1093 
1094 #if __cpp_deduction_guides >= 201606
1095 
1096  template<typename _InputIterator,
1097  typename _Hash =
1098  hash<typename iterator_traits<_InputIterator>::value_type>,
1099  typename _Pred =
1100  equal_to<typename iterator_traits<_InputIterator>::value_type>,
1101  typename _Allocator =
1102  allocator<typename iterator_traits<_InputIterator>::value_type>,
1103  typename = _RequireInputIter<_InputIterator>,
1104  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1105  typename = _RequireNotAllocator<_Pred>,
1106  typename = _RequireAllocator<_Allocator>>
1107  unordered_multiset(_InputIterator, _InputIterator,
1108  unordered_multiset<int>::size_type = {},
1109  _Hash = _Hash(), _Pred = _Pred(),
1110  _Allocator = _Allocator())
1111  -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1112  _Hash, _Pred, _Allocator>;
1113 
1114  template<typename _Tp, typename _Hash = hash<_Tp>,
1115  typename _Pred = equal_to<_Tp>,
1116  typename _Allocator = allocator<_Tp>,
1117  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1118  typename = _RequireNotAllocator<_Pred>,
1119  typename = _RequireAllocator<_Allocator>>
1120  unordered_multiset(initializer_list<_Tp>,
1121  unordered_multiset<int>::size_type = {},
1122  _Hash = _Hash(), _Pred = _Pred(),
1123  _Allocator = _Allocator())
1124  -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
1125 
1126  template<typename _InputIterator, typename _Allocator,
1127  typename = _RequireInputIter<_InputIterator>,
1128  typename = _RequireAllocator<_Allocator>>
1129  unordered_multiset(_InputIterator, _InputIterator,
1130  unordered_multiset<int>::size_type, _Allocator)
1131  -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
1132  hash<typename
1133  iterator_traits<_InputIterator>::value_type>,
1134  equal_to<typename
1135  iterator_traits<_InputIterator>::value_type>,
1136  _Allocator>;
1137 
1138  template<typename _InputIterator, typename _Hash, typename _Allocator,
1139  typename = _RequireInputIter<_InputIterator>,
1140  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1141  typename = _RequireAllocator<_Allocator>>
1142  unordered_multiset(_InputIterator, _InputIterator,
1143  unordered_multiset<int>::size_type,
1144  _Hash, _Allocator)
1145  -> unordered_multiset<typename
1146  iterator_traits<_InputIterator>::value_type,
1147  _Hash,
1148  equal_to<
1149  typename
1150  iterator_traits<_InputIterator>::value_type>,
1151  _Allocator>;
1152 
1153  template<typename _Tp, typename _Allocator,
1154  typename = _RequireAllocator<_Allocator>>
1155  unordered_multiset(initializer_list<_Tp>,
1156  unordered_multiset<int>::size_type, _Allocator)
1157  -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
1158 
1159  template<typename _Tp, typename _Hash, typename _Allocator,
1160  typename = _RequireNotAllocatorOrIntegral<_Hash>,
1161  typename = _RequireAllocator<_Allocator>>
1162  unordered_multiset(initializer_list<_Tp>,
1163  unordered_multiset<int>::size_type, _Hash, _Allocator)
1164  -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
1165 
1166 #endif
1167 
1168  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1169  inline void
1170  swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1171  unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1172  noexcept(noexcept(__x.swap(__y)))
1173  { __x.swap(__y); }
1174 
1175  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1176  inline bool
1177  operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1178  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1179  { return __x._M_base() == __y._M_base(); }
1180 
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 
1187 } // namespace __debug
1188 } // namespace std
1189 
1190 #endif // C++11
1191 
1192 #endif