OSDN Git Service

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