libstdc++
debug/unordered_set
1 // Debugging unordered_set/unordered_multiset implementation -*- C++ -*-
2 
3 // Copyright (C) 2003-2013 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 #if __cplusplus < 201103L
33 # include <bits/c++0x_warning.h>
34 #else
35 # include <unordered_set>
36 
37 #include <debug/safe_unordered_container.h>
38 #include <debug/safe_iterator.h>
39 #include <debug/safe_local_iterator.h>
40 
41 namespace std _GLIBCXX_VISIBILITY(default)
42 {
43 namespace __debug
44 {
45  /// Class std::unordered_set with safety/checking/debug instrumentation.
46  template<typename _Value,
47  typename _Hash = std::hash<_Value>,
48  typename _Pred = std::equal_to<_Value>,
49  typename _Alloc = std::allocator<_Value> >
50  class unordered_set
51  : public _GLIBCXX_STD_C::unordered_set<_Value, _Hash, _Pred, _Alloc>,
52  public __gnu_debug::_Safe_unordered_container<unordered_set<_Value, _Hash,
53  _Pred, _Alloc> >
54  {
55  typedef _GLIBCXX_STD_C::unordered_set<_Value, _Hash,
56  _Pred, _Alloc> _Base;
57  typedef __gnu_debug::_Safe_unordered_container<unordered_set> _Safe_base;
58  typedef typename _Base::const_iterator _Base_const_iterator;
59  typedef typename _Base::iterator _Base_iterator;
60  typedef typename _Base::const_local_iterator _Base_const_local_iterator;
61  typedef typename _Base::local_iterator _Base_local_iterator;
62 
63  public:
64  typedef typename _Base::size_type size_type;
65  typedef typename _Base::hasher hasher;
66  typedef typename _Base::key_equal key_equal;
67  typedef typename _Base::allocator_type allocator_type;
68 
69  typedef typename _Base::key_type key_type;
70  typedef typename _Base::value_type value_type;
71 
72  typedef __gnu_debug::_Safe_iterator<_Base_iterator,
73  unordered_set> iterator;
74  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
75  unordered_set> const_iterator;
76  typedef __gnu_debug::_Safe_local_iterator<_Base_local_iterator,
77  unordered_set> local_iterator;
78  typedef __gnu_debug::_Safe_local_iterator<_Base_const_local_iterator,
79  unordered_set> const_local_iterator;
80 
81  explicit
82  unordered_set(size_type __n = 10,
83  const hasher& __hf = hasher(),
84  const key_equal& __eql = key_equal(),
85  const allocator_type& __a = allocator_type())
86  : _Base(__n, __hf, __eql, __a) { }
87 
88  template<typename _InputIterator>
89  unordered_set(_InputIterator __first, _InputIterator __last,
90  size_type __n = 0,
91  const hasher& __hf = hasher(),
92  const key_equal& __eql = key_equal(),
93  const allocator_type& __a = allocator_type())
94  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
95  __last)),
96  __gnu_debug::__base(__last), __n,
97  __hf, __eql, __a) { }
98 
99  unordered_set(const unordered_set& __x) = default;
100 
101  unordered_set(const _Base& __x)
102  : _Base(__x) { }
103 
104  unordered_set(unordered_set&& __x) = default;
105 
106  unordered_set(initializer_list<value_type> __l,
107  size_type __n = 0,
108  const hasher& __hf = hasher(),
109  const key_equal& __eql = key_equal(),
110  const allocator_type& __a = allocator_type())
111  : _Base(__l, __n, __hf, __eql, __a) { }
112 
113  ~unordered_set() noexcept { }
114 
115  unordered_set&
116  operator=(const unordered_set& __x)
117  {
118  *static_cast<_Base*>(this) = __x;
119  this->_M_invalidate_all();
120  return *this;
121  }
122 
123  unordered_set&
124  operator=(unordered_set&& __x)
125  {
126  // NB: DR 1204.
127  // NB: DR 675.
128  __glibcxx_check_self_move_assign(__x);
129  clear();
130  swap(__x);
131  return *this;
132  }
133 
134  unordered_set&
135  operator=(initializer_list<value_type> __l)
136  {
137  this->clear();
138  this->insert(__l);
139  return *this;
140  }
141 
142  void
143  swap(unordered_set& __x)
144  {
145  _Base::swap(__x);
146  _Safe_base::_M_swap(__x);
147  }
148 
149  void
150  clear() noexcept
151  {
152  _Base::clear();
153  this->_M_invalidate_all();
154  }
155 
156  iterator
157  begin() noexcept
158  { return iterator(_Base::begin(), this); }
159 
160  const_iterator
161  begin() const noexcept
162  { return const_iterator(_Base::begin(), this); }
163 
164  iterator
165  end() noexcept
166  { return iterator(_Base::end(), this); }
167 
168  const_iterator
169  end() const noexcept
170  { return const_iterator(_Base::end(), this); }
171 
172  const_iterator
173  cbegin() const noexcept
174  { return const_iterator(_Base::begin(), this); }
175 
176  const_iterator
177  cend() const noexcept
178  { return const_iterator(_Base::end(), this); }
179 
180  // local versions
181  local_iterator
182  begin(size_type __b)
183  {
184  __glibcxx_check_bucket_index(__b);
185  return local_iterator(_Base::begin(__b), __b, this);
186  }
187 
188  local_iterator
189  end(size_type __b)
190  {
191  __glibcxx_check_bucket_index(__b);
192  return local_iterator(_Base::end(__b), __b, this);
193  }
194 
195  const_local_iterator
196  begin(size_type __b) const
197  {
198  __glibcxx_check_bucket_index(__b);
199  return const_local_iterator(_Base::begin(__b), __b, this);
200  }
201 
202  const_local_iterator
203  end(size_type __b) const
204  {
205  __glibcxx_check_bucket_index(__b);
206  return const_local_iterator(_Base::end(__b), __b, this);
207  }
208 
209  const_local_iterator
210  cbegin(size_type __b) const
211  {
212  __glibcxx_check_bucket_index(__b);
213  return const_local_iterator(_Base::cbegin(__b), __b, this);
214  }
215 
216  const_local_iterator
217  cend(size_type __b) const
218  {
219  __glibcxx_check_bucket_index(__b);
220  return const_local_iterator(_Base::cend(__b), __b, this);
221  }
222 
223  size_type
224  bucket_size(size_type __b) const
225  {
226  __glibcxx_check_bucket_index(__b);
227  return _Base::bucket_size(__b);
228  }
229 
230  float
231  max_load_factor() const noexcept
232  { return _Base::max_load_factor(); }
233 
234  void
235  max_load_factor(float __f)
236  {
237  __glibcxx_check_max_load_factor(__f);
238  _Base::max_load_factor(__f);
239  }
240 
241  template<typename... _Args>
242  std::pair<iterator, bool>
243  emplace(_Args&&... __args)
244  {
245  size_type __bucket_count = this->bucket_count();
246  std::pair<_Base_iterator, bool> __res
247  = _Base::emplace(std::forward<_Args>(__args)...);
248  _M_check_rehashed(__bucket_count);
249  return std::make_pair(iterator(__res.first, this), __res.second);
250  }
251 
252  template<typename... _Args>
253  iterator
254  emplace_hint(const_iterator __hint, _Args&&... __args)
255  {
256  __glibcxx_check_insert(__hint);
257  size_type __bucket_count = this->bucket_count();
258  _Base_iterator __it = _Base::emplace_hint(__hint.base(),
259  std::forward<_Args>(__args)...);
260  _M_check_rehashed(__bucket_count);
261  return iterator(__it, this);
262  }
263 
264  std::pair<iterator, bool>
265  insert(const value_type& __obj)
266  {
267  size_type __bucket_count = this->bucket_count();
268  typedef std::pair<_Base_iterator, bool> __pair_type;
269  __pair_type __res = _Base::insert(__obj);
270  _M_check_rehashed(__bucket_count);
271  return std::make_pair(iterator(__res.first, this), __res.second);
272  }
273 
274  iterator
275  insert(const_iterator __hint, const value_type& __obj)
276  {
277  __glibcxx_check_insert(__hint);
278  size_type __bucket_count = this->bucket_count();
279  _Base_iterator __it = _Base::insert(__hint.base(), __obj);
280  _M_check_rehashed(__bucket_count);
281  return iterator(__it, this);
282  }
283 
284  std::pair<iterator, bool>
285  insert(value_type&& __obj)
286  {
287  size_type __bucket_count = this->bucket_count();
288  typedef std::pair<typename _Base::iterator, bool> __pair_type;
289  __pair_type __res = _Base::insert(std::move(__obj));
290  _M_check_rehashed(__bucket_count);
291  return std::make_pair(iterator(__res.first, this), __res.second);
292  }
293 
294  iterator
295  insert(const_iterator __hint, value_type&& __obj)
296  {
297  __glibcxx_check_insert(__hint);
298  size_type __bucket_count = this->bucket_count();
299  _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
300  _M_check_rehashed(__bucket_count);
301  return iterator(__it, this);
302  }
303 
304  void
305  insert(std::initializer_list<value_type> __l)
306  {
307  size_type __bucket_count = this->bucket_count();
308  _Base::insert(__l);
309  _M_check_rehashed(__bucket_count);
310  }
311 
312  template<typename _InputIterator>
313  void
314  insert(_InputIterator __first, _InputIterator __last)
315  {
316  __glibcxx_check_valid_range(__first, __last);
317  size_type __bucket_count = this->bucket_count();
318  _Base::insert(__gnu_debug::__base(__first),
319  __gnu_debug::__base(__last));
320  _M_check_rehashed(__bucket_count);
321  }
322 
323  iterator
324  find(const key_type& __key)
325  { return iterator(_Base::find(__key), this); }
326 
327  const_iterator
328  find(const key_type& __key) const
329  { return const_iterator(_Base::find(__key), this); }
330 
331  std::pair<iterator, iterator>
332  equal_range(const key_type& __key)
333  {
334  typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
335  __pair_type __res = _Base::equal_range(__key);
336  return std::make_pair(iterator(__res.first, this),
337  iterator(__res.second, this));
338  }
339 
340  std::pair<const_iterator, const_iterator>
341  equal_range(const key_type& __key) const
342  {
343  std::pair<_Base_const_iterator, _Base_const_iterator>
344  __res = _Base::equal_range(__key);
345  return std::make_pair(const_iterator(__res.first, this),
346  const_iterator(__res.second, this));
347  }
348 
349  size_type
350  erase(const key_type& __key)
351  {
352  size_type __ret(0);
353  _Base_iterator __victim(_Base::find(__key));
354  if (__victim != _Base::end())
355  {
356  this->_M_invalidate_if(
357  [__victim](_Base_const_iterator __it)
358  { return __it == __victim; });
359  this->_M_invalidate_local_if(
360  [__victim](_Base_const_local_iterator __it)
361  { return __it._M_cur == __victim._M_cur; });
362  size_type __bucket_count = this->bucket_count();
363  _Base::erase(__victim);
364  _M_check_rehashed(__bucket_count);
365  __ret = 1;
366  }
367  return __ret;
368  }
369 
370  iterator
371  erase(const_iterator __it)
372  {
373  __glibcxx_check_erase(__it);
374  _Base_const_iterator __victim = __it.base();
375  this->_M_invalidate_if(
376  [__victim](_Base_const_iterator __it)
377  { return __it == __victim; });
378  this->_M_invalidate_local_if(
379  [__victim](_Base_const_local_iterator __it)
380  { return __it._M_cur == __victim._M_cur; });
381  size_type __bucket_count = this->bucket_count();
382  _Base_iterator __next = _Base::erase(__it.base());
383  _M_check_rehashed(__bucket_count);
384  return iterator(__next, this);
385  }
386 
387  iterator
388  erase(iterator __it)
389  { return erase(const_iterator(__it)); }
390 
391  iterator
392  erase(const_iterator __first, const_iterator __last)
393  {
394  __glibcxx_check_erase_range(__first, __last);
395  for (_Base_const_iterator __tmp = __first.base();
396  __tmp != __last.base(); ++__tmp)
397  {
398  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
399  _M_message(__gnu_debug::__msg_valid_range)
400  ._M_iterator(__first, "first")
401  ._M_iterator(__last, "last"));
402  this->_M_invalidate_if(
403  [__tmp](_Base_const_iterator __it)
404  { return __it == __tmp; });
405  this->_M_invalidate_local_if(
406  [__tmp](_Base_const_local_iterator __it)
407  { return __it._M_cur == __tmp._M_cur; });
408  }
409  size_type __bucket_count = this->bucket_count();
410  _Base_iterator __next = _Base::erase(__first.base(),
411  __last.base());
412  _M_check_rehashed(__bucket_count);
413  return iterator(__next, this);
414  }
415 
416  _Base&
417  _M_base() noexcept { return *this; }
418 
419  const _Base&
420  _M_base() const noexcept { return *this; }
421 
422  private:
423  void
424  _M_invalidate_locals()
425  {
426  _Base_local_iterator __local_end = _Base::end(0);
427  this->_M_invalidate_local_if(
428  [__local_end](_Base_const_local_iterator __it)
429  { return __it != __local_end; });
430  }
431 
432  void
433  _M_invalidate_all()
434  {
435  _Base_iterator __end = _Base::end();
436  this->_M_invalidate_if(
437  [__end](_Base_const_iterator __it)
438  { return __it != __end; });
439  _M_invalidate_locals();
440  }
441 
442  void
443  _M_check_rehashed(size_type __prev_count)
444  {
445  if (__prev_count != this->bucket_count())
446  _M_invalidate_locals();
447  }
448  };
449 
450  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
451  inline void
452  swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
453  unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
454  { __x.swap(__y); }
455 
456  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
457  inline bool
458  operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
459  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
460  { return __x._M_base() == __y._M_base(); }
461 
462  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
463  inline bool
464  operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
465  const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
466  { return !(__x == __y); }
467 
468 
469  /// Class std::unordered_multiset with safety/checking/debug instrumentation.
470  template<typename _Value,
471  typename _Hash = std::hash<_Value>,
472  typename _Pred = std::equal_to<_Value>,
473  typename _Alloc = std::allocator<_Value> >
474  class unordered_multiset
475  : public _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash, _Pred, _Alloc>,
476  public __gnu_debug::_Safe_unordered_container<
477  unordered_multiset<_Value, _Hash, _Pred, _Alloc> >
478  {
479  typedef _GLIBCXX_STD_C::unordered_multiset<_Value, _Hash,
480  _Pred, _Alloc> _Base;
481  typedef __gnu_debug::_Safe_unordered_container<unordered_multiset>
482  _Safe_base;
483  typedef typename _Base::const_iterator _Base_const_iterator;
484  typedef typename _Base::iterator _Base_iterator;
485  typedef typename _Base::const_local_iterator _Base_const_local_iterator;
486  typedef typename _Base::local_iterator _Base_local_iterator;
487 
488  public:
489  typedef typename _Base::size_type size_type;
490  typedef typename _Base::hasher hasher;
491  typedef typename _Base::key_equal key_equal;
492  typedef typename _Base::allocator_type allocator_type;
493 
494  typedef typename _Base::key_type key_type;
495  typedef typename _Base::value_type value_type;
496 
497  typedef __gnu_debug::_Safe_iterator<_Base_iterator,
498  unordered_multiset> iterator;
499  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
500  unordered_multiset> const_iterator;
501  typedef __gnu_debug::_Safe_local_iterator<
502  _Base_local_iterator, unordered_multiset> local_iterator;
503  typedef __gnu_debug::_Safe_local_iterator<
504  _Base_const_local_iterator, unordered_multiset> const_local_iterator;
505 
506  explicit
507  unordered_multiset(size_type __n = 10,
508  const hasher& __hf = hasher(),
509  const key_equal& __eql = key_equal(),
510  const allocator_type& __a = allocator_type())
511  : _Base(__n, __hf, __eql, __a) { }
512 
513  template<typename _InputIterator>
514  unordered_multiset(_InputIterator __first, _InputIterator __last,
515  size_type __n = 0,
516  const hasher& __hf = hasher(),
517  const key_equal& __eql = key_equal(),
518  const allocator_type& __a = allocator_type())
519  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
520  __last)),
521  __gnu_debug::__base(__last), __n,
522  __hf, __eql, __a) { }
523 
524  unordered_multiset(const unordered_multiset& __x) = default;
525 
526  unordered_multiset(const _Base& __x)
527  : _Base(__x) { }
528 
529  unordered_multiset(unordered_multiset&& __x) = default;
530 
531  unordered_multiset(initializer_list<value_type> __l,
532  size_type __n = 0,
533  const hasher& __hf = hasher(),
534  const key_equal& __eql = key_equal(),
535  const allocator_type& __a = allocator_type())
536  : _Base(__l, __n, __hf, __eql, __a) { }
537 
538  ~unordered_multiset() noexcept { }
539 
540  unordered_multiset&
541  operator=(const unordered_multiset& __x)
542  {
543  *static_cast<_Base*>(this) = __x;
544  this->_M_invalidate_all();
545  return *this;
546  }
547 
548  unordered_multiset&
549  operator=(unordered_multiset&& __x)
550  {
551  // NB: DR 1204.
552  // NB: DR 675.
553  __glibcxx_check_self_move_assign(__x);
554  clear();
555  swap(__x);
556  return *this;
557  }
558 
559  unordered_multiset&
560  operator=(initializer_list<value_type> __l)
561  {
562  this->clear();
563  this->insert(__l);
564  return *this;
565  }
566 
567  void
568  swap(unordered_multiset& __x)
569  {
570  _Base::swap(__x);
571  _Safe_base::_M_swap(__x);
572  }
573 
574  void
575  clear() noexcept
576  {
577  _Base::clear();
578  this->_M_invalidate_all();
579  }
580 
581  iterator
582  begin() noexcept
583  { return iterator(_Base::begin(), this); }
584 
585  const_iterator
586  begin() const noexcept
587  { return const_iterator(_Base::begin(), this); }
588 
589  iterator
590  end() noexcept
591  { return iterator(_Base::end(), this); }
592 
593  const_iterator
594  end() const noexcept
595  { return const_iterator(_Base::end(), this); }
596 
597  const_iterator
598  cbegin() const noexcept
599  { return const_iterator(_Base::begin(), this); }
600 
601  const_iterator
602  cend() const noexcept
603  { return const_iterator(_Base::end(), this); }
604 
605  // local versions
606  local_iterator
607  begin(size_type __b)
608  {
609  __glibcxx_check_bucket_index(__b);
610  return local_iterator(_Base::begin(__b), __b, this);
611  }
612 
613  local_iterator
614  end(size_type __b)
615  {
616  __glibcxx_check_bucket_index(__b);
617  return local_iterator(_Base::end(__b), __b, this);
618  }
619 
620  const_local_iterator
621  begin(size_type __b) const
622  {
623  __glibcxx_check_bucket_index(__b);
624  return const_local_iterator(_Base::begin(__b), __b, this);
625  }
626 
627  const_local_iterator
628  end(size_type __b) const
629  {
630  __glibcxx_check_bucket_index(__b);
631  return const_local_iterator(_Base::end(__b), __b, this);
632  }
633 
634  const_local_iterator
635  cbegin(size_type __b) const
636  {
637  __glibcxx_check_bucket_index(__b);
638  return const_local_iterator(_Base::cbegin(__b), __b, this);
639  }
640 
641  const_local_iterator
642  cend(size_type __b) const
643  {
644  __glibcxx_check_bucket_index(__b);
645  return const_local_iterator(_Base::cend(__b), __b, this);
646  }
647 
648  size_type
649  bucket_size(size_type __b) const
650  {
651  __glibcxx_check_bucket_index(__b);
652  return _Base::bucket_size(__b);
653  }
654 
655  float
656  max_load_factor() const noexcept
657  { return _Base::max_load_factor(); }
658 
659  void
660  max_load_factor(float __f)
661  {
662  __glibcxx_check_max_load_factor(__f);
663  _Base::max_load_factor(__f);
664  }
665 
666  template<typename... _Args>
667  iterator
668  emplace(_Args&&... __args)
669  {
670  size_type __bucket_count = this->bucket_count();
671  _Base_iterator __it
672  = _Base::emplace(std::forward<_Args>(__args)...);
673  _M_check_rehashed(__bucket_count);
674  return iterator(__it, this);
675  }
676 
677  template<typename... _Args>
678  iterator
679  emplace_hint(const_iterator __hint, _Args&&... __args)
680  {
681  __glibcxx_check_insert(__hint);
682  size_type __bucket_count = this->bucket_count();
683  _Base_iterator __it = _Base::emplace_hint(__hint.base(),
684  std::forward<_Args>(__args)...);
685  _M_check_rehashed(__bucket_count);
686  return iterator(__it, this);
687  }
688 
689  iterator
690  insert(const value_type& __obj)
691  {
692  size_type __bucket_count = this->bucket_count();
693  _Base_iterator __it = _Base::insert(__obj);
694  _M_check_rehashed(__bucket_count);
695  return iterator(__it, this);
696  }
697 
698  iterator
699  insert(const_iterator __hint, const value_type& __obj)
700  {
701  __glibcxx_check_insert(__hint);
702  size_type __bucket_count = this->bucket_count();
703  _Base_iterator __it = _Base::insert(__hint.base(), __obj);
704  _M_check_rehashed(__bucket_count);
705  return iterator(__it, this);
706  }
707 
708  iterator
709  insert(value_type&& __obj)
710  {
711  size_type __bucket_count = this->bucket_count();
712  _Base_iterator __it = _Base::insert(std::move(__obj));
713  _M_check_rehashed(__bucket_count);
714  return iterator(__it, this);
715  }
716 
717  iterator
718  insert(const_iterator __hint, value_type&& __obj)
719  {
720  __glibcxx_check_insert(__hint);
721  size_type __bucket_count = this->bucket_count();
722  _Base_iterator __it = _Base::insert(__hint.base(), std::move(__obj));
723  _M_check_rehashed(__bucket_count);
724  return iterator(__it, this);
725  }
726 
727  void
728  insert(std::initializer_list<value_type> __l)
729  {
730  size_type __bucket_count = this->bucket_count();
731  _Base::insert(__l);
732  _M_check_rehashed(__bucket_count);
733  }
734 
735  template<typename _InputIterator>
736  void
737  insert(_InputIterator __first, _InputIterator __last)
738  {
739  __glibcxx_check_valid_range(__first, __last);
740  size_type __bucket_count = this->bucket_count();
741  _Base::insert(__gnu_debug::__base(__first),
742  __gnu_debug::__base(__last));
743  _M_check_rehashed(__bucket_count);
744  }
745 
746  iterator
747  find(const key_type& __key)
748  { return iterator(_Base::find(__key), this); }
749 
750  const_iterator
751  find(const key_type& __key) const
752  { return const_iterator(_Base::find(__key), this); }
753 
754  std::pair<iterator, iterator>
755  equal_range(const key_type& __key)
756  {
757  typedef std::pair<_Base_iterator, _Base_iterator> __pair_type;
758  __pair_type __res = _Base::equal_range(__key);
759  return std::make_pair(iterator(__res.first, this),
760  iterator(__res.second, this));
761  }
762 
763  std::pair<const_iterator, const_iterator>
764  equal_range(const key_type& __key) const
765  {
766  std::pair<_Base_const_iterator, _Base_const_iterator>
767  __res = _Base::equal_range(__key);
768  return std::make_pair(const_iterator(__res.first, this),
769  const_iterator(__res.second, this));
770  }
771 
772  size_type
773  erase(const key_type& __key)
774  {
775  size_type __ret(0);
776  std::pair<_Base_iterator, _Base_iterator> __pair =
777  _Base::equal_range(__key);
778  for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
779  {
780  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
781  { return __it == __victim; });
782  this->_M_invalidate_local_if(
783  [__victim](_Base_const_local_iterator __it)
784  { return __it._M_cur == __victim._M_cur; });
785  _Base::erase(__victim++);
786  ++__ret;
787  }
788  return __ret;
789  }
790 
791  iterator
792  erase(const_iterator __it)
793  {
794  __glibcxx_check_erase(__it);
795  _Base_const_iterator __victim = __it.base();
796  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
797  { return __it == __victim; });
798  this->_M_invalidate_local_if(
799  [__victim](_Base_const_local_iterator __it)
800  { return __it._M_cur == __victim._M_cur; });
801  return iterator(_Base::erase(__it.base()), this);
802  }
803 
804  iterator
805  erase(iterator __it)
806  { return erase(const_iterator(__it)); }
807 
808  iterator
809  erase(const_iterator __first, const_iterator __last)
810  {
811  __glibcxx_check_erase_range(__first, __last);
812  for (_Base_const_iterator __tmp = __first.base();
813  __tmp != __last.base(); ++__tmp)
814  {
815  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
816  _M_message(__gnu_debug::__msg_valid_range)
817  ._M_iterator(__first, "first")
818  ._M_iterator(__last, "last"));
819  this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
820  { return __it == __tmp; });
821  this->_M_invalidate_local_if(
822  [__tmp](_Base_const_local_iterator __it)
823  { return __it._M_cur == __tmp._M_cur; });
824  }
825  return iterator(_Base::erase(__first.base(),
826  __last.base()), this);
827  }
828 
829  _Base&
830  _M_base() noexcept { return *this; }
831 
832  const _Base&
833  _M_base() const noexcept { return *this; }
834 
835  private:
836  void
837  _M_invalidate_locals()
838  {
839  _Base_local_iterator __local_end = _Base::end(0);
840  this->_M_invalidate_local_if(
841  [__local_end](_Base_const_local_iterator __it)
842  { return __it != __local_end; });
843  }
844 
845  void
846  _M_invalidate_all()
847  {
848  _Base_iterator __end = _Base::end();
849  this->_M_invalidate_if([__end](_Base_const_iterator __it)
850  { return __it != __end; });
851  _M_invalidate_locals();
852  }
853 
854  void
855  _M_check_rehashed(size_type __prev_count)
856  {
857  if (__prev_count != this->bucket_count())
858  _M_invalidate_locals();
859  }
860  };
861 
862  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
863  inline void
864  swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
865  unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
866  { __x.swap(__y); }
867 
868  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
869  inline bool
870  operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
871  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
872  { return __x._M_base() == __y._M_base(); }
873 
874  template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
875  inline bool
876  operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
877  const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
878  { return !(__x == __y); }
879 
880 } // namespace __debug
881 } // namespace std
882 
883 #endif // C++11
884 
885 #endif