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         auto __res = _Base::insert(__obj);
00316         _M_check_rehashed(__bucket_count);
00317         return { iterator(__res.first, this), __res.second };
00318       }
00319 
00320       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00321       // 2354. Unnecessary copying when inserting into maps with braced-init
00322       std::pair<iterator, bool>
00323       insert(value_type&& __x)
00324       {
00325         size_type __bucket_count = this->bucket_count();
00326         auto __res = _Base::insert(std::move(__x));
00327         _M_check_rehashed(__bucket_count);
00328         return { iterator(__res.first, this), __res.second };
00329       }
00330 
00331       template<typename _Pair, typename = typename
00332                std::enable_if<std::is_constructible<value_type,
00333                                                     _Pair&&>::value>::type>
00334         std::pair<iterator, bool>
00335         insert(_Pair&& __obj)
00336         {
00337           size_type __bucket_count = this->bucket_count();
00338           std::pair<_Base_iterator, bool> __res =
00339             _Base::insert(std::forward<_Pair>(__obj));
00340           _M_check_rehashed(__bucket_count);
00341           return std::make_pair(iterator(__res.first, this), __res.second);
00342         }
00343 
00344       iterator
00345       insert(const_iterator __hint, const value_type& __obj)
00346       {
00347         __glibcxx_check_insert(__hint);
00348         size_type __bucket_count = this->bucket_count();
00349         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
00350         _M_check_rehashed(__bucket_count);
00351         return iterator(__it, this);
00352       }
00353 
00354       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00355       // 2354. Unnecessary copying when inserting into maps with braced-init
00356       iterator
00357       insert(const_iterator __hint, value_type&& __x)
00358       {
00359         __glibcxx_check_insert(__hint);
00360         size_type __bucket_count = this->bucket_count();
00361         auto __it = _Base::insert(__hint.base(), std::move(__x));
00362         _M_check_rehashed(__bucket_count);
00363         return iterator(__it, this);
00364       }
00365 
00366       template<typename _Pair, typename = typename
00367                std::enable_if<std::is_constructible<value_type,
00368                                                     _Pair&&>::value>::type>
00369         iterator
00370         insert(const_iterator __hint, _Pair&& __obj)
00371         {
00372           __glibcxx_check_insert(__hint);
00373           size_type __bucket_count = this->bucket_count();
00374           _Base_iterator __it =
00375             _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
00376           _M_check_rehashed(__bucket_count);
00377           return iterator(__it, this);
00378         }
00379 
00380       void
00381       insert(std::initializer_list<value_type> __l)
00382       {
00383         size_type __bucket_count = this->bucket_count();
00384         _Base::insert(__l);
00385         _M_check_rehashed(__bucket_count);
00386       }
00387 
00388       template<typename _InputIterator>
00389         void
00390         insert(_InputIterator __first, _InputIterator __last)
00391         {
00392           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
00393           __glibcxx_check_valid_range2(__first, __last, __dist);
00394           size_type __bucket_count = this->bucket_count();
00395 
00396           if (__dist.second >= __gnu_debug::__dp_sign)
00397             _Base::insert(__gnu_debug::__unsafe(__first),
00398                           __gnu_debug::__unsafe(__last));
00399           else
00400             _Base::insert(__first, __last);
00401 
00402           _M_check_rehashed(__bucket_count);
00403         }
00404 
00405 #if __cplusplus > 201402L
00406       template <typename... _Args>
00407         pair<iterator, bool>
00408         try_emplace(const key_type& __k, _Args&&... __args)
00409         {
00410           auto __res = _Base::try_emplace(__k,
00411                                           std::forward<_Args>(__args)...);
00412           return { iterator(__res.first, this), __res.second };
00413         }
00414 
00415       template <typename... _Args>
00416         pair<iterator, bool>
00417         try_emplace(key_type&& __k, _Args&&... __args)
00418         {
00419           auto __res = _Base::try_emplace(std::move(__k),
00420                                           std::forward<_Args>(__args)...);
00421           return { iterator(__res.first, this), __res.second };
00422         }
00423 
00424       template <typename... _Args>
00425         iterator
00426         try_emplace(const_iterator __hint, const key_type& __k,
00427                     _Args&&... __args)
00428         {
00429           __glibcxx_check_insert(__hint);
00430           return iterator(_Base::try_emplace(__hint.base(), __k,
00431                                              std::forward<_Args>(__args)...),
00432                           this);
00433         }
00434 
00435       template <typename... _Args>
00436         iterator
00437         try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
00438         {
00439           __glibcxx_check_insert(__hint);
00440           return iterator(_Base::try_emplace(__hint.base(), std::move(__k),
00441                                              std::forward<_Args>(__args)...),
00442                           this);
00443         }
00444 
00445       template <typename _Obj>
00446         pair<iterator, bool>
00447         insert_or_assign(const key_type& __k, _Obj&& __obj)
00448         {
00449           auto __res = _Base::insert_or_assign(__k,
00450                                                std::forward<_Obj>(__obj));
00451           return { iterator(__res.first, this), __res.second };
00452         }
00453 
00454       template <typename _Obj>
00455         pair<iterator, bool>
00456         insert_or_assign(key_type&& __k, _Obj&& __obj)
00457         {
00458           auto __res = _Base::insert_or_assign(std::move(__k),
00459                                                std::forward<_Obj>(__obj));
00460           return { iterator(__res.first, this), __res.second };
00461         }
00462 
00463       template <typename _Obj>
00464         iterator
00465         insert_or_assign(const_iterator __hint, const key_type& __k,
00466                          _Obj&& __obj)
00467         {
00468           __glibcxx_check_insert(__hint);
00469           return iterator(_Base::insert_or_assign(__hint.base(), __k,
00470                                                   std::forward<_Obj>(__obj)),
00471                           this);
00472         }
00473 
00474       template <typename _Obj>
00475         iterator
00476         insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
00477         {
00478           __glibcxx_check_insert(__hint);
00479           return iterator(_Base::insert_or_assign(__hint.base(),
00480                                                   std::move(__k),
00481                                                   std::forward<_Obj>(__obj)),
00482                           this);
00483         }
00484 #endif // C++17
00485 
00486 #if __cplusplus > 201402L
00487       using node_type = typename _Base::node_type;
00488 
00489       struct insert_return_type
00490       {
00491         bool inserted;
00492         iterator position;
00493         node_type node;
00494       };
00495 
00496       node_type
00497       extract(const_iterator __position)
00498       {
00499         __glibcxx_check_erase(__position);
00500         _Base_const_iterator __victim = __position.base();
00501         this->_M_invalidate_if(
00502             [__victim](_Base_const_iterator __it) { return __it == __victim; }
00503             );
00504         this->_M_invalidate_local_if(
00505             [__victim](_Base_const_local_iterator __it) {
00506                 return __it._M_curr() == __victim._M_cur;
00507             });
00508         return _Base::extract(__position.base());
00509       }
00510 
00511       node_type
00512       extract(const key_type& __key)
00513       {
00514         const auto __position = find(__key);
00515         if (__position != end())
00516           return extract(__position);
00517         return {};
00518       }
00519 
00520       insert_return_type
00521       insert(node_type&& __nh)
00522       {
00523         auto __ret = _Base::insert(std::move(__nh));
00524         iterator __pos = iterator(__ret.position, this);
00525         return { __ret.inserted, __pos, std::move(__ret.node) };
00526       }
00527 
00528       iterator
00529       insert(const_iterator __hint, node_type&& __nh)
00530       {
00531         __glibcxx_check_insert(__hint);
00532         return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
00533       }
00534 
00535       using _Base::merge;
00536 #endif // C++17
00537 
00538       iterator
00539       find(const key_type& __key)
00540       { return iterator(_Base::find(__key), this); }
00541 
00542       const_iterator
00543       find(const key_type& __key) const
00544       { return const_iterator(_Base::find(__key), this); }
00545 
00546       std::pair<iterator, iterator>
00547       equal_range(const key_type& __key)
00548       {
00549         std::pair<_Base_iterator, _Base_iterator> __res =
00550           _Base::equal_range(__key);
00551         return std::make_pair(iterator(__res.first, this),
00552                               iterator(__res.second, this));
00553       }
00554 
00555       std::pair<const_iterator, const_iterator>
00556       equal_range(const key_type& __key) const
00557       {
00558         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00559           _Base::equal_range(__key);
00560         return std::make_pair(const_iterator(__res.first, this),
00561                               const_iterator(__res.second, this));
00562       }
00563 
00564       size_type
00565       erase(const key_type& __key)
00566       {
00567         size_type __ret(0);
00568         _Base_iterator __victim(_Base::find(__key));
00569         if (__victim != _Base::end())
00570           {
00571             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
00572                             { return __it == __victim; });
00573             this->_M_invalidate_local_if(
00574                             [__victim](_Base_const_local_iterator __it)
00575                             { return __it._M_curr() == __victim._M_cur; });
00576             size_type __bucket_count = this->bucket_count();
00577             _Base::erase(__victim);
00578             _M_check_rehashed(__bucket_count);
00579             __ret = 1;
00580           }
00581         return __ret;
00582       }
00583 
00584       iterator
00585       erase(const_iterator __it)
00586       {
00587         __glibcxx_check_erase(__it);
00588         _Base_const_iterator __victim = __it.base();
00589         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
00590                         { return __it == __victim; });
00591         this->_M_invalidate_local_if(
00592                         [__victim](_Base_const_local_iterator __it)
00593                         { return __it._M_curr() == __victim._M_cur; });
00594         size_type __bucket_count = this->bucket_count();
00595         _Base_iterator __next = _Base::erase(__it.base());
00596         _M_check_rehashed(__bucket_count);
00597         return iterator(__next, this);
00598       }
00599 
00600       iterator
00601       erase(iterator __it)
00602       { return erase(const_iterator(__it)); }
00603 
00604       iterator
00605       erase(const_iterator __first, const_iterator __last)
00606       {
00607         __glibcxx_check_erase_range(__first, __last);
00608         for (_Base_const_iterator __tmp = __first.base();
00609              __tmp != __last.base(); ++__tmp)
00610           {
00611             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00612                                   _M_message(__gnu_debug::__msg_valid_range)
00613                                   ._M_iterator(__first, "first")
00614                                   ._M_iterator(__last, "last"));
00615             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
00616                             { return __it == __tmp; });
00617             this->_M_invalidate_local_if(
00618                             [__tmp](_Base_const_local_iterator __it)
00619                             { return __it._M_curr() == __tmp._M_cur; });
00620           }
00621         size_type __bucket_count = this->bucket_count();
00622         _Base_iterator __next = _Base::erase(__first.base(), __last.base());
00623         _M_check_rehashed(__bucket_count);
00624         return iterator(__next, this);
00625       }
00626 
00627       _Base&
00628       _M_base() noexcept        { return *this; }
00629 
00630       const _Base&
00631       _M_base() const noexcept  { return *this; }
00632 
00633     private:
00634       void
00635       _M_check_rehashed(size_type __prev_count)
00636       {
00637         if (__prev_count != this->bucket_count())
00638           this->_M_invalidate_locals();
00639       }
00640     };
00641 
00642   template<typename _Key, typename _Tp, typename _Hash,
00643            typename _Pred, typename _Alloc>
00644     inline void
00645     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00646          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00647     noexcept(noexcept(__x.swap(__y)))
00648     { __x.swap(__y); }
00649 
00650   template<typename _Key, typename _Tp, typename _Hash,
00651            typename _Pred, typename _Alloc>
00652     inline bool
00653     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00654                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00655     { return __x._M_base() == __y._M_base(); }
00656 
00657   template<typename _Key, typename _Tp, typename _Hash,
00658            typename _Pred, typename _Alloc>
00659     inline bool
00660     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00661                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00662     { return !(__x == __y); }
00663 
00664 
00665   /// Class std::unordered_multimap with safety/checking/debug instrumentation.
00666   template<typename _Key, typename _Tp,
00667            typename _Hash = std::hash<_Key>,
00668            typename _Pred = std::equal_to<_Key>,
00669            typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
00670     class unordered_multimap
00671       : public __gnu_debug::_Safe_container<
00672         unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
00673         __gnu_debug::_Safe_unordered_container>,
00674         public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
00675     {
00676       typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
00677                                                  _Pred, _Alloc>         _Base;
00678       typedef __gnu_debug::_Safe_container<unordered_multimap,
00679         _Alloc, __gnu_debug::_Safe_unordered_container>                 _Safe;
00680       typedef typename _Base::const_iterator       _Base_const_iterator;
00681       typedef typename _Base::iterator             _Base_iterator;
00682       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
00683       typedef typename _Base::local_iterator       _Base_local_iterator;
00684 
00685     public:
00686       typedef typename _Base::size_type                 size_type;
00687       typedef typename _Base::hasher                    hasher;
00688       typedef typename _Base::key_equal                 key_equal;
00689       typedef typename _Base::allocator_type            allocator_type;
00690 
00691       typedef typename _Base::key_type                  key_type;
00692       typedef typename _Base::value_type                value_type;
00693 
00694       typedef __gnu_debug::_Safe_iterator<
00695         _Base_iterator, unordered_multimap>             iterator;
00696       typedef __gnu_debug::_Safe_iterator<
00697         _Base_const_iterator, unordered_multimap>       const_iterator;
00698       typedef __gnu_debug::_Safe_local_iterator<
00699         _Base_local_iterator, unordered_multimap>       local_iterator;
00700       typedef __gnu_debug::_Safe_local_iterator<
00701         _Base_const_local_iterator, unordered_multimap> const_local_iterator;
00702 
00703       unordered_multimap() = default;
00704 
00705       explicit
00706       unordered_multimap(size_type __n,
00707                          const hasher& __hf = hasher(),
00708                          const key_equal& __eql = key_equal(),
00709                          const allocator_type& __a = allocator_type())
00710       : _Base(__n, __hf, __eql, __a) { }
00711 
00712       template<typename _InputIterator>
00713         unordered_multimap(_InputIterator __first, _InputIterator __last,
00714                            size_type __n = 0,
00715                            const hasher& __hf = hasher(),
00716                            const key_equal& __eql = key_equal(),
00717                            const allocator_type& __a = allocator_type())
00718         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00719                                                                      __last)),
00720                 __gnu_debug::__base(__last), __n,
00721                 __hf, __eql, __a) { }
00722 
00723       unordered_multimap(const unordered_multimap&) = default;
00724 
00725       unordered_multimap(const _Base& __x)
00726       : _Base(__x) { }
00727 
00728       unordered_multimap(unordered_multimap&&) = default;
00729 
00730       explicit
00731       unordered_multimap(const allocator_type& __a)
00732       : _Base(__a) { }
00733 
00734       unordered_multimap(const unordered_multimap& __umap,
00735                          const allocator_type& __a)
00736       : _Base(__umap, __a) { }
00737 
00738       unordered_multimap(unordered_multimap&& __umap,
00739                          const allocator_type& __a)
00740       : _Safe(std::move(__umap._M_safe()), __a),
00741         _Base(std::move(__umap._M_base()), __a) { }
00742 
00743       unordered_multimap(initializer_list<value_type> __l,
00744                          size_type __n = 0,
00745                          const hasher& __hf = hasher(),
00746                          const key_equal& __eql = key_equal(),
00747                          const allocator_type& __a = allocator_type())
00748       : _Base(__l, __n, __hf, __eql, __a) { }
00749 
00750       unordered_multimap(size_type __n, const allocator_type& __a)
00751       : unordered_multimap(__n, hasher(), key_equal(), __a)
00752       { }
00753 
00754       unordered_multimap(size_type __n, const hasher& __hf,
00755                          const allocator_type& __a)
00756       : unordered_multimap(__n, __hf, key_equal(), __a)
00757       { }
00758 
00759       template<typename _InputIterator>
00760         unordered_multimap(_InputIterator __first, _InputIterator __last,
00761                            size_type __n,
00762                            const allocator_type& __a)
00763           : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
00764         { }
00765 
00766       template<typename _InputIterator>
00767         unordered_multimap(_InputIterator __first, _InputIterator __last,
00768                            size_type __n, const hasher& __hf,
00769                            const allocator_type& __a)
00770           : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
00771         { }
00772 
00773       unordered_multimap(initializer_list<value_type> __l,
00774                          size_type __n,
00775                          const allocator_type& __a)
00776         : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
00777       { }
00778 
00779       unordered_multimap(initializer_list<value_type> __l,
00780                          size_type __n, const hasher& __hf,
00781                          const allocator_type& __a)
00782         : unordered_multimap(__l, __n, __hf, key_equal(), __a)
00783       { }
00784 
00785       ~unordered_multimap() = default;
00786 
00787       unordered_multimap&
00788       operator=(const unordered_multimap&) = default;
00789 
00790       unordered_multimap&
00791       operator=(unordered_multimap&&) = default;
00792 
00793       unordered_multimap&
00794       operator=(initializer_list<value_type> __l)
00795       {
00796         this->_M_base() = __l;
00797         this->_M_invalidate_all();
00798         return *this;
00799       }
00800 
00801       void
00802       swap(unordered_multimap& __x)
00803         noexcept( noexcept(declval<_Base&>().swap(__x)) )
00804       {
00805         _Safe::_M_swap(__x);
00806         _Base::swap(__x);
00807       }
00808 
00809       void
00810       clear() noexcept
00811       {
00812         _Base::clear();
00813         this->_M_invalidate_all();
00814       }
00815 
00816       iterator
00817       begin() noexcept
00818       { return iterator(_Base::begin(), this); }
00819 
00820       const_iterator
00821       begin() const noexcept
00822       { return const_iterator(_Base::begin(), this); }
00823 
00824       iterator
00825       end() noexcept
00826       { return iterator(_Base::end(), this); }
00827 
00828       const_iterator
00829       end() const noexcept
00830       { return const_iterator(_Base::end(), this); }
00831 
00832       const_iterator
00833       cbegin() const noexcept
00834       { return const_iterator(_Base::begin(), this); }
00835 
00836       const_iterator
00837       cend() const noexcept
00838       { return const_iterator(_Base::end(), this); }
00839 
00840       // local versions
00841       local_iterator
00842       begin(size_type __b)
00843       {
00844         __glibcxx_check_bucket_index(__b);
00845         return local_iterator(_Base::begin(__b), this);
00846       }
00847 
00848       local_iterator
00849       end(size_type __b)
00850       {
00851         __glibcxx_check_bucket_index(__b);
00852         return local_iterator(_Base::end(__b), this);
00853       }
00854 
00855       const_local_iterator
00856       begin(size_type __b) const
00857       {
00858         __glibcxx_check_bucket_index(__b);
00859         return const_local_iterator(_Base::begin(__b), this);
00860       }
00861 
00862       const_local_iterator
00863       end(size_type __b) const
00864       {
00865         __glibcxx_check_bucket_index(__b);
00866         return const_local_iterator(_Base::end(__b), this);
00867       }
00868 
00869       const_local_iterator
00870       cbegin(size_type __b) const
00871       {
00872         __glibcxx_check_bucket_index(__b);
00873         return const_local_iterator(_Base::cbegin(__b), this);
00874       }
00875 
00876       const_local_iterator
00877       cend(size_type __b) const
00878       {
00879         __glibcxx_check_bucket_index(__b);
00880         return const_local_iterator(_Base::cend(__b), this);
00881       }
00882 
00883       size_type
00884       bucket_size(size_type __b) const
00885       {
00886         __glibcxx_check_bucket_index(__b);
00887         return _Base::bucket_size(__b);
00888       }
00889 
00890       float
00891       max_load_factor() const noexcept
00892       { return _Base::max_load_factor(); }
00893 
00894       void
00895       max_load_factor(float __f)
00896       {
00897         __glibcxx_check_max_load_factor(__f);
00898         _Base::max_load_factor(__f);
00899       }
00900 
00901       template<typename... _Args>
00902         iterator
00903         emplace(_Args&&... __args)
00904         {
00905           size_type __bucket_count = this->bucket_count();
00906           _Base_iterator __it
00907             = _Base::emplace(std::forward<_Args>(__args)...);
00908           _M_check_rehashed(__bucket_count);
00909           return iterator(__it, this);
00910         }
00911 
00912       template<typename... _Args>
00913         iterator
00914         emplace_hint(const_iterator __hint, _Args&&... __args)
00915         {
00916           __glibcxx_check_insert(__hint);
00917           size_type __bucket_count = this->bucket_count();
00918           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
00919                                         std::forward<_Args>(__args)...);
00920           _M_check_rehashed(__bucket_count);
00921           return iterator(__it, this);
00922         }
00923 
00924       iterator
00925       insert(const value_type& __obj)
00926       {
00927         size_type __bucket_count = this->bucket_count();
00928         _Base_iterator __it = _Base::insert(__obj);
00929         _M_check_rehashed(__bucket_count);
00930         return iterator(__it, this);
00931       }
00932 
00933       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00934       // 2354. Unnecessary copying when inserting into maps with braced-init
00935       iterator
00936       insert(value_type&& __x)
00937       {
00938         size_type __bucket_count = this->bucket_count();
00939         auto __it = _Base::insert(std::move(__x));
00940         _M_check_rehashed(__bucket_count);
00941         return { __it, this };
00942       }
00943 
00944       iterator
00945       insert(const_iterator __hint, const value_type& __obj)
00946       {
00947         __glibcxx_check_insert(__hint);
00948         size_type __bucket_count = this->bucket_count();
00949         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
00950         _M_check_rehashed(__bucket_count);
00951         return iterator(__it, this);
00952       }
00953 
00954       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00955       // 2354. Unnecessary copying when inserting into maps with braced-init
00956       iterator
00957       insert(const_iterator __hint, value_type&& __x)
00958       {
00959         __glibcxx_check_insert(__hint);
00960         size_type __bucket_count = this->bucket_count();
00961         auto __it = _Base::insert(__hint.base(), std::move(__x));
00962         _M_check_rehashed(__bucket_count);
00963         return iterator(__it, this);
00964       }
00965 
00966       template<typename _Pair, typename = typename
00967                std::enable_if<std::is_constructible<value_type,
00968                                                     _Pair&&>::value>::type>
00969         iterator
00970         insert(_Pair&& __obj)
00971         {
00972           size_type __bucket_count = this->bucket_count();
00973           _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj));
00974           _M_check_rehashed(__bucket_count);
00975           return iterator(__it, this);
00976         }
00977 
00978       template<typename _Pair, typename = typename
00979                std::enable_if<std::is_constructible<value_type,
00980                                                     _Pair&&>::value>::type>
00981         iterator
00982         insert(const_iterator __hint, _Pair&& __obj)
00983         {
00984           __glibcxx_check_insert(__hint);
00985           size_type __bucket_count = this->bucket_count();
00986           _Base_iterator __it =
00987             _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
00988           _M_check_rehashed(__bucket_count);
00989           return iterator(__it, this);
00990         }
00991 
00992       void
00993       insert(std::initializer_list<value_type> __l)
00994       { _Base::insert(__l); }
00995 
00996       template<typename _InputIterator>
00997         void
00998         insert(_InputIterator __first, _InputIterator __last)
00999         {
01000           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
01001           __glibcxx_check_valid_range2(__first, __last, __dist);
01002           size_type __bucket_count = this->bucket_count();
01003 
01004           if (__dist.second >= __gnu_debug::__dp_sign)
01005             _Base::insert(__gnu_debug::__unsafe(__first),
01006                           __gnu_debug::__unsafe(__last));
01007           else
01008             _Base::insert(__first, __last);
01009 
01010           _M_check_rehashed(__bucket_count);
01011         }
01012 
01013 #if __cplusplus > 201402L
01014       using node_type = typename _Base::node_type;
01015 
01016       node_type
01017       extract(const_iterator __position)
01018       {
01019         __glibcxx_check_erase(__position);
01020         _Base_const_iterator __victim = __position.base();
01021         this->_M_invalidate_if(
01022             [__victim](_Base_const_iterator __it) { return __it == __victim; }
01023             );
01024         this->_M_invalidate_local_if(
01025             [__victim](_Base_const_local_iterator __it) {
01026                 return __it._M_curr() == __victim._M_cur;
01027             });
01028         return _Base::extract(__position.base());
01029       }
01030 
01031       node_type
01032       extract(const key_type& __key)
01033       {
01034         const auto __position = find(__key);
01035         if (__position != end())
01036           return extract(__position);
01037         return {};
01038       }
01039 
01040       iterator
01041       insert(node_type&& __nh)
01042       { return iterator(_Base::insert(std::move(__nh)), this); }
01043 
01044       iterator
01045       insert(const_iterator __hint, node_type&& __nh)
01046       {
01047         __glibcxx_check_insert(__hint);
01048         return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
01049       }
01050 
01051       using _Base::merge;
01052 #endif // C++17
01053 
01054       iterator
01055       find(const key_type& __key)
01056       { return iterator(_Base::find(__key), this); }
01057 
01058       const_iterator
01059       find(const key_type& __key) const
01060       { return const_iterator(_Base::find(__key), this); }
01061 
01062       std::pair<iterator, iterator>
01063       equal_range(const key_type& __key)
01064       {
01065         std::pair<_Base_iterator, _Base_iterator> __res =
01066           _Base::equal_range(__key);
01067         return std::make_pair(iterator(__res.first, this),
01068                               iterator(__res.second, this));
01069       }
01070 
01071       std::pair<const_iterator, const_iterator>
01072       equal_range(const key_type& __key) const
01073       {
01074         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
01075           _Base::equal_range(__key);
01076         return std::make_pair(const_iterator(__res.first, this),
01077                               const_iterator(__res.second, this));
01078       }
01079 
01080       size_type
01081       erase(const key_type& __key)
01082       {
01083         size_type __ret(0);
01084         size_type __bucket_count = this->bucket_count();
01085         std::pair<_Base_iterator, _Base_iterator> __pair =
01086           _Base::equal_range(__key);
01087         for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
01088           {
01089             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
01090                             { return __it == __victim; });
01091             this->_M_invalidate_local_if(
01092                             [__victim](_Base_const_local_iterator __it)
01093                             { return __it._M_curr() == __victim._M_cur; });
01094             _Base::erase(__victim++);
01095             ++__ret;
01096           }
01097         _M_check_rehashed(__bucket_count);
01098         return __ret;
01099       }
01100 
01101       iterator
01102       erase(const_iterator __it)
01103       {
01104         __glibcxx_check_erase(__it);
01105         _Base_const_iterator __victim = __it.base();
01106         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
01107                         { return __it == __victim; });
01108         this->_M_invalidate_local_if(
01109                         [__victim](_Base_const_local_iterator __it)
01110                         { return __it._M_curr() == __victim._M_cur; });
01111         size_type __bucket_count = this->bucket_count();
01112         _Base_iterator __next = _Base::erase(__it.base());
01113         _M_check_rehashed(__bucket_count);
01114         return iterator(__next, this);
01115       }
01116 
01117       iterator
01118       erase(iterator __it)
01119       { return erase(const_iterator(__it)); }
01120 
01121       iterator
01122       erase(const_iterator __first, const_iterator __last)
01123       {
01124         __glibcxx_check_erase_range(__first, __last);
01125         for (_Base_const_iterator __tmp = __first.base();
01126              __tmp != __last.base(); ++__tmp)
01127           {
01128             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
01129                                   _M_message(__gnu_debug::__msg_valid_range)
01130                                   ._M_iterator(__first, "first")
01131                                   ._M_iterator(__last, "last"));
01132             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
01133                             { return __it == __tmp; });
01134             this->_M_invalidate_local_if(
01135                             [__tmp](_Base_const_local_iterator __it)
01136                             { return __it._M_curr() == __tmp._M_cur; });
01137           }
01138         size_type __bucket_count = this->bucket_count();
01139         _Base_iterator __next = _Base::erase(__first.base(), __last.base());
01140         _M_check_rehashed(__bucket_count);
01141         return iterator(__next, this);
01142       }
01143 
01144       _Base&
01145       _M_base() noexcept { return *this; }
01146 
01147       const _Base&
01148       _M_base() const noexcept { return *this; }
01149 
01150     private:
01151       void
01152       _M_check_rehashed(size_type __prev_count)
01153       {
01154         if (__prev_count != this->bucket_count())
01155           this->_M_invalidate_locals();
01156       }
01157     };
01158 
01159   template<typename _Key, typename _Tp, typename _Hash,
01160            typename _Pred, typename _Alloc>
01161     inline void
01162     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
01163          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
01164     noexcept(noexcept(__x.swap(__y)))
01165     { __x.swap(__y); }
01166 
01167   template<typename _Key, typename _Tp, typename _Hash,
01168            typename _Pred, typename _Alloc>
01169     inline bool
01170     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
01171                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
01172     { return __x._M_base() == __y._M_base(); }
01173 
01174   template<typename _Key, typename _Tp, typename _Hash,
01175            typename _Pred, typename _Alloc>
01176     inline bool
01177     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
01178                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
01179     { return !(__x == __y); }
01180 
01181 } // namespace __debug
01182 } // namespace std
01183 
01184 #endif // C++11
01185 
01186 #endif