libstdc++
debug/unordered_map
Go to the documentation of this file.
00001 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 3, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 /** @file debug/unordered_map
00027  *  This file is a GNU debug extension to the Standard C++ Library.
00028  */
00029 
00030 #ifndef _GLIBCXX_DEBUG_UNORDERED_MAP
00031 #define _GLIBCXX_DEBUG_UNORDERED_MAP 1
00032 
00033 #ifndef __GXX_EXPERIMENTAL_CXX0X__
00034 # include <bits/c++0x_warning.h>
00035 #else
00036 # include <unordered_map>
00037 
00038 #include <debug/safe_unordered_container.h>
00039 #include <debug/safe_iterator.h>
00040 #include <debug/safe_local_iterator.h>
00041 
00042 namespace std _GLIBCXX_VISIBILITY(default)
00043 {
00044 namespace __debug
00045 {
00046   /// Class std::unordered_map with safety/checking/debug instrumentation.
00047   template<typename _Key, typename _Tp,
00048        typename _Hash = std::hash<_Key>,
00049        typename _Pred = std::equal_to<_Key>,
00050        typename _Alloc = std::allocator<_Key> >
00051     class unordered_map
00052     : public _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>,
00053       public __gnu_debug::_Safe_unordered_container<unordered_map<_Key, _Tp,
00054                             _Hash, _Pred, _Alloc> >
00055     {
00056       typedef _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash,
00057                         _Pred, _Alloc> _Base;
00058       typedef __gnu_debug::_Safe_unordered_container<unordered_map> _Safe_base;
00059       typedef typename _Base::const_iterator _Base_const_iterator;
00060       typedef typename _Base::iterator _Base_iterator;
00061       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
00062       typedef typename _Base::local_iterator _Base_local_iterator;
00063 
00064     public:
00065       typedef typename _Base::size_type       size_type;
00066       typedef typename _Base::hasher          hasher;
00067       typedef typename _Base::key_equal       key_equal;
00068       typedef typename _Base::allocator_type  allocator_type;
00069 
00070       typedef typename _Base::key_type        key_type;
00071       typedef typename _Base::value_type      value_type;
00072 
00073       typedef __gnu_debug::_Safe_iterator<_Base_iterator,
00074                       unordered_map> iterator;
00075       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
00076                       unordered_map> const_iterator;
00077       typedef __gnu_debug::_Safe_local_iterator<_Base_local_iterator,
00078                       unordered_map> local_iterator;
00079       typedef __gnu_debug::_Safe_local_iterator<_Base_const_local_iterator,
00080                       unordered_map> const_local_iterator;
00081 
00082       explicit
00083       unordered_map(size_type __n = 10,
00084             const hasher& __hf = hasher(),
00085             const key_equal& __eql = key_equal(),
00086             const allocator_type& __a = allocator_type())
00087       : _Base(__n, __hf, __eql, __a) { }
00088 
00089       template<typename _InputIterator>
00090     unordered_map(_InputIterator __first, _InputIterator __last, 
00091               size_type __n = 0,
00092               const hasher& __hf = hasher(), 
00093               const key_equal& __eql = key_equal(), 
00094               const allocator_type& __a = allocator_type())
00095     : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00096                                      __last)),
00097         __gnu_debug::__base(__last), __n,
00098         __hf, __eql, __a) { }
00099 
00100       unordered_map(const unordered_map& __x) 
00101       : _Base(__x) { }
00102 
00103       unordered_map(const _Base& __x)
00104       : _Base(__x) { }
00105 
00106       unordered_map(unordered_map&& __x)
00107       : _Base(std::move(__x)) { }
00108 
00109       unordered_map(initializer_list<value_type> __l,
00110             size_type __n = 0,
00111             const hasher& __hf = hasher(),
00112             const key_equal& __eql = key_equal(),
00113             const allocator_type& __a = allocator_type())
00114       : _Base(__l, __n, __hf, __eql, __a) { }
00115 
00116       ~unordered_map() noexcept { }
00117 
00118       unordered_map&
00119       operator=(const unordered_map& __x)
00120       {
00121     *static_cast<_Base*>(this) = __x;
00122     this->_M_invalidate_all();
00123     return *this;
00124       }
00125 
00126       unordered_map&
00127       operator=(unordered_map&& __x)
00128       {
00129     // NB: DR 1204.
00130     // NB: DR 675.
00131     clear();
00132     swap(__x);
00133     return *this;
00134       }
00135 
00136       unordered_map&
00137       operator=(initializer_list<value_type> __l)
00138       {
00139     this->clear();
00140     this->insert(__l);
00141     return *this;
00142       }
00143 
00144       void
00145       swap(unordered_map& __x)
00146       {
00147     _Base::swap(__x);
00148     _Safe_base::_M_swap(__x);
00149       }
00150 
00151       void
00152       clear() noexcept
00153       {
00154     _Base::clear();
00155     this->_M_invalidate_all();
00156       }
00157 
00158       iterator 
00159       begin() noexcept
00160       { return iterator(_Base::begin(), this); }
00161 
00162       const_iterator
00163       begin() const noexcept
00164       { return const_iterator(_Base::begin(), this); }
00165 
00166       iterator
00167       end() noexcept
00168       { return iterator(_Base::end(), this); }
00169 
00170       const_iterator
00171       end() const noexcept
00172       { return const_iterator(_Base::end(), this); }
00173 
00174       const_iterator
00175       cbegin() const noexcept
00176       { return const_iterator(_Base::begin(), this); }
00177 
00178       const_iterator
00179       cend() const noexcept
00180       { return const_iterator(_Base::end(), this); }
00181 
00182       // local versions
00183       local_iterator
00184       begin(size_type __b)
00185       { return local_iterator(_Base::begin(__b), __b, this); }
00186 
00187       local_iterator
00188       end(size_type __b)
00189       { return local_iterator(_Base::end(__b), __b, this); }
00190 
00191       const_local_iterator
00192       begin(size_type __b) const
00193       { return const_local_iterator(_Base::begin(__b), __b, this); }
00194 
00195       const_local_iterator
00196       end(size_type __b) const
00197       { return const_local_iterator(_Base::end(__b), __b, this); }
00198 
00199       const_local_iterator
00200       cbegin(size_type __b) const
00201       { return const_local_iterator(_Base::cbegin(__b), __b, this); }
00202 
00203       const_local_iterator
00204       cend(size_type __b) const
00205       { return const_local_iterator(_Base::cend(__b), __b, this); }
00206 
00207       template<typename... _Args>
00208     std::pair<iterator, bool>
00209     emplace(_Args&&... __args)
00210     {
00211       size_type __bucket_count = this->bucket_count();
00212       std::pair<_Base_iterator, bool> __res
00213         = _Base::emplace(std::forward<_Args>(__args)...);
00214       _M_check_rehashed(__bucket_count);
00215       return std::make_pair(iterator(__res.first, this), __res.second);
00216     }
00217 
00218       template<typename... _Args>
00219     iterator
00220     emplace_hint(const_iterator __hint, _Args&&... __args)
00221     {
00222       __glibcxx_check_insert(__hint);
00223       size_type __bucket_count = this->bucket_count();
00224       _Base_iterator __it = _Base::emplace_hint(__hint.base(),
00225                     std::forward<_Args>(__args)...);
00226       _M_check_rehashed(__bucket_count);
00227       return iterator(__it, this);
00228     }
00229 
00230       std::pair<iterator, bool>
00231       insert(const value_type& __obj)
00232       {
00233     size_type __bucket_count = this->bucket_count();
00234     std::pair<_Base_iterator, bool> __res = _Base::insert(__obj);
00235     _M_check_rehashed(__bucket_count);
00236     return std::make_pair(iterator(__res.first, this), __res.second);
00237       }
00238 
00239       iterator
00240       insert(const_iterator __hint, const value_type& __obj)
00241       {
00242     __glibcxx_check_insert(__hint);
00243     size_type __bucket_count = this->bucket_count();
00244     _Base_iterator __it = _Base::insert(__hint.base(), __obj); 
00245     _M_check_rehashed(__bucket_count);
00246     return iterator(__it, this);
00247       }
00248 
00249       template<typename _Pair, typename = typename
00250            std::enable_if<std::is_convertible<_Pair,
00251                           value_type>::value>::type>
00252     std::pair<iterator, bool>
00253     insert(_Pair&& __obj)
00254     {
00255       size_type __bucket_count = this->bucket_count();
00256       std::pair<_Base_iterator, bool> __res =
00257         _Base::insert(std::forward<_Pair>(__obj));
00258       _M_check_rehashed(__bucket_count);
00259       return std::make_pair(iterator(__res.first, this), __res.second);
00260     }
00261 
00262       template<typename _Pair, typename = typename
00263            std::enable_if<std::is_convertible<_Pair,
00264                           value_type>::value>::type>
00265     iterator
00266     insert(const_iterator __hint, _Pair&& __obj)
00267     {
00268       __glibcxx_check_insert(__hint);
00269       size_type __bucket_count = this->bucket_count();
00270       _Base_iterator __it =
00271         _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
00272       _M_check_rehashed(__bucket_count);
00273       return iterator(__it, this);
00274     }
00275 
00276       void
00277       insert(std::initializer_list<value_type> __l)
00278       {
00279     size_type __bucket_count = this->bucket_count();
00280     _Base::insert(__l);
00281     _M_check_rehashed(__bucket_count);
00282       }
00283 
00284       template<typename _InputIterator>
00285     void
00286     insert(_InputIterator __first, _InputIterator __last)
00287     {
00288       __glibcxx_check_valid_range(__first, __last);
00289       size_type __bucket_count = this->bucket_count();
00290       _Base::insert(__gnu_debug::__base(__first),
00291             __gnu_debug::__base(__last));
00292       _M_check_rehashed(__bucket_count);
00293     }
00294 
00295       iterator
00296       find(const key_type& __key)
00297       { return iterator(_Base::find(__key), this); }
00298 
00299       const_iterator
00300       find(const key_type& __key) const
00301       { return const_iterator(_Base::find(__key), this); }
00302 
00303       std::pair<iterator, iterator>
00304       equal_range(const key_type& __key)
00305       {
00306     std::pair<_Base_iterator, _Base_iterator> __res =
00307       _Base::equal_range(__key);
00308     return std::make_pair(iterator(__res.first, this),
00309                   iterator(__res.second, this));
00310       }
00311 
00312       std::pair<const_iterator, const_iterator>
00313       equal_range(const key_type& __key) const
00314       {
00315     std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00316       _Base::equal_range(__key);
00317     return std::make_pair(const_iterator(__res.first, this),
00318                   const_iterator(__res.second, this));
00319       }
00320 
00321       size_type
00322       erase(const key_type& __key)
00323       {
00324     size_type __ret(0);
00325     _Base_iterator __victim(_Base::find(__key));
00326     if (__victim != _Base::end())
00327       {
00328         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
00329                 { return __it == __victim; });
00330         _Base_local_iterator __local_victim = _S_to_local(__victim);
00331         this->_M_invalidate_local_if(
00332                 [__local_victim](_Base_const_local_iterator __it)
00333                 { return __it == __local_victim; });
00334         size_type __bucket_count = this->bucket_count();
00335         _Base::erase(__victim);
00336         _M_check_rehashed(__bucket_count);
00337         __ret = 1;
00338       }
00339     return __ret;
00340       }
00341 
00342       iterator
00343       erase(const_iterator __it)
00344       {
00345     __glibcxx_check_erase(__it);
00346     _Base_const_iterator __victim = __it.base();
00347     this->_M_invalidate_if([__victim](_Base_const_iterator __it)
00348             { return __it == __victim; });
00349     _Base_const_local_iterator __local_victim = _S_to_local(__victim);
00350     this->_M_invalidate_local_if(
00351             [__local_victim](_Base_const_local_iterator __it)
00352             { return __it == __local_victim; });
00353     size_type __bucket_count = this->bucket_count();
00354     _Base_iterator __next = _Base::erase(__it.base()); 
00355     _M_check_rehashed(__bucket_count);
00356     return iterator(__next, this);
00357       }
00358 
00359       iterator
00360       erase(iterator __it)
00361       { return erase(const_iterator(__it)); }
00362 
00363       iterator
00364       erase(const_iterator __first, const_iterator __last)
00365       {
00366     __glibcxx_check_erase_range(__first, __last);
00367     for (_Base_const_iterator __tmp = __first.base();
00368          __tmp != __last.base(); ++__tmp)
00369       {
00370         _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00371                   _M_message(__gnu_debug::__msg_valid_range)
00372                   ._M_iterator(__first, "first")
00373                   ._M_iterator(__last, "last"));
00374         this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
00375                 { return __it == __tmp; });
00376         _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
00377         this->_M_invalidate_local_if(
00378                 [__local_tmp](_Base_const_local_iterator __it)
00379                 { return __it == __local_tmp; });
00380       }
00381     size_type __bucket_count = this->bucket_count();
00382     _Base_iterator __next = _Base::erase(__first.base(), __last.base());
00383     _M_check_rehashed(__bucket_count);
00384     return iterator(__next, this);
00385       }
00386 
00387       _Base&
00388       _M_base() noexcept       { return *this; }
00389 
00390       const _Base&
00391       _M_base() const noexcept { return *this; }
00392 
00393     private:
00394       void
00395       _M_invalidate_locals()
00396       {
00397     _Base_local_iterator __local_end = _Base::end(0);
00398     this->_M_invalidate_local_if(
00399             [__local_end](_Base_const_local_iterator __it)
00400             { return __it != __local_end; });
00401       }
00402 
00403       void
00404       _M_invalidate_all()
00405       {
00406     _Base_iterator __end = _Base::end();
00407     this->_M_invalidate_if([__end](_Base_const_iterator __it)
00408             { return __it != __end; });
00409     _M_invalidate_locals();
00410       }
00411 
00412       void
00413       _M_check_rehashed(size_type __prev_count)
00414       {
00415     if (__prev_count != this->bucket_count())
00416       _M_invalidate_locals();
00417       }
00418 
00419       static _Base_local_iterator
00420       _S_to_local(_Base_iterator __it)
00421       {
00422         // The returned local iterator will not be incremented so we don't
00423     // need to compute __it's node bucket
00424     return _Base_local_iterator(__it._M_cur, 0, 0);
00425       }
00426 
00427       static _Base_const_local_iterator
00428       _S_to_local(_Base_const_iterator __it)
00429       {
00430         // The returned local iterator will not be incremented so we don't
00431     // need to compute __it's node bucket
00432     return _Base_const_local_iterator(__it._M_cur, 0, 0);
00433       }
00434     };
00435 
00436   template<typename _Key, typename _Tp, typename _Hash,
00437        typename _Pred, typename _Alloc>
00438     inline void
00439     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00440      unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00441     { __x.swap(__y); }
00442 
00443   template<typename _Key, typename _Tp, typename _Hash,
00444        typename _Pred, typename _Alloc>
00445     inline bool
00446     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00447            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00448     { return __x._M_equal(__y); }
00449 
00450   template<typename _Key, typename _Tp, typename _Hash,
00451        typename _Pred, typename _Alloc>
00452     inline bool
00453     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00454            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00455     { return !(__x == __y); }
00456 
00457 
00458   /// Class std::unordered_multimap with safety/checking/debug instrumentation.
00459   template<typename _Key, typename _Tp,
00460        typename _Hash = std::hash<_Key>,
00461        typename _Pred = std::equal_to<_Key>,
00462        typename _Alloc = std::allocator<_Key> >
00463     class unordered_multimap
00464     : public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
00465                         _Pred, _Alloc>,
00466       public __gnu_debug::_Safe_unordered_container<unordered_multimap<_Key,
00467                         _Tp, _Hash, _Pred, _Alloc> >
00468     {
00469       typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
00470                          _Pred, _Alloc> _Base;
00471       typedef __gnu_debug::_Safe_unordered_container<unordered_multimap>
00472     _Safe_base;
00473       typedef typename _Base::const_iterator _Base_const_iterator;
00474       typedef typename _Base::iterator _Base_iterator;
00475       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
00476       typedef typename _Base::local_iterator _Base_local_iterator;
00477 
00478     public:
00479       typedef typename _Base::size_type       size_type;
00480       typedef typename _Base::hasher          hasher;
00481       typedef typename _Base::key_equal       key_equal;
00482       typedef typename _Base::allocator_type  allocator_type;
00483 
00484       typedef typename _Base::key_type        key_type;
00485       typedef typename _Base::value_type      value_type;
00486 
00487       typedef __gnu_debug::_Safe_iterator<_Base_iterator,
00488                       unordered_multimap> iterator;
00489       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
00490                       unordered_multimap> const_iterator;
00491       typedef __gnu_debug::_Safe_local_iterator<
00492     _Base_local_iterator, unordered_multimap> local_iterator;
00493       typedef __gnu_debug::_Safe_local_iterator<
00494     _Base_const_local_iterator, unordered_multimap> const_local_iterator;
00495 
00496       explicit
00497       unordered_multimap(size_type __n = 10,
00498              const hasher& __hf = hasher(),
00499              const key_equal& __eql = key_equal(),
00500              const allocator_type& __a = allocator_type())
00501       : _Base(__n, __hf, __eql, __a) { }
00502 
00503       template<typename _InputIterator>
00504     unordered_multimap(_InputIterator __first, _InputIterator __last, 
00505                size_type __n = 0,
00506                const hasher& __hf = hasher(), 
00507                const key_equal& __eql = key_equal(), 
00508                const allocator_type& __a = allocator_type())
00509     : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00510                                      __last)),
00511         __gnu_debug::__base(__last), __n,
00512         __hf, __eql, __a) { }
00513 
00514       unordered_multimap(const unordered_multimap& __x) 
00515       : _Base(__x) { }
00516 
00517       unordered_multimap(const _Base& __x) 
00518       : _Base(__x) { }
00519 
00520       unordered_multimap(unordered_multimap&& __x)
00521       : _Base(std::move(__x)) { }
00522 
00523       unordered_multimap(initializer_list<value_type> __l,
00524              size_type __n = 0,
00525              const hasher& __hf = hasher(),
00526              const key_equal& __eql = key_equal(),
00527              const allocator_type& __a = allocator_type())
00528       : _Base(__l, __n, __hf, __eql, __a) { }
00529 
00530       ~unordered_multimap() noexcept { }
00531 
00532       unordered_multimap&
00533       operator=(const unordered_multimap& __x)
00534       {
00535     *static_cast<_Base*>(this) = __x;
00536     this->_M_invalidate_all();
00537     return *this;
00538       }
00539 
00540       unordered_multimap&
00541       operator=(unordered_multimap&& __x)
00542       {
00543     // NB: DR 1204.
00544     // NB: DR 675.
00545     clear();
00546     swap(__x);
00547     return *this;
00548       }
00549 
00550       unordered_multimap&
00551       operator=(initializer_list<value_type> __l)
00552       {
00553     this->clear();
00554     this->insert(__l);
00555     return *this;
00556       }
00557 
00558       void
00559       swap(unordered_multimap& __x)
00560       {
00561     _Base::swap(__x);
00562     _Safe_base::_M_swap(__x);
00563       }
00564 
00565       void
00566       clear() noexcept
00567       {
00568     _Base::clear();
00569     this->_M_invalidate_all();
00570       }
00571 
00572       iterator 
00573       begin() noexcept
00574       { return iterator(_Base::begin(), this); }
00575 
00576       const_iterator
00577       begin() const noexcept
00578       { return const_iterator(_Base::begin(), this); }
00579 
00580       iterator
00581       end() noexcept
00582       { return iterator(_Base::end(), this); }
00583 
00584       const_iterator
00585       end() const noexcept
00586       { return const_iterator(_Base::end(), this); }
00587 
00588       const_iterator
00589       cbegin() const noexcept
00590       { return const_iterator(_Base::begin(), this); }
00591 
00592       const_iterator
00593       cend() const noexcept
00594       { return const_iterator(_Base::end(), this); }
00595 
00596       // local versions
00597       local_iterator
00598       begin(size_type __b)
00599       { return local_iterator(_Base::begin(__b), __b, this); }
00600 
00601       local_iterator
00602       end(size_type __b)
00603       { return local_iterator(_Base::end(__b), __b, this); }
00604 
00605       const_local_iterator
00606       begin(size_type __b) const
00607       { return const_local_iterator(_Base::begin(__b), __b, this); }
00608 
00609       const_local_iterator
00610       end(size_type __b) const
00611       { return const_local_iterator(_Base::end(__b), __b, this); }
00612 
00613       const_local_iterator
00614       cbegin(size_type __b) const
00615       { return const_local_iterator(_Base::cbegin(__b), __b, this); }
00616 
00617       const_local_iterator
00618       cend(size_type __b) const
00619       { return const_local_iterator(_Base::cend(__b), __b, this); }
00620 
00621       template<typename... _Args>
00622     iterator
00623     emplace(_Args&&... __args)
00624     {
00625       size_type __bucket_count = this->bucket_count();
00626       _Base_iterator __it
00627         = _Base::emplace(std::forward<_Args>(__args)...);
00628       _M_check_rehashed(__bucket_count);
00629       return iterator(__it, this);
00630     }
00631 
00632       template<typename... _Args>
00633     iterator
00634     emplace_hint(const_iterator __hint, _Args&&... __args)
00635     {
00636       __glibcxx_check_insert(__hint);
00637       size_type __bucket_count = this->bucket_count();
00638       _Base_iterator __it = _Base::emplace_hint(__hint.base(),
00639                     std::forward<_Args>(__args)...);
00640       _M_check_rehashed(__bucket_count);
00641       return iterator(__it, this);
00642     }
00643 
00644       iterator
00645       insert(const value_type& __obj)
00646       {
00647     size_type __bucket_count = this->bucket_count();
00648     _Base_iterator __it = _Base::insert(__obj);
00649     _M_check_rehashed(__bucket_count);
00650     return iterator(__it, this);
00651       }
00652 
00653       iterator
00654       insert(const_iterator __hint, const value_type& __obj)
00655       {
00656     __glibcxx_check_insert(__hint);
00657     size_type __bucket_count = this->bucket_count();
00658     _Base_iterator __it = _Base::insert(__hint.base(), __obj);
00659     _M_check_rehashed(__bucket_count);
00660     return iterator(__it, this);
00661       }
00662 
00663       template<typename _Pair, typename = typename
00664            std::enable_if<std::is_convertible<_Pair,
00665                           value_type>::value>::type>
00666     iterator
00667     insert(_Pair&& __obj)
00668     {
00669       size_type __bucket_count = this->bucket_count();
00670       _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj));
00671       _M_check_rehashed(__bucket_count);
00672       return iterator(__it, this);
00673     }
00674 
00675       template<typename _Pair, typename = typename
00676            std::enable_if<std::is_convertible<_Pair,
00677                           value_type>::value>::type>
00678     iterator
00679     insert(const_iterator __hint, _Pair&& __obj)
00680     {
00681       __glibcxx_check_insert(__hint);
00682       size_type __bucket_count = this->bucket_count();
00683       _Base_iterator __it =
00684         _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
00685       _M_check_rehashed(__bucket_count);
00686       return iterator(__it, this);
00687     }
00688 
00689       void
00690       insert(std::initializer_list<value_type> __l)
00691       { _Base::insert(__l); }
00692 
00693       template<typename _InputIterator>
00694     void
00695     insert(_InputIterator __first, _InputIterator __last)
00696     {
00697       __glibcxx_check_valid_range(__first, __last);
00698       size_type __bucket_count = this->bucket_count();
00699       _Base::insert(__gnu_debug::__base(__first),
00700             __gnu_debug::__base(__last));
00701       _M_check_rehashed(__bucket_count);
00702     }
00703 
00704       iterator
00705       find(const key_type& __key)
00706       { return iterator(_Base::find(__key), this); }
00707 
00708       const_iterator
00709       find(const key_type& __key) const
00710       { return const_iterator(_Base::find(__key), this); }
00711 
00712       std::pair<iterator, iterator>
00713       equal_range(const key_type& __key)
00714       {
00715     std::pair<_Base_iterator, _Base_iterator> __res =
00716       _Base::equal_range(__key);
00717     return std::make_pair(iterator(__res.first, this),
00718                   iterator(__res.second, this));
00719       }
00720 
00721       std::pair<const_iterator, const_iterator>
00722       equal_range(const key_type& __key) const
00723       {
00724     std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00725       _Base::equal_range(__key);
00726     return std::make_pair(const_iterator(__res.first, this),
00727                   const_iterator(__res.second, this));
00728       }
00729 
00730       size_type
00731       erase(const key_type& __key)
00732       {
00733     size_type __ret(0);
00734     size_type __bucket_count = this->bucket_count();
00735     std::pair<_Base_iterator, _Base_iterator> __pair =
00736       _Base::equal_range(__key);
00737     for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
00738       {
00739         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
00740                 { return __it == __victim; });
00741         _Base_local_iterator __local_victim = _S_to_local(__victim);
00742         this->_M_invalidate_local_if(
00743                 [__local_victim](_Base_const_local_iterator __it)
00744                 { return __it == __local_victim; });
00745         _Base::erase(__victim++);
00746         ++__ret;
00747       }
00748     _M_check_rehashed(__bucket_count);
00749     return __ret;
00750       }
00751 
00752       iterator
00753       erase(const_iterator __it)
00754       {
00755     __glibcxx_check_erase(__it);
00756     _Base_const_iterator __victim = __it.base();
00757     this->_M_invalidate_if([__victim](_Base_const_iterator __it)
00758             { return __it == __victim; });
00759     _Base_const_local_iterator __local_victim = _S_to_local(__victim);
00760     this->_M_invalidate_local_if(
00761             [__local_victim](_Base_const_local_iterator __it)
00762             { return __it == __local_victim; });
00763     size_type __bucket_count = this->bucket_count();
00764     _Base_iterator __next = _Base::erase(__it.base());
00765     _M_check_rehashed(__bucket_count);
00766     return iterator(__next, this);
00767       }
00768 
00769       iterator
00770       erase(iterator __it)
00771       { return erase(const_iterator(__it)); }
00772 
00773       iterator
00774       erase(const_iterator __first, const_iterator __last)
00775       {
00776     __glibcxx_check_erase_range(__first, __last);
00777     for (_Base_const_iterator __tmp = __first.base();
00778          __tmp != __last.base(); ++__tmp)
00779       {
00780         _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00781                   _M_message(__gnu_debug::__msg_valid_range)
00782                   ._M_iterator(__first, "first")
00783                   ._M_iterator(__last, "last"));
00784         this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
00785                 { return __it == __tmp; });
00786         _Base_const_local_iterator __local_tmp = _S_to_local(__tmp);
00787         this->_M_invalidate_local_if(
00788                 [__local_tmp](_Base_const_local_iterator __it)
00789                 { return __it == __local_tmp; });
00790       }
00791     size_type __bucket_count = this->bucket_count();
00792     _Base_iterator __next = _Base::erase(__first.base(), __last.base());
00793     _M_check_rehashed(__bucket_count);
00794     return iterator(__next, this);
00795       }
00796 
00797       _Base&
00798       _M_base() noexcept       { return *this; }
00799 
00800       const _Base&
00801       _M_base() const noexcept { return *this; }
00802 
00803     private:
00804       void
00805       _M_invalidate_locals()
00806       {
00807     _Base_local_iterator __local_end = _Base::end(0);
00808     this->_M_invalidate_local_if(
00809             [__local_end](_Base_const_local_iterator __it)
00810             { return __it != __local_end; });
00811       }
00812 
00813       void
00814       _M_invalidate_all()
00815       {
00816     _Base_iterator __end = _Base::end();
00817     this->_M_invalidate_if([__end](_Base_const_iterator __it)
00818             { return __it != __end; });
00819     _M_invalidate_locals();
00820       }
00821 
00822       void
00823       _M_check_rehashed(size_type __prev_count)
00824       {
00825     if (__prev_count != this->bucket_count())
00826       _M_invalidate_locals();
00827       }
00828 
00829       static _Base_local_iterator
00830       _S_to_local(_Base_iterator __it)
00831       {
00832         // The returned local iterator will not be incremented so we don't
00833     // need to compute __it's node bucket
00834     return _Base_local_iterator(__it._M_cur, 0, 0);
00835       }
00836 
00837       static _Base_const_local_iterator
00838       _S_to_local(_Base_const_iterator __it)
00839       {
00840         // The returned local iterator will not be incremented so we don't
00841     // need to compute __it's node bucket
00842     return _Base_const_local_iterator(__it._M_cur, 0, 0);
00843       }
00844     };
00845 
00846   template<typename _Key, typename _Tp, typename _Hash,
00847        typename _Pred, typename _Alloc>
00848     inline void
00849     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00850      unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00851     { __x.swap(__y); }
00852 
00853   template<typename _Key, typename _Tp, typename _Hash,
00854        typename _Pred, typename _Alloc>
00855     inline bool
00856     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00857            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00858     { return __x._M_equal(__y); }
00859 
00860   template<typename _Key, typename _Tp, typename _Hash,
00861        typename _Pred, typename _Alloc>
00862     inline bool
00863     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00864            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00865     { return !(__x == __y); }
00866 
00867 } // namespace __debug
00868 } // namespace std
00869 
00870 #endif // __GXX_EXPERIMENTAL_CXX0X__
00871 
00872 #endif