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