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