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