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
38#include <debug/safe_unordered_container.h>
39#include <debug/safe_iterator.h>
40#include <debug/safe_local_iterator.h>
41
42namespace std _GLIBCXX_VISIBILITY(default)
43{
44namespace __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> >
51    class unordered_map
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;
58      typedef __gnu_debug::_Safe_unordered_container<unordered_map> _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_map> iterator;
75      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
76					  unordered_map> const_iterator;
77      typedef __gnu_debug::_Safe_local_iterator<_Base_local_iterator,
78					  unordered_map> local_iterator;
79      typedef __gnu_debug::_Safe_local_iterator<_Base_const_local_iterator,
80					  unordered_map> 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
106      unordered_map(unordered_map&& __x)
107      : _Base(std::move(__x)) { }
108
109      unordered_map(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_map() noexcept { }
117
118      unordered_map&
119      operator=(const unordered_map& __x)
120      {
121	*static_cast<_Base*>(this) = __x;
122	this->_M_invalidate_all();
123	return *this;
124      }
125
126      unordered_map&
127      operator=(unordered_map&& __x)
128      {
129   	// NB: DR 1204.
130	// NB: DR 675.
131	clear();
132	swap(__x);
133	return *this;
134      }
135
136      unordered_map&
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
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	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
250	       std::enable_if<std::is_constructible<value_type,
251						    _Pair&&>::value>::type>
252	std::pair<iterator, bool>
253	insert(_Pair&& __obj)
254	{
255	  size_type __bucket_count = this->bucket_count();
256	  std::pair<_Base_iterator, bool> __res =
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
263	       std::enable_if<std::is_constructible<value_type,
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
277      insert(std::initializer_list<value_type> __l)
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
299      const_iterator
300      find(const key_type& __key) const
301      { return const_iterator(_Base::find(__key), this); }
302
303      std::pair<iterator, iterator>
304      equal_range(const key_type& __key)
305      {
306	std::pair<_Base_iterator, _Base_iterator> __res =
307	  _Base::equal_range(__key);
308	return std::make_pair(iterator(__res.first, this),
309			      iterator(__res.second, this));
310      }
311
312      std::pair<const_iterator, const_iterator>
313      equal_range(const key_type& __key) const
314      {
315	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
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);
331	    this->_M_invalidate_local_if(
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);
350	this->_M_invalidate_local_if(
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);
377	    this->_M_invalidate_local_if(
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);
398	this->_M_invalidate_local_if(
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
439    swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
440	 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
441    { __x.swap(__y); }
442
443  template<typename _Key, typename _Tp, typename _Hash,
444	   typename _Pred, typename _Alloc>
445    inline bool
446    operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
447	       const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
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> >
463    class unordered_multimap
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;
471      typedef __gnu_debug::_Safe_unordered_container<unordered_multimap>
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,
488					  unordered_multimap> iterator;
489      typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
490					  unordered_multimap> const_iterator;
491      typedef __gnu_debug::_Safe_local_iterator<
492	_Base_local_iterator, unordered_multimap> local_iterator;
493      typedef __gnu_debug::_Safe_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
514      unordered_multimap(const unordered_multimap& __x) 
515      : _Base(__x) { }
516
517      unordered_multimap(const _Base& __x) 
518      : _Base(__x) { }
519
520      unordered_multimap(unordered_multimap&& __x)
521      : _Base(std::move(__x)) { }
522
523      unordered_multimap(initializer_list<value_type> __l,
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
532      unordered_multimap&
533      operator=(const unordered_multimap& __x)
534      {
535	*static_cast<_Base*>(this) = __x;
536	this->_M_invalidate_all();
537	return *this;
538      }
539
540      unordered_multimap&
541      operator=(unordered_multimap&& __x)
542      {
543	// NB: DR 1204.
544	// NB: DR 675.
545	clear();
546	swap(__x);
547	return *this;
548      }
549
550      unordered_multimap&
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
576      const_iterator
577      begin() const noexcept
578      { return const_iterator(_Base::begin(), this); }
579
580      iterator
581      end() noexcept
582      { return iterator(_Base::end(), this); }
583
584      const_iterator
585      end() const noexcept
586      { return const_iterator(_Base::end(), this); }
587
588      const_iterator
589      cbegin() const noexcept
590      { return const_iterator(_Base::begin(), this); }
591
592      const_iterator
593      cend() const noexcept
594      { return const_iterator(_Base::end(), this); }
595
596      // local versions
597      local_iterator
598      begin(size_type __b)
599      { return local_iterator(_Base::begin(__b), __b, this); }
600
601      local_iterator
602      end(size_type __b)
603      { return local_iterator(_Base::end(__b), __b, this); }
604
605      const_local_iterator
606      begin(size_type __b) const
607      { return const_local_iterator(_Base::begin(__b), __b, this); }
608
609      const_local_iterator
610      end(size_type __b) const
611      { return const_local_iterator(_Base::end(__b), __b, this); }
612
613      const_local_iterator
614      cbegin(size_type __b) const
615      { return const_local_iterator(_Base::cbegin(__b), __b, this); }
616
617      const_local_iterator
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
664	       std::enable_if<std::is_constructible<value_type,
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
676	       std::enable_if<std::is_constructible<value_type,
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
690      insert(std::initializer_list<value_type> __l)
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
708      const_iterator
709      find(const key_type& __key) const
710      { return const_iterator(_Base::find(__key), this); }
711
712      std::pair<iterator, iterator>
713      equal_range(const key_type& __key)
714      {
715	std::pair<_Base_iterator, _Base_iterator> __res =
716	  _Base::equal_range(__key);
717	return std::make_pair(iterator(__res.first, this),
718			      iterator(__res.second, this));
719      }
720
721      std::pair<const_iterator, const_iterator>
722      equal_range(const key_type& __key) const
723      {
724	std::pair<_Base_const_iterator, _Base_const_iterator> __res =
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();
735	std::pair<_Base_iterator, _Base_iterator> __pair =
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);
742	    this->_M_invalidate_local_if(
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);
760	this->_M_invalidate_local_if(
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);
787	    this->_M_invalidate_local_if(
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);
808	this->_M_invalidate_local_if(
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
849    swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
850	 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
851    { __x.swap(__y); }
852
853  template<typename _Key, typename _Tp, typename _Hash,
854	   typename _Pred, typename _Alloc>
855    inline bool
856    operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
857	       const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
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
873