libstdc++
debug/unordered_map
Go to the documentation of this file.
1 // Debugging unordered_map/unordered_multimap 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_map
27  * This file is a GNU debug extension to the Standard C++ Library.
28  */
29 
30 #ifndef _GLIBCXX_DEBUG_UNORDERED_MAP
31 #define _GLIBCXX_DEBUG_UNORDERED_MAP 1
32 
33 #ifndef __GXX_EXPERIMENTAL_CXX0X__
34 # include <bits/c++0x_warning.h>
35 #else
36 # include <unordered_map>
37 
39 #include <debug/safe_iterator.h>
41 
42 namespace std _GLIBCXX_VISIBILITY(default)
43 {
44 namespace __debug
45 {
46  /// Class std::unordered_map with safety/checking/debug instrumentation.
47  template<typename _Key, typename _Tp,
48  typename _Hash = std::hash<_Key>,
49  typename _Pred = std::equal_to<_Key>,
50  typename _Alloc = std::allocator<_Key> >
52  : public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,
53  public __gnu_debug::_Safe_unordered_container<unordered_map<_Key, _Tp,
54  _Hash, _Pred, _Alloc> >
55  {
56  typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
57  _Pred, _Alloc> _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,
75  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
77  typedef __gnu_debug::_Safe_local_iterator<_Base_local_iterator,
79  typedef __gnu_debug::_Safe_local_iterator<_Base_const_local_iterator,
81 
82  explicit
83  unordered_map(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_map(_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_map(const unordered_map& __x)
101  : _Base(__x) { }
102 
103  unordered_map(const _Base& __x)
104  : _Base(__x) { }
105 
107  : _Base(std::move(__x)) { }
108 
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_map() noexcept { }
117 
119  operator=(const unordered_map& __x)
120  {
121  *static_cast<_Base*>(this) = __x;
122  this->_M_invalidate_all();
123  return *this;
124  }
125 
127  operator=(unordered_map&& __x)
128  {
129  // NB: DR 1204.
130  // NB: DR 675.
131  clear();
132  swap(__x);
133  return *this;
134  }
135 
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_map& __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 
163  begin() const noexcept
164  { return const_iterator(_Base::begin(), this); }
165 
166  iterator
167  end() noexcept
168  { return iterator(_Base::end(), this); }
169 
171  end() const noexcept
172  { return const_iterator(_Base::end(), this); }
173 
175  cbegin() const noexcept
176  { return const_iterator(_Base::begin(), this); }
177 
179  cend() const noexcept
180  { return const_iterator(_Base::end(), this); }
181 
182  // local versions
184  begin(size_type __b)
185  { return local_iterator(_Base::begin(__b), __b, this); }
186 
188  end(size_type __b)
189  { return local_iterator(_Base::end(__b), __b, this); }
190 
192  begin(size_type __b) const
193  { return const_local_iterator(_Base::begin(__b), __b, this); }
194 
196  end(size_type __b) const
197  { return const_local_iterator(_Base::end(__b), __b, this); }
198 
200  cbegin(size_type __b) const
201  { return const_local_iterator(_Base::cbegin(__b), __b, this); }
202 
204  cend(size_type __b) const
205  { return const_local_iterator(_Base::cend(__b), __b, this); }
206 
207  template<typename... _Args>
209  emplace(_Args&&... __args)
210  {
211  size_type __bucket_count = this->bucket_count();
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 
231  insert(const value_type& __obj)
232  {
233  size_type __bucket_count = this->bucket_count();
234  std::pair<_Base_iterator, bool> __res = _Base::insert(__obj);
235  _M_check_rehashed(__bucket_count);
236  return std::make_pair(iterator(__res.first, this), __res.second);
237  }
238 
239  iterator
240  insert(const_iterator __hint, const value_type& __obj)
241  {
242  __glibcxx_check_insert(__hint);
243  size_type __bucket_count = this->bucket_count();
244  _Base_iterator __it = _Base::insert(__hint.base(), __obj);
245  _M_check_rehashed(__bucket_count);
246  return iterator(__it, this);
247  }
248 
249  template<typename _Pair, typename = typename
251  _Pair&&>::value>::type>
253  insert(_Pair&& __obj)
254  {
255  size_type __bucket_count = this->bucket_count();
257  _Base::insert(std::forward<_Pair>(__obj));
258  _M_check_rehashed(__bucket_count);
259  return std::make_pair(iterator(__res.first, this), __res.second);
260  }
261 
262  template<typename _Pair, typename = typename
264  _Pair&&>::value>::type>
265  iterator
266  insert(const_iterator __hint, _Pair&& __obj)
267  {
268  __glibcxx_check_insert(__hint);
269  size_type __bucket_count = this->bucket_count();
270  _Base_iterator __it =
271  _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
272  _M_check_rehashed(__bucket_count);
273  return iterator(__it, this);
274  }
275 
276  void
278  {
279  size_type __bucket_count = this->bucket_count();
280  _Base::insert(__l);
281  _M_check_rehashed(__bucket_count);
282  }
283 
284  template<typename _InputIterator>
285  void
286  insert(_InputIterator __first, _InputIterator __last)
287  {
288  __glibcxx_check_valid_range(__first, __last);
289  size_type __bucket_count = this->bucket_count();
290  _Base::insert(__gnu_debug::__base(__first),
291  __gnu_debug::__base(__last));
292  _M_check_rehashed(__bucket_count);
293  }
294 
295  iterator
296  find(const key_type& __key)
297  { return iterator(_Base::find(__key), this); }
298 
300  find(const key_type& __key) const
301  { return const_iterator(_Base::find(__key), this); }
302 
304  equal_range(const key_type& __key)
305  {
307  _Base::equal_range(__key);
308  return std::make_pair(iterator(__res.first, this),
309  iterator(__res.second, this));
310  }
311 
313  equal_range(const key_type& __key) const
314  {
316  _Base::equal_range(__key);
317  return std::make_pair(const_iterator(__res.first, this),
318  const_iterator(__res.second, this));
319  }
320 
321  size_type
322  erase(const key_type& __key)
323  {
324  size_type __ret(0);
325  _Base_iterator __victim(_Base::find(__key));
326  if (__victim != _Base::end())
327  {
328  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
329  { return __it == __victim; });
330  _Base_local_iterator __local_victim = _S_to_local(__victim);
332  [__local_victim](_Base_const_local_iterator __it)
333  { return __it == __local_victim; });
334  size_type __bucket_count = this->bucket_count();
335  _Base::erase(__victim);
336  _M_check_rehashed(__bucket_count);
337  __ret = 1;
338  }
339  return __ret;
340  }
341 
342  iterator
343  erase(const_iterator __it)
344  {
345  __glibcxx_check_erase(__it);
346  _Base_const_iterator __victim = __it.base();
347  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
348  { return __it == __victim; });
349  _Base_const_local_iterator __local_victim = _S_to_local(__victim);
351  [__local_victim](_Base_const_local_iterator __it)
352  { return __it == __local_victim; });
353  size_type __bucket_count = this->bucket_count();
354  _Base_iterator __next = _Base::erase(__it.base());
355  _M_check_rehashed(__bucket_count);
356  return iterator(__next, this);
357  }
358 
359  iterator
360  erase(iterator __it)
361  { return erase(const_iterator(__it)); }
362 
363  iterator
364  erase(const_iterator __first, const_iterator __last)
365  {
366  __glibcxx_check_erase_range(__first, __last);
367  for (_Base_const_iterator __tmp = __first.base();
368  __tmp != __last.base(); ++__tmp)
369  {
370  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
371  _M_message(__gnu_debug::__msg_valid_range)
372  ._M_iterator(__first, "first")
373  ._M_iterator(__last, "last"));
374  this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
375  { return __it == __tmp; });
376  _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
378  [__local_tmp](_Base_const_local_iterator __it)
379  { return __it == __local_tmp; });
380  }
381  size_type __bucket_count = this->bucket_count();
382  _Base_iterator __next = _Base::erase(__first.base(), __last.base());
383  _M_check_rehashed(__bucket_count);
384  return iterator(__next, this);
385  }
386 
387  _Base&
388  _M_base() noexcept { return *this; }
389 
390  const _Base&
391  _M_base() const noexcept { return *this; }
392 
393  private:
394  void
395  _M_invalidate_locals()
396  {
397  _Base_local_iterator __local_end = _Base::end(0);
399  [__local_end](_Base_const_local_iterator __it)
400  { return __it != __local_end; });
401  }
402 
403  void
404  _M_invalidate_all()
405  {
406  _Base_iterator __end = _Base::end();
407  this->_M_invalidate_if([__end](_Base_const_iterator __it)
408  { return __it != __end; });
409  _M_invalidate_locals();
410  }
411 
412  void
413  _M_check_rehashed(size_type __prev_count)
414  {
415  if (__prev_count != this->bucket_count())
416  _M_invalidate_locals();
417  }
418 
419  static _Base_local_iterator
420  _S_to_local(_Base_iterator __it)
421  {
422  // The returned local iterator will not be incremented so we don't
423  // need to compute __it's node bucket
424  return _Base_local_iterator(__it._M_cur, 0, 0);
425  }
426 
427  static _Base_const_local_iterator
428  _S_to_local(_Base_const_iterator __it)
429  {
430  // The returned local iterator will not be incremented so we don't
431  // need to compute __it's node bucket
432  return _Base_const_local_iterator(__it._M_cur, 0, 0);
433  }
434  };
435 
436  template<typename _Key, typename _Tp, typename _Hash,
437  typename _Pred, typename _Alloc>
438  inline void
441  { __x.swap(__y); }
442 
443  template<typename _Key, typename _Tp, typename _Hash,
444  typename _Pred, typename _Alloc>
445  inline bool
448  { return __x._M_equal(__y); }
449 
450  template<typename _Key, typename _Tp, typename _Hash,
451  typename _Pred, typename _Alloc>
452  inline bool
453  operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
454  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
455  { return !(__x == __y); }
456 
457 
458  /// Class std::unordered_multimap with safety/checking/debug instrumentation.
459  template<typename _Key, typename _Tp,
460  typename _Hash = std::hash<_Key>,
461  typename _Pred = std::equal_to<_Key>,
462  typename _Alloc = std::allocator<_Key> >
464  : public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
465  _Pred, _Alloc>,
466  public __gnu_debug::_Safe_unordered_container<unordered_multimap<_Key,
467  _Tp, _Hash, _Pred, _Alloc> >
468  {
469  typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
470  _Pred, _Alloc> _Base;
472  _Safe_base;
473  typedef typename _Base::const_iterator _Base_const_iterator;
474  typedef typename _Base::iterator _Base_iterator;
475  typedef typename _Base::const_local_iterator _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<_Base_iterator,
489  typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
492  _Base_local_iterator, unordered_multimap> local_iterator;
494  _Base_const_local_iterator, unordered_multimap> const_local_iterator;
495 
496  explicit
497  unordered_multimap(size_type __n = 10,
498  const hasher& __hf = hasher(),
499  const key_equal& __eql = key_equal(),
500  const allocator_type& __a = allocator_type())
501  : _Base(__n, __hf, __eql, __a) { }
502 
503  template<typename _InputIterator>
504  unordered_multimap(_InputIterator __first, _InputIterator __last,
505  size_type __n = 0,
506  const hasher& __hf = hasher(),
507  const key_equal& __eql = key_equal(),
508  const allocator_type& __a = allocator_type())
509  : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
510  __last)),
511  __gnu_debug::__base(__last), __n,
512  __hf, __eql, __a) { }
513 
515  : _Base(__x) { }
516 
517  unordered_multimap(const _Base& __x)
518  : _Base(__x) { }
519 
521  : _Base(std::move(__x)) { }
522 
524  size_type __n = 0,
525  const hasher& __hf = hasher(),
526  const key_equal& __eql = key_equal(),
527  const allocator_type& __a = allocator_type())
528  : _Base(__l, __n, __hf, __eql, __a) { }
529 
530  ~unordered_multimap() noexcept { }
531 
533  operator=(const unordered_multimap& __x)
534  {
535  *static_cast<_Base*>(this) = __x;
536  this->_M_invalidate_all();
537  return *this;
538  }
539 
541  operator=(unordered_multimap&& __x)
542  {
543  // NB: DR 1204.
544  // NB: DR 675.
545  clear();
546  swap(__x);
547  return *this;
548  }
549 
551  operator=(initializer_list<value_type> __l)
552  {
553  this->clear();
554  this->insert(__l);
555  return *this;
556  }
557 
558  void
559  swap(unordered_multimap& __x)
560  {
561  _Base::swap(__x);
562  _Safe_base::_M_swap(__x);
563  }
564 
565  void
566  clear() noexcept
567  {
568  _Base::clear();
569  this->_M_invalidate_all();
570  }
571 
572  iterator
573  begin() noexcept
574  { return iterator(_Base::begin(), this); }
575 
577  begin() const noexcept
578  { return const_iterator(_Base::begin(), this); }
579 
580  iterator
581  end() noexcept
582  { return iterator(_Base::end(), this); }
583 
585  end() const noexcept
586  { return const_iterator(_Base::end(), this); }
587 
589  cbegin() const noexcept
590  { return const_iterator(_Base::begin(), this); }
591 
593  cend() const noexcept
594  { return const_iterator(_Base::end(), this); }
595 
596  // local versions
598  begin(size_type __b)
599  { return local_iterator(_Base::begin(__b), __b, this); }
600 
602  end(size_type __b)
603  { return local_iterator(_Base::end(__b), __b, this); }
604 
606  begin(size_type __b) const
607  { return const_local_iterator(_Base::begin(__b), __b, this); }
608 
610  end(size_type __b) const
611  { return const_local_iterator(_Base::end(__b), __b, this); }
612 
614  cbegin(size_type __b) const
615  { return const_local_iterator(_Base::cbegin(__b), __b, this); }
616 
618  cend(size_type __b) const
619  { return const_local_iterator(_Base::cend(__b), __b, this); }
620 
621  template<typename... _Args>
622  iterator
623  emplace(_Args&&... __args)
624  {
625  size_type __bucket_count = this->bucket_count();
626  _Base_iterator __it
627  = _Base::emplace(std::forward<_Args>(__args)...);
628  _M_check_rehashed(__bucket_count);
629  return iterator(__it, this);
630  }
631 
632  template<typename... _Args>
633  iterator
634  emplace_hint(const_iterator __hint, _Args&&... __args)
635  {
636  __glibcxx_check_insert(__hint);
637  size_type __bucket_count = this->bucket_count();
638  _Base_iterator __it = _Base::emplace_hint(__hint.base(),
639  std::forward<_Args>(__args)...);
640  _M_check_rehashed(__bucket_count);
641  return iterator(__it, this);
642  }
643 
644  iterator
645  insert(const value_type& __obj)
646  {
647  size_type __bucket_count = this->bucket_count();
648  _Base_iterator __it = _Base::insert(__obj);
649  _M_check_rehashed(__bucket_count);
650  return iterator(__it, this);
651  }
652 
653  iterator
654  insert(const_iterator __hint, const value_type& __obj)
655  {
656  __glibcxx_check_insert(__hint);
657  size_type __bucket_count = this->bucket_count();
658  _Base_iterator __it = _Base::insert(__hint.base(), __obj);
659  _M_check_rehashed(__bucket_count);
660  return iterator(__it, this);
661  }
662 
663  template<typename _Pair, typename = typename
665  _Pair&&>::value>::type>
666  iterator
667  insert(_Pair&& __obj)
668  {
669  size_type __bucket_count = this->bucket_count();
670  _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj));
671  _M_check_rehashed(__bucket_count);
672  return iterator(__it, this);
673  }
674 
675  template<typename _Pair, typename = typename
677  _Pair&&>::value>::type>
678  iterator
679  insert(const_iterator __hint, _Pair&& __obj)
680  {
681  __glibcxx_check_insert(__hint);
682  size_type __bucket_count = this->bucket_count();
683  _Base_iterator __it =
684  _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
685  _M_check_rehashed(__bucket_count);
686  return iterator(__it, this);
687  }
688 
689  void
691  { _Base::insert(__l); }
692 
693  template<typename _InputIterator>
694  void
695  insert(_InputIterator __first, _InputIterator __last)
696  {
697  __glibcxx_check_valid_range(__first, __last);
698  size_type __bucket_count = this->bucket_count();
699  _Base::insert(__gnu_debug::__base(__first),
700  __gnu_debug::__base(__last));
701  _M_check_rehashed(__bucket_count);
702  }
703 
704  iterator
705  find(const key_type& __key)
706  { return iterator(_Base::find(__key), this); }
707 
709  find(const key_type& __key) const
710  { return const_iterator(_Base::find(__key), this); }
711 
713  equal_range(const key_type& __key)
714  {
716  _Base::equal_range(__key);
717  return std::make_pair(iterator(__res.first, this),
718  iterator(__res.second, this));
719  }
720 
722  equal_range(const key_type& __key) const
723  {
725  _Base::equal_range(__key);
726  return std::make_pair(const_iterator(__res.first, this),
727  const_iterator(__res.second, this));
728  }
729 
730  size_type
731  erase(const key_type& __key)
732  {
733  size_type __ret(0);
734  size_type __bucket_count = this->bucket_count();
736  _Base::equal_range(__key);
737  for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
738  {
739  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
740  { return __it == __victim; });
741  _Base_local_iterator __local_victim = _S_to_local(__victim);
743  [__local_victim](_Base_const_local_iterator __it)
744  { return __it == __local_victim; });
745  _Base::erase(__victim++);
746  ++__ret;
747  }
748  _M_check_rehashed(__bucket_count);
749  return __ret;
750  }
751 
752  iterator
753  erase(const_iterator __it)
754  {
755  __glibcxx_check_erase(__it);
756  _Base_const_iterator __victim = __it.base();
757  this->_M_invalidate_if([__victim](_Base_const_iterator __it)
758  { return __it == __victim; });
759  _Base_const_local_iterator __local_victim = _S_to_local(__victim);
761  [__local_victim](_Base_const_local_iterator __it)
762  { return __it == __local_victim; });
763  size_type __bucket_count = this->bucket_count();
764  _Base_iterator __next = _Base::erase(__it.base());
765  _M_check_rehashed(__bucket_count);
766  return iterator(__next, this);
767  }
768 
769  iterator
770  erase(iterator __it)
771  { return erase(const_iterator(__it)); }
772 
773  iterator
774  erase(const_iterator __first, const_iterator __last)
775  {
776  __glibcxx_check_erase_range(__first, __last);
777  for (_Base_const_iterator __tmp = __first.base();
778  __tmp != __last.base(); ++__tmp)
779  {
780  _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
781  _M_message(__gnu_debug::__msg_valid_range)
782  ._M_iterator(__first, "first")
783  ._M_iterator(__last, "last"));
784  this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
785  { return __it == __tmp; });
786  _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
788  [__local_tmp](_Base_const_local_iterator __it)
789  { return __it == __local_tmp; });
790  }
791  size_type __bucket_count = this->bucket_count();
792  _Base_iterator __next = _Base::erase(__first.base(), __last.base());
793  _M_check_rehashed(__bucket_count);
794  return iterator(__next, this);
795  }
796 
797  _Base&
798  _M_base() noexcept { return *this; }
799 
800  const _Base&
801  _M_base() const noexcept { return *this; }
802 
803  private:
804  void
805  _M_invalidate_locals()
806  {
807  _Base_local_iterator __local_end = _Base::end(0);
809  [__local_end](_Base_const_local_iterator __it)
810  { return __it != __local_end; });
811  }
812 
813  void
814  _M_invalidate_all()
815  {
816  _Base_iterator __end = _Base::end();
817  this->_M_invalidate_if([__end](_Base_const_iterator __it)
818  { return __it != __end; });
819  _M_invalidate_locals();
820  }
821 
822  void
823  _M_check_rehashed(size_type __prev_count)
824  {
825  if (__prev_count != this->bucket_count())
826  _M_invalidate_locals();
827  }
828 
829  static _Base_local_iterator
830  _S_to_local(_Base_iterator __it)
831  {
832  // The returned local iterator will not be incremented so we don't
833  // need to compute __it's node bucket
834  return _Base_local_iterator(__it._M_cur, 0, 0);
835  }
836 
837  static _Base_const_local_iterator
838  _S_to_local(_Base_const_iterator __it)
839  {
840  // The returned local iterator will not be incremented so we don't
841  // need to compute __it's node bucket
842  return _Base_const_local_iterator(__it._M_cur, 0, 0);
843  }
844  };
845 
846  template<typename _Key, typename _Tp, typename _Hash,
847  typename _Pred, typename _Alloc>
848  inline void
851  { __x.swap(__y); }
852 
853  template<typename _Key, typename _Tp, typename _Hash,
854  typename _Pred, typename _Alloc>
855  inline bool
858  { return __x._M_equal(__y); }
859 
860  template<typename _Key, typename _Tp, typename _Hash,
861  typename _Pred, typename _Alloc>
862  inline bool
863  operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
864  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
865  { return !(__x == __y); }
866 
867 } // namespace __debug
868 } // namespace std
869 
870 #endif // __GXX_EXPERIMENTAL_CXX0X__
871 
872 #endif