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