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