libstdc++
unordered_map
Go to the documentation of this file.
00001 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003-2015 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           __glibcxx_check_valid_range(__first, __last);
00368           size_type __bucket_count = this->bucket_count();
00369           _Base::insert(__gnu_debug::__base(__first),
00370                           __gnu_debug::__base(__last));
00371           _M_check_rehashed(__bucket_count);
00372         }
00373 
00374       iterator
00375       find(const key_type& __key)
00376       { return iterator(_Base::find(__key), this); }
00377 
00378       const_iterator
00379       find(const key_type& __key) const
00380       { return const_iterator(_Base::find(__key), this); }
00381 
00382       std::pair<iterator, iterator>
00383       equal_range(const key_type& __key)
00384       {
00385         std::pair<_Base_iterator, _Base_iterator> __res =
00386           _Base::equal_range(__key);
00387         return std::make_pair(iterator(__res.first, this),
00388                               iterator(__res.second, this));
00389       }
00390 
00391       std::pair<const_iterator, const_iterator>
00392       equal_range(const key_type& __key) const
00393       {
00394         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00395           _Base::equal_range(__key);
00396         return std::make_pair(const_iterator(__res.first, this),
00397                               const_iterator(__res.second, this));
00398       }
00399 
00400       size_type
00401       erase(const key_type& __key)
00402       {
00403         size_type __ret(0);
00404         _Base_iterator __victim(_Base::find(__key));
00405         if (__victim != _Base::end())
00406           {
00407             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
00408                             { return __it == __victim; });
00409             this->_M_invalidate_local_if(
00410                             [__victim](_Base_const_local_iterator __it)
00411                             { return __it._M_curr() == __victim._M_cur; });
00412             size_type __bucket_count = this->bucket_count();
00413             _Base::erase(__victim);
00414             _M_check_rehashed(__bucket_count);
00415             __ret = 1;
00416           }
00417         return __ret;
00418       }
00419 
00420       iterator
00421       erase(const_iterator __it)
00422       {
00423         __glibcxx_check_erase(__it);
00424         _Base_const_iterator __victim = __it.base();
00425         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
00426                         { return __it == __victim; });
00427         this->_M_invalidate_local_if(
00428                         [__victim](_Base_const_local_iterator __it)
00429                         { return __it._M_curr() == __victim._M_cur; });
00430         size_type __bucket_count = this->bucket_count();
00431         _Base_iterator __next = _Base::erase(__it.base());
00432         _M_check_rehashed(__bucket_count);
00433         return iterator(__next, this);
00434       }
00435 
00436       iterator
00437       erase(iterator __it)
00438       { return erase(const_iterator(__it)); }
00439 
00440       iterator
00441       erase(const_iterator __first, const_iterator __last)
00442       {
00443         __glibcxx_check_erase_range(__first, __last);
00444         for (_Base_const_iterator __tmp = __first.base();
00445              __tmp != __last.base(); ++__tmp)
00446           {
00447             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00448                                   _M_message(__gnu_debug::__msg_valid_range)
00449                                   ._M_iterator(__first, "first")
00450                                   ._M_iterator(__last, "last"));
00451             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
00452                             { return __it == __tmp; });
00453             this->_M_invalidate_local_if(
00454                             [__tmp](_Base_const_local_iterator __it)
00455                             { return __it._M_curr() == __tmp._M_cur; });
00456           }
00457         size_type __bucket_count = this->bucket_count();
00458         _Base_iterator __next = _Base::erase(__first.base(), __last.base());
00459         _M_check_rehashed(__bucket_count);
00460         return iterator(__next, this);
00461       }
00462 
00463       _Base&
00464       _M_base() noexcept        { return *this; }
00465 
00466       const _Base&
00467       _M_base() const noexcept  { return *this; }
00468 
00469     private:
00470       void
00471       _M_check_rehashed(size_type __prev_count)
00472       {
00473         if (__prev_count != this->bucket_count())
00474           this->_M_invalidate_locals();
00475       }
00476     };
00477 
00478   template<typename _Key, typename _Tp, typename _Hash,
00479            typename _Pred, typename _Alloc>
00480     inline void
00481     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00482          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00483     { __x.swap(__y); }
00484 
00485   template<typename _Key, typename _Tp, typename _Hash,
00486            typename _Pred, typename _Alloc>
00487     inline bool
00488     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00489                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00490     { return __x._M_base() == __y._M_base(); }
00491 
00492   template<typename _Key, typename _Tp, typename _Hash,
00493            typename _Pred, typename _Alloc>
00494     inline bool
00495     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00496                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00497     { return !(__x == __y); }
00498 
00499 
00500   /// Class std::unordered_multimap with safety/checking/debug instrumentation.
00501   template<typename _Key, typename _Tp,
00502            typename _Hash = std::hash<_Key>,
00503            typename _Pred = std::equal_to<_Key>,
00504            typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
00505     class unordered_multimap
00506       : public __gnu_debug::_Safe_container<
00507         unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
00508         __gnu_debug::_Safe_unordered_container>,
00509         public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
00510     {
00511       typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
00512                                                  _Pred, _Alloc>         _Base;
00513       typedef __gnu_debug::_Safe_container<unordered_multimap,
00514         _Alloc, __gnu_debug::_Safe_unordered_container>                 _Safe;
00515       typedef typename _Base::const_iterator       _Base_const_iterator;
00516       typedef typename _Base::iterator             _Base_iterator;
00517       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
00518       typedef typename _Base::local_iterator       _Base_local_iterator;
00519 
00520     public:
00521       typedef typename _Base::size_type                 size_type;
00522       typedef typename _Base::hasher                    hasher;
00523       typedef typename _Base::key_equal                 key_equal;
00524       typedef typename _Base::allocator_type            allocator_type;
00525 
00526       typedef typename _Base::key_type                  key_type;
00527       typedef typename _Base::value_type                value_type;
00528 
00529       typedef __gnu_debug::_Safe_iterator<
00530         _Base_iterator, unordered_multimap>             iterator;
00531       typedef __gnu_debug::_Safe_iterator<
00532         _Base_const_iterator, unordered_multimap>       const_iterator;
00533       typedef __gnu_debug::_Safe_local_iterator<
00534         _Base_local_iterator, unordered_multimap>       local_iterator;
00535       typedef __gnu_debug::_Safe_local_iterator<
00536         _Base_const_local_iterator, unordered_multimap> const_local_iterator;
00537 
00538       unordered_multimap() = default;
00539 
00540       explicit
00541       unordered_multimap(size_type __n,
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       unordered_multimap(const unordered_multimap& __umap,
00570                          const allocator_type& __a)
00571       : _Base(__umap, __a) { }
00572 
00573       unordered_multimap(unordered_multimap&& __umap,
00574                          const allocator_type& __a)
00575       : _Safe(std::move(__umap._M_safe()), __a),
00576         _Base(std::move(__umap._M_base()), __a) { }
00577 
00578       unordered_multimap(initializer_list<value_type> __l,
00579                          size_type __n = 0,
00580                          const hasher& __hf = hasher(),
00581                          const key_equal& __eql = key_equal(),
00582                          const allocator_type& __a = allocator_type())
00583       : _Base(__l, __n, __hf, __eql, __a) { }
00584 
00585       unordered_multimap(size_type __n, const allocator_type& __a)
00586       : unordered_multimap(__n, hasher(), key_equal(), __a)
00587       { }
00588 
00589       unordered_multimap(size_type __n, const hasher& __hf,
00590                          const allocator_type& __a)
00591       : unordered_multimap(__n, __hf, key_equal(), __a)
00592       { }
00593 
00594       template<typename _InputIterator>
00595         unordered_multimap(_InputIterator __first, _InputIterator __last,
00596                            size_type __n,
00597                            const allocator_type& __a)
00598           : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
00599         { }
00600 
00601       template<typename _InputIterator>
00602         unordered_multimap(_InputIterator __first, _InputIterator __last,
00603                            size_type __n, const hasher& __hf,
00604                            const allocator_type& __a)
00605           : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
00606         { }
00607 
00608       unordered_multimap(initializer_list<value_type> __l,
00609                          size_type __n,
00610                          const allocator_type& __a)
00611         : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
00612       { }
00613 
00614       unordered_multimap(initializer_list<value_type> __l,
00615                          size_type __n, const hasher& __hf,
00616                          const allocator_type& __a)
00617         : unordered_multimap(__l, __n, __hf, key_equal(), __a)
00618       { }
00619 
00620       ~unordered_multimap() = default;
00621 
00622       unordered_multimap&
00623       operator=(const unordered_multimap&) = default;
00624 
00625       unordered_multimap&
00626       operator=(unordered_multimap&&) = default;
00627 
00628       unordered_multimap&
00629       operator=(initializer_list<value_type> __l)
00630       {
00631         this->_M_base() = __l;
00632         this->_M_invalidate_all();
00633         return *this;
00634       }
00635 
00636       void
00637       swap(unordered_multimap& __x)
00638         noexcept( noexcept(declval<_Base>().swap(__x)) )
00639       {
00640         _Safe::_M_swap(__x);
00641         _Base::swap(__x);
00642       }
00643 
00644       void
00645       clear() noexcept
00646       {
00647         _Base::clear();
00648         this->_M_invalidate_all();
00649       }
00650 
00651       iterator
00652       begin() noexcept
00653       { return iterator(_Base::begin(), this); }
00654 
00655       const_iterator
00656       begin() const noexcept
00657       { return const_iterator(_Base::begin(), this); }
00658 
00659       iterator
00660       end() noexcept
00661       { return iterator(_Base::end(), this); }
00662 
00663       const_iterator
00664       end() const noexcept
00665       { return const_iterator(_Base::end(), this); }
00666 
00667       const_iterator
00668       cbegin() const noexcept
00669       { return const_iterator(_Base::begin(), this); }
00670 
00671       const_iterator
00672       cend() const noexcept
00673       { return const_iterator(_Base::end(), this); }
00674 
00675       // local versions
00676       local_iterator
00677       begin(size_type __b)
00678       {
00679         __glibcxx_check_bucket_index(__b);
00680         return local_iterator(_Base::begin(__b), this);
00681       }
00682 
00683       local_iterator
00684       end(size_type __b)
00685       {
00686         __glibcxx_check_bucket_index(__b);
00687         return local_iterator(_Base::end(__b), this);
00688       }
00689 
00690       const_local_iterator
00691       begin(size_type __b) const
00692       {
00693         __glibcxx_check_bucket_index(__b);
00694         return const_local_iterator(_Base::begin(__b), this);
00695       }
00696 
00697       const_local_iterator
00698       end(size_type __b) const
00699       {
00700         __glibcxx_check_bucket_index(__b);
00701         return const_local_iterator(_Base::end(__b), this);
00702       }
00703 
00704       const_local_iterator
00705       cbegin(size_type __b) const
00706       {
00707         __glibcxx_check_bucket_index(__b);
00708         return const_local_iterator(_Base::cbegin(__b), this);
00709       }
00710 
00711       const_local_iterator
00712       cend(size_type __b) const
00713       {
00714         __glibcxx_check_bucket_index(__b);
00715         return const_local_iterator(_Base::cend(__b), this);
00716       }
00717 
00718       size_type
00719       bucket_size(size_type __b) const
00720       {
00721         __glibcxx_check_bucket_index(__b);
00722         return _Base::bucket_size(__b);
00723       }
00724 
00725       float
00726       max_load_factor() const noexcept
00727       { return _Base::max_load_factor(); }
00728 
00729       void
00730       max_load_factor(float __f)
00731       {
00732         __glibcxx_check_max_load_factor(__f);
00733         _Base::max_load_factor(__f);
00734       }
00735 
00736       template<typename... _Args>
00737         iterator
00738         emplace(_Args&&... __args)
00739         {
00740           size_type __bucket_count = this->bucket_count();
00741           _Base_iterator __it
00742             = _Base::emplace(std::forward<_Args>(__args)...);
00743           _M_check_rehashed(__bucket_count);
00744           return iterator(__it, this);
00745         }
00746 
00747       template<typename... _Args>
00748         iterator
00749         emplace_hint(const_iterator __hint, _Args&&... __args)
00750         {
00751           __glibcxx_check_insert(__hint);
00752           size_type __bucket_count = this->bucket_count();
00753           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
00754                                         std::forward<_Args>(__args)...);
00755           _M_check_rehashed(__bucket_count);
00756           return iterator(__it, this);
00757         }
00758 
00759       iterator
00760       insert(const value_type& __obj)
00761       {
00762         size_type __bucket_count = this->bucket_count();
00763         _Base_iterator __it = _Base::insert(__obj);
00764         _M_check_rehashed(__bucket_count);
00765         return iterator(__it, this);
00766       }
00767 
00768       iterator
00769       insert(const_iterator __hint, const value_type& __obj)
00770       {
00771         __glibcxx_check_insert(__hint);
00772         size_type __bucket_count = this->bucket_count();
00773         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
00774         _M_check_rehashed(__bucket_count);
00775         return iterator(__it, this);
00776       }
00777 
00778       template<typename _Pair, typename = typename
00779                std::enable_if<std::is_constructible<value_type,
00780                                                     _Pair&&>::value>::type>
00781         iterator
00782         insert(_Pair&& __obj)
00783         {
00784           size_type __bucket_count = this->bucket_count();
00785           _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj));
00786           _M_check_rehashed(__bucket_count);
00787           return iterator(__it, this);
00788         }
00789 
00790       template<typename _Pair, typename = typename
00791                std::enable_if<std::is_constructible<value_type,
00792                                                     _Pair&&>::value>::type>
00793         iterator
00794         insert(const_iterator __hint, _Pair&& __obj)
00795         {
00796           __glibcxx_check_insert(__hint);
00797           size_type __bucket_count = this->bucket_count();
00798           _Base_iterator __it =
00799             _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
00800           _M_check_rehashed(__bucket_count);
00801           return iterator(__it, this);
00802         }
00803 
00804       void
00805       insert(std::initializer_list<value_type> __l)
00806       { _Base::insert(__l); }
00807 
00808       template<typename _InputIterator>
00809         void
00810         insert(_InputIterator __first, _InputIterator __last)
00811         {
00812           __glibcxx_check_valid_range(__first, __last);
00813           size_type __bucket_count = this->bucket_count();
00814           _Base::insert(__gnu_debug::__base(__first),
00815                         __gnu_debug::__base(__last));
00816           _M_check_rehashed(__bucket_count);
00817         }
00818 
00819       iterator
00820       find(const key_type& __key)
00821       { return iterator(_Base::find(__key), this); }
00822 
00823       const_iterator
00824       find(const key_type& __key) const
00825       { return const_iterator(_Base::find(__key), this); }
00826 
00827       std::pair<iterator, iterator>
00828       equal_range(const key_type& __key)
00829       {
00830         std::pair<_Base_iterator, _Base_iterator> __res =
00831           _Base::equal_range(__key);
00832         return std::make_pair(iterator(__res.first, this),
00833                               iterator(__res.second, this));
00834       }
00835 
00836       std::pair<const_iterator, const_iterator>
00837       equal_range(const key_type& __key) const
00838       {
00839         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00840           _Base::equal_range(__key);
00841         return std::make_pair(const_iterator(__res.first, this),
00842                               const_iterator(__res.second, this));
00843       }
00844 
00845       size_type
00846       erase(const key_type& __key)
00847       {
00848         size_type __ret(0);
00849         size_type __bucket_count = this->bucket_count();
00850         std::pair<_Base_iterator, _Base_iterator> __pair =
00851           _Base::equal_range(__key);
00852         for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
00853           {
00854             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
00855                             { return __it == __victim; });
00856             this->_M_invalidate_local_if(
00857                             [__victim](_Base_const_local_iterator __it)
00858                             { return __it._M_curr() == __victim._M_cur; });
00859             _Base::erase(__victim++);
00860             ++__ret;
00861           }
00862         _M_check_rehashed(__bucket_count);
00863         return __ret;
00864       }
00865 
00866       iterator
00867       erase(const_iterator __it)
00868       {
00869         __glibcxx_check_erase(__it);
00870         _Base_const_iterator __victim = __it.base();
00871         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
00872                         { return __it == __victim; });
00873         this->_M_invalidate_local_if(
00874                         [__victim](_Base_const_local_iterator __it)
00875                         { return __it._M_curr() == __victim._M_cur; });
00876         size_type __bucket_count = this->bucket_count();
00877         _Base_iterator __next = _Base::erase(__it.base());
00878         _M_check_rehashed(__bucket_count);
00879         return iterator(__next, this);
00880       }
00881 
00882       iterator
00883       erase(iterator __it)
00884       { return erase(const_iterator(__it)); }
00885 
00886       iterator
00887       erase(const_iterator __first, const_iterator __last)
00888       {
00889         __glibcxx_check_erase_range(__first, __last);
00890         for (_Base_const_iterator __tmp = __first.base();
00891              __tmp != __last.base(); ++__tmp)
00892           {
00893             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00894                                   _M_message(__gnu_debug::__msg_valid_range)
00895                                   ._M_iterator(__first, "first")
00896                                   ._M_iterator(__last, "last"));
00897             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
00898                             { return __it == __tmp; });
00899             this->_M_invalidate_local_if(
00900                             [__tmp](_Base_const_local_iterator __it)
00901                             { return __it._M_curr() == __tmp._M_cur; });
00902           }
00903         size_type __bucket_count = this->bucket_count();
00904         _Base_iterator __next = _Base::erase(__first.base(), __last.base());
00905         _M_check_rehashed(__bucket_count);
00906         return iterator(__next, this);
00907       }
00908 
00909       _Base&
00910       _M_base() noexcept { return *this; }
00911 
00912       const _Base&
00913       _M_base() const noexcept { return *this; }
00914 
00915     private:
00916       void
00917       _M_check_rehashed(size_type __prev_count)
00918       {
00919         if (__prev_count != this->bucket_count())
00920           this->_M_invalidate_locals();
00921       }
00922     };
00923 
00924   template<typename _Key, typename _Tp, typename _Hash,
00925            typename _Pred, typename _Alloc>
00926     inline void
00927     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00928          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00929     { __x.swap(__y); }
00930 
00931   template<typename _Key, typename _Tp, typename _Hash,
00932            typename _Pred, typename _Alloc>
00933     inline bool
00934     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00935                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00936     { return __x._M_base() == __y._M_base(); }
00937 
00938   template<typename _Key, typename _Tp, typename _Hash,
00939            typename _Pred, typename _Alloc>
00940     inline bool
00941     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00942                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00943     { return !(__x == __y); }
00944 
00945 } // namespace __debug
00946 } // namespace std
00947 
00948 #endif // C++11
00949 
00950 #endif