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