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