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