OSDN Git Service

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