libstdc++
unordered_map.h
Go to the documentation of this file.
00001 // unordered_map implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2010-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 bits/unordered_map.h
00026  *  This is an internal header file, included by other library headers.
00027  *  Do not attempt to use it directly. @headername{unordered_map}
00028  */
00029 
00030 #ifndef _UNORDERED_MAP_H
00031 #define _UNORDERED_MAP_H
00032 
00033 namespace std _GLIBCXX_VISIBILITY(default)
00034 {
00035 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00036 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00037 
00038   /// Base types for unordered_map.
00039   template<bool _Cache>
00040     using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>;
00041 
00042   template<typename _Key,
00043            typename _Tp,
00044            typename _Hash = hash<_Key>,
00045            typename _Pred = std::equal_to<_Key>,
00046            typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
00047            typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>>
00048     using __umap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>,
00049                                         _Alloc, __detail::_Select1st,
00050                                         _Pred, _Hash,
00051                                         __detail::_Mod_range_hashing,
00052                                         __detail::_Default_ranged_hash,
00053                                         __detail::_Prime_rehash_policy, _Tr>;
00054 
00055   /// Base types for unordered_multimap.
00056   template<bool _Cache>
00057     using __ummap_traits = __detail::_Hashtable_traits<_Cache, false, false>;
00058 
00059   template<typename _Key,
00060            typename _Tp,
00061            typename _Hash = hash<_Key>,
00062            typename _Pred = std::equal_to<_Key>,
00063            typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
00064            typename _Tr = __ummap_traits<__cache_default<_Key, _Hash>::value>>
00065     using __ummap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>,
00066                                          _Alloc, __detail::_Select1st,
00067                                          _Pred, _Hash,
00068                                          __detail::_Mod_range_hashing,
00069                                          __detail::_Default_ranged_hash,
00070                                          __detail::_Prime_rehash_policy, _Tr>;
00071 
00072   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
00073     class unordered_multimap;
00074 
00075   /**
00076    *  @brief A standard container composed of unique keys (containing
00077    *  at most one of each key value) that associates values of another type
00078    *  with the keys.
00079    *
00080    *  @ingroup unordered_associative_containers
00081    *
00082    *  @tparam  _Key    Type of key objects.
00083    *  @tparam  _Tp     Type of mapped objects.
00084    *  @tparam  _Hash   Hashing function object type, defaults to hash<_Value>.
00085    *  @tparam  _Pred   Predicate function object type, defaults
00086    *                   to equal_to<_Value>.
00087    *  @tparam  _Alloc  Allocator type, defaults to 
00088    *                   std::allocator<std::pair<const _Key, _Tp>>.
00089    *
00090    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
00091    *  <a href="tables.html#xx">unordered associative container</a>
00092    *
00093    * The resulting value type of the container is std::pair<const _Key, _Tp>.
00094    *
00095    *  Base is _Hashtable, dispatched at compile time via template
00096    *  alias __umap_hashtable.
00097    */
00098   template<typename _Key, typename _Tp,
00099            typename _Hash = hash<_Key>,
00100            typename _Pred = equal_to<_Key>,
00101            typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
00102     class unordered_map
00103     {
00104       typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
00105       _Hashtable _M_h;
00106 
00107     public:
00108       // typedefs:
00109       //@{
00110       /// Public typedefs.
00111       typedef typename _Hashtable::key_type     key_type;
00112       typedef typename _Hashtable::value_type   value_type;
00113       typedef typename _Hashtable::mapped_type  mapped_type;
00114       typedef typename _Hashtable::hasher       hasher;
00115       typedef typename _Hashtable::key_equal    key_equal;
00116       typedef typename _Hashtable::allocator_type allocator_type;
00117       //@}
00118 
00119       //@{
00120       ///  Iterator-related typedefs.
00121       typedef typename _Hashtable::pointer              pointer;
00122       typedef typename _Hashtable::const_pointer        const_pointer;
00123       typedef typename _Hashtable::reference            reference;
00124       typedef typename _Hashtable::const_reference      const_reference;
00125       typedef typename _Hashtable::iterator             iterator;
00126       typedef typename _Hashtable::const_iterator       const_iterator;
00127       typedef typename _Hashtable::local_iterator       local_iterator;
00128       typedef typename _Hashtable::const_local_iterator const_local_iterator;
00129       typedef typename _Hashtable::size_type            size_type;
00130       typedef typename _Hashtable::difference_type      difference_type;
00131       //@}
00132 
00133 #if __cplusplus > 201402L
00134       using node_type = typename _Hashtable::node_type;
00135       using insert_return_type = typename _Hashtable::insert_return_type;
00136 #endif
00137 
00138       //construct/destroy/copy
00139 
00140       /// Default constructor.
00141       unordered_map() = default;
00142 
00143       /**
00144        *  @brief  Default constructor creates no elements.
00145        *  @param __n  Minimal initial number of buckets.
00146        *  @param __hf  A hash functor.
00147        *  @param __eql  A key equality functor.
00148        *  @param __a  An allocator object.
00149        */
00150       explicit
00151       unordered_map(size_type __n,
00152                     const hasher& __hf = hasher(),
00153                     const key_equal& __eql = key_equal(),
00154                     const allocator_type& __a = allocator_type())
00155       : _M_h(__n, __hf, __eql, __a)
00156       { }
00157 
00158       /**
00159        *  @brief  Builds an %unordered_map from a range.
00160        *  @param  __first  An input iterator.
00161        *  @param  __last  An input iterator.
00162        *  @param __n  Minimal initial number of buckets.
00163        *  @param __hf  A hash functor.
00164        *  @param __eql  A key equality functor.
00165        *  @param __a  An allocator object.
00166        *
00167        *  Create an %unordered_map consisting of copies of the elements from
00168        *  [__first,__last).  This is linear in N (where N is
00169        *  distance(__first,__last)).
00170        */
00171       template<typename _InputIterator>
00172         unordered_map(_InputIterator __first, _InputIterator __last,
00173                       size_type __n = 0,
00174                       const hasher& __hf = hasher(),
00175                       const key_equal& __eql = key_equal(),
00176                       const allocator_type& __a = allocator_type())
00177         : _M_h(__first, __last, __n, __hf, __eql, __a)
00178         { }
00179 
00180       /// Copy constructor.
00181       unordered_map(const unordered_map&) = default;
00182 
00183       /// Move constructor.
00184       unordered_map(unordered_map&&) = default;
00185 
00186       /**
00187        *  @brief Creates an %unordered_map with no elements.
00188        *  @param __a An allocator object.
00189        */
00190       explicit
00191       unordered_map(const allocator_type& __a)
00192         : _M_h(__a)
00193       { }
00194 
00195       /*
00196        *  @brief Copy constructor with allocator argument.
00197        * @param  __uset  Input %unordered_map to copy.
00198        * @param  __a  An allocator object.
00199        */
00200       unordered_map(const unordered_map& __umap,
00201                     const allocator_type& __a)
00202       : _M_h(__umap._M_h, __a)
00203       { }
00204 
00205       /*
00206        *  @brief  Move constructor with allocator argument.
00207        *  @param  __uset Input %unordered_map to move.
00208        *  @param  __a    An allocator object.
00209        */
00210       unordered_map(unordered_map&& __umap,
00211                     const allocator_type& __a)
00212       : _M_h(std::move(__umap._M_h), __a)
00213       { }
00214 
00215       /**
00216        *  @brief  Builds an %unordered_map from an initializer_list.
00217        *  @param  __l  An initializer_list.
00218        *  @param __n  Minimal initial number of buckets.
00219        *  @param __hf  A hash functor.
00220        *  @param __eql  A key equality functor.
00221        *  @param  __a  An allocator object.
00222        *
00223        *  Create an %unordered_map consisting of copies of the elements in the
00224        *  list. This is linear in N (where N is @a __l.size()).
00225        */
00226       unordered_map(initializer_list<value_type> __l,
00227                     size_type __n = 0,
00228                     const hasher& __hf = hasher(),
00229                     const key_equal& __eql = key_equal(),
00230                     const allocator_type& __a = allocator_type())
00231       : _M_h(__l, __n, __hf, __eql, __a)
00232       { }
00233 
00234       unordered_map(size_type __n, const allocator_type& __a)
00235       : unordered_map(__n, hasher(), key_equal(), __a)
00236       { }
00237 
00238       unordered_map(size_type __n, const hasher& __hf,
00239                     const allocator_type& __a)
00240       : unordered_map(__n, __hf, key_equal(), __a)
00241       { }
00242 
00243       template<typename _InputIterator>
00244         unordered_map(_InputIterator __first, _InputIterator __last,
00245                       size_type __n,
00246                       const allocator_type& __a)
00247         : unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
00248         { }
00249 
00250       template<typename _InputIterator>
00251         unordered_map(_InputIterator __first, _InputIterator __last,
00252                       size_type __n, const hasher& __hf,
00253                       const allocator_type& __a)
00254           : unordered_map(__first, __last, __n, __hf, key_equal(), __a)
00255         { }
00256 
00257       unordered_map(initializer_list<value_type> __l,
00258                     size_type __n,
00259                     const allocator_type& __a)
00260       : unordered_map(__l, __n, hasher(), key_equal(), __a)
00261       { }
00262 
00263       unordered_map(initializer_list<value_type> __l,
00264                     size_type __n, const hasher& __hf,
00265                     const allocator_type& __a)
00266       : unordered_map(__l, __n, __hf, key_equal(), __a)
00267       { }
00268 
00269       /// Copy assignment operator.
00270       unordered_map&
00271       operator=(const unordered_map&) = default;
00272 
00273       /// Move assignment operator.
00274       unordered_map&
00275       operator=(unordered_map&&) = default;
00276 
00277       /**
00278        *  @brief  %Unordered_map list assignment operator.
00279        *  @param  __l  An initializer_list.
00280        *
00281        *  This function fills an %unordered_map with copies of the elements in
00282        *  the initializer list @a __l.
00283        *
00284        *  Note that the assignment completely changes the %unordered_map and
00285        *  that the resulting %unordered_map's size is the same as the number
00286        *  of elements assigned.
00287        */
00288       unordered_map&
00289       operator=(initializer_list<value_type> __l)
00290       {
00291         _M_h = __l;
00292         return *this;
00293       }
00294 
00295       ///  Returns the allocator object used by the %unordered_map.
00296       allocator_type
00297       get_allocator() const noexcept
00298       { return _M_h.get_allocator(); }
00299 
00300       // size and capacity:
00301 
00302       ///  Returns true if the %unordered_map is empty.
00303       bool
00304       empty() const noexcept
00305       { return _M_h.empty(); }
00306 
00307       ///  Returns the size of the %unordered_map.
00308       size_type
00309       size() const noexcept
00310       { return _M_h.size(); }
00311 
00312       ///  Returns the maximum size of the %unordered_map.
00313       size_type
00314       max_size() const noexcept
00315       { return _M_h.max_size(); }
00316 
00317       // iterators.
00318 
00319       /**
00320        *  Returns a read/write iterator that points to the first element in the
00321        *  %unordered_map.
00322        */
00323       iterator
00324       begin() noexcept
00325       { return _M_h.begin(); }
00326 
00327       //@{
00328       /**
00329        *  Returns a read-only (constant) iterator that points to the first
00330        *  element in the %unordered_map.
00331        */
00332       const_iterator
00333       begin() const noexcept
00334       { return _M_h.begin(); }
00335 
00336       const_iterator
00337       cbegin() const noexcept
00338       { return _M_h.begin(); }
00339       //@}
00340 
00341       /**
00342        *  Returns a read/write iterator that points one past the last element in
00343        *  the %unordered_map.
00344        */
00345       iterator
00346       end() noexcept
00347       { return _M_h.end(); }
00348 
00349       //@{
00350       /**
00351        *  Returns a read-only (constant) iterator that points one past the last
00352        *  element in the %unordered_map.
00353        */
00354       const_iterator
00355       end() const noexcept
00356       { return _M_h.end(); }
00357 
00358       const_iterator
00359       cend() const noexcept
00360       { return _M_h.end(); }
00361       //@}
00362 
00363       // modifiers.
00364 
00365       /**
00366        *  @brief Attempts to build and insert a std::pair into the
00367        *  %unordered_map.
00368        *
00369        *  @param __args  Arguments used to generate a new pair instance (see
00370        *                std::piecewise_contruct for passing arguments to each
00371        *                part of the pair constructor).
00372        *
00373        *  @return  A pair, of which the first element is an iterator that points
00374        *           to the possibly inserted pair, and the second is a bool that
00375        *           is true if the pair was actually inserted.
00376        *
00377        *  This function attempts to build and insert a (key, value) %pair into
00378        *  the %unordered_map.
00379        *  An %unordered_map relies on unique keys and thus a %pair is only
00380        *  inserted if its first element (the key) is not already present in the
00381        *  %unordered_map.
00382        *
00383        *  Insertion requires amortized constant time.
00384        */
00385       template<typename... _Args>
00386         std::pair<iterator, bool>
00387         emplace(_Args&&... __args)
00388         { return _M_h.emplace(std::forward<_Args>(__args)...); }
00389 
00390       /**
00391        *  @brief Attempts to build and insert a std::pair into the
00392        *  %unordered_map.
00393        *
00394        *  @param  __pos  An iterator that serves as a hint as to where the pair
00395        *                should be inserted.
00396        *  @param  __args  Arguments used to generate a new pair instance (see
00397        *                 std::piecewise_contruct for passing arguments to each
00398        *                 part of the pair constructor).
00399        *  @return An iterator that points to the element with key of the
00400        *          std::pair built from @a __args (may or may not be that
00401        *          std::pair).
00402        *
00403        *  This function is not concerned about whether the insertion took place,
00404        *  and thus does not return a boolean like the single-argument emplace()
00405        *  does.
00406        *  Note that the first parameter is only a hint and can potentially
00407        *  improve the performance of the insertion process. A bad hint would
00408        *  cause no gains in efficiency.
00409        *
00410        *  See
00411        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
00412        *  for more on @a hinting.
00413        *
00414        *  Insertion requires amortized constant time.
00415        */
00416       template<typename... _Args>
00417         iterator
00418         emplace_hint(const_iterator __pos, _Args&&... __args)
00419         { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
00420 
00421 #if __cplusplus > 201402L
00422       /// Extract a node.
00423       node_type
00424       extract(const_iterator __pos)
00425       {
00426         __glibcxx_assert(__pos != end());
00427         return _M_h.extract(__pos);
00428       }
00429 
00430       /// Extract a node.
00431       node_type
00432       extract(const key_type& __key)
00433       { return _M_h.extract(__key); }
00434 
00435       /// Re-insert an extracted node.
00436       insert_return_type
00437       insert(node_type&& __nh)
00438       { return _M_h._M_reinsert_node(std::move(__nh)); }
00439 
00440       /// Re-insert an extracted node.
00441       iterator
00442       insert(const_iterator, node_type&& __nh)
00443       { return _M_h._M_reinsert_node(std::move(__nh)).position; }
00444 
00445 #define __cpp_lib_unordered_map_try_emplace 201411
00446       /**
00447        *  @brief Attempts to build and insert a std::pair into the
00448        *  %unordered_map.
00449        *
00450        *  @param __k    Key to use for finding a possibly existing pair in
00451        *                the unordered_map.
00452        *  @param __args  Arguments used to generate the .second for a 
00453        *                new pair instance.
00454        *
00455        *  @return  A pair, of which the first element is an iterator that points
00456        *           to the possibly inserted pair, and the second is a bool that
00457        *           is true if the pair was actually inserted.
00458        *
00459        *  This function attempts to build and insert a (key, value) %pair into
00460        *  the %unordered_map.
00461        *  An %unordered_map relies on unique keys and thus a %pair is only
00462        *  inserted if its first element (the key) is not already present in the
00463        *  %unordered_map.
00464        *  If a %pair is not inserted, this function has no effect.
00465        *
00466        *  Insertion requires amortized constant time.
00467        */
00468       template <typename... _Args>
00469         pair<iterator, bool>
00470         try_emplace(const key_type& __k, _Args&&... __args)
00471         {
00472           iterator __i = find(__k);
00473           if (__i == end())
00474             {
00475               __i = emplace(std::piecewise_construct,
00476                             std::forward_as_tuple(__k),
00477                             std::forward_as_tuple(
00478                               std::forward<_Args>(__args)...))
00479                 .first;
00480               return {__i, true};
00481             }
00482           return {__i, false};
00483         }
00484 
00485       // move-capable overload
00486       template <typename... _Args>
00487         pair<iterator, bool>
00488         try_emplace(key_type&& __k, _Args&&... __args)
00489         {
00490           iterator __i = find(__k);
00491           if (__i == end())
00492             {
00493               __i = emplace(std::piecewise_construct,
00494                             std::forward_as_tuple(std::move(__k)),
00495                             std::forward_as_tuple(
00496                               std::forward<_Args>(__args)...))
00497                 .first;
00498               return {__i, true};
00499             }
00500           return {__i, false};
00501         }
00502 
00503       /**
00504        *  @brief Attempts to build and insert a std::pair into the
00505        *  %unordered_map.
00506        *
00507        *  @param  __hint  An iterator that serves as a hint as to where the pair
00508        *                should be inserted.
00509        *  @param __k    Key to use for finding a possibly existing pair in
00510        *                the unordered_map.
00511        *  @param __args  Arguments used to generate the .second for a 
00512        *                new pair instance.
00513        *  @return An iterator that points to the element with key of the
00514        *          std::pair built from @a __args (may or may not be that
00515        *          std::pair).
00516        *
00517        *  This function is not concerned about whether the insertion took place,
00518        *  and thus does not return a boolean like the single-argument emplace()
00519        *  does. However, if insertion did not take place,
00520        *  this function has no effect.
00521        *  Note that the first parameter is only a hint and can potentially
00522        *  improve the performance of the insertion process. A bad hint would
00523        *  cause no gains in efficiency.
00524        *
00525        *  See
00526        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
00527        *  for more on @a hinting.
00528        *
00529        *  Insertion requires amortized constant time.
00530        */
00531       template <typename... _Args>
00532         iterator
00533         try_emplace(const_iterator __hint, const key_type& __k,
00534                     _Args&&... __args)
00535         {
00536           iterator __i = find(__k);
00537           if (__i == end())
00538             __i = emplace_hint(__hint, std::piecewise_construct,
00539                                std::forward_as_tuple(__k),
00540                                std::forward_as_tuple(
00541                                  std::forward<_Args>(__args)...));
00542           return __i;
00543         }
00544 
00545       // move-capable overload
00546       template <typename... _Args>
00547         iterator
00548         try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
00549         {
00550           iterator __i = find(__k);
00551           if (__i == end())
00552             __i = emplace_hint(__hint, std::piecewise_construct,
00553                                std::forward_as_tuple(std::move(__k)),
00554                                std::forward_as_tuple(
00555                                  std::forward<_Args>(__args)...));
00556           return __i;
00557         }
00558 #endif // C++17
00559 
00560       //@{
00561       /**
00562        *  @brief Attempts to insert a std::pair into the %unordered_map.
00563 
00564        *  @param __x Pair to be inserted (see std::make_pair for easy
00565        *             creation of pairs).
00566        *
00567        *  @return  A pair, of which the first element is an iterator that 
00568        *           points to the possibly inserted pair, and the second is 
00569        *           a bool that is true if the pair was actually inserted.
00570        *
00571        *  This function attempts to insert a (key, value) %pair into the
00572        *  %unordered_map. An %unordered_map relies on unique keys and thus a
00573        *  %pair is only inserted if its first element (the key) is not already
00574        *  present in the %unordered_map.
00575        *
00576        *  Insertion requires amortized constant time.
00577        */
00578       std::pair<iterator, bool>
00579       insert(const value_type& __x)
00580       { return _M_h.insert(__x); }
00581 
00582       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00583       // 2354. Unnecessary copying when inserting into maps with braced-init
00584       std::pair<iterator, bool>
00585       insert(value_type&& __x)
00586       { return _M_h.insert(std::move(__x)); }
00587 
00588       template<typename _Pair, typename = typename
00589                std::enable_if<std::is_constructible<value_type,
00590                                                     _Pair&&>::value>::type>
00591         std::pair<iterator, bool>
00592         insert(_Pair&& __x)
00593         { return _M_h.insert(std::forward<_Pair>(__x)); }
00594       //@}
00595 
00596       //@{
00597       /**
00598        *  @brief Attempts to insert a std::pair into the %unordered_map.
00599        *  @param  __hint  An iterator that serves as a hint as to where the
00600        *                 pair should be inserted.
00601        *  @param  __x  Pair to be inserted (see std::make_pair for easy creation
00602        *               of pairs).
00603        *  @return An iterator that points to the element with key of
00604        *           @a __x (may or may not be the %pair passed in).
00605        *
00606        *  This function is not concerned about whether the insertion took place,
00607        *  and thus does not return a boolean like the single-argument insert()
00608        *  does.  Note that the first parameter is only a hint and can
00609        *  potentially improve the performance of the insertion process.  A bad
00610        *  hint would cause no gains in efficiency.
00611        *
00612        *  See
00613        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
00614        *  for more on @a hinting.
00615        *
00616        *  Insertion requires amortized constant time.
00617        */
00618       iterator
00619       insert(const_iterator __hint, const value_type& __x)
00620       { return _M_h.insert(__hint, __x); }
00621 
00622       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00623       // 2354. Unnecessary copying when inserting into maps with braced-init
00624       iterator
00625       insert(const_iterator __hint, value_type&& __x)
00626       { return _M_h.insert(__hint, std::move(__x)); }
00627 
00628       template<typename _Pair, typename = typename
00629                std::enable_if<std::is_constructible<value_type,
00630                                                     _Pair&&>::value>::type>
00631         iterator
00632         insert(const_iterator __hint, _Pair&& __x)
00633         { return _M_h.insert(__hint, std::forward<_Pair>(__x)); }
00634       //@}
00635 
00636       /**
00637        *  @brief A template function that attempts to insert a range of
00638        *  elements.
00639        *  @param  __first  Iterator pointing to the start of the range to be
00640        *                   inserted.
00641        *  @param  __last  Iterator pointing to the end of the range.
00642        *
00643        *  Complexity similar to that of the range constructor.
00644        */
00645       template<typename _InputIterator>
00646         void
00647         insert(_InputIterator __first, _InputIterator __last)
00648         { _M_h.insert(__first, __last); }
00649 
00650       /**
00651        *  @brief Attempts to insert a list of elements into the %unordered_map.
00652        *  @param  __l  A std::initializer_list<value_type> of elements
00653        *               to be inserted.
00654        *
00655        *  Complexity similar to that of the range constructor.
00656        */
00657       void
00658       insert(initializer_list<value_type> __l)
00659       { _M_h.insert(__l); }
00660 
00661 
00662 #if __cplusplus > 201402L
00663 #define __cpp_lib_unordered_map_insertion 201411
00664       /**
00665        *  @brief Attempts to insert a std::pair into the %unordered_map.
00666        *  @param __k    Key to use for finding a possibly existing pair in
00667        *                the map.
00668        *  @param __obj  Argument used to generate the .second for a pair 
00669        *                instance.
00670        *
00671        *  @return  A pair, of which the first element is an iterator that 
00672        *           points to the possibly inserted pair, and the second is 
00673        *           a bool that is true if the pair was actually inserted.
00674        *
00675        *  This function attempts to insert a (key, value) %pair into the
00676        *  %unordered_map. An %unordered_map relies on unique keys and thus a
00677        *  %pair is only inserted if its first element (the key) is not already
00678        *  present in the %unordered_map.
00679        *  If the %pair was already in the %unordered_map, the .second of 
00680        *  the %pair is assigned from __obj.
00681        *
00682        *  Insertion requires amortized constant time.
00683        */
00684       template <typename _Obj>
00685         pair<iterator, bool>
00686         insert_or_assign(const key_type& __k, _Obj&& __obj)
00687         {
00688           iterator __i = find(__k);
00689           if (__i == end())
00690             {
00691               __i = emplace(std::piecewise_construct,
00692                             std::forward_as_tuple(__k),
00693                             std::forward_as_tuple(std::forward<_Obj>(__obj)))
00694                 .first;
00695               return {__i, true};
00696             }
00697           (*__i).second = std::forward<_Obj>(__obj);
00698           return {__i, false};
00699         }
00700 
00701       // move-capable overload
00702       template <typename _Obj>
00703         pair<iterator, bool>
00704         insert_or_assign(key_type&& __k, _Obj&& __obj)
00705         {
00706           iterator __i = find(__k);
00707           if (__i == end())
00708             {
00709               __i = emplace(std::piecewise_construct,
00710                             std::forward_as_tuple(std::move(__k)),
00711                             std::forward_as_tuple(std::forward<_Obj>(__obj)))
00712                 .first;
00713               return {__i, true};
00714             }
00715           (*__i).second = std::forward<_Obj>(__obj);
00716           return {__i, false};
00717         }
00718 
00719       /**
00720        *  @brief Attempts to insert a std::pair into the %unordered_map.
00721        *  @param  __hint  An iterator that serves as a hint as to where the
00722        *                  pair should be inserted.
00723        *  @param __k    Key to use for finding a possibly existing pair in
00724        *                the unordered_map.
00725        *  @param __obj  Argument used to generate the .second for a pair 
00726        *                instance.
00727        *  @return An iterator that points to the element with key of
00728        *           @a __x (may or may not be the %pair passed in).
00729        *
00730        *  This function is not concerned about whether the insertion took place,
00731        *  and thus does not return a boolean like the single-argument insert()
00732        *  does.         
00733        *  If the %pair was already in the %unordered map, the .second of
00734        *  the %pair is assigned from __obj.
00735        *  Note that the first parameter is only a hint and can
00736        *  potentially improve the performance of the insertion process.  A bad
00737        *  hint would cause no gains in efficiency.
00738        *
00739        *  See
00740        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
00741        *  for more on @a hinting.
00742        *
00743        *  Insertion requires amortized constant time.
00744        */
00745       template <typename _Obj>
00746         iterator
00747         insert_or_assign(const_iterator __hint, const key_type& __k,
00748                          _Obj&& __obj)
00749         {
00750           iterator __i = find(__k);
00751           if (__i == end())
00752             {
00753               return emplace_hint(__hint, std::piecewise_construct,
00754                                   std::forward_as_tuple(__k),
00755                                   std::forward_as_tuple(
00756                                     std::forward<_Obj>(__obj)));
00757             }
00758           (*__i).second = std::forward<_Obj>(__obj);
00759           return __i;
00760         }
00761 
00762       // move-capable overload
00763       template <typename _Obj>
00764         iterator
00765         insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
00766         {
00767           iterator __i = find(__k);
00768           if (__i == end())
00769             {
00770               return emplace_hint(__hint, std::piecewise_construct,
00771                                   std::forward_as_tuple(std::move(__k)),
00772                                   std::forward_as_tuple(
00773                                     std::forward<_Obj>(__obj)));
00774             }
00775           (*__i).second = std::forward<_Obj>(__obj);
00776           return __i;
00777         }
00778 #endif
00779 
00780       //@{
00781       /**
00782        *  @brief Erases an element from an %unordered_map.
00783        *  @param  __position  An iterator pointing to the element to be erased.
00784        *  @return An iterator pointing to the element immediately following
00785        *          @a __position prior to the element being erased. If no such
00786        *          element exists, end() is returned.
00787        *
00788        *  This function erases an element, pointed to by the given iterator,
00789        *  from an %unordered_map.
00790        *  Note that this function only erases the element, and that if the
00791        *  element is itself a pointer, the pointed-to memory is not touched in
00792        *  any way.  Managing the pointer is the user's responsibility.
00793        */
00794       iterator
00795       erase(const_iterator __position)
00796       { return _M_h.erase(__position); }
00797 
00798       // LWG 2059.
00799       iterator
00800       erase(iterator __position)
00801       { return _M_h.erase(__position); }
00802       //@}
00803 
00804       /**
00805        *  @brief Erases elements according to the provided key.
00806        *  @param  __x  Key of element to be erased.
00807        *  @return  The number of elements erased.
00808        *
00809        *  This function erases all the elements located by the given key from
00810        *  an %unordered_map. For an %unordered_map the result of this function
00811        *  can only be 0 (not present) or 1 (present).
00812        *  Note that this function only erases the element, and that if the
00813        *  element is itself a pointer, the pointed-to memory is not touched in
00814        *  any way.  Managing the pointer is the user's responsibility.
00815        */
00816       size_type
00817       erase(const key_type& __x)
00818       { return _M_h.erase(__x); }
00819 
00820       /**
00821        *  @brief Erases a [__first,__last) range of elements from an
00822        *  %unordered_map.
00823        *  @param  __first  Iterator pointing to the start of the range to be
00824        *                  erased.
00825        *  @param __last  Iterator pointing to the end of the range to
00826        *                be erased.
00827        *  @return The iterator @a __last.
00828        *
00829        *  This function erases a sequence of elements from an %unordered_map.
00830        *  Note that this function only erases the elements, and that if
00831        *  the element is itself a pointer, the pointed-to memory is not touched
00832        *  in any way.  Managing the pointer is the user's responsibility.
00833        */
00834       iterator
00835       erase(const_iterator __first, const_iterator __last)
00836       { return _M_h.erase(__first, __last); }
00837 
00838       /**
00839        *  Erases all elements in an %unordered_map.
00840        *  Note that this function only erases the elements, and that if the
00841        *  elements themselves are pointers, the pointed-to memory is not touched
00842        *  in any way.  Managing the pointer is the user's responsibility.
00843        */
00844       void
00845       clear() noexcept
00846       { _M_h.clear(); }
00847 
00848       /**
00849        *  @brief  Swaps data with another %unordered_map.
00850        *  @param  __x  An %unordered_map of the same element and allocator
00851        *  types.
00852        *
00853        *  This exchanges the elements between two %unordered_map in constant
00854        *  time.
00855        *  Note that the global std::swap() function is specialized such that
00856        *  std::swap(m1,m2) will feed to this function.
00857        */
00858       void
00859       swap(unordered_map& __x)
00860       noexcept( noexcept(_M_h.swap(__x._M_h)) )
00861       { _M_h.swap(__x._M_h); }
00862 
00863 #if __cplusplus > 201402L
00864       template<typename, typename, typename>
00865         friend class std::_Hash_merge_helper;
00866 
00867       template<typename _H2, typename _P2>
00868         void
00869         merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
00870         {
00871           using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
00872           _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
00873         }
00874 
00875       template<typename _H2, typename _P2>
00876         void
00877         merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
00878         { merge(__source); }
00879 
00880       template<typename _H2, typename _P2>
00881         void
00882         merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
00883         {
00884           using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
00885           _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
00886         }
00887 
00888       template<typename _H2, typename _P2>
00889         void
00890         merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
00891         { merge(__source); }
00892 #endif // C++17
00893 
00894       // observers.
00895 
00896       ///  Returns the hash functor object with which the %unordered_map was
00897       ///  constructed.
00898       hasher
00899       hash_function() const
00900       { return _M_h.hash_function(); }
00901 
00902       ///  Returns the key comparison object with which the %unordered_map was
00903       ///  constructed.
00904       key_equal
00905       key_eq() const
00906       { return _M_h.key_eq(); }
00907 
00908       // lookup.
00909 
00910       //@{
00911       /**
00912        *  @brief Tries to locate an element in an %unordered_map.
00913        *  @param  __x  Key to be located.
00914        *  @return  Iterator pointing to sought-after element, or end() if not
00915        *           found.
00916        *
00917        *  This function takes a key and tries to locate the element with which
00918        *  the key matches.  If successful the function returns an iterator
00919        *  pointing to the sought after element.  If unsuccessful it returns the
00920        *  past-the-end ( @c end() ) iterator.
00921        */
00922       iterator
00923       find(const key_type& __x)
00924       { return _M_h.find(__x); }
00925 
00926       const_iterator
00927       find(const key_type& __x) const
00928       { return _M_h.find(__x); }
00929       //@}
00930 
00931       /**
00932        *  @brief  Finds the number of elements.
00933        *  @param  __x  Key to count.
00934        *  @return  Number of elements with specified key.
00935        *
00936        *  This function only makes sense for %unordered_multimap; for
00937        *  %unordered_map the result will either be 0 (not present) or 1
00938        *  (present).
00939        */
00940       size_type
00941       count(const key_type& __x) const
00942       { return _M_h.count(__x); }
00943 
00944       //@{
00945       /**
00946        *  @brief Finds a subsequence matching given key.
00947        *  @param  __x  Key to be located.
00948        *  @return  Pair of iterators that possibly points to the subsequence
00949        *           matching given key.
00950        *
00951        *  This function probably only makes sense for %unordered_multimap.
00952        */
00953       std::pair<iterator, iterator>
00954       equal_range(const key_type& __x)
00955       { return _M_h.equal_range(__x); }
00956 
00957       std::pair<const_iterator, const_iterator>
00958       equal_range(const key_type& __x) const
00959       { return _M_h.equal_range(__x); }
00960       //@}
00961 
00962       //@{
00963       /**
00964        *  @brief  Subscript ( @c [] ) access to %unordered_map data.
00965        *  @param  __k  The key for which data should be retrieved.
00966        *  @return  A reference to the data of the (key,data) %pair.
00967        *
00968        *  Allows for easy lookup with the subscript ( @c [] )operator.  Returns
00969        *  data associated with the key specified in subscript.  If the key does
00970        *  not exist, a pair with that key is created using default values, which
00971        *  is then returned.
00972        *
00973        *  Lookup requires constant time.
00974        */
00975       mapped_type&
00976       operator[](const key_type& __k)
00977       { return _M_h[__k]; }
00978 
00979       mapped_type&
00980       operator[](key_type&& __k)
00981       { return _M_h[std::move(__k)]; }
00982       //@}
00983 
00984       //@{
00985       /**
00986        *  @brief  Access to %unordered_map data.
00987        *  @param  __k  The key for which data should be retrieved.
00988        *  @return  A reference to the data whose key is equal to @a __k, if
00989        *           such a data is present in the %unordered_map.
00990        *  @throw  std::out_of_range  If no such data is present.
00991        */
00992       mapped_type&
00993       at(const key_type& __k)
00994       { return _M_h.at(__k); }
00995 
00996       const mapped_type&
00997       at(const key_type& __k) const
00998       { return _M_h.at(__k); }
00999       //@}
01000 
01001       // bucket interface.
01002 
01003       /// Returns the number of buckets of the %unordered_map.
01004       size_type
01005       bucket_count() const noexcept
01006       { return _M_h.bucket_count(); }
01007 
01008       /// Returns the maximum number of buckets of the %unordered_map.
01009       size_type
01010       max_bucket_count() const noexcept
01011       { return _M_h.max_bucket_count(); }
01012 
01013       /*
01014        * @brief  Returns the number of elements in a given bucket.
01015        * @param  __n  A bucket index.
01016        * @return  The number of elements in the bucket.
01017        */
01018       size_type
01019       bucket_size(size_type __n) const
01020       { return _M_h.bucket_size(__n); }
01021 
01022       /*
01023        * @brief  Returns the bucket index of a given element.
01024        * @param  __key  A key instance.
01025        * @return  The key bucket index.
01026        */
01027       size_type
01028       bucket(const key_type& __key) const
01029       { return _M_h.bucket(__key); }
01030       
01031       /**
01032        *  @brief  Returns a read/write iterator pointing to the first bucket
01033        *         element.
01034        *  @param  __n The bucket index.
01035        *  @return  A read/write local iterator.
01036        */
01037       local_iterator
01038       begin(size_type __n)
01039       { return _M_h.begin(__n); }
01040 
01041       //@{
01042       /**
01043        *  @brief  Returns a read-only (constant) iterator pointing to the first
01044        *         bucket element.
01045        *  @param  __n The bucket index.
01046        *  @return  A read-only local iterator.
01047        */
01048       const_local_iterator
01049       begin(size_type __n) const
01050       { return _M_h.begin(__n); }
01051 
01052       const_local_iterator
01053       cbegin(size_type __n) const
01054       { return _M_h.cbegin(__n); }
01055       //@}
01056 
01057       /**
01058        *  @brief  Returns a read/write iterator pointing to one past the last
01059        *         bucket elements.
01060        *  @param  __n The bucket index.
01061        *  @return  A read/write local iterator.
01062        */
01063       local_iterator
01064       end(size_type __n)
01065       { return _M_h.end(__n); }
01066 
01067       //@{
01068       /**
01069        *  @brief  Returns a read-only (constant) iterator pointing to one past
01070        *         the last bucket elements.
01071        *  @param  __n The bucket index.
01072        *  @return  A read-only local iterator.
01073        */
01074       const_local_iterator
01075       end(size_type __n) const
01076       { return _M_h.end(__n); }
01077 
01078       const_local_iterator
01079       cend(size_type __n) const
01080       { return _M_h.cend(__n); }
01081       //@}
01082 
01083       // hash policy.
01084 
01085       /// Returns the average number of elements per bucket.
01086       float
01087       load_factor() const noexcept
01088       { return _M_h.load_factor(); }
01089 
01090       /// Returns a positive number that the %unordered_map tries to keep the
01091       /// load factor less than or equal to.
01092       float
01093       max_load_factor() const noexcept
01094       { return _M_h.max_load_factor(); }
01095 
01096       /**
01097        *  @brief  Change the %unordered_map maximum load factor.
01098        *  @param  __z The new maximum load factor.
01099        */
01100       void
01101       max_load_factor(float __z)
01102       { _M_h.max_load_factor(__z); }
01103 
01104       /**
01105        *  @brief  May rehash the %unordered_map.
01106        *  @param  __n The new number of buckets.
01107        *
01108        *  Rehash will occur only if the new number of buckets respect the
01109        *  %unordered_map maximum load factor.
01110        */
01111       void
01112       rehash(size_type __n)
01113       { _M_h.rehash(__n); }
01114 
01115       /**
01116        *  @brief  Prepare the %unordered_map for a specified number of
01117        *          elements.
01118        *  @param  __n Number of elements required.
01119        *
01120        *  Same as rehash(ceil(n / max_load_factor())).
01121        */
01122       void
01123       reserve(size_type __n)
01124       { _M_h.reserve(__n); }
01125 
01126       template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
01127                typename _Alloc1>
01128         friend bool
01129         operator==(const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&,
01130                    const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&);
01131     };
01132 
01133 #if __cpp_deduction_guides >= 201606
01134 
01135   template<typename _InputIterator,
01136            typename _Hash = hash<__iter_key_t<_InputIterator>>,
01137            typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
01138            typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
01139            typename = _RequireInputIter<_InputIterator>,
01140            typename = _RequireAllocator<_Allocator>>
01141     unordered_map(_InputIterator, _InputIterator,
01142                   typename unordered_map<int, int>::size_type = {},
01143                   _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
01144     -> unordered_map<__iter_key_t<_InputIterator>,
01145                      __iter_val_t<_InputIterator>,
01146                      _Hash, _Pred, _Allocator>;
01147 
01148   template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
01149            typename _Pred = equal_to<_Key>,
01150            typename _Allocator = allocator<pair<const _Key, _Tp>>,
01151            typename = _RequireAllocator<_Allocator>>
01152     unordered_map(initializer_list<pair<_Key, _Tp>>,
01153                   typename unordered_map<int, int>::size_type = {},
01154                   _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
01155     -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
01156 
01157   template<typename _InputIterator, typename _Allocator,
01158            typename = _RequireInputIter<_InputIterator>,
01159            typename = _RequireAllocator<_Allocator>>
01160     unordered_map(_InputIterator, _InputIterator,
01161                   typename unordered_map<int, int>::size_type, _Allocator)
01162     -> unordered_map<__iter_key_t<_InputIterator>,
01163                      __iter_val_t<_InputIterator>,
01164                      hash<__iter_key_t<_InputIterator>>,
01165                      equal_to<__iter_key_t<_InputIterator>>,
01166                      _Allocator>;
01167 
01168   template<typename _InputIterator, typename _Allocator,
01169            typename = _RequireInputIter<_InputIterator>,
01170            typename = _RequireAllocator<_Allocator>>
01171     unordered_map(_InputIterator, _InputIterator, _Allocator)
01172     -> unordered_map<__iter_key_t<_InputIterator>,
01173                      __iter_val_t<_InputIterator>,
01174                      hash<__iter_key_t<_InputIterator>>,
01175                      equal_to<__iter_key_t<_InputIterator>>,
01176                      _Allocator>;
01177 
01178   template<typename _InputIterator, typename _Hash, typename _Allocator,
01179            typename = _RequireInputIter<_InputIterator>,
01180            typename = _RequireAllocator<_Allocator>>
01181     unordered_map(_InputIterator, _InputIterator,
01182                   typename unordered_map<int, int>::size_type,
01183                   _Hash, _Allocator)
01184     -> unordered_map<__iter_key_t<_InputIterator>,
01185                      __iter_val_t<_InputIterator>, _Hash,
01186                      equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
01187 
01188   template<typename _Key, typename _Tp, typename _Allocator,
01189            typename = _RequireAllocator<_Allocator>>
01190     unordered_map(initializer_list<pair<_Key, _Tp>>,
01191                   typename unordered_map<int, int>::size_type,
01192                   _Allocator)
01193     -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
01194 
01195   template<typename _Key, typename _Tp, typename _Allocator,
01196            typename = _RequireAllocator<_Allocator>>
01197     unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
01198     -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
01199 
01200   template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
01201            typename = _RequireAllocator<_Allocator>>
01202     unordered_map(initializer_list<pair<_Key, _Tp>>,
01203                   typename unordered_map<int, int>::size_type,
01204                   _Hash, _Allocator)
01205     -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
01206 
01207 #endif
01208 
01209   /**
01210    *  @brief A standard container composed of equivalent keys
01211    *  (possibly containing multiple of each key value) that associates
01212    *  values of another type with the keys.
01213    *
01214    *  @ingroup unordered_associative_containers
01215    *
01216    *  @tparam  _Key    Type of key objects.
01217    *  @tparam  _Tp     Type of mapped objects.
01218    *  @tparam  _Hash   Hashing function object type, defaults to hash<_Value>.
01219    *  @tparam  _Pred   Predicate function object type, defaults
01220    *                   to equal_to<_Value>.
01221    *  @tparam  _Alloc  Allocator type, defaults to
01222    *                   std::allocator<std::pair<const _Key, _Tp>>.
01223    *
01224    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
01225    *  <a href="tables.html#xx">unordered associative container</a>
01226    *
01227    * The resulting value type of the container is std::pair<const _Key, _Tp>.
01228    *
01229    *  Base is _Hashtable, dispatched at compile time via template
01230    *  alias __ummap_hashtable.
01231    */
01232   template<typename _Key, typename _Tp,
01233            typename _Hash = hash<_Key>,
01234            typename _Pred = equal_to<_Key>,
01235            typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
01236     class unordered_multimap
01237     {
01238       typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
01239       _Hashtable _M_h;
01240 
01241     public:
01242       // typedefs:
01243       //@{
01244       /// Public typedefs.
01245       typedef typename _Hashtable::key_type     key_type;
01246       typedef typename _Hashtable::value_type   value_type;
01247       typedef typename _Hashtable::mapped_type  mapped_type;
01248       typedef typename _Hashtable::hasher       hasher;
01249       typedef typename _Hashtable::key_equal    key_equal;
01250       typedef typename _Hashtable::allocator_type allocator_type;
01251       //@}
01252 
01253       //@{
01254       ///  Iterator-related typedefs.
01255       typedef typename _Hashtable::pointer              pointer;
01256       typedef typename _Hashtable::const_pointer        const_pointer;
01257       typedef typename _Hashtable::reference            reference;
01258       typedef typename _Hashtable::const_reference      const_reference;
01259       typedef typename _Hashtable::iterator             iterator;
01260       typedef typename _Hashtable::const_iterator       const_iterator;
01261       typedef typename _Hashtable::local_iterator       local_iterator;
01262       typedef typename _Hashtable::const_local_iterator const_local_iterator;
01263       typedef typename _Hashtable::size_type            size_type;
01264       typedef typename _Hashtable::difference_type      difference_type;
01265       //@}
01266 
01267 #if __cplusplus > 201402L
01268       using node_type = typename _Hashtable::node_type;
01269 #endif
01270 
01271       //construct/destroy/copy
01272 
01273       /// Default constructor.
01274       unordered_multimap() = default;
01275 
01276       /**
01277        *  @brief  Default constructor creates no elements.
01278        *  @param __n  Mnimal initial number of buckets.
01279        *  @param __hf  A hash functor.
01280        *  @param __eql  A key equality functor.
01281        *  @param __a  An allocator object.
01282        */
01283       explicit
01284       unordered_multimap(size_type __n,
01285                          const hasher& __hf = hasher(),
01286                          const key_equal& __eql = key_equal(),
01287                          const allocator_type& __a = allocator_type())
01288       : _M_h(__n, __hf, __eql, __a)
01289       { }
01290 
01291       /**
01292        *  @brief  Builds an %unordered_multimap from a range.
01293        *  @param  __first An input iterator.
01294        *  @param  __last  An input iterator.
01295        *  @param __n      Minimal initial number of buckets.
01296        *  @param __hf     A hash functor.
01297        *  @param __eql    A key equality functor.
01298        *  @param __a      An allocator object.
01299        *
01300        *  Create an %unordered_multimap consisting of copies of the elements
01301        *  from [__first,__last).  This is linear in N (where N is
01302        *  distance(__first,__last)).
01303        */
01304       template<typename _InputIterator>
01305         unordered_multimap(_InputIterator __first, _InputIterator __last,
01306                            size_type __n = 0,
01307                            const hasher& __hf = hasher(),
01308                            const key_equal& __eql = key_equal(),
01309                            const allocator_type& __a = allocator_type())
01310         : _M_h(__first, __last, __n, __hf, __eql, __a)
01311         { }
01312 
01313       /// Copy constructor.
01314       unordered_multimap(const unordered_multimap&) = default;
01315 
01316       /// Move constructor.
01317       unordered_multimap(unordered_multimap&&) = default;
01318 
01319       /**
01320        *  @brief Creates an %unordered_multimap with no elements.
01321        *  @param __a An allocator object.
01322        */
01323       explicit
01324       unordered_multimap(const allocator_type& __a)
01325       : _M_h(__a)
01326       { }
01327 
01328       /*
01329        *  @brief Copy constructor with allocator argument.
01330        * @param  __uset  Input %unordered_multimap to copy.
01331        * @param  __a  An allocator object.
01332        */
01333       unordered_multimap(const unordered_multimap& __ummap,
01334                          const allocator_type& __a)
01335       : _M_h(__ummap._M_h, __a)
01336       { }
01337 
01338       /*
01339        *  @brief  Move constructor with allocator argument.
01340        *  @param  __uset Input %unordered_multimap to move.
01341        *  @param  __a    An allocator object.
01342        */
01343       unordered_multimap(unordered_multimap&& __ummap,
01344                          const allocator_type& __a)
01345       : _M_h(std::move(__ummap._M_h), __a)
01346       { }
01347 
01348       /**
01349        *  @brief  Builds an %unordered_multimap from an initializer_list.
01350        *  @param  __l  An initializer_list.
01351        *  @param __n  Minimal initial number of buckets.
01352        *  @param __hf  A hash functor.
01353        *  @param __eql  A key equality functor.
01354        *  @param  __a  An allocator object.
01355        *
01356        *  Create an %unordered_multimap consisting of copies of the elements in
01357        *  the list. This is linear in N (where N is @a __l.size()).
01358        */
01359       unordered_multimap(initializer_list<value_type> __l,
01360                          size_type __n = 0,
01361                          const hasher& __hf = hasher(),
01362                          const key_equal& __eql = key_equal(),
01363                          const allocator_type& __a = allocator_type())
01364       : _M_h(__l, __n, __hf, __eql, __a)
01365       { }
01366 
01367       unordered_multimap(size_type __n, const allocator_type& __a)
01368       : unordered_multimap(__n, hasher(), key_equal(), __a)
01369       { }
01370 
01371       unordered_multimap(size_type __n, const hasher& __hf,
01372                          const allocator_type& __a)
01373       : unordered_multimap(__n, __hf, key_equal(), __a)
01374       { }
01375 
01376       template<typename _InputIterator>
01377         unordered_multimap(_InputIterator __first, _InputIterator __last,
01378                            size_type __n,
01379                            const allocator_type& __a)
01380         : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
01381         { }
01382 
01383       template<typename _InputIterator>
01384         unordered_multimap(_InputIterator __first, _InputIterator __last,
01385                            size_type __n, const hasher& __hf,
01386                            const allocator_type& __a)
01387         : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
01388         { }
01389 
01390       unordered_multimap(initializer_list<value_type> __l,
01391                          size_type __n,
01392                          const allocator_type& __a)
01393       : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
01394       { }
01395 
01396       unordered_multimap(initializer_list<value_type> __l,
01397                          size_type __n, const hasher& __hf,
01398                          const allocator_type& __a)
01399       : unordered_multimap(__l, __n, __hf, key_equal(), __a)
01400       { }
01401 
01402       /// Copy assignment operator.
01403       unordered_multimap&
01404       operator=(const unordered_multimap&) = default;
01405 
01406       /// Move assignment operator.
01407       unordered_multimap&
01408       operator=(unordered_multimap&&) = default;
01409 
01410       /**
01411        *  @brief  %Unordered_multimap list assignment operator.
01412        *  @param  __l  An initializer_list.
01413        *
01414        *  This function fills an %unordered_multimap with copies of the
01415        *  elements in the initializer list @a __l.
01416        *
01417        *  Note that the assignment completely changes the %unordered_multimap
01418        *  and that the resulting %unordered_multimap's size is the same as the
01419        *  number of elements assigned.
01420        */
01421       unordered_multimap&
01422       operator=(initializer_list<value_type> __l)
01423       {
01424         _M_h = __l;
01425         return *this;
01426       }
01427 
01428       ///  Returns the allocator object used by the %unordered_multimap.
01429       allocator_type
01430       get_allocator() const noexcept
01431       { return _M_h.get_allocator(); }
01432 
01433       // size and capacity:
01434 
01435       ///  Returns true if the %unordered_multimap is empty.
01436       bool
01437       empty() const noexcept
01438       { return _M_h.empty(); }
01439 
01440       ///  Returns the size of the %unordered_multimap.
01441       size_type
01442       size() const noexcept
01443       { return _M_h.size(); }
01444 
01445       ///  Returns the maximum size of the %unordered_multimap.
01446       size_type
01447       max_size() const noexcept
01448       { return _M_h.max_size(); }
01449 
01450       // iterators.
01451 
01452       /**
01453        *  Returns a read/write iterator that points to the first element in the
01454        *  %unordered_multimap.
01455        */
01456       iterator
01457       begin() noexcept
01458       { return _M_h.begin(); }
01459 
01460       //@{
01461       /**
01462        *  Returns a read-only (constant) iterator that points to the first
01463        *  element in the %unordered_multimap.
01464        */
01465       const_iterator
01466       begin() const noexcept
01467       { return _M_h.begin(); }
01468 
01469       const_iterator
01470       cbegin() const noexcept
01471       { return _M_h.begin(); }
01472       //@}
01473 
01474       /**
01475        *  Returns a read/write iterator that points one past the last element in
01476        *  the %unordered_multimap.
01477        */
01478       iterator
01479       end() noexcept
01480       { return _M_h.end(); }
01481 
01482       //@{
01483       /**
01484        *  Returns a read-only (constant) iterator that points one past the last
01485        *  element in the %unordered_multimap.
01486        */
01487       const_iterator
01488       end() const noexcept
01489       { return _M_h.end(); }
01490 
01491       const_iterator
01492       cend() const noexcept
01493       { return _M_h.end(); }
01494       //@}
01495 
01496       // modifiers.
01497 
01498       /**
01499        *  @brief Attempts to build and insert a std::pair into the
01500        *  %unordered_multimap.
01501        *
01502        *  @param __args  Arguments used to generate a new pair instance (see
01503        *                std::piecewise_contruct for passing arguments to each
01504        *                part of the pair constructor).
01505        *
01506        *  @return  An iterator that points to the inserted pair.
01507        *
01508        *  This function attempts to build and insert a (key, value) %pair into
01509        *  the %unordered_multimap.
01510        *
01511        *  Insertion requires amortized constant time.
01512        */
01513       template<typename... _Args>
01514         iterator
01515         emplace(_Args&&... __args)
01516         { return _M_h.emplace(std::forward<_Args>(__args)...); }
01517 
01518       /**
01519        *  @brief Attempts to build and insert a std::pair into the
01520        *  %unordered_multimap.
01521        *
01522        *  @param  __pos  An iterator that serves as a hint as to where the pair
01523        *                should be inserted.
01524        *  @param  __args  Arguments used to generate a new pair instance (see
01525        *                 std::piecewise_contruct for passing arguments to each
01526        *                 part of the pair constructor).
01527        *  @return An iterator that points to the element with key of the
01528        *          std::pair built from @a __args.
01529        *
01530        *  Note that the first parameter is only a hint and can potentially
01531        *  improve the performance of the insertion process. A bad hint would
01532        *  cause no gains in efficiency.
01533        *
01534        *  See
01535        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
01536        *  for more on @a hinting.
01537        *
01538        *  Insertion requires amortized constant time.
01539        */
01540       template<typename... _Args>
01541         iterator
01542         emplace_hint(const_iterator __pos, _Args&&... __args)
01543         { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
01544 
01545       //@{
01546       /**
01547        *  @brief Inserts a std::pair into the %unordered_multimap.
01548        *  @param __x Pair to be inserted (see std::make_pair for easy
01549        *             creation of pairs).
01550        *
01551        *  @return  An iterator that points to the inserted pair.
01552        *
01553        *  Insertion requires amortized constant time.
01554        */
01555       iterator
01556       insert(const value_type& __x)
01557       { return _M_h.insert(__x); }
01558 
01559       iterator
01560       insert(value_type&& __x)
01561       { return _M_h.insert(std::move(__x)); }
01562 
01563       template<typename _Pair, typename = typename
01564                std::enable_if<std::is_constructible<value_type,
01565                                                     _Pair&&>::value>::type>
01566         iterator
01567         insert(_Pair&& __x)
01568         { return _M_h.insert(std::forward<_Pair>(__x)); }
01569       //@}
01570 
01571       //@{
01572       /**
01573        *  @brief Inserts a std::pair into the %unordered_multimap.
01574        *  @param  __hint  An iterator that serves as a hint as to where the
01575        *                 pair should be inserted.
01576        *  @param  __x  Pair to be inserted (see std::make_pair for easy creation
01577        *               of pairs).
01578        *  @return An iterator that points to the element with key of
01579        *           @a __x (may or may not be the %pair passed in).
01580        *
01581        *  Note that the first parameter is only a hint and can potentially
01582        *  improve the performance of the insertion process.  A bad hint would
01583        *  cause no gains in efficiency.
01584        *
01585        *  See
01586        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
01587        *  for more on @a hinting.
01588        *
01589        *  Insertion requires amortized constant time.
01590        */
01591       iterator
01592       insert(const_iterator __hint, const value_type& __x)
01593       { return _M_h.insert(__hint, __x); }
01594 
01595       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01596       // 2354. Unnecessary copying when inserting into maps with braced-init
01597       iterator
01598       insert(const_iterator __hint, value_type&& __x)
01599       { return _M_h.insert(__hint, std::move(__x)); }
01600 
01601       template<typename _Pair, typename = typename
01602                std::enable_if<std::is_constructible<value_type,
01603                                                     _Pair&&>::value>::type>
01604         iterator
01605         insert(const_iterator __hint, _Pair&& __x)
01606         { return _M_h.insert(__hint, std::forward<_Pair>(__x)); }
01607       //@}
01608 
01609       /**
01610        *  @brief A template function that attempts to insert a range of
01611        *  elements.
01612        *  @param  __first  Iterator pointing to the start of the range to be
01613        *                   inserted.
01614        *  @param  __last  Iterator pointing to the end of the range.
01615        *
01616        *  Complexity similar to that of the range constructor.
01617        */
01618       template<typename _InputIterator>
01619         void
01620         insert(_InputIterator __first, _InputIterator __last)
01621         { _M_h.insert(__first, __last); }
01622 
01623       /**
01624        *  @brief Attempts to insert a list of elements into the
01625        *  %unordered_multimap.
01626        *  @param  __l  A std::initializer_list<value_type> of elements
01627        *               to be inserted.
01628        *
01629        *  Complexity similar to that of the range constructor.
01630        */
01631       void
01632       insert(initializer_list<value_type> __l)
01633       { _M_h.insert(__l); }
01634 
01635 #if __cplusplus > 201402L
01636       /// Extract a node.
01637       node_type
01638       extract(const_iterator __pos)
01639       {
01640         __glibcxx_assert(__pos != end());
01641         return _M_h.extract(__pos);
01642       }
01643 
01644       /// Extract a node.
01645       node_type
01646       extract(const key_type& __key)
01647       { return _M_h.extract(__key); }
01648 
01649       /// Re-insert an extracted node.
01650       iterator
01651       insert(node_type&& __nh)
01652       { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
01653 
01654       /// Re-insert an extracted node.
01655       iterator
01656       insert(const_iterator __hint, node_type&& __nh)
01657       { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
01658 #endif // C++17
01659 
01660       //@{
01661       /**
01662        *  @brief Erases an element from an %unordered_multimap.
01663        *  @param  __position  An iterator pointing to the element to be erased.
01664        *  @return An iterator pointing to the element immediately following
01665        *          @a __position prior to the element being erased. If no such
01666        *          element exists, end() is returned.
01667        *
01668        *  This function erases an element, pointed to by the given iterator,
01669        *  from an %unordered_multimap.
01670        *  Note that this function only erases the element, and that if the
01671        *  element is itself a pointer, the pointed-to memory is not touched in
01672        *  any way.  Managing the pointer is the user's responsibility.
01673        */
01674       iterator
01675       erase(const_iterator __position)
01676       { return _M_h.erase(__position); }
01677 
01678       // LWG 2059.
01679       iterator
01680       erase(iterator __position)
01681       { return _M_h.erase(__position); }
01682       //@}
01683 
01684       /**
01685        *  @brief Erases elements according to the provided key.
01686        *  @param  __x  Key of elements to be erased.
01687        *  @return  The number of elements erased.
01688        *
01689        *  This function erases all the elements located by the given key from
01690        *  an %unordered_multimap.
01691        *  Note that this function only erases the element, and that if the
01692        *  element is itself a pointer, the pointed-to memory is not touched in
01693        *  any way.  Managing the pointer is the user's responsibility.
01694        */
01695       size_type
01696       erase(const key_type& __x)
01697       { return _M_h.erase(__x); }
01698 
01699       /**
01700        *  @brief Erases a [__first,__last) range of elements from an
01701        *  %unordered_multimap.
01702        *  @param  __first  Iterator pointing to the start of the range to be
01703        *                  erased.
01704        *  @param __last  Iterator pointing to the end of the range to
01705        *                be erased.
01706        *  @return The iterator @a __last.
01707        *
01708        *  This function erases a sequence of elements from an
01709        *  %unordered_multimap.
01710        *  Note that this function only erases the elements, and that if
01711        *  the element is itself a pointer, the pointed-to memory is not touched
01712        *  in any way.  Managing the pointer is the user's responsibility.
01713        */
01714       iterator
01715       erase(const_iterator __first, const_iterator __last)
01716       { return _M_h.erase(__first, __last); }
01717 
01718       /**
01719        *  Erases all elements in an %unordered_multimap.
01720        *  Note that this function only erases the elements, and that if the
01721        *  elements themselves are pointers, the pointed-to memory is not touched
01722        *  in any way.  Managing the pointer is the user's responsibility.
01723        */
01724       void
01725       clear() noexcept
01726       { _M_h.clear(); }
01727 
01728       /**
01729        *  @brief  Swaps data with another %unordered_multimap.
01730        *  @param  __x  An %unordered_multimap of the same element and allocator
01731        *  types.
01732        *
01733        *  This exchanges the elements between two %unordered_multimap in
01734        *  constant time.
01735        *  Note that the global std::swap() function is specialized such that
01736        *  std::swap(m1,m2) will feed to this function.
01737        */
01738       void
01739       swap(unordered_multimap& __x)
01740       noexcept( noexcept(_M_h.swap(__x._M_h)) )
01741       { _M_h.swap(__x._M_h); }
01742 
01743 #if __cplusplus > 201402L
01744       template<typename, typename, typename>
01745         friend class std::_Hash_merge_helper;
01746 
01747       template<typename _H2, typename _P2>
01748         void
01749         merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
01750         {
01751           using _Merge_helper
01752             = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
01753           _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
01754         }
01755 
01756       template<typename _H2, typename _P2>
01757         void
01758         merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
01759         { merge(__source); }
01760 
01761       template<typename _H2, typename _P2>
01762         void
01763         merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
01764         {
01765           using _Merge_helper
01766             = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
01767           _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
01768         }
01769 
01770       template<typename _H2, typename _P2>
01771         void
01772         merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
01773         { merge(__source); }
01774 #endif // C++17
01775 
01776       // observers.
01777 
01778       ///  Returns the hash functor object with which the %unordered_multimap
01779       ///  was constructed.
01780       hasher
01781       hash_function() const
01782       { return _M_h.hash_function(); }
01783 
01784       ///  Returns the key comparison object with which the %unordered_multimap
01785       ///  was constructed.
01786       key_equal
01787       key_eq() const
01788       { return _M_h.key_eq(); }
01789 
01790       // lookup.
01791 
01792       //@{
01793       /**
01794        *  @brief Tries to locate an element in an %unordered_multimap.
01795        *  @param  __x  Key to be located.
01796        *  @return  Iterator pointing to sought-after element, or end() if not
01797        *           found.
01798        *
01799        *  This function takes a key and tries to locate the element with which
01800        *  the key matches.  If successful the function returns an iterator
01801        *  pointing to the sought after element.  If unsuccessful it returns the
01802        *  past-the-end ( @c end() ) iterator.
01803        */
01804       iterator
01805       find(const key_type& __x)
01806       { return _M_h.find(__x); }
01807 
01808       const_iterator
01809       find(const key_type& __x) const
01810       { return _M_h.find(__x); }
01811       //@}
01812 
01813       /**
01814        *  @brief  Finds the number of elements.
01815        *  @param  __x  Key to count.
01816        *  @return  Number of elements with specified key.
01817        */
01818       size_type
01819       count(const key_type& __x) const
01820       { return _M_h.count(__x); }
01821 
01822       //@{
01823       /**
01824        *  @brief Finds a subsequence matching given key.
01825        *  @param  __x  Key to be located.
01826        *  @return  Pair of iterators that possibly points to the subsequence
01827        *           matching given key.
01828        */
01829       std::pair<iterator, iterator>
01830       equal_range(const key_type& __x)
01831       { return _M_h.equal_range(__x); }
01832 
01833       std::pair<const_iterator, const_iterator>
01834       equal_range(const key_type& __x) const
01835       { return _M_h.equal_range(__x); }
01836       //@}
01837 
01838       // bucket interface.
01839 
01840       /// Returns the number of buckets of the %unordered_multimap.
01841       size_type
01842       bucket_count() const noexcept
01843       { return _M_h.bucket_count(); }
01844 
01845       /// Returns the maximum number of buckets of the %unordered_multimap.
01846       size_type
01847       max_bucket_count() const noexcept
01848       { return _M_h.max_bucket_count(); }
01849 
01850       /*
01851        * @brief  Returns the number of elements in a given bucket.
01852        * @param  __n  A bucket index.
01853        * @return  The number of elements in the bucket.
01854        */
01855       size_type
01856       bucket_size(size_type __n) const
01857       { return _M_h.bucket_size(__n); }
01858 
01859       /*
01860        * @brief  Returns the bucket index of a given element.
01861        * @param  __key  A key instance.
01862        * @return  The key bucket index.
01863        */
01864       size_type
01865       bucket(const key_type& __key) const
01866       { return _M_h.bucket(__key); }
01867       
01868       /**
01869        *  @brief  Returns a read/write iterator pointing to the first bucket
01870        *         element.
01871        *  @param  __n The bucket index.
01872        *  @return  A read/write local iterator.
01873        */
01874       local_iterator
01875       begin(size_type __n)
01876       { return _M_h.begin(__n); }
01877 
01878       //@{
01879       /**
01880        *  @brief  Returns a read-only (constant) iterator pointing to the first
01881        *         bucket element.
01882        *  @param  __n The bucket index.
01883        *  @return  A read-only local iterator.
01884        */
01885       const_local_iterator
01886       begin(size_type __n) const
01887       { return _M_h.begin(__n); }
01888 
01889       const_local_iterator
01890       cbegin(size_type __n) const
01891       { return _M_h.cbegin(__n); }
01892       //@}
01893 
01894       /**
01895        *  @brief  Returns a read/write iterator pointing to one past the last
01896        *         bucket elements.
01897        *  @param  __n The bucket index.
01898        *  @return  A read/write local iterator.
01899        */
01900       local_iterator
01901       end(size_type __n)
01902       { return _M_h.end(__n); }
01903 
01904       //@{
01905       /**
01906        *  @brief  Returns a read-only (constant) iterator pointing to one past
01907        *         the last bucket elements.
01908        *  @param  __n The bucket index.
01909        *  @return  A read-only local iterator.
01910        */
01911       const_local_iterator
01912       end(size_type __n) const
01913       { return _M_h.end(__n); }
01914 
01915       const_local_iterator
01916       cend(size_type __n) const
01917       { return _M_h.cend(__n); }
01918       //@}
01919 
01920       // hash policy.
01921 
01922       /// Returns the average number of elements per bucket.
01923       float
01924       load_factor() const noexcept
01925       { return _M_h.load_factor(); }
01926 
01927       /// Returns a positive number that the %unordered_multimap tries to keep
01928       /// the load factor less than or equal to.
01929       float
01930       max_load_factor() const noexcept
01931       { return _M_h.max_load_factor(); }
01932 
01933       /**
01934        *  @brief  Change the %unordered_multimap maximum load factor.
01935        *  @param  __z The new maximum load factor.
01936        */
01937       void
01938       max_load_factor(float __z)
01939       { _M_h.max_load_factor(__z); }
01940 
01941       /**
01942        *  @brief  May rehash the %unordered_multimap.
01943        *  @param  __n The new number of buckets.
01944        *
01945        *  Rehash will occur only if the new number of buckets respect the
01946        *  %unordered_multimap maximum load factor.
01947        */
01948       void
01949       rehash(size_type __n)
01950       { _M_h.rehash(__n); }
01951 
01952       /**
01953        *  @brief  Prepare the %unordered_multimap for a specified number of
01954        *          elements.
01955        *  @param  __n Number of elements required.
01956        *
01957        *  Same as rehash(ceil(n / max_load_factor())).
01958        */
01959       void
01960       reserve(size_type __n)
01961       { _M_h.reserve(__n); }
01962 
01963       template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
01964                typename _Alloc1>
01965         friend bool
01966         operator==(const unordered_multimap<_Key1, _Tp1,
01967                                             _Hash1, _Pred1, _Alloc1>&,
01968                    const unordered_multimap<_Key1, _Tp1,
01969                                             _Hash1, _Pred1, _Alloc1>&);
01970     };
01971 
01972 #if __cpp_deduction_guides >= 201606
01973 
01974   template<typename _InputIterator,
01975            typename _Hash = hash<__iter_key_t<_InputIterator>>,
01976            typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
01977            typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
01978            typename = _RequireInputIter<_InputIterator>,
01979            typename = _RequireAllocator<_Allocator>>
01980     unordered_multimap(_InputIterator, _InputIterator,
01981                        unordered_multimap<int, int>::size_type = {},
01982                        _Hash = _Hash(), _Pred = _Pred(),
01983                        _Allocator = _Allocator())
01984     -> unordered_multimap<__iter_key_t<_InputIterator>,
01985                           __iter_val_t<_InputIterator>, _Hash, _Pred,
01986                           _Allocator>;
01987 
01988   template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
01989            typename _Pred = equal_to<_Key>,
01990            typename _Allocator = allocator<pair<const _Key, _Tp>>,
01991            typename = _RequireAllocator<_Allocator>>
01992     unordered_multimap(initializer_list<pair<_Key, _Tp>>,
01993                        unordered_multimap<int, int>::size_type = {},
01994                        _Hash = _Hash(), _Pred = _Pred(),
01995                        _Allocator = _Allocator())
01996     -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
01997 
01998   template<typename _InputIterator, typename _Allocator,
01999            typename = _RequireInputIter<_InputIterator>,
02000            typename = _RequireAllocator<_Allocator>>
02001     unordered_multimap(_InputIterator, _InputIterator,
02002                        unordered_multimap<int, int>::size_type, _Allocator)
02003     -> unordered_multimap<__iter_key_t<_InputIterator>,
02004                           __iter_val_t<_InputIterator>,
02005                           hash<__iter_key_t<_InputIterator>>,
02006                           equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
02007 
02008   template<typename _InputIterator, typename _Allocator,
02009            typename = _RequireInputIter<_InputIterator>,
02010            typename = _RequireAllocator<_Allocator>>
02011     unordered_multimap(_InputIterator, _InputIterator, _Allocator)
02012     -> unordered_multimap<__iter_key_t<_InputIterator>,
02013                           __iter_val_t<_InputIterator>,
02014                           hash<__iter_key_t<_InputIterator>>,
02015                           equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
02016 
02017   template<typename _InputIterator, typename _Hash, typename _Allocator,
02018            typename = _RequireInputIter<_InputIterator>,
02019            typename = _RequireAllocator<_Allocator>>
02020     unordered_multimap(_InputIterator, _InputIterator,
02021                        unordered_multimap<int, int>::size_type, _Hash,
02022                        _Allocator)
02023     -> unordered_multimap<__iter_key_t<_InputIterator>,
02024                           __iter_val_t<_InputIterator>, _Hash,
02025                           equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
02026 
02027   template<typename _Key, typename _Tp, typename _Allocator,
02028            typename = _RequireAllocator<_Allocator>>
02029     unordered_multimap(initializer_list<pair<_Key, _Tp>>,
02030                        unordered_multimap<int, int>::size_type,
02031                        _Allocator)
02032     -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
02033 
02034   template<typename _Key, typename _Tp, typename _Allocator,
02035            typename = _RequireAllocator<_Allocator>>
02036     unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
02037     -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
02038 
02039   template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
02040            typename = _RequireAllocator<_Allocator>>
02041     unordered_multimap(initializer_list<pair<_Key, _Tp>>,
02042                        unordered_multimap<int, int>::size_type,
02043                        _Hash, _Allocator)
02044     -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
02045 
02046 #endif
02047 
02048   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
02049     inline void
02050     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
02051          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
02052     noexcept(noexcept(__x.swap(__y)))
02053     { __x.swap(__y); }
02054 
02055   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
02056     inline void
02057     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
02058          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
02059     noexcept(noexcept(__x.swap(__y)))
02060     { __x.swap(__y); }
02061 
02062   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
02063     inline bool
02064     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
02065                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
02066     { return __x._M_h._M_equal(__y._M_h); }
02067 
02068   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
02069     inline bool
02070     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
02071                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
02072     { return !(__x == __y); }
02073 
02074   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
02075     inline bool
02076     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
02077                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
02078     { return __x._M_h._M_equal(__y._M_h); }
02079 
02080   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
02081     inline bool
02082     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
02083                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
02084     { return !(__x == __y); }
02085 
02086 _GLIBCXX_END_NAMESPACE_CONTAINER
02087 
02088 #if __cplusplus > 201402L
02089   // Allow std::unordered_map access to internals of compatible maps.
02090   template<typename _Key, typename _Val, typename _Hash1, typename _Eq1,
02091            typename _Alloc, typename _Hash2, typename _Eq2>
02092     struct _Hash_merge_helper<
02093       _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>,
02094       _Hash2, _Eq2>
02095     {
02096     private:
02097       template<typename... _Tp>
02098         using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
02099       template<typename... _Tp>
02100         using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
02101 
02102       friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>;
02103 
02104       static auto&
02105       _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
02106       { return __map._M_h; }
02107 
02108       static auto&
02109       _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
02110       { return __map._M_h; }
02111     };
02112 
02113   // Allow std::unordered_multimap access to internals of compatible maps.
02114   template<typename _Key, typename _Val, typename _Hash1, typename _Eq1,
02115            typename _Alloc, typename _Hash2, typename _Eq2>
02116     struct _Hash_merge_helper<
02117       _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>,
02118       _Hash2, _Eq2>
02119     {
02120     private:
02121       template<typename... _Tp>
02122         using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
02123       template<typename... _Tp>
02124         using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
02125 
02126       friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>;
02127 
02128       static auto&
02129       _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
02130       { return __map._M_h; }
02131 
02132       static auto&
02133       _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
02134       { return __map._M_h; }
02135     };
02136 #endif // C++17
02137 
02138 _GLIBCXX_END_NAMESPACE_VERSION
02139 } // namespace std
02140 
02141 #endif /* _UNORDERED_MAP_H */