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