libstdc++
unordered_map.h
Go to the documentation of this file.
00001 // unordered_map implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2010-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 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       _GLIBCXX_NODISCARD 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>
00589         __enable_if_t<is_constructible<value_type, _Pair&&>::value,
00590                       pair<iterator, bool>>
00591         insert(_Pair&& __x)
00592         { return _M_h.emplace(std::forward<_Pair>(__x)); }
00593       //@}
00594 
00595       //@{
00596       /**
00597        *  @brief Attempts to insert a std::pair into the %unordered_map.
00598        *  @param  __hint  An iterator that serves as a hint as to where the
00599        *                 pair should be inserted.
00600        *  @param  __x  Pair to be inserted (see std::make_pair for easy creation
00601        *               of pairs).
00602        *  @return An iterator that points to the element with key of
00603        *           @a __x (may or may not be the %pair passed in).
00604        *
00605        *  This function is not concerned about whether the insertion took place,
00606        *  and thus does not return a boolean like the single-argument insert()
00607        *  does.  Note that the first parameter is only a hint and can
00608        *  potentially improve the performance of the insertion process.  A bad
00609        *  hint would cause no gains in efficiency.
00610        *
00611        *  See
00612        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
00613        *  for more on @a hinting.
00614        *
00615        *  Insertion requires amortized constant time.
00616        */
00617       iterator
00618       insert(const_iterator __hint, const value_type& __x)
00619       { return _M_h.insert(__hint, __x); }
00620 
00621       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00622       // 2354. Unnecessary copying when inserting into maps with braced-init
00623       iterator
00624       insert(const_iterator __hint, value_type&& __x)
00625       { return _M_h.insert(__hint, std::move(__x)); }
00626 
00627       template<typename _Pair>
00628         __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
00629         insert(const_iterator __hint, _Pair&& __x)
00630         { return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
00631       //@}
00632 
00633       /**
00634        *  @brief A template function that attempts to insert a range of
00635        *  elements.
00636        *  @param  __first  Iterator pointing to the start of the range to be
00637        *                   inserted.
00638        *  @param  __last  Iterator pointing to the end of the range.
00639        *
00640        *  Complexity similar to that of the range constructor.
00641        */
00642       template<typename _InputIterator>
00643         void
00644         insert(_InputIterator __first, _InputIterator __last)
00645         { _M_h.insert(__first, __last); }
00646 
00647       /**
00648        *  @brief Attempts to insert a list of elements into the %unordered_map.
00649        *  @param  __l  A std::initializer_list<value_type> of elements
00650        *               to be inserted.
00651        *
00652        *  Complexity similar to that of the range constructor.
00653        */
00654       void
00655       insert(initializer_list<value_type> __l)
00656       { _M_h.insert(__l); }
00657 
00658 
00659 #if __cplusplus > 201402L
00660 #define __cpp_lib_unordered_map_insertion 201411
00661       /**
00662        *  @brief Attempts to insert a std::pair into the %unordered_map.
00663        *  @param __k    Key to use for finding a possibly existing pair in
00664        *                the map.
00665        *  @param __obj  Argument used to generate the .second for a pair 
00666        *                instance.
00667        *
00668        *  @return  A pair, of which the first element is an iterator that 
00669        *           points to the possibly inserted pair, and the second is 
00670        *           a bool that is true if the pair was actually inserted.
00671        *
00672        *  This function attempts to insert a (key, value) %pair into the
00673        *  %unordered_map. An %unordered_map relies on unique keys and thus a
00674        *  %pair is only inserted if its first element (the key) is not already
00675        *  present in the %unordered_map.
00676        *  If the %pair was already in the %unordered_map, the .second of 
00677        *  the %pair is assigned from __obj.
00678        *
00679        *  Insertion requires amortized constant time.
00680        */
00681       template <typename _Obj>
00682         pair<iterator, bool>
00683         insert_or_assign(const key_type& __k, _Obj&& __obj)
00684         {
00685           iterator __i = find(__k);
00686           if (__i == end())
00687             {
00688               __i = emplace(std::piecewise_construct,
00689                             std::forward_as_tuple(__k),
00690                             std::forward_as_tuple(std::forward<_Obj>(__obj)))
00691                 .first;
00692               return {__i, true};
00693             }
00694           (*__i).second = std::forward<_Obj>(__obj);
00695           return {__i, false};
00696         }
00697 
00698       // move-capable overload
00699       template <typename _Obj>
00700         pair<iterator, bool>
00701         insert_or_assign(key_type&& __k, _Obj&& __obj)
00702         {
00703           iterator __i = find(__k);
00704           if (__i == end())
00705             {
00706               __i = emplace(std::piecewise_construct,
00707                             std::forward_as_tuple(std::move(__k)),
00708                             std::forward_as_tuple(std::forward<_Obj>(__obj)))
00709                 .first;
00710               return {__i, true};
00711             }
00712           (*__i).second = std::forward<_Obj>(__obj);
00713           return {__i, false};
00714         }
00715 
00716       /**
00717        *  @brief Attempts to insert a std::pair into the %unordered_map.
00718        *  @param  __hint  An iterator that serves as a hint as to where the
00719        *                  pair should be inserted.
00720        *  @param __k    Key to use for finding a possibly existing pair in
00721        *                the unordered_map.
00722        *  @param __obj  Argument used to generate the .second for a pair 
00723        *                instance.
00724        *  @return An iterator that points to the element with key of
00725        *           @a __x (may or may not be the %pair passed in).
00726        *
00727        *  This function is not concerned about whether the insertion took place,
00728        *  and thus does not return a boolean like the single-argument insert()
00729        *  does.         
00730        *  If the %pair was already in the %unordered map, the .second of
00731        *  the %pair is assigned from __obj.
00732        *  Note that the first parameter is only a hint and can
00733        *  potentially improve the performance of the insertion process.  A bad
00734        *  hint would cause no gains in efficiency.
00735        *
00736        *  See
00737        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
00738        *  for more on @a hinting.
00739        *
00740        *  Insertion requires amortized constant time.
00741        */
00742       template <typename _Obj>
00743         iterator
00744         insert_or_assign(const_iterator __hint, const key_type& __k,
00745                          _Obj&& __obj)
00746         {
00747           iterator __i = find(__k);
00748           if (__i == end())
00749             {
00750               return emplace_hint(__hint, std::piecewise_construct,
00751                                   std::forward_as_tuple(__k),
00752                                   std::forward_as_tuple(
00753                                     std::forward<_Obj>(__obj)));
00754             }
00755           (*__i).second = std::forward<_Obj>(__obj);
00756           return __i;
00757         }
00758 
00759       // move-capable overload
00760       template <typename _Obj>
00761         iterator
00762         insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
00763         {
00764           iterator __i = find(__k);
00765           if (__i == end())
00766             {
00767               return emplace_hint(__hint, std::piecewise_construct,
00768                                   std::forward_as_tuple(std::move(__k)),
00769                                   std::forward_as_tuple(
00770                                     std::forward<_Obj>(__obj)));
00771             }
00772           (*__i).second = std::forward<_Obj>(__obj);
00773           return __i;
00774         }
00775 #endif
00776 
00777       //@{
00778       /**
00779        *  @brief Erases an element from an %unordered_map.
00780        *  @param  __position  An iterator pointing to the element to be erased.
00781        *  @return An iterator pointing to the element immediately following
00782        *          @a __position prior to the element being erased. If no such
00783        *          element exists, end() is returned.
00784        *
00785        *  This function erases an element, pointed to by the given iterator,
00786        *  from an %unordered_map.
00787        *  Note that this function only erases the element, and that if the
00788        *  element is itself a pointer, the pointed-to memory is not touched in
00789        *  any way.  Managing the pointer is the user's responsibility.
00790        */
00791       iterator
00792       erase(const_iterator __position)
00793       { return _M_h.erase(__position); }
00794 
00795       // LWG 2059.
00796       iterator
00797       erase(iterator __position)
00798       { return _M_h.erase(__position); }
00799       //@}
00800 
00801       /**
00802        *  @brief Erases elements according to the provided key.
00803        *  @param  __x  Key of element to be erased.
00804        *  @return  The number of elements erased.
00805        *
00806        *  This function erases all the elements located by the given key from
00807        *  an %unordered_map. For an %unordered_map the result of this function
00808        *  can only be 0 (not present) or 1 (present).
00809        *  Note that this function only erases the element, and that if the
00810        *  element is itself a pointer, the pointed-to memory is not touched in
00811        *  any way.  Managing the pointer is the user's responsibility.
00812        */
00813       size_type
00814       erase(const key_type& __x)
00815       { return _M_h.erase(__x); }
00816 
00817       /**
00818        *  @brief Erases a [__first,__last) range of elements from an
00819        *  %unordered_map.
00820        *  @param  __first  Iterator pointing to the start of the range to be
00821        *                  erased.
00822        *  @param __last  Iterator pointing to the end of the range to
00823        *                be erased.
00824        *  @return The iterator @a __last.
00825        *
00826        *  This function erases a sequence of elements from an %unordered_map.
00827        *  Note that this function only erases the elements, and that if
00828        *  the element is itself a pointer, the pointed-to memory is not touched
00829        *  in any way.  Managing the pointer is the user's responsibility.
00830        */
00831       iterator
00832       erase(const_iterator __first, const_iterator __last)
00833       { return _M_h.erase(__first, __last); }
00834 
00835       /**
00836        *  Erases all elements in an %unordered_map.
00837        *  Note that this function only erases the elements, and that if the
00838        *  elements themselves are pointers, the pointed-to memory is not touched
00839        *  in any way.  Managing the pointer is the user's responsibility.
00840        */
00841       void
00842       clear() noexcept
00843       { _M_h.clear(); }
00844 
00845       /**
00846        *  @brief  Swaps data with another %unordered_map.
00847        *  @param  __x  An %unordered_map of the same element and allocator
00848        *  types.
00849        *
00850        *  This exchanges the elements between two %unordered_map in constant
00851        *  time.
00852        *  Note that the global std::swap() function is specialized such that
00853        *  std::swap(m1,m2) will feed to this function.
00854        */
00855       void
00856       swap(unordered_map& __x)
00857       noexcept( noexcept(_M_h.swap(__x._M_h)) )
00858       { _M_h.swap(__x._M_h); }
00859 
00860 #if __cplusplus > 201402L
00861       template<typename, typename, typename>
00862         friend class std::_Hash_merge_helper;
00863 
00864       template<typename _H2, typename _P2>
00865         void
00866         merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
00867         {
00868           using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
00869           _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
00870         }
00871 
00872       template<typename _H2, typename _P2>
00873         void
00874         merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
00875         { merge(__source); }
00876 
00877       template<typename _H2, typename _P2>
00878         void
00879         merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
00880         {
00881           using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
00882           _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
00883         }
00884 
00885       template<typename _H2, typename _P2>
00886         void
00887         merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
00888         { merge(__source); }
00889 #endif // C++17
00890 
00891       // observers.
00892 
00893       ///  Returns the hash functor object with which the %unordered_map was
00894       ///  constructed.
00895       hasher
00896       hash_function() const
00897       { return _M_h.hash_function(); }
00898 
00899       ///  Returns the key comparison object with which the %unordered_map was
00900       ///  constructed.
00901       key_equal
00902       key_eq() const
00903       { return _M_h.key_eq(); }
00904 
00905       // lookup.
00906 
00907       //@{
00908       /**
00909        *  @brief Tries to locate an element in an %unordered_map.
00910        *  @param  __x  Key to be located.
00911        *  @return  Iterator pointing to sought-after element, or end() if not
00912        *           found.
00913        *
00914        *  This function takes a key and tries to locate the element with which
00915        *  the key matches.  If successful the function returns an iterator
00916        *  pointing to the sought after element.  If unsuccessful it returns the
00917        *  past-the-end ( @c end() ) iterator.
00918        */
00919       iterator
00920       find(const key_type& __x)
00921       { return _M_h.find(__x); }
00922 
00923       const_iterator
00924       find(const key_type& __x) const
00925       { return _M_h.find(__x); }
00926       //@}
00927 
00928       /**
00929        *  @brief  Finds the number of elements.
00930        *  @param  __x  Key to count.
00931        *  @return  Number of elements with specified key.
00932        *
00933        *  This function only makes sense for %unordered_multimap; for
00934        *  %unordered_map the result will either be 0 (not present) or 1
00935        *  (present).
00936        */
00937       size_type
00938       count(const key_type& __x) const
00939       { return _M_h.count(__x); }
00940 
00941 #if __cplusplus > 201703L
00942       /**
00943        *  @brief  Finds whether an element with the given key exists.
00944        *  @param  __x  Key of elements to be located.
00945        *  @return  True if there is any element with the specified key.
00946        */
00947       bool
00948       contains(const key_type& __x) const
00949       { return _M_h.find(__x) != _M_h.end(); }
00950 #endif
00951 
00952       //@{
00953       /**
00954        *  @brief Finds a subsequence matching given key.
00955        *  @param  __x  Key to be located.
00956        *  @return  Pair of iterators that possibly points to the subsequence
00957        *           matching given key.
00958        *
00959        *  This function probably only makes sense for %unordered_multimap.
00960        */
00961       std::pair<iterator, iterator>
00962       equal_range(const key_type& __x)
00963       { return _M_h.equal_range(__x); }
00964 
00965       std::pair<const_iterator, const_iterator>
00966       equal_range(const key_type& __x) const
00967       { return _M_h.equal_range(__x); }
00968       //@}
00969 
00970       //@{
00971       /**
00972        *  @brief  Subscript ( @c [] ) access to %unordered_map data.
00973        *  @param  __k  The key for which data should be retrieved.
00974        *  @return  A reference to the data of the (key,data) %pair.
00975        *
00976        *  Allows for easy lookup with the subscript ( @c [] )operator.  Returns
00977        *  data associated with the key specified in subscript.  If the key does
00978        *  not exist, a pair with that key is created using default values, which
00979        *  is then returned.
00980        *
00981        *  Lookup requires constant time.
00982        */
00983       mapped_type&
00984       operator[](const key_type& __k)
00985       { return _M_h[__k]; }
00986 
00987       mapped_type&
00988       operator[](key_type&& __k)
00989       { return _M_h[std::move(__k)]; }
00990       //@}
00991 
00992       //@{
00993       /**
00994        *  @brief  Access to %unordered_map data.
00995        *  @param  __k  The key for which data should be retrieved.
00996        *  @return  A reference to the data whose key is equal to @a __k, if
00997        *           such a data is present in the %unordered_map.
00998        *  @throw  std::out_of_range  If no such data is present.
00999        */
01000       mapped_type&
01001       at(const key_type& __k)
01002       { return _M_h.at(__k); }
01003 
01004       const mapped_type&
01005       at(const key_type& __k) const
01006       { return _M_h.at(__k); }
01007       //@}
01008 
01009       // bucket interface.
01010 
01011       /// Returns the number of buckets of the %unordered_map.
01012       size_type
01013       bucket_count() const noexcept
01014       { return _M_h.bucket_count(); }
01015 
01016       /// Returns the maximum number of buckets of the %unordered_map.
01017       size_type
01018       max_bucket_count() const noexcept
01019       { return _M_h.max_bucket_count(); }
01020 
01021       /*
01022        * @brief  Returns the number of elements in a given bucket.
01023        * @param  __n  A bucket index.
01024        * @return  The number of elements in the bucket.
01025        */
01026       size_type
01027       bucket_size(size_type __n) const
01028       { return _M_h.bucket_size(__n); }
01029 
01030       /*
01031        * @brief  Returns the bucket index of a given element.
01032        * @param  __key  A key instance.
01033        * @return  The key bucket index.
01034        */
01035       size_type
01036       bucket(const key_type& __key) const
01037       { return _M_h.bucket(__key); }
01038       
01039       /**
01040        *  @brief  Returns a read/write iterator pointing to the first bucket
01041        *         element.
01042        *  @param  __n The bucket index.
01043        *  @return  A read/write local iterator.
01044        */
01045       local_iterator
01046       begin(size_type __n)
01047       { return _M_h.begin(__n); }
01048 
01049       //@{
01050       /**
01051        *  @brief  Returns a read-only (constant) iterator pointing to the first
01052        *         bucket element.
01053        *  @param  __n The bucket index.
01054        *  @return  A read-only local iterator.
01055        */
01056       const_local_iterator
01057       begin(size_type __n) const
01058       { return _M_h.begin(__n); }
01059 
01060       const_local_iterator
01061       cbegin(size_type __n) const
01062       { return _M_h.cbegin(__n); }
01063       //@}
01064 
01065       /**
01066        *  @brief  Returns a read/write iterator pointing to one past the last
01067        *         bucket elements.
01068        *  @param  __n The bucket index.
01069        *  @return  A read/write local iterator.
01070        */
01071       local_iterator
01072       end(size_type __n)
01073       { return _M_h.end(__n); }
01074 
01075       //@{
01076       /**
01077        *  @brief  Returns a read-only (constant) iterator pointing to one past
01078        *         the last bucket elements.
01079        *  @param  __n The bucket index.
01080        *  @return  A read-only local iterator.
01081        */
01082       const_local_iterator
01083       end(size_type __n) const
01084       { return _M_h.end(__n); }
01085 
01086       const_local_iterator
01087       cend(size_type __n) const
01088       { return _M_h.cend(__n); }
01089       //@}
01090 
01091       // hash policy.
01092 
01093       /// Returns the average number of elements per bucket.
01094       float
01095       load_factor() const noexcept
01096       { return _M_h.load_factor(); }
01097 
01098       /// Returns a positive number that the %unordered_map tries to keep the
01099       /// load factor less than or equal to.
01100       float
01101       max_load_factor() const noexcept
01102       { return _M_h.max_load_factor(); }
01103 
01104       /**
01105        *  @brief  Change the %unordered_map maximum load factor.
01106        *  @param  __z The new maximum load factor.
01107        */
01108       void
01109       max_load_factor(float __z)
01110       { _M_h.max_load_factor(__z); }
01111 
01112       /**
01113        *  @brief  May rehash the %unordered_map.
01114        *  @param  __n The new number of buckets.
01115        *
01116        *  Rehash will occur only if the new number of buckets respect the
01117        *  %unordered_map maximum load factor.
01118        */
01119       void
01120       rehash(size_type __n)
01121       { _M_h.rehash(__n); }
01122 
01123       /**
01124        *  @brief  Prepare the %unordered_map for a specified number of
01125        *          elements.
01126        *  @param  __n Number of elements required.
01127        *
01128        *  Same as rehash(ceil(n / max_load_factor())).
01129        */
01130       void
01131       reserve(size_type __n)
01132       { _M_h.reserve(__n); }
01133 
01134       template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
01135                typename _Alloc1>
01136         friend bool
01137         operator==(const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&,
01138                    const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&);
01139     };
01140 
01141 #if __cpp_deduction_guides >= 201606
01142 
01143   template<typename _InputIterator,
01144            typename _Hash = hash<__iter_key_t<_InputIterator>>,
01145            typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
01146            typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
01147            typename = _RequireInputIter<_InputIterator>,
01148            typename = _RequireNotAllocatorOrIntegral<_Hash>,
01149            typename = _RequireNotAllocator<_Pred>,
01150            typename = _RequireAllocator<_Allocator>>
01151     unordered_map(_InputIterator, _InputIterator,
01152                   typename unordered_map<int, int>::size_type = {},
01153                   _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
01154     -> unordered_map<__iter_key_t<_InputIterator>,
01155                      __iter_val_t<_InputIterator>,
01156                      _Hash, _Pred, _Allocator>;
01157 
01158   template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
01159            typename _Pred = equal_to<_Key>,
01160            typename _Allocator = allocator<pair<const _Key, _Tp>>,
01161            typename = _RequireNotAllocatorOrIntegral<_Hash>,
01162            typename = _RequireNotAllocator<_Pred>,
01163            typename = _RequireAllocator<_Allocator>>
01164     unordered_map(initializer_list<pair<_Key, _Tp>>,
01165                   typename unordered_map<int, int>::size_type = {},
01166                   _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
01167     -> unordered_map<_Key, _Tp, _Hash, _Pred, _Allocator>;
01168 
01169   template<typename _InputIterator, typename _Allocator,
01170            typename = _RequireInputIter<_InputIterator>,
01171            typename = _RequireAllocator<_Allocator>>
01172     unordered_map(_InputIterator, _InputIterator,
01173                   typename unordered_map<int, int>::size_type, _Allocator)
01174     -> unordered_map<__iter_key_t<_InputIterator>,
01175                      __iter_val_t<_InputIterator>,
01176                      hash<__iter_key_t<_InputIterator>>,
01177                      equal_to<__iter_key_t<_InputIterator>>,
01178                      _Allocator>;
01179 
01180   template<typename _InputIterator, typename _Allocator,
01181            typename = _RequireInputIter<_InputIterator>,
01182            typename = _RequireAllocator<_Allocator>>
01183     unordered_map(_InputIterator, _InputIterator, _Allocator)
01184     -> unordered_map<__iter_key_t<_InputIterator>,
01185                      __iter_val_t<_InputIterator>,
01186                      hash<__iter_key_t<_InputIterator>>,
01187                      equal_to<__iter_key_t<_InputIterator>>,
01188                      _Allocator>;
01189 
01190   template<typename _InputIterator, typename _Hash, typename _Allocator,
01191            typename = _RequireInputIter<_InputIterator>,
01192            typename = _RequireNotAllocatorOrIntegral<_Hash>,
01193            typename = _RequireAllocator<_Allocator>>
01194     unordered_map(_InputIterator, _InputIterator,
01195                   typename unordered_map<int, int>::size_type,
01196                   _Hash, _Allocator)
01197     -> unordered_map<__iter_key_t<_InputIterator>,
01198                      __iter_val_t<_InputIterator>, _Hash,
01199                      equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
01200 
01201   template<typename _Key, typename _Tp, typename _Allocator,
01202            typename = _RequireAllocator<_Allocator>>
01203     unordered_map(initializer_list<pair<_Key, _Tp>>,
01204                   typename unordered_map<int, int>::size_type,
01205                   _Allocator)
01206     -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
01207 
01208   template<typename _Key, typename _Tp, typename _Allocator,
01209            typename = _RequireAllocator<_Allocator>>
01210     unordered_map(initializer_list<pair<_Key, _Tp>>, _Allocator)
01211     -> unordered_map<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
01212 
01213   template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
01214            typename = _RequireNotAllocatorOrIntegral<_Hash>,
01215            typename = _RequireAllocator<_Allocator>>
01216     unordered_map(initializer_list<pair<_Key, _Tp>>,
01217                   typename unordered_map<int, int>::size_type,
01218                   _Hash, _Allocator)
01219     -> unordered_map<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
01220 
01221 #endif
01222 
01223   /**
01224    *  @brief A standard container composed of equivalent keys
01225    *  (possibly containing multiple of each key value) that associates
01226    *  values of another type with the keys.
01227    *
01228    *  @ingroup unordered_associative_containers
01229    *
01230    *  @tparam  _Key    Type of key objects.
01231    *  @tparam  _Tp     Type of mapped objects.
01232    *  @tparam  _Hash   Hashing function object type, defaults to hash<_Value>.
01233    *  @tparam  _Pred   Predicate function object type, defaults
01234    *                   to equal_to<_Value>.
01235    *  @tparam  _Alloc  Allocator type, defaults to
01236    *                   std::allocator<std::pair<const _Key, _Tp>>.
01237    *
01238    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
01239    *  <a href="tables.html#xx">unordered associative container</a>
01240    *
01241    * The resulting value type of the container is std::pair<const _Key, _Tp>.
01242    *
01243    *  Base is _Hashtable, dispatched at compile time via template
01244    *  alias __ummap_hashtable.
01245    */
01246   template<typename _Key, typename _Tp,
01247            typename _Hash = hash<_Key>,
01248            typename _Pred = equal_to<_Key>,
01249            typename _Alloc = allocator<std::pair<const _Key, _Tp>>>
01250     class unordered_multimap
01251     {
01252       typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
01253       _Hashtable _M_h;
01254 
01255     public:
01256       // typedefs:
01257       //@{
01258       /// Public typedefs.
01259       typedef typename _Hashtable::key_type     key_type;
01260       typedef typename _Hashtable::value_type   value_type;
01261       typedef typename _Hashtable::mapped_type  mapped_type;
01262       typedef typename _Hashtable::hasher       hasher;
01263       typedef typename _Hashtable::key_equal    key_equal;
01264       typedef typename _Hashtable::allocator_type allocator_type;
01265       //@}
01266 
01267       //@{
01268       ///  Iterator-related typedefs.
01269       typedef typename _Hashtable::pointer              pointer;
01270       typedef typename _Hashtable::const_pointer        const_pointer;
01271       typedef typename _Hashtable::reference            reference;
01272       typedef typename _Hashtable::const_reference      const_reference;
01273       typedef typename _Hashtable::iterator             iterator;
01274       typedef typename _Hashtable::const_iterator       const_iterator;
01275       typedef typename _Hashtable::local_iterator       local_iterator;
01276       typedef typename _Hashtable::const_local_iterator const_local_iterator;
01277       typedef typename _Hashtable::size_type            size_type;
01278       typedef typename _Hashtable::difference_type      difference_type;
01279       //@}
01280 
01281 #if __cplusplus > 201402L
01282       using node_type = typename _Hashtable::node_type;
01283 #endif
01284 
01285       //construct/destroy/copy
01286 
01287       /// Default constructor.
01288       unordered_multimap() = default;
01289 
01290       /**
01291        *  @brief  Default constructor creates no elements.
01292        *  @param __n  Mnimal initial number of buckets.
01293        *  @param __hf  A hash functor.
01294        *  @param __eql  A key equality functor.
01295        *  @param __a  An allocator object.
01296        */
01297       explicit
01298       unordered_multimap(size_type __n,
01299                          const hasher& __hf = hasher(),
01300                          const key_equal& __eql = key_equal(),
01301                          const allocator_type& __a = allocator_type())
01302       : _M_h(__n, __hf, __eql, __a)
01303       { }
01304 
01305       /**
01306        *  @brief  Builds an %unordered_multimap from a range.
01307        *  @param  __first An input iterator.
01308        *  @param  __last  An input iterator.
01309        *  @param __n      Minimal initial number of buckets.
01310        *  @param __hf     A hash functor.
01311        *  @param __eql    A key equality functor.
01312        *  @param __a      An allocator object.
01313        *
01314        *  Create an %unordered_multimap consisting of copies of the elements
01315        *  from [__first,__last).  This is linear in N (where N is
01316        *  distance(__first,__last)).
01317        */
01318       template<typename _InputIterator>
01319         unordered_multimap(_InputIterator __first, _InputIterator __last,
01320                            size_type __n = 0,
01321                            const hasher& __hf = hasher(),
01322                            const key_equal& __eql = key_equal(),
01323                            const allocator_type& __a = allocator_type())
01324         : _M_h(__first, __last, __n, __hf, __eql, __a)
01325         { }
01326 
01327       /// Copy constructor.
01328       unordered_multimap(const unordered_multimap&) = default;
01329 
01330       /// Move constructor.
01331       unordered_multimap(unordered_multimap&&) = default;
01332 
01333       /**
01334        *  @brief Creates an %unordered_multimap with no elements.
01335        *  @param __a An allocator object.
01336        */
01337       explicit
01338       unordered_multimap(const allocator_type& __a)
01339       : _M_h(__a)
01340       { }
01341 
01342       /*
01343        *  @brief Copy constructor with allocator argument.
01344        * @param  __uset  Input %unordered_multimap to copy.
01345        * @param  __a  An allocator object.
01346        */
01347       unordered_multimap(const unordered_multimap& __ummap,
01348                          const allocator_type& __a)
01349       : _M_h(__ummap._M_h, __a)
01350       { }
01351 
01352       /*
01353        *  @brief  Move constructor with allocator argument.
01354        *  @param  __uset Input %unordered_multimap to move.
01355        *  @param  __a    An allocator object.
01356        */
01357       unordered_multimap(unordered_multimap&& __ummap,
01358                          const allocator_type& __a)
01359       : _M_h(std::move(__ummap._M_h), __a)
01360       { }
01361 
01362       /**
01363        *  @brief  Builds an %unordered_multimap from an initializer_list.
01364        *  @param  __l  An initializer_list.
01365        *  @param __n  Minimal initial number of buckets.
01366        *  @param __hf  A hash functor.
01367        *  @param __eql  A key equality functor.
01368        *  @param  __a  An allocator object.
01369        *
01370        *  Create an %unordered_multimap consisting of copies of the elements in
01371        *  the list. This is linear in N (where N is @a __l.size()).
01372        */
01373       unordered_multimap(initializer_list<value_type> __l,
01374                          size_type __n = 0,
01375                          const hasher& __hf = hasher(),
01376                          const key_equal& __eql = key_equal(),
01377                          const allocator_type& __a = allocator_type())
01378       : _M_h(__l, __n, __hf, __eql, __a)
01379       { }
01380 
01381       unordered_multimap(size_type __n, const allocator_type& __a)
01382       : unordered_multimap(__n, hasher(), key_equal(), __a)
01383       { }
01384 
01385       unordered_multimap(size_type __n, const hasher& __hf,
01386                          const allocator_type& __a)
01387       : unordered_multimap(__n, __hf, key_equal(), __a)
01388       { }
01389 
01390       template<typename _InputIterator>
01391         unordered_multimap(_InputIterator __first, _InputIterator __last,
01392                            size_type __n,
01393                            const allocator_type& __a)
01394         : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
01395         { }
01396 
01397       template<typename _InputIterator>
01398         unordered_multimap(_InputIterator __first, _InputIterator __last,
01399                            size_type __n, const hasher& __hf,
01400                            const allocator_type& __a)
01401         : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
01402         { }
01403 
01404       unordered_multimap(initializer_list<value_type> __l,
01405                          size_type __n,
01406                          const allocator_type& __a)
01407       : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
01408       { }
01409 
01410       unordered_multimap(initializer_list<value_type> __l,
01411                          size_type __n, const hasher& __hf,
01412                          const allocator_type& __a)
01413       : unordered_multimap(__l, __n, __hf, key_equal(), __a)
01414       { }
01415 
01416       /// Copy assignment operator.
01417       unordered_multimap&
01418       operator=(const unordered_multimap&) = default;
01419 
01420       /// Move assignment operator.
01421       unordered_multimap&
01422       operator=(unordered_multimap&&) = default;
01423 
01424       /**
01425        *  @brief  %Unordered_multimap list assignment operator.
01426        *  @param  __l  An initializer_list.
01427        *
01428        *  This function fills an %unordered_multimap with copies of the
01429        *  elements in the initializer list @a __l.
01430        *
01431        *  Note that the assignment completely changes the %unordered_multimap
01432        *  and that the resulting %unordered_multimap's size is the same as the
01433        *  number of elements assigned.
01434        */
01435       unordered_multimap&
01436       operator=(initializer_list<value_type> __l)
01437       {
01438         _M_h = __l;
01439         return *this;
01440       }
01441 
01442       ///  Returns the allocator object used by the %unordered_multimap.
01443       allocator_type
01444       get_allocator() const noexcept
01445       { return _M_h.get_allocator(); }
01446 
01447       // size and capacity:
01448 
01449       ///  Returns true if the %unordered_multimap is empty.
01450       _GLIBCXX_NODISCARD bool
01451       empty() const noexcept
01452       { return _M_h.empty(); }
01453 
01454       ///  Returns the size of the %unordered_multimap.
01455       size_type
01456       size() const noexcept
01457       { return _M_h.size(); }
01458 
01459       ///  Returns the maximum size of the %unordered_multimap.
01460       size_type
01461       max_size() const noexcept
01462       { return _M_h.max_size(); }
01463 
01464       // iterators.
01465 
01466       /**
01467        *  Returns a read/write iterator that points to the first element in the
01468        *  %unordered_multimap.
01469        */
01470       iterator
01471       begin() noexcept
01472       { return _M_h.begin(); }
01473 
01474       //@{
01475       /**
01476        *  Returns a read-only (constant) iterator that points to the first
01477        *  element in the %unordered_multimap.
01478        */
01479       const_iterator
01480       begin() const noexcept
01481       { return _M_h.begin(); }
01482 
01483       const_iterator
01484       cbegin() const noexcept
01485       { return _M_h.begin(); }
01486       //@}
01487 
01488       /**
01489        *  Returns a read/write iterator that points one past the last element in
01490        *  the %unordered_multimap.
01491        */
01492       iterator
01493       end() noexcept
01494       { return _M_h.end(); }
01495 
01496       //@{
01497       /**
01498        *  Returns a read-only (constant) iterator that points one past the last
01499        *  element in the %unordered_multimap.
01500        */
01501       const_iterator
01502       end() const noexcept
01503       { return _M_h.end(); }
01504 
01505       const_iterator
01506       cend() const noexcept
01507       { return _M_h.end(); }
01508       //@}
01509 
01510       // modifiers.
01511 
01512       /**
01513        *  @brief Attempts to build and insert a std::pair into the
01514        *  %unordered_multimap.
01515        *
01516        *  @param __args  Arguments used to generate a new pair instance (see
01517        *                std::piecewise_contruct for passing arguments to each
01518        *                part of the pair constructor).
01519        *
01520        *  @return  An iterator that points to the inserted pair.
01521        *
01522        *  This function attempts to build and insert a (key, value) %pair into
01523        *  the %unordered_multimap.
01524        *
01525        *  Insertion requires amortized constant time.
01526        */
01527       template<typename... _Args>
01528         iterator
01529         emplace(_Args&&... __args)
01530         { return _M_h.emplace(std::forward<_Args>(__args)...); }
01531 
01532       /**
01533        *  @brief Attempts to build and insert a std::pair into the
01534        *  %unordered_multimap.
01535        *
01536        *  @param  __pos  An iterator that serves as a hint as to where the pair
01537        *                should be inserted.
01538        *  @param  __args  Arguments used to generate a new pair instance (see
01539        *                 std::piecewise_contruct for passing arguments to each
01540        *                 part of the pair constructor).
01541        *  @return An iterator that points to the element with key of the
01542        *          std::pair built from @a __args.
01543        *
01544        *  Note that the first parameter is only a hint and can potentially
01545        *  improve the performance of the insertion process. A bad hint would
01546        *  cause no gains in efficiency.
01547        *
01548        *  See
01549        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
01550        *  for more on @a hinting.
01551        *
01552        *  Insertion requires amortized constant time.
01553        */
01554       template<typename... _Args>
01555         iterator
01556         emplace_hint(const_iterator __pos, _Args&&... __args)
01557         { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
01558 
01559       //@{
01560       /**
01561        *  @brief Inserts a std::pair into the %unordered_multimap.
01562        *  @param __x Pair to be inserted (see std::make_pair for easy
01563        *             creation of pairs).
01564        *
01565        *  @return  An iterator that points to the inserted pair.
01566        *
01567        *  Insertion requires amortized constant time.
01568        */
01569       iterator
01570       insert(const value_type& __x)
01571       { return _M_h.insert(__x); }
01572 
01573       iterator
01574       insert(value_type&& __x)
01575       { return _M_h.insert(std::move(__x)); }
01576 
01577       template<typename _Pair>
01578         __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
01579         insert(_Pair&& __x)
01580         { return _M_h.emplace(std::forward<_Pair>(__x)); }
01581       //@}
01582 
01583       //@{
01584       /**
01585        *  @brief Inserts a std::pair into the %unordered_multimap.
01586        *  @param  __hint  An iterator that serves as a hint as to where the
01587        *                 pair should be inserted.
01588        *  @param  __x  Pair to be inserted (see std::make_pair for easy creation
01589        *               of pairs).
01590        *  @return An iterator that points to the element with key of
01591        *           @a __x (may or may not be the %pair passed in).
01592        *
01593        *  Note that the first parameter is only a hint and can potentially
01594        *  improve the performance of the insertion process.  A bad hint would
01595        *  cause no gains in efficiency.
01596        *
01597        *  See
01598        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
01599        *  for more on @a hinting.
01600        *
01601        *  Insertion requires amortized constant time.
01602        */
01603       iterator
01604       insert(const_iterator __hint, const value_type& __x)
01605       { return _M_h.insert(__hint, __x); }
01606 
01607       // _GLIBCXX_RESOLVE_LIB_DEFECTS
01608       // 2354. Unnecessary copying when inserting into maps with braced-init
01609       iterator
01610       insert(const_iterator __hint, value_type&& __x)
01611       { return _M_h.insert(__hint, std::move(__x)); }
01612 
01613       template<typename _Pair>
01614         __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
01615         insert(const_iterator __hint, _Pair&& __x)
01616         { return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
01617       //@}
01618 
01619       /**
01620        *  @brief A template function that attempts to insert a range of
01621        *  elements.
01622        *  @param  __first  Iterator pointing to the start of the range to be
01623        *                   inserted.
01624        *  @param  __last  Iterator pointing to the end of the range.
01625        *
01626        *  Complexity similar to that of the range constructor.
01627        */
01628       template<typename _InputIterator>
01629         void
01630         insert(_InputIterator __first, _InputIterator __last)
01631         { _M_h.insert(__first, __last); }
01632 
01633       /**
01634        *  @brief Attempts to insert a list of elements into the
01635        *  %unordered_multimap.
01636        *  @param  __l  A std::initializer_list<value_type> of elements
01637        *               to be inserted.
01638        *
01639        *  Complexity similar to that of the range constructor.
01640        */
01641       void
01642       insert(initializer_list<value_type> __l)
01643       { _M_h.insert(__l); }
01644 
01645 #if __cplusplus > 201402L
01646       /// Extract a node.
01647       node_type
01648       extract(const_iterator __pos)
01649       {
01650         __glibcxx_assert(__pos != end());
01651         return _M_h.extract(__pos);
01652       }
01653 
01654       /// Extract a node.
01655       node_type
01656       extract(const key_type& __key)
01657       { return _M_h.extract(__key); }
01658 
01659       /// Re-insert an extracted node.
01660       iterator
01661       insert(node_type&& __nh)
01662       { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
01663 
01664       /// Re-insert an extracted node.
01665       iterator
01666       insert(const_iterator __hint, node_type&& __nh)
01667       { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
01668 #endif // C++17
01669 
01670       //@{
01671       /**
01672        *  @brief Erases an element from an %unordered_multimap.
01673        *  @param  __position  An iterator pointing to the element to be erased.
01674        *  @return An iterator pointing to the element immediately following
01675        *          @a __position prior to the element being erased. If no such
01676        *          element exists, end() is returned.
01677        *
01678        *  This function erases an element, pointed to by the given iterator,
01679        *  from an %unordered_multimap.
01680        *  Note that this function only erases the element, and that if the
01681        *  element is itself a pointer, the pointed-to memory is not touched in
01682        *  any way.  Managing the pointer is the user's responsibility.
01683        */
01684       iterator
01685       erase(const_iterator __position)
01686       { return _M_h.erase(__position); }
01687 
01688       // LWG 2059.
01689       iterator
01690       erase(iterator __position)
01691       { return _M_h.erase(__position); }
01692       //@}
01693 
01694       /**
01695        *  @brief Erases elements according to the provided key.
01696        *  @param  __x  Key of elements to be erased.
01697        *  @return  The number of elements erased.
01698        *
01699        *  This function erases all the elements located by the given key from
01700        *  an %unordered_multimap.
01701        *  Note that this function only erases the element, and that if the
01702        *  element is itself a pointer, the pointed-to memory is not touched in
01703        *  any way.  Managing the pointer is the user's responsibility.
01704        */
01705       size_type
01706       erase(const key_type& __x)
01707       { return _M_h.erase(__x); }
01708 
01709       /**
01710        *  @brief Erases a [__first,__last) range of elements from an
01711        *  %unordered_multimap.
01712        *  @param  __first  Iterator pointing to the start of the range to be
01713        *                  erased.
01714        *  @param __last  Iterator pointing to the end of the range to
01715        *                be erased.
01716        *  @return The iterator @a __last.
01717        *
01718        *  This function erases a sequence of elements from an
01719        *  %unordered_multimap.
01720        *  Note that this function only erases the elements, and that if
01721        *  the element is itself a pointer, the pointed-to memory is not touched
01722        *  in any way.  Managing the pointer is the user's responsibility.
01723        */
01724       iterator
01725       erase(const_iterator __first, const_iterator __last)
01726       { return _M_h.erase(__first, __last); }
01727 
01728       /**
01729        *  Erases all elements in an %unordered_multimap.
01730        *  Note that this function only erases the elements, and that if the
01731        *  elements themselves are pointers, the pointed-to memory is not touched
01732        *  in any way.  Managing the pointer is the user's responsibility.
01733        */
01734       void
01735       clear() noexcept
01736       { _M_h.clear(); }
01737 
01738       /**
01739        *  @brief  Swaps data with another %unordered_multimap.
01740        *  @param  __x  An %unordered_multimap of the same element and allocator
01741        *  types.
01742        *
01743        *  This exchanges the elements between two %unordered_multimap in
01744        *  constant time.
01745        *  Note that the global std::swap() function is specialized such that
01746        *  std::swap(m1,m2) will feed to this function.
01747        */
01748       void
01749       swap(unordered_multimap& __x)
01750       noexcept( noexcept(_M_h.swap(__x._M_h)) )
01751       { _M_h.swap(__x._M_h); }
01752 
01753 #if __cplusplus > 201402L
01754       template<typename, typename, typename>
01755         friend class std::_Hash_merge_helper;
01756 
01757       template<typename _H2, typename _P2>
01758         void
01759         merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
01760         {
01761           using _Merge_helper
01762             = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
01763           _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
01764         }
01765 
01766       template<typename _H2, typename _P2>
01767         void
01768         merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
01769         { merge(__source); }
01770 
01771       template<typename _H2, typename _P2>
01772         void
01773         merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
01774         {
01775           using _Merge_helper
01776             = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
01777           _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
01778         }
01779 
01780       template<typename _H2, typename _P2>
01781         void
01782         merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
01783         { merge(__source); }
01784 #endif // C++17
01785 
01786       // observers.
01787 
01788       ///  Returns the hash functor object with which the %unordered_multimap
01789       ///  was constructed.
01790       hasher
01791       hash_function() const
01792       { return _M_h.hash_function(); }
01793 
01794       ///  Returns the key comparison object with which the %unordered_multimap
01795       ///  was constructed.
01796       key_equal
01797       key_eq() const
01798       { return _M_h.key_eq(); }
01799 
01800       // lookup.
01801 
01802       //@{
01803       /**
01804        *  @brief Tries to locate an element in an %unordered_multimap.
01805        *  @param  __x  Key to be located.
01806        *  @return  Iterator pointing to sought-after element, or end() if not
01807        *           found.
01808        *
01809        *  This function takes a key and tries to locate the element with which
01810        *  the key matches.  If successful the function returns an iterator
01811        *  pointing to the sought after element.  If unsuccessful it returns the
01812        *  past-the-end ( @c end() ) iterator.
01813        */
01814       iterator
01815       find(const key_type& __x)
01816       { return _M_h.find(__x); }
01817 
01818       const_iterator
01819       find(const key_type& __x) const
01820       { return _M_h.find(__x); }
01821       //@}
01822 
01823       /**
01824        *  @brief  Finds the number of elements.
01825        *  @param  __x  Key to count.
01826        *  @return  Number of elements with specified key.
01827        */
01828       size_type
01829       count(const key_type& __x) const
01830       { return _M_h.count(__x); }
01831 
01832 #if __cplusplus > 201703L
01833       /**
01834        *  @brief  Finds whether an element with the given key exists.
01835        *  @param  __x  Key of elements to be located.
01836        *  @return  True if there is any element with the specified key.
01837        */
01838       bool
01839       contains(const key_type& __x) const
01840       { return _M_h.find(__x) != _M_h.end(); }
01841 #endif
01842 
01843       //@{
01844       /**
01845        *  @brief Finds a subsequence matching given key.
01846        *  @param  __x  Key to be located.
01847        *  @return  Pair of iterators that possibly points to the subsequence
01848        *           matching given key.
01849        */
01850       std::pair<iterator, iterator>
01851       equal_range(const key_type& __x)
01852       { return _M_h.equal_range(__x); }
01853 
01854       std::pair<const_iterator, const_iterator>
01855       equal_range(const key_type& __x) const
01856       { return _M_h.equal_range(__x); }
01857       //@}
01858 
01859       // bucket interface.
01860 
01861       /// Returns the number of buckets of the %unordered_multimap.
01862       size_type
01863       bucket_count() const noexcept
01864       { return _M_h.bucket_count(); }
01865 
01866       /// Returns the maximum number of buckets of the %unordered_multimap.
01867       size_type
01868       max_bucket_count() const noexcept
01869       { return _M_h.max_bucket_count(); }
01870 
01871       /*
01872        * @brief  Returns the number of elements in a given bucket.
01873        * @param  __n  A bucket index.
01874        * @return  The number of elements in the bucket.
01875        */
01876       size_type
01877       bucket_size(size_type __n) const
01878       { return _M_h.bucket_size(__n); }
01879 
01880       /*
01881        * @brief  Returns the bucket index of a given element.
01882        * @param  __key  A key instance.
01883        * @return  The key bucket index.
01884        */
01885       size_type
01886       bucket(const key_type& __key) const
01887       { return _M_h.bucket(__key); }
01888       
01889       /**
01890        *  @brief  Returns a read/write iterator pointing to the first bucket
01891        *         element.
01892        *  @param  __n The bucket index.
01893        *  @return  A read/write local iterator.
01894        */
01895       local_iterator
01896       begin(size_type __n)
01897       { return _M_h.begin(__n); }
01898 
01899       //@{
01900       /**
01901        *  @brief  Returns a read-only (constant) iterator pointing to the first
01902        *         bucket element.
01903        *  @param  __n The bucket index.
01904        *  @return  A read-only local iterator.
01905        */
01906       const_local_iterator
01907       begin(size_type __n) const
01908       { return _M_h.begin(__n); }
01909 
01910       const_local_iterator
01911       cbegin(size_type __n) const
01912       { return _M_h.cbegin(__n); }
01913       //@}
01914 
01915       /**
01916        *  @brief  Returns a read/write iterator pointing to one past the last
01917        *         bucket elements.
01918        *  @param  __n The bucket index.
01919        *  @return  A read/write local iterator.
01920        */
01921       local_iterator
01922       end(size_type __n)
01923       { return _M_h.end(__n); }
01924 
01925       //@{
01926       /**
01927        *  @brief  Returns a read-only (constant) iterator pointing to one past
01928        *         the last bucket elements.
01929        *  @param  __n The bucket index.
01930        *  @return  A read-only local iterator.
01931        */
01932       const_local_iterator
01933       end(size_type __n) const
01934       { return _M_h.end(__n); }
01935 
01936       const_local_iterator
01937       cend(size_type __n) const
01938       { return _M_h.cend(__n); }
01939       //@}
01940 
01941       // hash policy.
01942 
01943       /// Returns the average number of elements per bucket.
01944       float
01945       load_factor() const noexcept
01946       { return _M_h.load_factor(); }
01947 
01948       /// Returns a positive number that the %unordered_multimap tries to keep
01949       /// the load factor less than or equal to.
01950       float
01951       max_load_factor() const noexcept
01952       { return _M_h.max_load_factor(); }
01953 
01954       /**
01955        *  @brief  Change the %unordered_multimap maximum load factor.
01956        *  @param  __z The new maximum load factor.
01957        */
01958       void
01959       max_load_factor(float __z)
01960       { _M_h.max_load_factor(__z); }
01961 
01962       /**
01963        *  @brief  May rehash the %unordered_multimap.
01964        *  @param  __n The new number of buckets.
01965        *
01966        *  Rehash will occur only if the new number of buckets respect the
01967        *  %unordered_multimap maximum load factor.
01968        */
01969       void
01970       rehash(size_type __n)
01971       { _M_h.rehash(__n); }
01972 
01973       /**
01974        *  @brief  Prepare the %unordered_multimap for a specified number of
01975        *          elements.
01976        *  @param  __n Number of elements required.
01977        *
01978        *  Same as rehash(ceil(n / max_load_factor())).
01979        */
01980       void
01981       reserve(size_type __n)
01982       { _M_h.reserve(__n); }
01983 
01984       template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
01985                typename _Alloc1>
01986         friend bool
01987         operator==(const unordered_multimap<_Key1, _Tp1,
01988                                             _Hash1, _Pred1, _Alloc1>&,
01989                    const unordered_multimap<_Key1, _Tp1,
01990                                             _Hash1, _Pred1, _Alloc1>&);
01991     };
01992 
01993 #if __cpp_deduction_guides >= 201606
01994 
01995   template<typename _InputIterator,
01996            typename _Hash = hash<__iter_key_t<_InputIterator>>,
01997            typename _Pred = equal_to<__iter_key_t<_InputIterator>>,
01998            typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>,
01999            typename = _RequireInputIter<_InputIterator>,
02000            typename = _RequireNotAllocatorOrIntegral<_Hash>,
02001            typename = _RequireNotAllocator<_Pred>,
02002            typename = _RequireAllocator<_Allocator>>
02003     unordered_multimap(_InputIterator, _InputIterator,
02004                        unordered_multimap<int, int>::size_type = {},
02005                        _Hash = _Hash(), _Pred = _Pred(),
02006                        _Allocator = _Allocator())
02007     -> unordered_multimap<__iter_key_t<_InputIterator>,
02008                           __iter_val_t<_InputIterator>, _Hash, _Pred,
02009                           _Allocator>;
02010 
02011   template<typename _Key, typename _Tp, typename _Hash = hash<_Key>,
02012            typename _Pred = equal_to<_Key>,
02013            typename _Allocator = allocator<pair<const _Key, _Tp>>,
02014            typename = _RequireNotAllocatorOrIntegral<_Hash>,
02015            typename = _RequireNotAllocator<_Pred>,
02016            typename = _RequireAllocator<_Allocator>>
02017     unordered_multimap(initializer_list<pair<_Key, _Tp>>,
02018                        unordered_multimap<int, int>::size_type = {},
02019                        _Hash = _Hash(), _Pred = _Pred(),
02020                        _Allocator = _Allocator())
02021     -> unordered_multimap<_Key, _Tp, _Hash, _Pred, _Allocator>;
02022 
02023   template<typename _InputIterator, typename _Allocator,
02024            typename = _RequireInputIter<_InputIterator>,
02025            typename = _RequireAllocator<_Allocator>>
02026     unordered_multimap(_InputIterator, _InputIterator,
02027                        unordered_multimap<int, int>::size_type, _Allocator)
02028     -> unordered_multimap<__iter_key_t<_InputIterator>,
02029                           __iter_val_t<_InputIterator>,
02030                           hash<__iter_key_t<_InputIterator>>,
02031                           equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
02032 
02033   template<typename _InputIterator, typename _Allocator,
02034            typename = _RequireInputIter<_InputIterator>,
02035            typename = _RequireAllocator<_Allocator>>
02036     unordered_multimap(_InputIterator, _InputIterator, _Allocator)
02037     -> unordered_multimap<__iter_key_t<_InputIterator>,
02038                           __iter_val_t<_InputIterator>,
02039                           hash<__iter_key_t<_InputIterator>>,
02040                           equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
02041 
02042   template<typename _InputIterator, typename _Hash, typename _Allocator,
02043            typename = _RequireInputIter<_InputIterator>,
02044            typename = _RequireNotAllocatorOrIntegral<_Hash>,
02045            typename = _RequireAllocator<_Allocator>>
02046     unordered_multimap(_InputIterator, _InputIterator,
02047                        unordered_multimap<int, int>::size_type, _Hash,
02048                        _Allocator)
02049     -> unordered_multimap<__iter_key_t<_InputIterator>,
02050                           __iter_val_t<_InputIterator>, _Hash,
02051                           equal_to<__iter_key_t<_InputIterator>>, _Allocator>;
02052 
02053   template<typename _Key, typename _Tp, typename _Allocator,
02054            typename = _RequireAllocator<_Allocator>>
02055     unordered_multimap(initializer_list<pair<_Key, _Tp>>,
02056                        unordered_multimap<int, int>::size_type,
02057                        _Allocator)
02058     -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
02059 
02060   template<typename _Key, typename _Tp, typename _Allocator,
02061            typename = _RequireAllocator<_Allocator>>
02062     unordered_multimap(initializer_list<pair<_Key, _Tp>>, _Allocator)
02063     -> unordered_multimap<_Key, _Tp, hash<_Key>, equal_to<_Key>, _Allocator>;
02064 
02065   template<typename _Key, typename _Tp, typename _Hash, typename _Allocator,
02066            typename = _RequireNotAllocatorOrIntegral<_Hash>,
02067            typename = _RequireAllocator<_Allocator>>
02068     unordered_multimap(initializer_list<pair<_Key, _Tp>>,
02069                        unordered_multimap<int, int>::size_type,
02070                        _Hash, _Allocator)
02071     -> unordered_multimap<_Key, _Tp, _Hash, equal_to<_Key>, _Allocator>;
02072 
02073 #endif
02074 
02075   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
02076     inline void
02077     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
02078          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
02079     noexcept(noexcept(__x.swap(__y)))
02080     { __x.swap(__y); }
02081 
02082   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
02083     inline void
02084     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
02085          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
02086     noexcept(noexcept(__x.swap(__y)))
02087     { __x.swap(__y); }
02088 
02089   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
02090     inline bool
02091     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
02092                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
02093     { return __x._M_h._M_equal(__y._M_h); }
02094 
02095   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
02096     inline bool
02097     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
02098                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
02099     { return !(__x == __y); }
02100 
02101   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
02102     inline bool
02103     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
02104                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
02105     { return __x._M_h._M_equal(__y._M_h); }
02106 
02107   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
02108     inline bool
02109     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
02110                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
02111     { return !(__x == __y); }
02112 
02113 _GLIBCXX_END_NAMESPACE_CONTAINER
02114 
02115 #if __cplusplus > 201402L
02116   // Allow std::unordered_map access to internals of compatible maps.
02117   template<typename _Key, typename _Val, typename _Hash1, typename _Eq1,
02118            typename _Alloc, typename _Hash2, typename _Eq2>
02119     struct _Hash_merge_helper<
02120       _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>,
02121       _Hash2, _Eq2>
02122     {
02123     private:
02124       template<typename... _Tp>
02125         using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
02126       template<typename... _Tp>
02127         using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
02128 
02129       friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>;
02130 
02131       static auto&
02132       _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
02133       { return __map._M_h; }
02134 
02135       static auto&
02136       _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
02137       { return __map._M_h; }
02138     };
02139 
02140   // Allow std::unordered_multimap access to internals of compatible maps.
02141   template<typename _Key, typename _Val, typename _Hash1, typename _Eq1,
02142            typename _Alloc, typename _Hash2, typename _Eq2>
02143     struct _Hash_merge_helper<
02144       _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>,
02145       _Hash2, _Eq2>
02146     {
02147     private:
02148       template<typename... _Tp>
02149         using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
02150       template<typename... _Tp>
02151         using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
02152 
02153       friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>;
02154 
02155       static auto&
02156       _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
02157       { return __map._M_h; }
02158 
02159       static auto&
02160       _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
02161       { return __map._M_h; }
02162     };
02163 #endif // C++17
02164 
02165 _GLIBCXX_END_NAMESPACE_VERSION
02166 } // namespace std
02167 
02168 #endif /* _UNORDERED_MAP_H */