libstdc++
unordered_map
Go to the documentation of this file.
00001 // Debugging unordered_map/unordered_multimap implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003-2018 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       using insert_return_type = _Node_insert_return<iterator, node_type>;
00489 
00490       node_type
00491       extract(const_iterator __position)
00492       {
00493         __glibcxx_check_erase(__position);
00494         _Base_const_iterator __victim = __position.base();
00495         this->_M_invalidate_if(
00496             [__victim](_Base_const_iterator __it) { return __it == __victim; }
00497             );
00498         this->_M_invalidate_local_if(
00499             [__victim](_Base_const_local_iterator __it) {
00500                 return __it._M_curr() == __victim._M_cur;
00501             });
00502         return _Base::extract(__position.base());
00503       }
00504 
00505       node_type
00506       extract(const key_type& __key)
00507       {
00508         const auto __position = find(__key);
00509         if (__position != end())
00510           return extract(__position);
00511         return {};
00512       }
00513 
00514       insert_return_type
00515       insert(node_type&& __nh)
00516       {
00517         auto __ret = _Base::insert(std::move(__nh));
00518         iterator __pos = iterator(__ret.position, this);
00519         return { __pos, __ret.inserted, std::move(__ret.node) };
00520       }
00521 
00522       iterator
00523       insert(const_iterator __hint, node_type&& __nh)
00524       {
00525         __glibcxx_check_insert(__hint);
00526         return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
00527       }
00528 
00529       using _Base::merge;
00530 #endif // C++17
00531 
00532       iterator
00533       find(const key_type& __key)
00534       { return iterator(_Base::find(__key), this); }
00535 
00536       const_iterator
00537       find(const key_type& __key) const
00538       { return const_iterator(_Base::find(__key), this); }
00539 
00540       std::pair<iterator, iterator>
00541       equal_range(const key_type& __key)
00542       {
00543         std::pair<_Base_iterator, _Base_iterator> __res =
00544           _Base::equal_range(__key);
00545         return std::make_pair(iterator(__res.first, this),
00546                               iterator(__res.second, this));
00547       }
00548 
00549       std::pair<const_iterator, const_iterator>
00550       equal_range(const key_type& __key) const
00551       {
00552         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00553           _Base::equal_range(__key);
00554         return std::make_pair(const_iterator(__res.first, this),
00555                               const_iterator(__res.second, this));
00556       }
00557 
00558       size_type
00559       erase(const key_type& __key)
00560       {
00561         size_type __ret(0);
00562         _Base_iterator __victim(_Base::find(__key));
00563         if (__victim != _Base::end())
00564           {
00565             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
00566                             { return __it == __victim; });
00567             this->_M_invalidate_local_if(
00568                             [__victim](_Base_const_local_iterator __it)
00569                             { return __it._M_curr() == __victim._M_cur; });
00570             size_type __bucket_count = this->bucket_count();
00571             _Base::erase(__victim);
00572             _M_check_rehashed(__bucket_count);
00573             __ret = 1;
00574           }
00575         return __ret;
00576       }
00577 
00578       iterator
00579       erase(const_iterator __it)
00580       {
00581         __glibcxx_check_erase(__it);
00582         _Base_const_iterator __victim = __it.base();
00583         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
00584                         { return __it == __victim; });
00585         this->_M_invalidate_local_if(
00586                         [__victim](_Base_const_local_iterator __it)
00587                         { return __it._M_curr() == __victim._M_cur; });
00588         size_type __bucket_count = this->bucket_count();
00589         _Base_iterator __next = _Base::erase(__it.base());
00590         _M_check_rehashed(__bucket_count);
00591         return iterator(__next, this);
00592       }
00593 
00594       iterator
00595       erase(iterator __it)
00596       { return erase(const_iterator(__it)); }
00597 
00598       iterator
00599       erase(const_iterator __first, const_iterator __last)
00600       {
00601         __glibcxx_check_erase_range(__first, __last);
00602         for (_Base_const_iterator __tmp = __first.base();
00603              __tmp != __last.base(); ++__tmp)
00604           {
00605             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
00606                                   _M_message(__gnu_debug::__msg_valid_range)
00607                                   ._M_iterator(__first, "first")
00608                                   ._M_iterator(__last, "last"));
00609             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
00610                             { return __it == __tmp; });
00611             this->_M_invalidate_local_if(
00612                             [__tmp](_Base_const_local_iterator __it)
00613                             { return __it._M_curr() == __tmp._M_cur; });
00614           }
00615         size_type __bucket_count = this->bucket_count();
00616         _Base_iterator __next = _Base::erase(__first.base(), __last.base());
00617         _M_check_rehashed(__bucket_count);
00618         return iterator(__next, this);
00619       }
00620 
00621       _Base&
00622       _M_base() noexcept        { return *this; }
00623 
00624       const _Base&
00625       _M_base() const noexcept  { return *this; }
00626 
00627     private:
00628       void
00629       _M_check_rehashed(size_type __prev_count)
00630       {
00631         if (__prev_count != this->bucket_count())
00632           this->_M_invalidate_locals();
00633       }
00634     };
00635 
00636 #if __cpp_deduction_guides >= 201606
00637 
00638   template<typename _InputIterator,
00639            typename _Hash = hash<__iter_key_t<_InputIterator>>,
00640            typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
00641            typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
00642            typename = _RequireInputIter<_InputIterator>,
00643            typename = _RequireAllocator<_Allocator>>
00644     unordered_map(_InputIterator, _InputIterator,
00645                   typename unordered_map<int, int>::size_type = {},
00646                   _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
00647     -> unordered_map<__iter_key_t<_InputIterator>,
00648                      __iter_val_t<_InputIterator>,
00649                      _Hash, _Pred, _Allocator>;
00650 
00651   template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
00652            typename _Pred = equal_to<_Key>,
00653            typename _Allocator = allocator<pair<const _Key, _Tp>>,
00654            typename = _RequireAllocator<_Allocator>>
00655     unordered_map(initializer_list<pair<_Key, _Tp>>,
00656                   typename unordered_map<int, int>::size_type = {},
00657                   _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
00658     -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
00659 
00660   template<typename _InputIterator, typename _Allocator,
00661            typename = _RequireInputIter<_InputIterator>,
00662            typename = _RequireAllocator<_Allocator>>
00663     unordered_map(_InputIterator, _InputIterator,
00664                   typename unordered_map<int, int>::size_type, _Allocator)
00665     -> unordered_map<__iter_key_t<_InputIterator>,
00666                      __iter_val_t<_InputIterator>,
00667                      hash<__iter_key_t<_InputIterator>>,
00668                      equal_to<__iter_key_t<_InputIterator>>,
00669                      _Allocator>;
00670 
00671   template<typename _InputIterator, typename _Allocator,
00672            typename = _RequireInputIter<_InputIterator>,
00673            typename = _RequireAllocator<_Allocator>>
00674     unordered_map(_InputIterator, _InputIterator, _Allocator)
00675     -> unordered_map<__iter_key_t<_InputIterator>,
00676                      __iter_val_t<_InputIterator>,
00677                      hash<__iter_key_t<_InputIterator>>,
00678                      equal_to<__iter_key_t<_InputIterator>>,
00679                      _Allocator>;
00680 
00681   template<typename _InputIterator, typename _Hash, typename _Allocator,
00682            typename = _RequireInputIter<_InputIterator>,
00683            typename = _RequireAllocator<_Allocator>>
00684     unordered_map(_InputIterator, _InputIterator,
00685                   typename unordered_map<int, int>::size_type,
00686                   _Hash, _Allocator)
00687     -> unordered_map<__iter_key_t<_InputIterator>,
00688                      __iter_val_t<_InputIterator>, _Hash,
00689                      equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
00690 
00691   template<typename _Key, typename _Tp, typename _Allocator,
00692            typename = _RequireAllocator<_Allocator>>
00693     unordered_map(initializer_list<pair<_Key, _Tp>>,
00694                   typename unordered_map<int, int>::size_type,
00695                   _Allocator)
00696     -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
00697 
00698   template<typename _Key, typename _Tp, typename _Allocator,
00699            typename = _RequireAllocator<_Allocator>>
00700     unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
00701     -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
00702 
00703   template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
00704            typename = _RequireAllocator<_Allocator>>
00705     unordered_map(initializer_list<pair<_Key, _Tp>>,
00706                   typename unordered_map<int, int>::size_type,
00707                   _Hash, _Allocator)
00708     -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
00709 
00710 #endif
00711 
00712   template<typename _Key, typename _Tp, typename _Hash,
00713            typename _Pred, typename _Alloc>
00714     inline void
00715     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00716          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00717     noexcept(noexcept(__x.swap(__y)))
00718     { __x.swap(__y); }
00719 
00720   template<typename _Key, typename _Tp, typename _Hash,
00721            typename _Pred, typename _Alloc>
00722     inline bool
00723     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00724                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00725     { return __x._M_base() == __y._M_base(); }
00726 
00727   template<typename _Key, typename _Tp, typename _Hash,
00728            typename _Pred, typename _Alloc>
00729     inline bool
00730     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
00731                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
00732     { return !(__x == __y); }
00733 
00734 
00735   /// Class std::unordered_multimap with safety/checking/debug instrumentation.
00736   template<typename _Key, typename _Tp,
00737            typename _Hash = std::hash<_Key>,
00738            typename _Pred = std::equal_to<_Key>,
00739            typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
00740     class unordered_multimap
00741       : public __gnu_debug::_Safe_container<
00742         unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>, _Alloc,
00743         __gnu_debug::_Safe_unordered_container>,
00744         public _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
00745     {
00746       typedef _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _Hash,
00747                                                  _Pred, _Alloc>         _Base;
00748       typedef __gnu_debug::_Safe_container<unordered_multimap,
00749         _Alloc, __gnu_debug::_Safe_unordered_container>                 _Safe;
00750       typedef typename _Base::const_iterator       _Base_const_iterator;
00751       typedef typename _Base::iterator             _Base_iterator;
00752       typedef typename _Base::const_local_iterator _Base_const_local_iterator;
00753       typedef typename _Base::local_iterator       _Base_local_iterator;
00754 
00755     public:
00756       typedef typename _Base::size_type                 size_type;
00757       typedef typename _Base::hasher                    hasher;
00758       typedef typename _Base::key_equal                 key_equal;
00759       typedef typename _Base::allocator_type            allocator_type;
00760 
00761       typedef typename _Base::key_type                  key_type;
00762       typedef typename _Base::value_type                value_type;
00763 
00764       typedef __gnu_debug::_Safe_iterator<
00765         _Base_iterator, unordered_multimap>             iterator;
00766       typedef __gnu_debug::_Safe_iterator<
00767         _Base_const_iterator, unordered_multimap>       const_iterator;
00768       typedef __gnu_debug::_Safe_local_iterator<
00769         _Base_local_iterator, unordered_multimap>       local_iterator;
00770       typedef __gnu_debug::_Safe_local_iterator<
00771         _Base_const_local_iterator, unordered_multimap> const_local_iterator;
00772 
00773       unordered_multimap() = default;
00774 
00775       explicit
00776       unordered_multimap(size_type __n,
00777                          const hasher& __hf = hasher(),
00778                          const key_equal& __eql = key_equal(),
00779                          const allocator_type& __a = allocator_type())
00780       : _Base(__n, __hf, __eql, __a) { }
00781 
00782       template<typename _InputIterator>
00783         unordered_multimap(_InputIterator __first, _InputIterator __last,
00784                            size_type __n = 0,
00785                            const hasher& __hf = hasher(),
00786                            const key_equal& __eql = key_equal(),
00787                            const allocator_type& __a = allocator_type())
00788         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00789                                                                      __last)),
00790                 __gnu_debug::__base(__last), __n,
00791                 __hf, __eql, __a) { }
00792 
00793       unordered_multimap(const unordered_multimap&) = default;
00794 
00795       unordered_multimap(const _Base& __x)
00796       : _Base(__x) { }
00797 
00798       unordered_multimap(unordered_multimap&&) = default;
00799 
00800       explicit
00801       unordered_multimap(const allocator_type& __a)
00802       : _Base(__a) { }
00803 
00804       unordered_multimap(const unordered_multimap& __umap,
00805                          const allocator_type& __a)
00806       : _Base(__umap, __a) { }
00807 
00808       unordered_multimap(unordered_multimap&& __umap,
00809                          const allocator_type& __a)
00810       : _Safe(std::move(__umap._M_safe()), __a),
00811         _Base(std::move(__umap._M_base()), __a) { }
00812 
00813       unordered_multimap(initializer_list<value_type> __l,
00814                          size_type __n = 0,
00815                          const hasher& __hf = hasher(),
00816                          const key_equal& __eql = key_equal(),
00817                          const allocator_type& __a = allocator_type())
00818       : _Base(__l, __n, __hf, __eql, __a) { }
00819 
00820       unordered_multimap(size_type __n, const allocator_type& __a)
00821       : unordered_multimap(__n, hasher(), key_equal(), __a)
00822       { }
00823 
00824       unordered_multimap(size_type __n, const hasher& __hf,
00825                          const allocator_type& __a)
00826       : unordered_multimap(__n, __hf, key_equal(), __a)
00827       { }
00828 
00829       template<typename _InputIterator>
00830         unordered_multimap(_InputIterator __first, _InputIterator __last,
00831                            size_type __n,
00832                            const allocator_type& __a)
00833           : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
00834         { }
00835 
00836       template<typename _InputIterator>
00837         unordered_multimap(_InputIterator __first, _InputIterator __last,
00838                            size_type __n, const hasher& __hf,
00839                            const allocator_type& __a)
00840           : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
00841         { }
00842 
00843       unordered_multimap(initializer_list<value_type> __l,
00844                          size_type __n,
00845                          const allocator_type& __a)
00846         : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
00847       { }
00848 
00849       unordered_multimap(initializer_list<value_type> __l,
00850                          size_type __n, const hasher& __hf,
00851                          const allocator_type& __a)
00852         : unordered_multimap(__l, __n, __hf, key_equal(), __a)
00853       { }
00854 
00855       ~unordered_multimap() = default;
00856 
00857       unordered_multimap&
00858       operator=(const unordered_multimap&) = default;
00859 
00860       unordered_multimap&
00861       operator=(unordered_multimap&&) = default;
00862 
00863       unordered_multimap&
00864       operator=(initializer_list<value_type> __l)
00865       {
00866         this->_M_base() = __l;
00867         this->_M_invalidate_all();
00868         return *this;
00869       }
00870 
00871       void
00872       swap(unordered_multimap& __x)
00873         noexcept( noexcept(declval<_Base&>().swap(__x)) )
00874       {
00875         _Safe::_M_swap(__x);
00876         _Base::swap(__x);
00877       }
00878 
00879       void
00880       clear() noexcept
00881       {
00882         _Base::clear();
00883         this->_M_invalidate_all();
00884       }
00885 
00886       iterator
00887       begin() noexcept
00888       { return iterator(_Base::begin(), this); }
00889 
00890       const_iterator
00891       begin() const noexcept
00892       { return const_iterator(_Base::begin(), this); }
00893 
00894       iterator
00895       end() noexcept
00896       { return iterator(_Base::end(), this); }
00897 
00898       const_iterator
00899       end() const noexcept
00900       { return const_iterator(_Base::end(), this); }
00901 
00902       const_iterator
00903       cbegin() const noexcept
00904       { return const_iterator(_Base::begin(), this); }
00905 
00906       const_iterator
00907       cend() const noexcept
00908       { return const_iterator(_Base::end(), this); }
00909 
00910       // local versions
00911       local_iterator
00912       begin(size_type __b)
00913       {
00914         __glibcxx_check_bucket_index(__b);
00915         return local_iterator(_Base::begin(__b), this);
00916       }
00917 
00918       local_iterator
00919       end(size_type __b)
00920       {
00921         __glibcxx_check_bucket_index(__b);
00922         return local_iterator(_Base::end(__b), this);
00923       }
00924 
00925       const_local_iterator
00926       begin(size_type __b) const
00927       {
00928         __glibcxx_check_bucket_index(__b);
00929         return const_local_iterator(_Base::begin(__b), this);
00930       }
00931 
00932       const_local_iterator
00933       end(size_type __b) const
00934       {
00935         __glibcxx_check_bucket_index(__b);
00936         return const_local_iterator(_Base::end(__b), this);
00937       }
00938 
00939       const_local_iterator
00940       cbegin(size_type __b) const
00941       {
00942         __glibcxx_check_bucket_index(__b);
00943         return const_local_iterator(_Base::cbegin(__b), this);
00944       }
00945 
00946       const_local_iterator
00947       cend(size_type __b) const
00948       {
00949         __glibcxx_check_bucket_index(__b);
00950         return const_local_iterator(_Base::cend(__b), this);
00951       }
00952 
00953       size_type
00954       bucket_size(size_type __b) const
00955       {
00956         __glibcxx_check_bucket_index(__b);
00957         return _Base::bucket_size(__b);
00958       }
00959 
00960       float
00961       max_load_factor() const noexcept
00962       { return _Base::max_load_factor(); }
00963 
00964       void
00965       max_load_factor(float __f)
00966       {
00967         __glibcxx_check_max_load_factor(__f);
00968         _Base::max_load_factor(__f);
00969       }
00970 
00971       template<typename... _Args>
00972         iterator
00973         emplace(_Args&&... __args)
00974         {
00975           size_type __bucket_count = this->bucket_count();
00976           _Base_iterator __it
00977             = _Base::emplace(std::forward<_Args>(__args)...);
00978           _M_check_rehashed(__bucket_count);
00979           return iterator(__it, this);
00980         }
00981 
00982       template<typename... _Args>
00983         iterator
00984         emplace_hint(const_iterator __hint, _Args&&... __args)
00985         {
00986           __glibcxx_check_insert(__hint);
00987           size_type __bucket_count = this->bucket_count();
00988           _Base_iterator __it = _Base::emplace_hint(__hint.base(),
00989                                         std::forward<_Args>(__args)...);
00990           _M_check_rehashed(__bucket_count);
00991           return iterator(__it, this);
00992         }
00993 
00994       iterator
00995       insert(const value_type& __obj)
00996       {
00997         size_type __bucket_count = this->bucket_count();
00998         _Base_iterator __it = _Base::insert(__obj);
00999         _M_check_rehashed(__bucket_count);
01000         return iterator(__it, this);
01001       }
01002 
01003       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01004       // 2354. Unnecessary copying when inserting into maps with braced-init
01005       iterator
01006       insert(value_type&& __x)
01007       {
01008         size_type __bucket_count = this->bucket_count();
01009         auto __it = _Base::insert(std::move(__x));
01010         _M_check_rehashed(__bucket_count);
01011         return { __it, this };
01012       }
01013 
01014       iterator
01015       insert(const_iterator __hint, const value_type& __obj)
01016       {
01017         __glibcxx_check_insert(__hint);
01018         size_type __bucket_count = this->bucket_count();
01019         _Base_iterator __it = _Base::insert(__hint.base(), __obj);
01020         _M_check_rehashed(__bucket_count);
01021         return iterator(__it, this);
01022       }
01023 
01024       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01025       // 2354. Unnecessary copying when inserting into maps with braced-init
01026       iterator
01027       insert(const_iterator __hint, value_type&& __x)
01028       {
01029         __glibcxx_check_insert(__hint);
01030         size_type __bucket_count = this->bucket_count();
01031         auto __it = _Base::insert(__hint.base(), std::move(__x));
01032         _M_check_rehashed(__bucket_count);
01033         return iterator(__it, this);
01034       }
01035 
01036       template<typename _Pair, typename = typename
01037                std::enable_if<std::is_constructible<value_type,
01038                                                     _Pair&&>::value>::type>
01039         iterator
01040         insert(_Pair&& __obj)
01041         {
01042           size_type __bucket_count = this->bucket_count();
01043           _Base_iterator __it = _Base::insert(std::forward<_Pair>(__obj));
01044           _M_check_rehashed(__bucket_count);
01045           return iterator(__it, this);
01046         }
01047 
01048       template<typename _Pair, typename = typename
01049                std::enable_if<std::is_constructible<value_type,
01050                                                     _Pair&&>::value>::type>
01051         iterator
01052         insert(const_iterator __hint, _Pair&& __obj)
01053         {
01054           __glibcxx_check_insert(__hint);
01055           size_type __bucket_count = this->bucket_count();
01056           _Base_iterator __it =
01057             _Base::insert(__hint.base(), std::forward<_Pair>(__obj));
01058           _M_check_rehashed(__bucket_count);
01059           return iterator(__it, this);
01060         }
01061 
01062       void
01063       insert(std::initializer_list<value_type> __l)
01064       { _Base::insert(__l); }
01065 
01066       template<typename _InputIterator>
01067         void
01068         insert(_InputIterator __first, _InputIterator __last)
01069         {
01070           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
01071           __glibcxx_check_valid_range2(__first, __last, __dist);
01072           size_type __bucket_count = this->bucket_count();
01073 
01074           if (__dist.second >= __gnu_debug::__dp_sign)
01075             _Base::insert(__gnu_debug::__unsafe(__first),
01076                           __gnu_debug::__unsafe(__last));
01077           else
01078             _Base::insert(__first, __last);
01079 
01080           _M_check_rehashed(__bucket_count);
01081         }
01082 
01083 #if __cplusplus > 201402L
01084       using node_type = typename _Base::node_type;
01085 
01086       node_type
01087       extract(const_iterator __position)
01088       {
01089         __glibcxx_check_erase(__position);
01090         _Base_const_iterator __victim = __position.base();
01091         this->_M_invalidate_if(
01092             [__victim](_Base_const_iterator __it) { return __it == __victim; }
01093             );
01094         this->_M_invalidate_local_if(
01095             [__victim](_Base_const_local_iterator __it) {
01096                 return __it._M_curr() == __victim._M_cur;
01097             });
01098         return _Base::extract(__position.base());
01099       }
01100 
01101       node_type
01102       extract(const key_type& __key)
01103       {
01104         const auto __position = find(__key);
01105         if (__position != end())
01106           return extract(__position);
01107         return {};
01108       }
01109 
01110       iterator
01111       insert(node_type&& __nh)
01112       { return iterator(_Base::insert(std::move(__nh)), this); }
01113 
01114       iterator
01115       insert(const_iterator __hint, node_type&& __nh)
01116       {
01117         __glibcxx_check_insert(__hint);
01118         return iterator(_Base::insert(__hint.base(), std::move(__nh)), this);
01119       }
01120 
01121       using _Base::merge;
01122 #endif // C++17
01123 
01124       iterator
01125       find(const key_type& __key)
01126       { return iterator(_Base::find(__key), this); }
01127 
01128       const_iterator
01129       find(const key_type& __key) const
01130       { return const_iterator(_Base::find(__key), this); }
01131 
01132       std::pair<iterator, iterator>
01133       equal_range(const key_type& __key)
01134       {
01135         std::pair<_Base_iterator, _Base_iterator> __res =
01136           _Base::equal_range(__key);
01137         return std::make_pair(iterator(__res.first, this),
01138                               iterator(__res.second, this));
01139       }
01140 
01141       std::pair<const_iterator, const_iterator>
01142       equal_range(const key_type& __key) const
01143       {
01144         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
01145           _Base::equal_range(__key);
01146         return std::make_pair(const_iterator(__res.first, this),
01147                               const_iterator(__res.second, this));
01148       }
01149 
01150       size_type
01151       erase(const key_type& __key)
01152       {
01153         size_type __ret(0);
01154         size_type __bucket_count = this->bucket_count();
01155         std::pair<_Base_iterator, _Base_iterator> __pair =
01156           _Base::equal_range(__key);
01157         for (_Base_iterator __victim = __pair.first; __victim != __pair.second;)
01158           {
01159             this->_M_invalidate_if([__victim](_Base_const_iterator __it)
01160                             { return __it == __victim; });
01161             this->_M_invalidate_local_if(
01162                             [__victim](_Base_const_local_iterator __it)
01163                             { return __it._M_curr() == __victim._M_cur; });
01164             _Base::erase(__victim++);
01165             ++__ret;
01166           }
01167         _M_check_rehashed(__bucket_count);
01168         return __ret;
01169       }
01170 
01171       iterator
01172       erase(const_iterator __it)
01173       {
01174         __glibcxx_check_erase(__it);
01175         _Base_const_iterator __victim = __it.base();
01176         this->_M_invalidate_if([__victim](_Base_const_iterator __it)
01177                         { return __it == __victim; });
01178         this->_M_invalidate_local_if(
01179                         [__victim](_Base_const_local_iterator __it)
01180                         { return __it._M_curr() == __victim._M_cur; });
01181         size_type __bucket_count = this->bucket_count();
01182         _Base_iterator __next = _Base::erase(__it.base());
01183         _M_check_rehashed(__bucket_count);
01184         return iterator(__next, this);
01185       }
01186 
01187       iterator
01188       erase(iterator __it)
01189       { return erase(const_iterator(__it)); }
01190 
01191       iterator
01192       erase(const_iterator __first, const_iterator __last)
01193       {
01194         __glibcxx_check_erase_range(__first, __last);
01195         for (_Base_const_iterator __tmp = __first.base();
01196              __tmp != __last.base(); ++__tmp)
01197           {
01198             _GLIBCXX_DEBUG_VERIFY(__tmp != _Base::end(),
01199                                   _M_message(__gnu_debug::__msg_valid_range)
01200                                   ._M_iterator(__first, "first")
01201                                   ._M_iterator(__last, "last"));
01202             this->_M_invalidate_if([__tmp](_Base_const_iterator __it)
01203                             { return __it == __tmp; });
01204             this->_M_invalidate_local_if(
01205                             [__tmp](_Base_const_local_iterator __it)
01206                             { return __it._M_curr() == __tmp._M_cur; });
01207           }
01208         size_type __bucket_count = this->bucket_count();
01209         _Base_iterator __next = _Base::erase(__first.base(), __last.base());
01210         _M_check_rehashed(__bucket_count);
01211         return iterator(__next, this);
01212       }
01213 
01214       _Base&
01215       _M_base() noexcept { return *this; }
01216 
01217       const _Base&
01218       _M_base() const noexcept { return *this; }
01219 
01220     private:
01221       void
01222       _M_check_rehashed(size_type __prev_count)
01223       {
01224         if (__prev_count != this->bucket_count())
01225           this->_M_invalidate_locals();
01226       }
01227     };
01228 
01229 #if __cpp_deduction_guides >= 201606
01230 
01231   template<typename _InputIterator,
01232            typename _Hash = hash<__iter_key_t<_InputIterator>>,
01233            typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
01234            typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
01235            typename = _RequireInputIter<_InputIterator>,
01236            typename = _RequireAllocator<_Allocator>>
01237     unordered_multimap(_InputIterator, _InputIterator,
01238                        unordered_multimap<int, int>::size_type = {},
01239                        _Hash = _Hash(), _Pred = _Pred(),
01240                        _Allocator = _Allocator())
01241     -> unordered_multimap<__iter_key_t<_InputIterator>,
01242                           __iter_val_t<_InputIterator>, _Hash, _Pred,
01243                           _Allocator>;
01244 
01245   template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
01246            typename _Pred = equal_to<_Key>,
01247            typename _Allocator = allocator<pair<const _Key, _Tp>>,
01248            typename = _RequireAllocator<_Allocator>>
01249     unordered_multimap(initializer_list<pair<_Key, _Tp>>,
01250                        unordered_multimap<int, int>::size_type = {},
01251                        _Hash = _Hash(), _Pred = _Pred(),
01252                        _Allocator = _Allocator())
01253     -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
01254 
01255   template<typename _InputIterator, typename _Allocator,
01256            typename = _RequireInputIter<_InputIterator>,
01257            typename = _RequireAllocator<_Allocator>>
01258     unordered_multimap(_InputIterator, _InputIterator,
01259                        unordered_multimap<int, int>::size_type, _Allocator)
01260     -> unordered_multimap<__iter_key_t<_InputIterator>,
01261                           __iter_val_t<_InputIterator>,
01262                           hash<__iter_key_t<_InputIterator>>,
01263                           equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
01264 
01265   template<typename _InputIterator, typename _Allocator,
01266            typename = _RequireInputIter<_InputIterator>,
01267            typename = _RequireAllocator<_Allocator>>
01268     unordered_multimap(_InputIterator, _InputIterator, _Allocator)
01269     -> unordered_multimap<__iter_key_t<_InputIterator>,
01270                           __iter_val_t<_InputIterator>,
01271                           hash<__iter_key_t<_InputIterator>>,
01272                           equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
01273 
01274   template<typename _InputIterator, typename _Hash, typename _Allocator,
01275            typename = _RequireInputIter<_InputIterator>,
01276            typename = _RequireAllocator<_Allocator>>
01277     unordered_multimap(_InputIterator, _InputIterator,
01278                        unordered_multimap<int, int>::size_type, _Hash,
01279                        _Allocator)
01280     -> unordered_multimap<__iter_key_t<_InputIterator>,
01281                           __iter_val_t<_InputIterator>, _Hash,
01282                           equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
01283 
01284   template<typename _Key, typename _Tp, typename _Allocator,
01285            typename = _RequireAllocator<_Allocator>>
01286     unordered_multimap(initializer_list<pair<_Key, _Tp>>,
01287                        unordered_multimap<int, int>::size_type,
01288                        _Allocator)
01289     -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
01290 
01291   template<typename _Key, typename _Tp, typename _Allocator,
01292            typename = _RequireAllocator<_Allocator>>
01293     unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
01294     -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
01295 
01296   template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
01297            typename = _RequireAllocator<_Allocator>>
01298     unordered_multimap(initializer_list<pair<_Key, _Tp>>,
01299                        unordered_multimap<int, int>::size_type,
01300                        _Hash, _Allocator)
01301     -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
01302 
01303 #endif
01304 
01305   template<typename _Key, typename _Tp, typename _Hash,
01306            typename _Pred, typename _Alloc>
01307     inline void
01308     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
01309          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
01310     noexcept(noexcept(__x.swap(__y)))
01311     { __x.swap(__y); }
01312 
01313   template<typename _Key, typename _Tp, typename _Hash,
01314            typename _Pred, typename _Alloc>
01315     inline bool
01316     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
01317                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
01318     { return __x._M_base() == __y._M_base(); }
01319 
01320   template<typename _Key, typename _Tp, typename _Hash,
01321            typename _Pred, typename _Alloc>
01322     inline bool
01323     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
01324                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
01325     { return !(__x == __y); }
01326 
01327 } // namespace __debug
01328 } // namespace std
01329 
01330 #endif // C++11
01331 
01332 #endif