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