OSDN Git Service

2011-11-23 Fran├žois Dumont <fdumont@gcc.gnu.org>
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / debug / unordered_map
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
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> >
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       std::pair<iterator, bool>
208       insert(const value_type& __obj)
209       {
210         size_type __bucket_count = this->bucket_count();
211         std::pair<_Base_iterator, bool> __res = _Base::insert(__obj);
212         _M_check_rehashed(__bucket_count);
213         return std::make_pair(iterator(__res.first, this), __res.second);
214       }
215
216       iterator
217       insert(const_iterator __hint, const value_type& __obj)
218       {
219         __glibcxx_check_insert(__hint);
220         size_type __bucket_count = this->bucket_count();
221         _Base_iterator __it = _Base::insert(__hint.base(), __obj); 
222         _M_check_rehashed(__bucket_count);
223         return iterator(__it, this);
224       }
225
226       template<typename _Pair, typename = typename
227                std::enable_if<std::is_convertible<_Pair,
228                                                   value_type>::value>::type>
229         std::pair<iterator, bool>
230         insert(_Pair&& __obj)
231         {
232           size_type __bucket_count = this->bucket_count();
233           std::pair<_Base_iterator, bool> __res =
234             _Base::insert(std::forward<_Pair>(__obj));
235           _M_check_rehashed(__bucket_count);
236           return std::make_pair(iterator(__res.first, this), __res.second);
237         }
238
239       template<typename _Pair, typename = typename
240                std::enable_if<std::is_convertible<_Pair,
241                                                   value_type>::value>::type>
242         iterator
243         insert(const_iterator __hint, _Pair&& __obj)
244         {
245           __glibcxx_check_insert(__hint);
246           size_type __bucket_count = this->bucket_count();
247           _Base_iterator __it =
248             _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
249           _M_check_rehashed(__bucket_count);
250           return iterator(__it, this);
251         }
252
253       void
254       insert(std::initializer_list<value_type> __l)
255       {
256         size_type __bucket_count = this->bucket_count();
257         _Base::insert(__l);
258         _M_check_rehashed(__bucket_count);
259       }
260
261       template<typename _InputIterator>
262         void
263         insert(_InputIterator __first, _InputIterator __last)
264         {
265           __glibcxx_check_valid_range(__first, __last);
266           size_type __bucket_count = this->bucket_count();
267           _Base::insert(__gnu_debug::__base(__first),
268                         __gnu_debug::__base(__last));
269           _M_check_rehashed(__bucket_count);
270         }
271
272       iterator
273       find(const key_type& __key)
274       { return iterator(_Base::find(__key), this); }
275
276       const_iterator
277       find(const key_type& __key) const
278       { return const_iterator(_Base::find(__key), this); }
279
280       std::pair<iterator, iterator>
281       equal_range(const key_type& __key)
282       {
283         std::pair<_Base_iterator, _Base_iterator> __res =
284           _Base::equal_range(__key);
285         return std::make_pair(iterator(__res.first, this),
286                               iterator(__res.second, this));
287       }
288
289       std::pair<const_iterator, const_iterator>
290       equal_range(const key_type& __key) const
291       {
292         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
293           _Base::equal_range(__key);
294         return std::make_pair(const_iterator(__res.first, this),
295                               const_iterator(__res.second, this));
296       }
297
298       size_type
299       erase(const key_type& __key)
300       {
301         size_type __ret(0);
302         _Base_iterator __victim(_Base::find(__key));
303         if (__victim != _Base::end())
304           {
305             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
306                             { return __it == __victim; });
307             _Base_local_iterator __local_victim = _S_to_local(__victim);
308             this->_M_invalidate_local_if(
309                             [__local_victim](_Base_const_local_iterator __it)
310                             { return __it == __local_victim; });
311             size_type __bucket_count = this->bucket_count();
312             _Base::erase(__victim);
313             _M_check_rehashed(__bucket_count);
314             __ret = 1;
315           }
316         return __ret;
317       }
318
319       iterator
320       erase(const_iterator __it)
321       {
322         __glibcxx_check_erase(__it);
323         _Base_const_iterator __victim = __it.base();
324         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
325                         { return __it == __victim; });
326         _Base_const_local_iterator __local_victim = _S_to_local(__victim);
327         this->_M_invalidate_local_if(
328                         [__local_victim](_Base_const_local_iterator __it)
329                         { return __it == __local_victim; });
330         size_type __bucket_count = this->bucket_count();
331         _Base_iterator __next = _Base::erase(__it.base()); 
332         _M_check_rehashed(__bucket_count);
333         return iterator(__next, this);
334       }
335
336       iterator
337       erase(iterator __it)
338       { return erase(const_iterator(__it)); }
339
340       iterator
341       erase(const_iterator __first, const_iterator __last)
342       {
343         __glibcxx_check_erase_range(__first, __last);
344         for (_Base_const_iterator __tmp = __first.base();
345              __tmp != __last.base(); ++__tmp)
346           {
347             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
348                                   _M_message(__gnu_debug::__msg_valid_range)
349                                   ._M_iterator(__first, "first")
350                                   ._M_iterator(__last, "last"));
351             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
352                             { return __it == __tmp; });
353             _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
354             this->_M_invalidate_local_if(
355                             [__local_tmp](_Base_const_local_iterator __it)
356                             { return __it == __local_tmp; });
357           }
358         size_type __bucket_count = this->bucket_count();
359         _Base_iterator __next = _Base::erase(__first.base(), __last.base());
360         _M_check_rehashed(__bucket_count);
361         return iterator(__next, this);
362       }
363
364       _Base&
365       _M_base() noexcept       { return *this; }
366
367       const _Base&
368       _M_base() const noexcept { return *this; }
369
370     private:
371       void
372       _M_invalidate_locals()
373       {
374         _Base_local_iterator __local_end = _Base::end(0);
375         this->_M_invalidate_local_if(
376                         [__local_end](_Base_const_local_iterator __it)
377                         { return __it != __local_end; });
378       }
379
380       void
381       _M_invalidate_all()
382       {
383         _Base_iterator __end = _Base::end();
384         this->_M_invalidate_if([__end](_Base_const_iterator __it)
385                         { return __it != __end; });
386         _M_invalidate_locals();
387       }
388
389       void
390       _M_check_rehashed(size_type __prev_count)
391       {
392         if (__prev_count != this->bucket_count())
393           _M_invalidate_locals();
394       }
395
396       static _Base_local_iterator
397       _S_to_local(_Base_iterator __it)
398       { return _Base_local_iterator(__it._M_cur); }
399
400       static _Base_const_local_iterator
401       _S_to_local(_Base_const_iterator __it)
402       { return _Base_const_local_iterator(__it._M_cur); }
403     };
404
405   template<typename _Key, typename _Tp, typename _Hash,
406            typename _Pred, typename _Alloc>
407     inline void
408     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
409          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
410     { __x.swap(__y); }
411
412   template<typename _Key, typename _Tp, typename _Hash,
413            typename _Pred, typename _Alloc>
414     inline bool
415     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
416                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
417     { return __x._M_equal(__y); }
418
419   template<typename _Key, typename _Tp, typename _Hash,
420            typename _Pred, typename _Alloc>
421     inline bool
422     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
423                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
424     { return !(__x == __y); }
425
426
427   /// Class std::unordered_multimap with safety/checking/debug instrumentation.
428   template<typename _Key, typename _Tp,
429            typename _Hash = std::hash<_Key>,
430            typename _Pred = std::equal_to<_Key>,
431            typename _Alloc = std::allocator<_Key> >
432     class unordered_multimap
433     : public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
434                                                 _Pred, _Alloc>,
435       public __gnu_debug::_Safe_unordered_container<unordered_multimap<_Key,
436                                                 _Tp, _Hash, _Pred, _Alloc> >
437     {
438       typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
439                                                  _Pred, _Alloc> _Base;
440       typedef __gnu_debug::_Safe_unordered_container<unordered_multimap>
441         _Safe_base;
442       typedef typename _Base::const_iterator _Base_const_iterator;
443       typedef typename _Base::iterator _Base_iterator;
444       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
445       typedef typename _Base::local_iterator _Base_local_iterator;
446
447     public:
448       typedef typename _Base::size_type       size_type;
449       typedef typename _Base::hasher          hasher;
450       typedef typename _Base::key_equal       key_equal;
451       typedef typename _Base::allocator_type  allocator_type;
452
453       typedef typename _Base::key_type        key_type;
454       typedef typename _Base::value_type      value_type;
455
456       typedef __gnu_debug::_Safe_iterator<_Base_iterator,
457                                           unordered_multimap> iterator;
458       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
459                                           unordered_multimap> const_iterator;
460       typedef __gnu_debug::_Safe_local_iterator<
461         _Base_local_iterator, unordered_multimap> local_iterator;
462       typedef __gnu_debug::_Safe_local_iterator<
463         _Base_const_local_iterator, unordered_multimap> const_local_iterator;
464
465       explicit
466       unordered_multimap(size_type __n = 10,
467                          const hasher& __hf = hasher(),
468                          const key_equal& __eql = key_equal(),
469                          const allocator_type& __a = allocator_type())
470       : _Base(__n, __hf, __eql, __a) { }
471
472       template<typename _InputIterator>
473         unordered_multimap(_InputIterator __first, _InputIterator __last, 
474                            size_type __n = 0,
475                            const hasher& __hf = hasher(), 
476                            const key_equal& __eql = key_equal(), 
477                            const allocator_type& __a = allocator_type())
478         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
479                                                                      __last)),
480                 __gnu_debug::__base(__last), __n,
481                 __hf, __eql, __a) { }
482
483       unordered_multimap(const unordered_multimap& __x) 
484       : _Base(__x) { }
485
486       unordered_multimap(const _Base& __x) 
487       : _Base(__x) { }
488
489       unordered_multimap(unordered_multimap&& __x)
490       : _Base(std::move(__x)) { }
491
492       unordered_multimap(initializer_list<value_type> __l,
493                          size_type __n = 0,
494                          const hasher& __hf = hasher(),
495                          const key_equal& __eql = key_equal(),
496                          const allocator_type& __a = allocator_type())
497       : _Base(__l, __n, __hf, __eql, __a) { }
498
499       ~unordered_multimap() noexcept { }
500
501       unordered_multimap&
502       operator=(const unordered_multimap& __x)
503       {
504         *static_cast<_Base*>(this) = __x;
505         this->_M_invalidate_all();
506         return *this;
507       }
508
509       unordered_multimap&
510       operator=(unordered_multimap&& __x)
511       {
512         // NB: DR 1204.
513         // NB: DR 675.
514         clear();
515         swap(__x);
516         return *this;
517       }
518
519       unordered_multimap&
520       operator=(initializer_list<value_type> __l)
521       {
522         this->clear();
523         this->insert(__l);
524         return *this;
525       }
526
527       void
528       swap(unordered_multimap& __x)
529       {
530         _Base::swap(__x);
531         _Safe_base::_M_swap(__x);
532       }
533
534       void
535       clear() noexcept
536       {
537         _Base::clear();
538         this->_M_invalidate_all();
539       }
540
541       iterator 
542       begin() noexcept
543       { return iterator(_Base::begin(), this); }
544
545       const_iterator
546       begin() const noexcept
547       { return const_iterator(_Base::begin(), this); }
548
549       iterator
550       end() noexcept
551       { return iterator(_Base::end(), this); }
552
553       const_iterator
554       end() const noexcept
555       { return const_iterator(_Base::end(), this); }
556
557       const_iterator
558       cbegin() const noexcept
559       { return const_iterator(_Base::begin(), this); }
560
561       const_iterator
562       cend() const noexcept
563       { return const_iterator(_Base::end(), this); }
564
565       // local versions
566       local_iterator
567       begin(size_type __b)
568       { return local_iterator(_Base::begin(__b), __b, this); }
569
570       local_iterator
571       end(size_type __b)
572       { return local_iterator(_Base::end(__b), __b, this); }
573
574       const_local_iterator
575       begin(size_type __b) const
576       { return const_local_iterator(_Base::begin(__b), __b, this); }
577
578       const_local_iterator
579       end(size_type __b) const
580       { return const_local_iterator(_Base::end(__b), __b, this); }
581
582       const_local_iterator
583       cbegin(size_type __b) const
584       { return const_local_iterator(_Base::cbegin(__b), __b, this); }
585
586       const_local_iterator
587       cend(size_type __b) const
588       { return const_local_iterator(_Base::cend(__b), __b, this); }
589
590       iterator
591       insert(const value_type& __obj)
592       {
593         size_type __bucket_count = this->bucket_count();
594         _Base_iterator __it = _Base::insert(__obj);
595         _M_check_rehashed(__bucket_count);
596         return iterator(__it, this);
597       }
598
599       iterator
600       insert(const_iterator __hint, const value_type& __obj)
601       {
602         __glibcxx_check_insert(__hint);
603         size_type __bucket_count = this->bucket_count();
604         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
605         _M_check_rehashed(__bucket_count);
606         return iterator(__it, this);
607       }
608
609       template<typename _Pair, typename = typename
610                std::enable_if<std::is_convertible<_Pair,
611                                                   value_type>::value>::type>
612         iterator
613         insert(_Pair&& __obj)
614         {
615           size_type __bucket_count = this->bucket_count();
616           _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj));
617           _M_check_rehashed(__bucket_count);
618           return iterator(__it, this);
619         }
620
621       template<typename _Pair, typename = typename
622                std::enable_if<std::is_convertible<_Pair,
623                                                   value_type>::value>::type>
624         iterator
625         insert(const_iterator __hint, _Pair&& __obj)
626         {
627           __glibcxx_check_insert(__hint);
628           size_type __bucket_count = this->bucket_count();
629           _Base_iterator __it =
630             _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
631           _M_check_rehashed(__bucket_count);
632           return iterator(__it, this);
633         }
634
635       void
636       insert(std::initializer_list<value_type> __l)
637       { _Base::insert(__l); }
638
639       template<typename _InputIterator>
640         void
641         insert(_InputIterator __first, _InputIterator __last)
642         {
643           __glibcxx_check_valid_range(__first, __last);
644           size_type __bucket_count = this->bucket_count();
645           _Base::insert(__gnu_debug::__base(__first),
646                         __gnu_debug::__base(__last));
647           _M_check_rehashed(__bucket_count);
648         }
649
650       iterator
651       find(const key_type& __key)
652       { return iterator(_Base::find(__key), this); }
653
654       const_iterator
655       find(const key_type& __key) const
656       { return const_iterator(_Base::find(__key), this); }
657
658       std::pair<iterator, iterator>
659       equal_range(const key_type& __key)
660       {
661         std::pair<_Base_iterator, _Base_iterator> __res =
662           _Base::equal_range(__key);
663         return std::make_pair(iterator(__res.first, this),
664                               iterator(__res.second, this));
665       }
666
667       std::pair<const_iterator, const_iterator>
668       equal_range(const key_type& __key) const
669       {
670         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
671           _Base::equal_range(__key);
672         return std::make_pair(const_iterator(__res.first, this),
673                               const_iterator(__res.second, this));
674       }
675
676       size_type
677       erase(const key_type& __key)
678       {
679         size_type __ret(0);
680         size_type __bucket_count = this->bucket_count();
681         std::pair<_Base_iterator, _Base_iterator> __pair =
682           _Base::equal_range(__key);
683         for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
684           {
685             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
686                             { return __it == __victim; });
687             _Base_local_iterator __local_victim = _S_to_local(__victim);
688             this->_M_invalidate_local_if(
689                             [__local_victim](_Base_const_local_iterator __it)
690                             { return __it == __local_victim; });
691             _Base::erase(__victim++);
692             ++__ret;
693           }
694         _M_check_rehashed(__bucket_count);
695         return __ret;
696       }
697
698       iterator
699       erase(const_iterator __it)
700       {
701         __glibcxx_check_erase(__it);
702         _Base_const_iterator __victim = __it.base();
703         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
704                         { return __it == __victim; });
705         _Base_const_local_iterator __local_victim = _S_to_local(__victim);
706         this->_M_invalidate_local_if(
707                         [__local_victim](_Base_const_local_iterator __it)
708                         { return __it == __local_victim; });
709         size_type __bucket_count = this->bucket_count();
710         _Base_iterator __next = _Base::erase(__it.base());
711         _M_check_rehashed(__bucket_count);
712         return iterator(__next, this);
713       }
714
715       iterator
716       erase(iterator __it)
717       { return erase(const_iterator(__it)); }
718
719       iterator
720       erase(const_iterator __first, const_iterator __last)
721       {
722         __glibcxx_check_erase_range(__first, __last);
723         for (_Base_const_iterator __tmp = __first.base();
724              __tmp != __last.base(); ++__tmp)
725           {
726             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
727                                   _M_message(__gnu_debug::__msg_valid_range)
728                                   ._M_iterator(__first, "first")
729                                   ._M_iterator(__last, "last"));
730             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
731                             { return __it == __tmp; });
732             _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
733             this->_M_invalidate_local_if(
734                             [__local_tmp](_Base_const_local_iterator __it)
735                             { return __it == __local_tmp; });
736           }
737         size_type __bucket_count = this->bucket_count();
738         _Base_iterator __next = _Base::erase(__first.base(), __last.base());
739         _M_check_rehashed(__bucket_count);
740         return iterator(__next, this);
741       }
742
743       _Base&
744       _M_base() noexcept       { return *this; }
745
746       const _Base&
747       _M_base() const noexcept { return *this; }
748
749     private:
750       void
751       _M_invalidate_locals()
752       {
753         _Base_local_iterator __local_end = _Base::end(0);
754         this->_M_invalidate_local_if(
755                         [__local_end](_Base_const_local_iterator __it)
756                         { return __it != __local_end; });
757       }
758
759       void
760       _M_invalidate_all()
761       {
762         _Base_iterator __end = _Base::end();
763         this->_M_invalidate_if([__end](_Base_const_iterator __it)
764                         { return __it != __end; });
765         _M_invalidate_locals();
766       }
767
768       void
769       _M_check_rehashed(size_type __prev_count)
770       {
771         if (__prev_count != this->bucket_count())
772           _M_invalidate_locals();
773       }
774
775       static _Base_local_iterator
776       _S_to_local(_Base_iterator __it)
777       { return _Base_local_iterator(__it._M_cur); }
778
779       static _Base_const_local_iterator
780       _S_to_local(_Base_const_iterator __it)
781       { return _Base_const_local_iterator(__it._M_cur); }
782     };
783
784   template<typename _Key, typename _Tp, typename _Hash,
785            typename _Pred, typename _Alloc>
786     inline void
787     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
788          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
789     { __x.swap(__y); }
790
791   template<typename _Key, typename _Tp, typename _Hash,
792            typename _Pred, typename _Alloc>
793     inline bool
794     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
795                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
796     { return __x._M_equal(__y); }
797
798   template<typename _Key, typename _Tp, typename _Hash,
799            typename _Pred, typename _Alloc>
800     inline bool
801     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
802                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
803     { return !(__x == __y); }
804
805 } // namespace __debug
806 } // namespace std
807
808 #endif // __GXX_EXPERIMENTAL_CXX0X__
809
810 #endif