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