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