libstdc++
debug/unordered_set
Go to the documentation of this file.
1 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2017 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 
376  struct insert_return_type
377  {
378  bool inserted;
379  iterator position;
380  node_type node;
381  };
382 
383  node_type
384  extract(const_iterator __position)
385  {
386  __glibcxx_check_erase(__position);
387  _Base_const_iterator __victim = __position.base();
388  this->_M_invalidate_if(
389  [__victim](_Base_const_iterator __it) { return __it == __victim; }
390  );
391  this->_M_invalidate_local_if(
392  [__victim](_Base_const_local_iterator __it) {
393  return __it._M_curr() == __victim._M_cur;
394  });
395  return _Base::extract(__position.base());
396  }
397 
398  node_type
399  extract(const key_type& __key)
400  {
401  const auto __position = find(__key);
402  if (__position != end())
403  return extract(__position);
404  return {};
405  }
406 
407  insert_return_type
408  insert(node_type&& __nh)
409  {
410  auto __ret = _Base::insert(std::move(__nh));
411  iterator __pos = iterator(__ret.position, this);
412  return { __ret.inserted, __pos, std::move(__ret.node) };
413  }
414 
415  iterator
416  insert(const_iterator __hint, node_type&& __nh)
417  {
418  __glibcxx_check_insert(__hint);
419  return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
420  }
421 
422  using _Base::merge;
423 #endif // C++17
424 
425  iterator
426  find(const key_type& __key)
427  { return iterator(_Base::find(__key), this); }
428 
429  const_iterator
430  find(const key_type& __key) const
431  { return const_iterator(_Base::find(__key), this); }
432 
433  std::pair<iterator, iterator>
434  equal_range(const key_type& __key)
435  {
436  std::pair<_Base_iterator, _Base_iterator> __res
437  = _Base::equal_range(__key);
438  return std::make_pair(iterator(__res.first, this),
439  iterator(__res.second, this));
440  }
441 
442  std::pair<const_iterator, const_iterator>
443  equal_range(const key_type& __key) const
444  {
445  std::pair<_Base_const_iterator, _Base_const_iterator>
446  __res = _Base::equal_range(__key);
447  return std::make_pair(const_iterator(__res.first, this),
448  const_iterator(__res.second, this));
449  }
450 
451  size_type
452  erase(const key_type& __key)
453  {
454  size_type __ret(0);
455  _Base_iterator __victim(_Base::find(__key));
456  if (__victim != _Base::end())
457  {
458  this->_M_invalidate_if(
459  [__victim](_Base_const_iterator __it)
460  { return __it == __victim; });
461  this->_M_invalidate_local_if(
462  [__victim](_Base_const_local_iterator __it)
463  { return __it._M_curr() == __victim._M_cur; });
464  size_type __bucket_count = this->bucket_count();
465  _Base::erase(__victim);
466  _M_check_rehashed(__bucket_count);
467  __ret = 1;
468  }
469  return __ret;
470  }
471 
472  iterator
473  erase(const_iterator __it)
474  {
475  __glibcxx_check_erase(__it);
476  _Base_const_iterator __victim = __it.base();
477  this->_M_invalidate_if(
478  [__victim](_Base_const_iterator __it)
479  { return __it == __victim; });
480  this->_M_invalidate_local_if(
481  [__victim](_Base_const_local_iterator __it)
482  { return __it._M_curr() == __victim._M_cur; });
483  size_type __bucket_count = this->bucket_count();
484  _Base_iterator __next = _Base::erase(__it.base());
485  _M_check_rehashed(__bucket_count);
486  return iterator(__next, this);
487  }
488 
489  iterator
490  erase(iterator __it)
491  { return erase(const_iterator(__it)); }
492 
493  iterator
494  erase(const_iterator __first, const_iterator __last)
495  {
496  __glibcxx_check_erase_range(__first, __last);
497  for (_Base_const_iterator __tmp = __first.base();
498  __tmp != __last.base(); ++__tmp)
499  {
500  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
501  _M_message(__gnu_debug::__msg_valid_range)
502  ._M_iterator(__first, "first")
503  ._M_iterator(__last, "last"));
504  this->_M_invalidate_if(
505  [__tmp](_Base_const_iterator __it)
506  { return __it == __tmp; });
507  this->_M_invalidate_local_if(
508  [__tmp](_Base_const_local_iterator __it)
509  { return __it._M_curr() == __tmp._M_cur; });
510  }
511  size_type __bucket_count = this->bucket_count();
512  _Base_iterator __next = _Base::erase(__first.base(),
513  __last.base());
514  _M_check_rehashed(__bucket_count);
515  return iterator(__next, this);
516  }
517 
518  _Base&
519  _M_base() noexcept { return *this; }
520 
521  const _Base&
522  _M_base() const noexcept { return *this; }
523 
524  private:
525  void
526  _M_check_rehashed(size_type __prev_count)
527  {
528  if (__prev_count != this->bucket_count())
529  this->_M_invalidate_locals();
530  }
531  };
532 
533  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
534  inline void
535  swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
536  unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
537  noexcept(noexcept(__x.swap(__y)))
538  { __x.swap(__y); }
539 
540  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
541  inline bool
542  operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
543  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
544  { return __x._M_base() == __y._M_base(); }
545 
546  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
547  inline bool
548  operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
549  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
550  { return !(__x == __y); }
551 
552 
553  /// Class std::unordered_multiset with safety/checking/debug instrumentation.
554  template<typename _Value,
555  typename _Hash = std::hash<_Value>,
556  typename _Pred = std::equal_to<_Value>,
557  typename _Alloc = std::allocator<_Value> >
558  class unordered_multiset
559  : public __gnu_debug::_Safe_container<
560  unordered_multiset<_Value, _Hash, _Pred, _Alloc>, _Alloc,
561  __gnu_debug::_Safe_unordered_container>,
562  public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>
563  {
564  typedef _GLIBCXX_STD_C::unordered_multiset<
565  _Value, _Hash, _Pred, _Alloc> _Base;
566  typedef __gnu_debug::_Safe_container<unordered_multiset,
567  _Alloc, __gnu_debug::_Safe_unordered_container> _Safe;
568  typedef typename _Base::const_iterator _Base_const_iterator;
569  typedef typename _Base::iterator _Base_iterator;
570  typedef typename _Base::const_local_iterator
571  _Base_const_local_iterator;
572  typedef typename _Base::local_iterator _Base_local_iterator;
573 
574  public:
575  typedef typename _Base::size_type size_type;
576  typedef typename _Base::hasher hasher;
577  typedef typename _Base::key_equal key_equal;
578  typedef typename _Base::allocator_type allocator_type;
579 
580  typedef typename _Base::key_type key_type;
581  typedef typename _Base::value_type value_type;
582 
583  typedef __gnu_debug::_Safe_iterator<
584  _Base_iterator, unordered_multiset> iterator;
585  typedef __gnu_debug::_Safe_iterator<
586  _Base_const_iterator, unordered_multiset> const_iterator;
587  typedef __gnu_debug::_Safe_local_iterator<
588  _Base_local_iterator, unordered_multiset> local_iterator;
589  typedef __gnu_debug::_Safe_local_iterator<
590  _Base_const_local_iterator, unordered_multiset> const_local_iterator;
591 
592  unordered_multiset() = default;
593 
594  explicit
595  unordered_multiset(size_type __n,
596  const hasher& __hf = hasher(),
597  const key_equal& __eql = key_equal(),
598  const allocator_type& __a = allocator_type())
599  : _Base(__n, __hf, __eql, __a) { }
600 
601  template<typename _InputIterator>
602  unordered_multiset(_InputIterator __first, _InputIterator __last,
603  size_type __n = 0,
604  const hasher& __hf = hasher(),
605  const key_equal& __eql = key_equal(),
606  const allocator_type& __a = allocator_type())
607  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
608  __last)),
609  __gnu_debug::__base(__last), __n,
610  __hf, __eql, __a) { }
611 
612  unordered_multiset(const unordered_multiset&) = default;
613 
614  unordered_multiset(const _Base& __x)
615  : _Base(__x) { }
616 
617  unordered_multiset(unordered_multiset&&) = default;
618 
619  explicit
620  unordered_multiset(const allocator_type& __a)
621  : _Base(__a) { }
622 
623  unordered_multiset(const unordered_multiset& __uset,
624  const allocator_type& __a)
625  : _Base(__uset, __a) { }
626 
627  unordered_multiset(unordered_multiset&& __uset,
628  const allocator_type& __a)
629  : _Safe(std::move(__uset._M_safe()), __a),
630  _Base(std::move(__uset._M_base()), __a) { }
631 
632  unordered_multiset(initializer_list<value_type> __l,
633  size_type __n = 0,
634  const hasher& __hf = hasher(),
635  const key_equal& __eql = key_equal(),
636  const allocator_type& __a = allocator_type())
637  : _Base(__l, __n, __hf, __eql, __a) { }
638 
639  unordered_multiset(size_type __n, const allocator_type& __a)
640  : unordered_multiset(__n, hasher(), key_equal(), __a)
641  { }
642 
643  unordered_multiset(size_type __n, const hasher& __hf,
644  const allocator_type& __a)
645  : unordered_multiset(__n, __hf, key_equal(), __a)
646  { }
647 
648  template<typename _InputIterator>
649  unordered_multiset(_InputIterator __first, _InputIterator __last,
650  size_type __n,
651  const allocator_type& __a)
652  : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
653  { }
654 
655  template<typename _InputIterator>
656  unordered_multiset(_InputIterator __first, _InputIterator __last,
657  size_type __n, const hasher& __hf,
658  const allocator_type& __a)
659  : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
660  { }
661 
662  unordered_multiset(initializer_list<value_type> __l,
663  size_type __n,
664  const allocator_type& __a)
665  : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
666  { }
667 
668  unordered_multiset(initializer_list<value_type> __l,
669  size_type __n, const hasher& __hf,
670  const allocator_type& __a)
671  : unordered_multiset(__l, __n, __hf, key_equal(), __a)
672  { }
673 
674  ~unordered_multiset() = default;
675 
676  unordered_multiset&
677  operator=(const unordered_multiset&) = default;
678 
679  unordered_multiset&
680  operator=(unordered_multiset&&) = default;
681 
682  unordered_multiset&
683  operator=(initializer_list<value_type> __l)
684  {
685  this->_M_base() = __l;
686  this->_M_invalidate_all();
687  return *this;
688  }
689 
690  void
691  swap(unordered_multiset& __x)
692  noexcept( noexcept(declval<_Base&>().swap(__x)) )
693  {
694  _Safe::_M_swap(__x);
695  _Base::swap(__x);
696  }
697 
698  void
699  clear() noexcept
700  {
701  _Base::clear();
702  this->_M_invalidate_all();
703  }
704 
705  iterator
706  begin() noexcept
707  { return iterator(_Base::begin(), this); }
708 
709  const_iterator
710  begin() const noexcept
711  { return const_iterator(_Base::begin(), this); }
712 
713  iterator
714  end() noexcept
715  { return iterator(_Base::end(), this); }
716 
717  const_iterator
718  end() const noexcept
719  { return const_iterator(_Base::end(), this); }
720 
721  const_iterator
722  cbegin() const noexcept
723  { return const_iterator(_Base::begin(), this); }
724 
725  const_iterator
726  cend() const noexcept
727  { return const_iterator(_Base::end(), this); }
728 
729  // local versions
730  local_iterator
731  begin(size_type __b)
732  {
733  __glibcxx_check_bucket_index(__b);
734  return local_iterator(_Base::begin(__b), this);
735  }
736 
737  local_iterator
738  end(size_type __b)
739  {
740  __glibcxx_check_bucket_index(__b);
741  return local_iterator(_Base::end(__b), this);
742  }
743 
744  const_local_iterator
745  begin(size_type __b) const
746  {
747  __glibcxx_check_bucket_index(__b);
748  return const_local_iterator(_Base::begin(__b), this);
749  }
750 
751  const_local_iterator
752  end(size_type __b) const
753  {
754  __glibcxx_check_bucket_index(__b);
755  return const_local_iterator(_Base::end(__b), this);
756  }
757 
758  const_local_iterator
759  cbegin(size_type __b) const
760  {
761  __glibcxx_check_bucket_index(__b);
762  return const_local_iterator(_Base::cbegin(__b), this);
763  }
764 
765  const_local_iterator
766  cend(size_type __b) const
767  {
768  __glibcxx_check_bucket_index(__b);
769  return const_local_iterator(_Base::cend(__b), this);
770  }
771 
772  size_type
773  bucket_size(size_type __b) const
774  {
775  __glibcxx_check_bucket_index(__b);
776  return _Base::bucket_size(__b);
777  }
778 
779  float
780  max_load_factor() const noexcept
781  { return _Base::max_load_factor(); }
782 
783  void
784  max_load_factor(float __f)
785  {
786  __glibcxx_check_max_load_factor(__f);
787  _Base::max_load_factor(__f);
788  }
789 
790  template<typename... _Args>
791  iterator
792  emplace(_Args&&... __args)
793  {
794  size_type __bucket_count = this->bucket_count();
795  _Base_iterator __it
796  = _Base::emplace(std::forward<_Args>(__args)...);
797  _M_check_rehashed(__bucket_count);
798  return iterator(__it, this);
799  }
800 
801  template<typename... _Args>
802  iterator
803  emplace_hint(const_iterator __hint, _Args&&... __args)
804  {
805  __glibcxx_check_insert(__hint);
806  size_type __bucket_count = this->bucket_count();
807  _Base_iterator __it = _Base::emplace_hint(__hint.base(),
808  std::forward<_Args>(__args)...);
809  _M_check_rehashed(__bucket_count);
810  return iterator(__it, this);
811  }
812 
813  iterator
814  insert(const value_type& __obj)
815  {
816  size_type __bucket_count = this->bucket_count();
817  _Base_iterator __it = _Base::insert(__obj);
818  _M_check_rehashed(__bucket_count);
819  return iterator(__it, this);
820  }
821 
822  iterator
823  insert(const_iterator __hint, const value_type& __obj)
824  {
825  __glibcxx_check_insert(__hint);
826  size_type __bucket_count = this->bucket_count();
827  _Base_iterator __it = _Base::insert(__hint.base(), __obj);
828  _M_check_rehashed(__bucket_count);
829  return iterator(__it, this);
830  }
831 
832  iterator
833  insert(value_type&& __obj)
834  {
835  size_type __bucket_count = this->bucket_count();
836  _Base_iterator __it = _Base::insert(std::move(__obj));
837  _M_check_rehashed(__bucket_count);
838  return iterator(__it, this);
839  }
840 
841  iterator
842  insert(const_iterator __hint, value_type&& __obj)
843  {
844  __glibcxx_check_insert(__hint);
845  size_type __bucket_count = this->bucket_count();
846  _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
847  _M_check_rehashed(__bucket_count);
848  return iterator(__it, this);
849  }
850 
851  void
852  insert(std::initializer_list<value_type> __l)
853  {
854  size_type __bucket_count = this->bucket_count();
855  _Base::insert(__l);
856  _M_check_rehashed(__bucket_count);
857  }
858 
859  template<typename _InputIterator>
860  void
861  insert(_InputIterator __first, _InputIterator __last)
862  {
863  typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
864  __glibcxx_check_valid_range2(__first, __last, __dist);
865  size_type __bucket_count = this->bucket_count();
866 
867  if (__dist.second >= __gnu_debug::__dp_sign)
868  _Base::insert(__gnu_debug::__unsafe(__first),
869  __gnu_debug::__unsafe(__last));
870  else
871  _Base::insert(__first, __last);
872 
873  _M_check_rehashed(__bucket_count);
874  }
875 
876 #if __cplusplus > 201402L
877  using node_type = typename _Base::node_type;
878 
879  node_type
880  extract(const_iterator __position)
881  {
882  __glibcxx_check_erase(__position);
883  _Base_const_iterator __victim = __position.base();
884  this->_M_invalidate_if(
885  [__victim](_Base_const_iterator __it) { return __it == __victim; }
886  );
887  this->_M_invalidate_local_if(
888  [__victim](_Base_const_local_iterator __it) {
889  return __it._M_curr() == __victim._M_cur;
890  });
891  return _Base::extract(__position.base());
892  }
893 
894  node_type
895  extract(const key_type& __key)
896  {
897  const auto __position = find(__key);
898  if (__position != end())
899  return extract(__position);
900  return {};
901  }
902 
903  iterator
904  insert(node_type&& __nh)
905  { return iterator(_Base::insert(std::move(__nh)), this); }
906 
907  iterator
908  insert(const_iterator __hint, node_type&& __nh)
909  {
910  __glibcxx_check_insert(__hint);
911  return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
912  }
913 
914  using _Base::merge;
915 #endif // C++17
916 
917  iterator
918  find(const key_type& __key)
919  { return iterator(_Base::find(__key), this); }
920 
921  const_iterator
922  find(const key_type& __key) const
923  { return const_iterator(_Base::find(__key), this); }
924 
925  std::pair<iterator, iterator>
926  equal_range(const key_type& __key)
927  {
928  std::pair<_Base_iterator, _Base_iterator> __res
929  = _Base::equal_range(__key);
930  return std::make_pair(iterator(__res.first, this),
931  iterator(__res.second, this));
932  }
933 
934  std::pair<const_iterator, const_iterator>
935  equal_range(const key_type& __key) const
936  {
937  std::pair<_Base_const_iterator, _Base_const_iterator>
938  __res = _Base::equal_range(__key);
939  return std::make_pair(const_iterator(__res.first, this),
940  const_iterator(__res.second, this));
941  }
942 
943  size_type
944  erase(const key_type& __key)
945  {
946  size_type __ret(0);
947  std::pair<_Base_iterator, _Base_iterator> __pair =
948  _Base::equal_range(__key);
949  for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
950  {
951  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
952  { return __it == __victim; });
953  this->_M_invalidate_local_if(
954  [__victim](_Base_const_local_iterator __it)
955  { return __it._M_curr() == __victim._M_cur; });
956  _Base::erase(__victim++);
957  ++__ret;
958  }
959  return __ret;
960  }
961 
962  iterator
963  erase(const_iterator __it)
964  {
965  __glibcxx_check_erase(__it);
966  _Base_const_iterator __victim = __it.base();
967  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
968  { return __it == __victim; });
969  this->_M_invalidate_local_if(
970  [__victim](_Base_const_local_iterator __it)
971  { return __it._M_curr() == __victim._M_cur; });
972  return iterator(_Base::erase(__it.base()), this);
973  }
974 
975  iterator
976  erase(iterator __it)
977  { return erase(const_iterator(__it)); }
978 
979  iterator
980  erase(const_iterator __first, const_iterator __last)
981  {
982  __glibcxx_check_erase_range(__first, __last);
983  for (_Base_const_iterator __tmp = __first.base();
984  __tmp != __last.base(); ++__tmp)
985  {
986  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
987  _M_message(__gnu_debug::__msg_valid_range)
988  ._M_iterator(__first, "first")
989  ._M_iterator(__last, "last"));
990  this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
991  { return __it == __tmp; });
992  this->_M_invalidate_local_if(
993  [__tmp](_Base_const_local_iterator __it)
994  { return __it._M_curr() == __tmp._M_cur; });
995  }
996  return iterator(_Base::erase(__first.base(),
997  __last.base()), this);
998  }
999 
1000  _Base&
1001  _M_base() noexcept { return *this; }
1002 
1003  const _Base&
1004  _M_base() const noexcept { return *this; }
1005 
1006  private:
1007  void
1008  _M_check_rehashed(size_type __prev_count)
1009  {
1010  if (__prev_count != this->bucket_count())
1011  this->_M_invalidate_locals();
1012  }
1013  };
1014 
1015  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1016  inline void
1017  swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1018  unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1019  noexcept(noexcept(__x.swap(__y)))
1020  { __x.swap(__y); }
1021 
1022  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1023  inline bool
1024  operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1025  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1026  { return __x._M_base() == __y._M_base(); }
1027 
1028  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
1029  inline bool
1030  operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1031  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1032  { return !(__x == __y); }
1033 
1034 } // namespace __debug
1035 } // namespace std
1036 
1037 #endif // C++11
1038 
1039 #endif