OSDN Git Service

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