LCOV - code coverage report
Current view: top level - usr/include/c++/7/bits - unordered_map.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 15 17 88.2 %
Date: 2020-10-15 20:26:03 Functions: 9 10 90.0 %

          Line data    Source code
       1             : // unordered_map implementation -*- C++ -*-
       2             : 
       3             : // Copyright (C) 2010-2017 Free Software Foundation, Inc.
       4             : //
       5             : // This file is part of the GNU ISO C++ Library.  This library is free
       6             : // software; you can redistribute it and/or modify it under the
       7             : // terms of the GNU General Public License as published by the
       8             : // Free Software Foundation; either version 3, or (at your option)
       9             : // any later version.
      10             : 
      11             : // This library is distributed in the hope that it will be useful,
      12             : // but WITHOUT ANY WARRANTY; without even the implied warranty of
      13             : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      14             : // GNU General Public License for more details.
      15             : 
      16             : // Under Section 7 of GPL version 3, you are granted additional
      17             : // permissions described in the GCC Runtime Library Exception, version
      18             : // 3.1, as published by the Free Software Foundation.
      19             : 
      20             : // You should have received a copy of the GNU General Public License and
      21             : // a copy of the GCC Runtime Library Exception along with this program;
      22             : // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
      23             : // <http://www.gnu.org/licenses/>.
      24             : 
      25             : /** @file bits/unordered_map.h
      26             :  *  This is an internal header file, included by other library headers.
      27             :  *  Do not attempt to use it directly. @headername{unordered_map}
      28             :  */
      29             : 
      30             : #ifndef _UNORDERED_MAP_H
      31             : #define _UNORDERED_MAP_H
      32             : 
      33             : namespace std _GLIBCXX_VISIBILITY(default)
      34             : {
      35             : _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
      36             : 
      37             :   /// Base types for unordered_map.
      38             :   template<bool _Cache>
      39             :     using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>;
      40             : 
      41             :   template<typename _Key,
      42             :            typename _Tp,
      43             :            typename _Hash = hash<_Key>,
      44             :            typename _Pred = std::equal_to<_Key>,
      45             :            typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
      46             :            typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>>
      47             :     using __umap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>,
      48             :                                         _Alloc, __detail::_Select1st,
      49             :                                         _Pred, _Hash,
      50             :                                         __detail::_Mod_range_hashing,
      51             :                                         __detail::_Default_ranged_hash,
      52             :                                         __detail::_Prime_rehash_policy, _Tr>;
      53             : 
      54             :   /// Base types for unordered_multimap.
      55             :   template<bool _Cache>
      56             :     using __ummap_traits = __detail::_Hashtable_traits<_Cache, false, false>;
      57             : 
      58             :   template<typename _Key,
      59             :            typename _Tp,
      60             :            typename _Hash = hash<_Key>,
      61             :            typename _Pred = std::equal_to<_Key>,
      62             :            typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
      63             :            typename _Tr = __ummap_traits<__cache_default<_Key, _Hash>::value>>
      64             :     using __ummap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>,
      65             :                                          _Alloc, __detail::_Select1st,
      66             :                                          _Pred, _Hash,
      67             :                                          __detail::_Mod_range_hashing,
      68             :                                          __detail::_Default_ranged_hash,
      69             :                                          __detail::_Prime_rehash_policy, _Tr>;
      70             : 
      71             :   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
      72             :     class unordered_multimap;
      73             : 
      74             :   /**
      75             :    *  @brief A standard container composed of unique keys (containing
      76             :    *  at most one of each key value) that associates values of another type
      77             :    *  with the keys.
      78             :    *
      79             :    *  @ingroup unordered_associative_containers
      80             :    *
      81             :    *  @tparam  _Key    Type of key objects.
      82             :    *  @tparam  _Tp     Type of mapped objects.
      83             :    *  @tparam  _Hash   Hashing function object type, defaults to hash<_Value>.
      84             :    *  @tparam  _Pred   Predicate function object type, defaults
      85             :    *                   to equal_to<_Value>.
      86             :    *  @tparam  _Alloc  Allocator type, defaults to 
      87             :    *                   std::allocator<std::pair<const _Key, _Tp>>.
      88             :    *
      89             :    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
      90             :    *  <a href="tables.html#xx">unordered associative container</a>
      91             :    *
      92             :    * The resulting value type of the container is std::pair<const _Key, _Tp>.
      93             :    *
      94             :    *  Base is _Hashtable, dispatched at compile time via template
      95             :    *  alias __umap_hashtable.
      96             :    */
      97             :   template<class _Key, class _Tp,
      98             :            class _Hash = hash<_Key>,
      99             :            class _Pred = std::equal_to<_Key>,
     100             :            class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
     101          21 :     class unordered_map
     102             :     {
     103             :       typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
     104             :       _Hashtable _M_h;
     105             : 
     106             :     public:
     107             :       // typedefs:
     108             :       //@{
     109             :       /// Public typedefs.
     110             :       typedef typename _Hashtable::key_type     key_type;
     111             :       typedef typename _Hashtable::value_type   value_type;
     112             :       typedef typename _Hashtable::mapped_type  mapped_type;
     113             :       typedef typename _Hashtable::hasher       hasher;
     114             :       typedef typename _Hashtable::key_equal    key_equal;
     115             :       typedef typename _Hashtable::allocator_type allocator_type;
     116             :       //@}
     117             : 
     118             :       //@{
     119             :       ///  Iterator-related typedefs.
     120             :       typedef typename _Hashtable::pointer              pointer;
     121             :       typedef typename _Hashtable::const_pointer        const_pointer;
     122             :       typedef typename _Hashtable::reference            reference;
     123             :       typedef typename _Hashtable::const_reference      const_reference;
     124             :       typedef typename _Hashtable::iterator             iterator;
     125             :       typedef typename _Hashtable::const_iterator       const_iterator;
     126             :       typedef typename _Hashtable::local_iterator       local_iterator;
     127             :       typedef typename _Hashtable::const_local_iterator const_local_iterator;
     128             :       typedef typename _Hashtable::size_type            size_type;
     129             :       typedef typename _Hashtable::difference_type      difference_type;
     130             :       //@}
     131             : 
     132             : #if __cplusplus > 201402L
     133             :       using node_type = typename _Hashtable::node_type;
     134             :       using insert_return_type = typename _Hashtable::insert_return_type;
     135             : #endif
     136             : 
     137             :       //construct/destroy/copy
     138             : 
     139             :       /// Default constructor.
     140          20 :       unordered_map() = default;
     141             : 
     142             :       /**
     143             :        *  @brief  Default constructor creates no elements.
     144             :        *  @param __n  Minimal initial number of buckets.
     145             :        *  @param __hf  A hash functor.
     146             :        *  @param __eql  A key equality functor.
     147             :        *  @param __a  An allocator object.
     148             :        */
     149             :       explicit
     150             :       unordered_map(size_type __n,
     151             :                     const hasher& __hf = hasher(),
     152             :                     const key_equal& __eql = key_equal(),
     153             :                     const allocator_type& __a = allocator_type())
     154             :       : _M_h(__n, __hf, __eql, __a)
     155             :       { }
     156             : 
     157             :       /**
     158             :        *  @brief  Builds an %unordered_map from a range.
     159             :        *  @param  __first  An input iterator.
     160             :        *  @param  __last  An input iterator.
     161             :        *  @param __n  Minimal initial number of buckets.
     162             :        *  @param __hf  A hash functor.
     163             :        *  @param __eql  A key equality functor.
     164             :        *  @param __a  An allocator object.
     165             :        *
     166             :        *  Create an %unordered_map consisting of copies of the elements from
     167             :        *  [__first,__last).  This is linear in N (where N is
     168             :        *  distance(__first,__last)).
     169             :        */
     170             :       template<typename _InputIterator>
     171             :         unordered_map(_InputIterator __first, _InputIterator __last,
     172             :                       size_type __n = 0,
     173             :                       const hasher& __hf = hasher(),
     174             :                       const key_equal& __eql = key_equal(),
     175             :                       const allocator_type& __a = allocator_type())
     176             :         : _M_h(__first, __last, __n, __hf, __eql, __a)
     177             :         { }
     178             : 
     179             :       /// Copy constructor.
     180             :       unordered_map(const unordered_map&) = default;
     181             : 
     182             :       /// Move constructor.
     183             :       unordered_map(unordered_map&&) = default;
     184             : 
     185             :       /**
     186             :        *  @brief Creates an %unordered_map with no elements.
     187             :        *  @param __a An allocator object.
     188             :        */
     189             :       explicit
     190             :       unordered_map(const allocator_type& __a)
     191             :         : _M_h(__a)
     192             :       { }
     193             : 
     194             :       /*
     195             :        *  @brief Copy constructor with allocator argument.
     196             :        * @param  __uset  Input %unordered_map to copy.
     197             :        * @param  __a  An allocator object.
     198             :        */
     199             :       unordered_map(const unordered_map& __umap,
     200             :                     const allocator_type& __a)
     201             :       : _M_h(__umap._M_h, __a)
     202             :       { }
     203             : 
     204             :       /*
     205             :        *  @brief  Move constructor with allocator argument.
     206             :        *  @param  __uset Input %unordered_map to move.
     207             :        *  @param  __a    An allocator object.
     208             :        */
     209             :       unordered_map(unordered_map&& __umap,
     210             :                     const allocator_type& __a)
     211             :       : _M_h(std::move(__umap._M_h), __a)
     212             :       { }
     213             : 
     214             :       /**
     215             :        *  @brief  Builds an %unordered_map from an initializer_list.
     216             :        *  @param  __l  An initializer_list.
     217             :        *  @param __n  Minimal initial number of buckets.
     218             :        *  @param __hf  A hash functor.
     219             :        *  @param __eql  A key equality functor.
     220             :        *  @param  __a  An allocator object.
     221             :        *
     222             :        *  Create an %unordered_map consisting of copies of the elements in the
     223             :        *  list. This is linear in N (where N is @a __l.size()).
     224             :        */
     225           1 :       unordered_map(initializer_list<value_type> __l,
     226             :                     size_type __n = 0,
     227             :                     const hasher& __hf = hasher(),
     228             :                     const key_equal& __eql = key_equal(),
     229             :                     const allocator_type& __a = allocator_type())
     230           1 :       : _M_h(__l, __n, __hf, __eql, __a)
     231           1 :       { }
     232             : 
     233             :       unordered_map(size_type __n, const allocator_type& __a)
     234             :       : unordered_map(__n, hasher(), key_equal(), __a)
     235             :       { }
     236             : 
     237             :       unordered_map(size_type __n, const hasher& __hf,
     238             :                     const allocator_type& __a)
     239             :       : unordered_map(__n, __hf, key_equal(), __a)
     240             :       { }
     241             : 
     242             :       template<typename _InputIterator>
     243             :         unordered_map(_InputIterator __first, _InputIterator __last,
     244             :                       size_type __n,
     245             :                       const allocator_type& __a)
     246             :         : unordered_map(__first, __last, __n, hasher(), key_equal(), __a)
     247             :         { }
     248             : 
     249             :       template<typename _InputIterator>
     250             :         unordered_map(_InputIterator __first, _InputIterator __last,
     251             :                       size_type __n, const hasher& __hf,
     252             :                       const allocator_type& __a)
     253             :           : unordered_map(__first, __last, __n, __hf, key_equal(), __a)
     254             :         { }
     255             : 
     256             :       unordered_map(initializer_list<value_type> __l,
     257             :                     size_type __n,
     258             :                     const allocator_type& __a)
     259             :       : unordered_map(__l, __n, hasher(), key_equal(), __a)
     260             :       { }
     261             : 
     262             :       unordered_map(initializer_list<value_type> __l,
     263             :                     size_type __n, const hasher& __hf,
     264             :                     const allocator_type& __a)
     265             :       : unordered_map(__l, __n, __hf, key_equal(), __a)
     266             :       { }
     267             : 
     268             :       /// Copy assignment operator.
     269             :       unordered_map&
     270             :       operator=(const unordered_map&) = default;
     271             : 
     272             :       /// Move assignment operator.
     273             :       unordered_map&
     274             :       operator=(unordered_map&&) = default;
     275             : 
     276             :       /**
     277             :        *  @brief  %Unordered_map list assignment operator.
     278             :        *  @param  __l  An initializer_list.
     279             :        *
     280             :        *  This function fills an %unordered_map with copies of the elements in
     281             :        *  the initializer list @a __l.
     282             :        *
     283             :        *  Note that the assignment completely changes the %unordered_map and
     284             :        *  that the resulting %unordered_map's size is the same as the number
     285             :        *  of elements assigned.
     286             :        */
     287             :       unordered_map&
     288             :       operator=(initializer_list<value_type> __l)
     289             :       {
     290             :         _M_h = __l;
     291             :         return *this;
     292             :       }
     293             : 
     294             :       ///  Returns the allocator object used by the %unordered_map.
     295             :       allocator_type
     296             :       get_allocator() const noexcept
     297             :       { return _M_h.get_allocator(); }
     298             : 
     299             :       // size and capacity:
     300             : 
     301             :       ///  Returns true if the %unordered_map is empty.
     302             :       bool
     303             :       empty() const noexcept
     304             :       { return _M_h.empty(); }
     305             : 
     306             :       ///  Returns the size of the %unordered_map.
     307             :       size_type
     308             :       size() const noexcept
     309             :       { return _M_h.size(); }
     310             : 
     311             :       ///  Returns the maximum size of the %unordered_map.
     312             :       size_type
     313             :       max_size() const noexcept
     314             :       { return _M_h.max_size(); }
     315             : 
     316             :       // iterators.
     317             : 
     318             :       /**
     319             :        *  Returns a read/write iterator that points to the first element in the
     320             :        *  %unordered_map.
     321             :        */
     322             :       iterator
     323             :       begin() noexcept
     324             :       { return _M_h.begin(); }
     325             : 
     326             :       //@{
     327             :       /**
     328             :        *  Returns a read-only (constant) iterator that points to the first
     329             :        *  element in the %unordered_map.
     330             :        */
     331             :       const_iterator
     332             :       begin() const noexcept
     333             :       { return _M_h.begin(); }
     334             : 
     335             :       const_iterator
     336             :       cbegin() const noexcept
     337             :       { return _M_h.begin(); }
     338             :       //@}
     339             : 
     340             :       /**
     341             :        *  Returns a read/write iterator that points one past the last element in
     342             :        *  the %unordered_map.
     343             :        */
     344             :       iterator
     345          10 :       end() noexcept
     346          10 :       { return _M_h.end(); }
     347             : 
     348             :       //@{
     349             :       /**
     350             :        *  Returns a read-only (constant) iterator that points one past the last
     351             :        *  element in the %unordered_map.
     352             :        */
     353             :       const_iterator
     354             :       end() const noexcept
     355             :       { return _M_h.end(); }
     356             : 
     357             :       const_iterator
     358             :       cend() const noexcept
     359             :       { return _M_h.end(); }
     360             :       //@}
     361             : 
     362             :       // modifiers.
     363             : 
     364             :       /**
     365             :        *  @brief Attempts to build and insert a std::pair into the
     366             :        *  %unordered_map.
     367             :        *
     368             :        *  @param __args  Arguments used to generate a new pair instance (see
     369             :        *                std::piecewise_contruct for passing arguments to each
     370             :        *                part of the pair constructor).
     371             :        *
     372             :        *  @return  A pair, of which the first element is an iterator that points
     373             :        *           to the possibly inserted pair, and the second is a bool that
     374             :        *           is true if the pair was actually inserted.
     375             :        *
     376             :        *  This function attempts to build and insert a (key, value) %pair into
     377             :        *  the %unordered_map.
     378             :        *  An %unordered_map relies on unique keys and thus a %pair is only
     379             :        *  inserted if its first element (the key) is not already present in the
     380             :        *  %unordered_map.
     381             :        *
     382             :        *  Insertion requires amortized constant time.
     383             :        */
     384             :       template<typename... _Args>
     385             :         std::pair<iterator, bool>
     386             :         emplace(_Args&&... __args)
     387             :         { return _M_h.emplace(std::forward<_Args>(__args)...); }
     388             : 
     389             :       /**
     390             :        *  @brief Attempts to build and insert a std::pair into the
     391             :        *  %unordered_map.
     392             :        *
     393             :        *  @param  __pos  An iterator that serves as a hint as to where the pair
     394             :        *                should be inserted.
     395             :        *  @param  __args  Arguments used to generate a new pair instance (see
     396             :        *                 std::piecewise_contruct for passing arguments to each
     397             :        *                 part of the pair constructor).
     398             :        *  @return An iterator that points to the element with key of the
     399             :        *          std::pair built from @a __args (may or may not be that
     400             :        *          std::pair).
     401             :        *
     402             :        *  This function is not concerned about whether the insertion took place,
     403             :        *  and thus does not return a boolean like the single-argument emplace()
     404             :        *  does.
     405             :        *  Note that the first parameter is only a hint and can potentially
     406             :        *  improve the performance of the insertion process. A bad hint would
     407             :        *  cause no gains in efficiency.
     408             :        *
     409             :        *  See
     410             :        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
     411             :        *  for more on @a hinting.
     412             :        *
     413             :        *  Insertion requires amortized constant time.
     414             :        */
     415             :       template<typename... _Args>
     416             :         iterator
     417             :         emplace_hint(const_iterator __pos, _Args&&... __args)
     418             :         { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
     419             : 
     420             : #if __cplusplus > 201402L
     421             :       /// Extract a node.
     422             :       node_type
     423             :       extract(const_iterator __pos)
     424             :       {
     425             :         __glibcxx_assert(__pos != end());
     426             :         return _M_h.extract(__pos);
     427             :       }
     428             : 
     429             :       /// Extract a node.
     430             :       node_type
     431             :       extract(const key_type& __key)
     432             :       { return _M_h.extract(__key); }
     433             : 
     434             :       /// Re-insert an extracted node.
     435             :       insert_return_type
     436             :       insert(node_type&& __nh)
     437             :       { return _M_h._M_reinsert_node(std::move(__nh)); }
     438             : 
     439             :       /// Re-insert an extracted node.
     440             :       iterator
     441             :       insert(const_iterator, node_type&& __nh)
     442             :       { return _M_h._M_reinsert_node(std::move(__nh)).position; }
     443             : 
     444             : #define __cpp_lib_unordered_map_try_emplace 201411
     445             :       /**
     446             :        *  @brief Attempts to build and insert a std::pair into the
     447             :        *  %unordered_map.
     448             :        *
     449             :        *  @param __k    Key to use for finding a possibly existing pair in
     450             :        *                the unordered_map.
     451             :        *  @param __args  Arguments used to generate the .second for a 
     452             :        *                new pair instance.
     453             :        *
     454             :        *  @return  A pair, of which the first element is an iterator that points
     455             :        *           to the possibly inserted pair, and the second is a bool that
     456             :        *           is true if the pair was actually inserted.
     457             :        *
     458             :        *  This function attempts to build and insert a (key, value) %pair into
     459             :        *  the %unordered_map.
     460             :        *  An %unordered_map relies on unique keys and thus a %pair is only
     461             :        *  inserted if its first element (the key) is not already present in the
     462             :        *  %unordered_map.
     463             :        *  If a %pair is not inserted, this function has no effect.
     464             :        *
     465             :        *  Insertion requires amortized constant time.
     466             :        */
     467             :       template <typename... _Args>
     468             :         pair<iterator, bool>
     469             :         try_emplace(const key_type& __k, _Args&&... __args)
     470             :         {
     471             :           iterator __i = find(__k);
     472             :           if (__i == end())
     473             :             {
     474             :               __i = emplace(std::piecewise_construct,
     475             :                             std::forward_as_tuple(__k),
     476             :                             std::forward_as_tuple(
     477             :                               std::forward<_Args>(__args)...))
     478             :                 .first;
     479             :               return {__i, true};
     480             :             }
     481             :           return {__i, false};
     482             :         }
     483             : 
     484             :       // move-capable overload
     485             :       template <typename... _Args>
     486             :         pair<iterator, bool>
     487             :         try_emplace(key_type&& __k, _Args&&... __args)
     488             :         {
     489             :           iterator __i = find(__k);
     490             :           if (__i == end())
     491             :             {
     492             :               __i = emplace(std::piecewise_construct,
     493             :                             std::forward_as_tuple(std::move(__k)),
     494             :                             std::forward_as_tuple(
     495             :                               std::forward<_Args>(__args)...))
     496             :                 .first;
     497             :               return {__i, true};
     498             :             }
     499             :           return {__i, false};
     500             :         }
     501             : 
     502             :       /**
     503             :        *  @brief Attempts to build and insert a std::pair into the
     504             :        *  %unordered_map.
     505             :        *
     506             :        *  @param  __hint  An iterator that serves as a hint as to where the pair
     507             :        *                should be inserted.
     508             :        *  @param __k    Key to use for finding a possibly existing pair in
     509             :        *                the unordered_map.
     510             :        *  @param __args  Arguments used to generate the .second for a 
     511             :        *                new pair instance.
     512             :        *  @return An iterator that points to the element with key of the
     513             :        *          std::pair built from @a __args (may or may not be that
     514             :        *          std::pair).
     515             :        *
     516             :        *  This function is not concerned about whether the insertion took place,
     517             :        *  and thus does not return a boolean like the single-argument emplace()
     518             :        *  does. However, if insertion did not take place,
     519             :        *  this function has no effect.
     520             :        *  Note that the first parameter is only a hint and can potentially
     521             :        *  improve the performance of the insertion process. A bad hint would
     522             :        *  cause no gains in efficiency.
     523             :        *
     524             :        *  See
     525             :        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
     526             :        *  for more on @a hinting.
     527             :        *
     528             :        *  Insertion requires amortized constant time.
     529             :        */
     530             :       template <typename... _Args>
     531             :         iterator
     532             :         try_emplace(const_iterator __hint, const key_type& __k,
     533             :                     _Args&&... __args)
     534             :         {
     535             :           iterator __i = find(__k);
     536             :           if (__i == end())
     537             :             __i = emplace_hint(__hint, std::piecewise_construct,
     538             :                                std::forward_as_tuple(__k),
     539             :                                std::forward_as_tuple(
     540             :                                  std::forward<_Args>(__args)...));
     541             :           return __i;
     542             :         }
     543             : 
     544             :       // move-capable overload
     545             :       template <typename... _Args>
     546             :         iterator
     547             :         try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
     548             :         {
     549             :           iterator __i = find(__k);
     550             :           if (__i == end())
     551             :             __i = emplace_hint(__hint, std::piecewise_construct,
     552             :                                std::forward_as_tuple(std::move(__k)),
     553             :                                std::forward_as_tuple(
     554             :                                  std::forward<_Args>(__args)...));
     555             :           return __i;
     556             :         }
     557             : #endif // C++17
     558             : 
     559             :       //@{
     560             :       /**
     561             :        *  @brief Attempts to insert a std::pair into the %unordered_map.
     562             : 
     563             :        *  @param __x Pair to be inserted (see std::make_pair for easy
     564             :        *             creation of pairs).
     565             :        *
     566             :        *  @return  A pair, of which the first element is an iterator that 
     567             :        *           points to the possibly inserted pair, and the second is 
     568             :        *           a bool that is true if the pair was actually inserted.
     569             :        *
     570             :        *  This function attempts to insert a (key, value) %pair into the
     571             :        *  %unordered_map. An %unordered_map relies on unique keys and thus a
     572             :        *  %pair is only inserted if its first element (the key) is not already
     573             :        *  present in the %unordered_map.
     574             :        *
     575             :        *  Insertion requires amortized constant time.
     576             :        */
     577             :       std::pair<iterator, bool>
     578             :       insert(const value_type& __x)
     579             :       { return _M_h.insert(__x); }
     580             : 
     581             :       // _GLIBCXX_RESOLVE_LIB_DEFECTS
     582             :       // 2354. Unnecessary copying when inserting into maps with braced-init
     583             :       std::pair<iterator, bool>
     584             :       insert(value_type&& __x)
     585             :       { return _M_h.insert(std::move(__x)); }
     586             : 
     587             :       template<typename _Pair>
     588             :         __enable_if_t<is_constructible<value_type, _Pair&&>::value,
     589             :                       pair<iterator, bool>>
     590             :         insert(_Pair&& __x)
     591             :         { return _M_h.emplace(std::forward<_Pair>(__x)); }
     592             :       //@}
     593             : 
     594             :       //@{
     595             :       /**
     596             :        *  @brief Attempts to insert a std::pair into the %unordered_map.
     597             :        *  @param  __hint  An iterator that serves as a hint as to where the
     598             :        *                 pair should be inserted.
     599             :        *  @param  __x  Pair to be inserted (see std::make_pair for easy creation
     600             :        *               of pairs).
     601             :        *  @return An iterator that points to the element with key of
     602             :        *           @a __x (may or may not be the %pair passed in).
     603             :        *
     604             :        *  This function is not concerned about whether the insertion took place,
     605             :        *  and thus does not return a boolean like the single-argument insert()
     606             :        *  does.  Note that the first parameter is only a hint and can
     607             :        *  potentially improve the performance of the insertion process.  A bad
     608             :        *  hint would cause no gains in efficiency.
     609             :        *
     610             :        *  See
     611             :        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
     612             :        *  for more on @a hinting.
     613             :        *
     614             :        *  Insertion requires amortized constant time.
     615             :        */
     616             :       iterator
     617             :       insert(const_iterator __hint, const value_type& __x)
     618             :       { return _M_h.insert(__hint, __x); }
     619             : 
     620             :       // _GLIBCXX_RESOLVE_LIB_DEFECTS
     621             :       // 2354. Unnecessary copying when inserting into maps with braced-init
     622             :       iterator
     623             :       insert(const_iterator __hint, value_type&& __x)
     624             :       { return _M_h.insert(__hint, std::move(__x)); }
     625             : 
     626             :       template<typename _Pair>
     627             :         __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
     628             :         insert(const_iterator __hint, _Pair&& __x)
     629             :         { return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
     630             :       //@}
     631             : 
     632             :       /**
     633             :        *  @brief A template function that attempts to insert a range of
     634             :        *  elements.
     635             :        *  @param  __first  Iterator pointing to the start of the range to be
     636             :        *                   inserted.
     637             :        *  @param  __last  Iterator pointing to the end of the range.
     638             :        *
     639             :        *  Complexity similar to that of the range constructor.
     640             :        */
     641             :       template<typename _InputIterator>
     642             :         void
     643             :         insert(_InputIterator __first, _InputIterator __last)
     644             :         { _M_h.insert(__first, __last); }
     645             : 
     646             :       /**
     647             :        *  @brief Attempts to insert a list of elements into the %unordered_map.
     648             :        *  @param  __l  A std::initializer_list<value_type> of elements
     649             :        *               to be inserted.
     650             :        *
     651             :        *  Complexity similar to that of the range constructor.
     652             :        */
     653             :       void
     654             :       insert(initializer_list<value_type> __l)
     655             :       { _M_h.insert(__l); }
     656             : 
     657             : 
     658             : #if __cplusplus > 201402L
     659             : #define __cpp_lib_unordered_map_insertion 201411
     660             :       /**
     661             :        *  @brief Attempts to insert a std::pair into the %unordered_map.
     662             :        *  @param __k    Key to use for finding a possibly existing pair in
     663             :        *                the map.
     664             :        *  @param __obj  Argument used to generate the .second for a pair 
     665             :        *                instance.
     666             :        *
     667             :        *  @return  A pair, of which the first element is an iterator that 
     668             :        *           points to the possibly inserted pair, and the second is 
     669             :        *           a bool that is true if the pair was actually inserted.
     670             :        *
     671             :        *  This function attempts to insert a (key, value) %pair into the
     672             :        *  %unordered_map. An %unordered_map relies on unique keys and thus a
     673             :        *  %pair is only inserted if its first element (the key) is not already
     674             :        *  present in the %unordered_map.
     675             :        *  If the %pair was already in the %unordered_map, the .second of 
     676             :        *  the %pair is assigned from __obj.
     677             :        *
     678             :        *  Insertion requires amortized constant time.
     679             :        */
     680             :       template <typename _Obj>
     681             :         pair<iterator, bool>
     682             :         insert_or_assign(const key_type& __k, _Obj&& __obj)
     683             :         {
     684             :           iterator __i = find(__k);
     685             :           if (__i == end())
     686             :             {
     687             :               __i = emplace(std::piecewise_construct,
     688             :                             std::forward_as_tuple(__k),
     689             :                             std::forward_as_tuple(std::forward<_Obj>(__obj)))
     690             :                 .first;
     691             :               return {__i, true};
     692             :             }
     693             :           (*__i).second = std::forward<_Obj>(__obj);
     694             :           return {__i, false};
     695             :         }
     696             : 
     697             :       // move-capable overload
     698             :       template <typename _Obj>
     699             :         pair<iterator, bool>
     700             :         insert_or_assign(key_type&& __k, _Obj&& __obj)
     701             :         {
     702             :           iterator __i = find(__k);
     703             :           if (__i == end())
     704             :             {
     705             :               __i = emplace(std::piecewise_construct,
     706             :                             std::forward_as_tuple(std::move(__k)),
     707             :                             std::forward_as_tuple(std::forward<_Obj>(__obj)))
     708             :                 .first;
     709             :               return {__i, true};
     710             :             }
     711             :           (*__i).second = std::forward<_Obj>(__obj);
     712             :           return {__i, false};
     713             :         }
     714             : 
     715             :       /**
     716             :        *  @brief Attempts to insert a std::pair into the %unordered_map.
     717             :        *  @param  __hint  An iterator that serves as a hint as to where the
     718             :        *                  pair should be inserted.
     719             :        *  @param __k    Key to use for finding a possibly existing pair in
     720             :        *                the unordered_map.
     721             :        *  @param __obj  Argument used to generate the .second for a pair 
     722             :        *                instance.
     723             :        *  @return An iterator that points to the element with key of
     724             :        *           @a __x (may or may not be the %pair passed in).
     725             :        *
     726             :        *  This function is not concerned about whether the insertion took place,
     727             :        *  and thus does not return a boolean like the single-argument insert()
     728             :        *  does.         
     729             :        *  If the %pair was already in the %unordered map, the .second of
     730             :        *  the %pair is assigned from __obj.
     731             :        *  Note that the first parameter is only a hint and can
     732             :        *  potentially improve the performance of the insertion process.  A bad
     733             :        *  hint would cause no gains in efficiency.
     734             :        *
     735             :        *  See
     736             :        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
     737             :        *  for more on @a hinting.
     738             :        *
     739             :        *  Insertion requires amortized constant time.
     740             :        */
     741             :       template <typename _Obj>
     742             :         iterator
     743             :         insert_or_assign(const_iterator __hint, const key_type& __k,
     744             :                          _Obj&& __obj)
     745             :         {
     746             :           iterator __i = find(__k);
     747             :           if (__i == end())
     748             :             {
     749             :               return emplace_hint(__hint, std::piecewise_construct,
     750             :                                   std::forward_as_tuple(__k),
     751             :                                   std::forward_as_tuple(
     752             :                                     std::forward<_Obj>(__obj)));
     753             :             }
     754             :           (*__i).second = std::forward<_Obj>(__obj);
     755             :           return __i;
     756             :         }
     757             : 
     758             :       // move-capable overload
     759             :       template <typename _Obj>
     760             :         iterator
     761             :         insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
     762             :         {
     763             :           iterator __i = find(__k);
     764             :           if (__i == end())
     765             :             {
     766             :               return emplace_hint(__hint, std::piecewise_construct,
     767             :                                   std::forward_as_tuple(std::move(__k)),
     768             :                                   std::forward_as_tuple(
     769             :                                     std::forward<_Obj>(__obj)));
     770             :             }
     771             :           (*__i).second = std::forward<_Obj>(__obj);
     772             :           return __i;
     773             :         }
     774             : #endif
     775             : 
     776             :       //@{
     777             :       /**
     778             :        *  @brief Erases an element from an %unordered_map.
     779             :        *  @param  __position  An iterator pointing to the element to be erased.
     780             :        *  @return An iterator pointing to the element immediately following
     781             :        *          @a __position prior to the element being erased. If no such
     782             :        *          element exists, end() is returned.
     783             :        *
     784             :        *  This function erases an element, pointed to by the given iterator,
     785             :        *  from an %unordered_map.
     786             :        *  Note that this function only erases the element, and that if the
     787             :        *  element is itself a pointer, the pointed-to memory is not touched in
     788             :        *  any way.  Managing the pointer is the user's responsibility.
     789             :        */
     790             :       iterator
     791             :       erase(const_iterator __position)
     792             :       { return _M_h.erase(__position); }
     793             : 
     794             :       // LWG 2059.
     795             :       iterator
     796           0 :       erase(iterator __position)
     797           0 :       { return _M_h.erase(__position); }
     798             :       //@}
     799             : 
     800             :       /**
     801             :        *  @brief Erases elements according to the provided key.
     802             :        *  @param  __x  Key of element to be erased.
     803             :        *  @return  The number of elements erased.
     804             :        *
     805             :        *  This function erases all the elements located by the given key from
     806             :        *  an %unordered_map. For an %unordered_map the result of this function
     807             :        *  can only be 0 (not present) or 1 (present).
     808             :        *  Note that this function only erases the element, and that if the
     809             :        *  element is itself a pointer, the pointed-to memory is not touched in
     810             :        *  any way.  Managing the pointer is the user's responsibility.
     811             :        */
     812             :       size_type
     813             :       erase(const key_type& __x)
     814             :       { return _M_h.erase(__x); }
     815             : 
     816             :       /**
     817             :        *  @brief Erases a [__first,__last) range of elements from an
     818             :        *  %unordered_map.
     819             :        *  @param  __first  Iterator pointing to the start of the range to be
     820             :        *                  erased.
     821             :        *  @param __last  Iterator pointing to the end of the range to
     822             :        *                be erased.
     823             :        *  @return The iterator @a __last.
     824             :        *
     825             :        *  This function erases a sequence of elements from an %unordered_map.
     826             :        *  Note that this function only erases the elements, and that if
     827             :        *  the element is itself a pointer, the pointed-to memory is not touched
     828             :        *  in any way.  Managing the pointer is the user's responsibility.
     829             :        */
     830             :       iterator
     831             :       erase(const_iterator __first, const_iterator __last)
     832             :       { return _M_h.erase(__first, __last); }
     833             : 
     834             :       /**
     835             :        *  Erases all elements in an %unordered_map.
     836             :        *  Note that this function only erases the elements, and that if the
     837             :        *  elements themselves are pointers, the pointed-to memory is not touched
     838             :        *  in any way.  Managing the pointer is the user's responsibility.
     839             :        */
     840             :       void
     841             :       clear() noexcept
     842             :       { _M_h.clear(); }
     843             : 
     844             :       /**
     845             :        *  @brief  Swaps data with another %unordered_map.
     846             :        *  @param  __x  An %unordered_map of the same element and allocator
     847             :        *  types.
     848             :        *
     849             :        *  This exchanges the elements between two %unordered_map in constant
     850             :        *  time.
     851             :        *  Note that the global std::swap() function is specialized such that
     852             :        *  std::swap(m1,m2) will feed to this function.
     853             :        */
     854             :       void
     855             :       swap(unordered_map& __x)
     856             :       noexcept( noexcept(_M_h.swap(__x._M_h)) )
     857             :       { _M_h.swap(__x._M_h); }
     858             : 
     859             : #if __cplusplus > 201402L
     860             :       template<typename, typename, typename>
     861             :         friend class _Hash_merge_helper;
     862             : 
     863             :       template<typename _H2, typename _P2>
     864             :         void
     865             :         merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
     866             :         {
     867             :           using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
     868             :           _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
     869             :         }
     870             : 
     871             :       template<typename _H2, typename _P2>
     872             :         void
     873             :         merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
     874             :         { merge(__source); }
     875             : 
     876             :       template<typename _H2, typename _P2>
     877             :         void
     878             :         merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
     879             :         {
     880             :           using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
     881             :           _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
     882             :         }
     883             : 
     884             :       template<typename _H2, typename _P2>
     885             :         void
     886             :         merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
     887             :         { merge(__source); }
     888             : #endif // C++17
     889             : 
     890             :       // observers.
     891             : 
     892             :       ///  Returns the hash functor object with which the %unordered_map was
     893             :       ///  constructed.
     894             :       hasher
     895             :       hash_function() const
     896             :       { return _M_h.hash_function(); }
     897             : 
     898             :       ///  Returns the key comparison object with which the %unordered_map was
     899             :       ///  constructed.
     900             :       key_equal
     901             :       key_eq() const
     902             :       { return _M_h.key_eq(); }
     903             : 
     904             :       // lookup.
     905             : 
     906             :       //@{
     907             :       /**
     908             :        *  @brief Tries to locate an element in an %unordered_map.
     909             :        *  @param  __x  Key to be located.
     910             :        *  @return  Iterator pointing to sought-after element, or end() if not
     911             :        *           found.
     912             :        *
     913             :        *  This function takes a key and tries to locate the element with which
     914             :        *  the key matches.  If successful the function returns an iterator
     915             :        *  pointing to the sought after element.  If unsuccessful it returns the
     916             :        *  past-the-end ( @c end() ) iterator.
     917             :        */
     918             :       iterator
     919          10 :       find(const key_type& __x)
     920          10 :       { return _M_h.find(__x); }
     921             : 
     922             :       const_iterator
     923             :       find(const key_type& __x) const
     924             :       { return _M_h.find(__x); }
     925             :       //@}
     926             : 
     927             :       /**
     928             :        *  @brief  Finds the number of elements.
     929             :        *  @param  __x  Key to count.
     930             :        *  @return  Number of elements with specified key.
     931             :        *
     932             :        *  This function only makes sense for %unordered_multimap; for
     933             :        *  %unordered_map the result will either be 0 (not present) or 1
     934             :        *  (present).
     935             :        */
     936             :       size_type
     937         202 :       count(const key_type& __x) const
     938         202 :       { return _M_h.count(__x); }
     939             : 
     940             :       //@{
     941             :       /**
     942             :        *  @brief Finds a subsequence matching given key.
     943             :        *  @param  __x  Key to be located.
     944             :        *  @return  Pair of iterators that possibly points to the subsequence
     945             :        *           matching given key.
     946             :        *
     947             :        *  This function probably only makes sense for %unordered_multimap.
     948             :        */
     949             :       std::pair<iterator, iterator>
     950             :       equal_range(const key_type& __x)
     951             :       { return _M_h.equal_range(__x); }
     952             : 
     953             :       std::pair<const_iterator, const_iterator>
     954             :       equal_range(const key_type& __x) const
     955             :       { return _M_h.equal_range(__x); }
     956             :       //@}
     957             : 
     958             :       //@{
     959             :       /**
     960             :        *  @brief  Subscript ( @c [] ) access to %unordered_map data.
     961             :        *  @param  __k  The key for which data should be retrieved.
     962             :        *  @return  A reference to the data of the (key,data) %pair.
     963             :        *
     964             :        *  Allows for easy lookup with the subscript ( @c [] )operator.  Returns
     965             :        *  data associated with the key specified in subscript.  If the key does
     966             :        *  not exist, a pair with that key is created using default values, which
     967             :        *  is then returned.
     968             :        *
     969             :        *  Lookup requires constant time.
     970             :        */
     971             :       mapped_type&
     972        1194 :       operator[](const key_type& __k)
     973        1194 :       { return _M_h[__k]; }
     974             : 
     975             :       mapped_type&
     976             :       operator[](key_type&& __k)
     977             :       { return _M_h[std::move(__k)]; }
     978             :       //@}
     979             : 
     980             :       //@{
     981             :       /**
     982             :        *  @brief  Access to %unordered_map data.
     983             :        *  @param  __k  The key for which data should be retrieved.
     984             :        *  @return  A reference to the data whose key is equal to @a __k, if
     985             :        *           such a data is present in the %unordered_map.
     986             :        *  @throw  std::out_of_range  If no such data is present.
     987             :        */
     988             :       mapped_type&
     989             :       at(const key_type& __k)
     990             :       { return _M_h.at(__k); }
     991             : 
     992             :       const mapped_type&
     993         200 :       at(const key_type& __k) const
     994         200 :       { return _M_h.at(__k); }
     995             :       //@}
     996             : 
     997             :       // bucket interface.
     998             : 
     999             :       /// Returns the number of buckets of the %unordered_map.
    1000             :       size_type
    1001             :       bucket_count() const noexcept
    1002             :       { return _M_h.bucket_count(); }
    1003             : 
    1004             :       /// Returns the maximum number of buckets of the %unordered_map.
    1005             :       size_type
    1006             :       max_bucket_count() const noexcept
    1007             :       { return _M_h.max_bucket_count(); }
    1008             : 
    1009             :       /*
    1010             :        * @brief  Returns the number of elements in a given bucket.
    1011             :        * @param  __n  A bucket index.
    1012             :        * @return  The number of elements in the bucket.
    1013             :        */
    1014             :       size_type
    1015             :       bucket_size(size_type __n) const
    1016             :       { return _M_h.bucket_size(__n); }
    1017             : 
    1018             :       /*
    1019             :        * @brief  Returns the bucket index of a given element.
    1020             :        * @param  __key  A key instance.
    1021             :        * @return  The key bucket index.
    1022             :        */
    1023             :       size_type
    1024             :       bucket(const key_type& __key) const
    1025             :       { return _M_h.bucket(__key); }
    1026             :       
    1027             :       /**
    1028             :        *  @brief  Returns a read/write iterator pointing to the first bucket
    1029             :        *         element.
    1030             :        *  @param  __n The bucket index.
    1031             :        *  @return  A read/write local iterator.
    1032             :        */
    1033             :       local_iterator
    1034             :       begin(size_type __n)
    1035             :       { return _M_h.begin(__n); }
    1036             : 
    1037             :       //@{
    1038             :       /**
    1039             :        *  @brief  Returns a read-only (constant) iterator pointing to the first
    1040             :        *         bucket element.
    1041             :        *  @param  __n The bucket index.
    1042             :        *  @return  A read-only local iterator.
    1043             :        */
    1044             :       const_local_iterator
    1045             :       begin(size_type __n) const
    1046             :       { return _M_h.begin(__n); }
    1047             : 
    1048             :       const_local_iterator
    1049             :       cbegin(size_type __n) const
    1050             :       { return _M_h.cbegin(__n); }
    1051             :       //@}
    1052             : 
    1053             :       /**
    1054             :        *  @brief  Returns a read/write iterator pointing to one past the last
    1055             :        *         bucket elements.
    1056             :        *  @param  __n The bucket index.
    1057             :        *  @return  A read/write local iterator.
    1058             :        */
    1059             :       local_iterator
    1060             :       end(size_type __n)
    1061             :       { return _M_h.end(__n); }
    1062             : 
    1063             :       //@{
    1064             :       /**
    1065             :        *  @brief  Returns a read-only (constant) iterator pointing to one past
    1066             :        *         the last bucket elements.
    1067             :        *  @param  __n The bucket index.
    1068             :        *  @return  A read-only local iterator.
    1069             :        */
    1070             :       const_local_iterator
    1071             :       end(size_type __n) const
    1072             :       { return _M_h.end(__n); }
    1073             : 
    1074             :       const_local_iterator
    1075             :       cend(size_type __n) const
    1076             :       { return _M_h.cend(__n); }
    1077             :       //@}
    1078             : 
    1079             :       // hash policy.
    1080             : 
    1081             :       /// Returns the average number of elements per bucket.
    1082             :       float
    1083             :       load_factor() const noexcept
    1084             :       { return _M_h.load_factor(); }
    1085             : 
    1086             :       /// Returns a positive number that the %unordered_map tries to keep the
    1087             :       /// load factor less than or equal to.
    1088             :       float
    1089             :       max_load_factor() const noexcept
    1090             :       { return _M_h.max_load_factor(); }
    1091             : 
    1092             :       /**
    1093             :        *  @brief  Change the %unordered_map maximum load factor.
    1094             :        *  @param  __z The new maximum load factor.
    1095             :        */
    1096             :       void
    1097             :       max_load_factor(float __z)
    1098             :       { _M_h.max_load_factor(__z); }
    1099             : 
    1100             :       /**
    1101             :        *  @brief  May rehash the %unordered_map.
    1102             :        *  @param  __n The new number of buckets.
    1103             :        *
    1104             :        *  Rehash will occur only if the new number of buckets respect the
    1105             :        *  %unordered_map maximum load factor.
    1106             :        */
    1107             :       void
    1108             :       rehash(size_type __n)
    1109             :       { _M_h.rehash(__n); }
    1110             : 
    1111             :       /**
    1112             :        *  @brief  Prepare the %unordered_map for a specified number of
    1113             :        *          elements.
    1114             :        *  @param  __n Number of elements required.
    1115             :        *
    1116             :        *  Same as rehash(ceil(n / max_load_factor())).
    1117             :        */
    1118             :       void
    1119             :       reserve(size_type __n)
    1120             :       { _M_h.reserve(__n); }
    1121             : 
    1122             :       template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
    1123             :                typename _Alloc1>
    1124             :         friend bool
    1125             :         operator==(const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&,
    1126             :                    const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&);
    1127             :     };
    1128             : 
    1129             :   /**
    1130             :    *  @brief A standard container composed of equivalent keys
    1131             :    *  (possibly containing multiple of each key value) that associates
    1132             :    *  values of another type with the keys.
    1133             :    *
    1134             :    *  @ingroup unordered_associative_containers
    1135             :    *
    1136             :    *  @tparam  _Key    Type of key objects.
    1137             :    *  @tparam  _Tp     Type of mapped objects.
    1138             :    *  @tparam  _Hash   Hashing function object type, defaults to hash<_Value>.
    1139             :    *  @tparam  _Pred   Predicate function object type, defaults
    1140             :    *                   to equal_to<_Value>.
    1141             :    *  @tparam  _Alloc  Allocator type, defaults to
    1142             :    *                   std::allocator<std::pair<const _Key, _Tp>>.
    1143             :    *
    1144             :    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
    1145             :    *  <a href="tables.html#xx">unordered associative container</a>
    1146             :    *
    1147             :    * The resulting value type of the container is std::pair<const _Key, _Tp>.
    1148             :    *
    1149             :    *  Base is _Hashtable, dispatched at compile time via template
    1150             :    *  alias __ummap_hashtable.
    1151             :    */
    1152             :   template<class _Key, class _Tp,
    1153             :            class _Hash = hash<_Key>,
    1154             :            class _Pred = std::equal_to<_Key>,
    1155             :            class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
    1156             :     class unordered_multimap
    1157             :     {
    1158             :       typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
    1159             :       _Hashtable _M_h;
    1160             : 
    1161             :     public:
    1162             :       // typedefs:
    1163             :       //@{
    1164             :       /// Public typedefs.
    1165             :       typedef typename _Hashtable::key_type     key_type;
    1166             :       typedef typename _Hashtable::value_type   value_type;
    1167             :       typedef typename _Hashtable::mapped_type  mapped_type;
    1168             :       typedef typename _Hashtable::hasher       hasher;
    1169             :       typedef typename _Hashtable::key_equal    key_equal;
    1170             :       typedef typename _Hashtable::allocator_type allocator_type;
    1171             :       //@}
    1172             : 
    1173             :       //@{
    1174             :       ///  Iterator-related typedefs.
    1175             :       typedef typename _Hashtable::pointer              pointer;
    1176             :       typedef typename _Hashtable::const_pointer        const_pointer;
    1177             :       typedef typename _Hashtable::reference            reference;
    1178             :       typedef typename _Hashtable::const_reference      const_reference;
    1179             :       typedef typename _Hashtable::iterator             iterator;
    1180             :       typedef typename _Hashtable::const_iterator       const_iterator;
    1181             :       typedef typename _Hashtable::local_iterator       local_iterator;
    1182             :       typedef typename _Hashtable::const_local_iterator const_local_iterator;
    1183             :       typedef typename _Hashtable::size_type            size_type;
    1184             :       typedef typename _Hashtable::difference_type      difference_type;
    1185             :       //@}
    1186             : 
    1187             : #if __cplusplus > 201402L
    1188             :       using node_type = typename _Hashtable::node_type;
    1189             : #endif
    1190             : 
    1191             :       //construct/destroy/copy
    1192             : 
    1193             :       /// Default constructor.
    1194             :       unordered_multimap() = default;
    1195             : 
    1196             :       /**
    1197             :        *  @brief  Default constructor creates no elements.
    1198             :        *  @param __n  Mnimal initial number of buckets.
    1199             :        *  @param __hf  A hash functor.
    1200             :        *  @param __eql  A key equality functor.
    1201             :        *  @param __a  An allocator object.
    1202             :        */
    1203             :       explicit
    1204             :       unordered_multimap(size_type __n,
    1205             :                          const hasher& __hf = hasher(),
    1206             :                          const key_equal& __eql = key_equal(),
    1207             :                          const allocator_type& __a = allocator_type())
    1208             :       : _M_h(__n, __hf, __eql, __a)
    1209             :       { }
    1210             : 
    1211             :       /**
    1212             :        *  @brief  Builds an %unordered_multimap from a range.
    1213             :        *  @param  __first An input iterator.
    1214             :        *  @param  __last  An input iterator.
    1215             :        *  @param __n      Minimal initial number of buckets.
    1216             :        *  @param __hf     A hash functor.
    1217             :        *  @param __eql    A key equality functor.
    1218             :        *  @param __a      An allocator object.
    1219             :        *
    1220             :        *  Create an %unordered_multimap consisting of copies of the elements
    1221             :        *  from [__first,__last).  This is linear in N (where N is
    1222             :        *  distance(__first,__last)).
    1223             :        */
    1224             :       template<typename _InputIterator>
    1225             :         unordered_multimap(_InputIterator __first, _InputIterator __last,
    1226             :                            size_type __n = 0,
    1227             :                            const hasher& __hf = hasher(),
    1228             :                            const key_equal& __eql = key_equal(),
    1229             :                            const allocator_type& __a = allocator_type())
    1230             :         : _M_h(__first, __last, __n, __hf, __eql, __a)
    1231             :         { }
    1232             : 
    1233             :       /// Copy constructor.
    1234             :       unordered_multimap(const unordered_multimap&) = default;
    1235             : 
    1236             :       /// Move constructor.
    1237             :       unordered_multimap(unordered_multimap&&) = default;
    1238             : 
    1239             :       /**
    1240             :        *  @brief Creates an %unordered_multimap with no elements.
    1241             :        *  @param __a An allocator object.
    1242             :        */
    1243             :       explicit
    1244             :       unordered_multimap(const allocator_type& __a)
    1245             :       : _M_h(__a)
    1246             :       { }
    1247             : 
    1248             :       /*
    1249             :        *  @brief Copy constructor with allocator argument.
    1250             :        * @param  __uset  Input %unordered_multimap to copy.
    1251             :        * @param  __a  An allocator object.
    1252             :        */
    1253             :       unordered_multimap(const unordered_multimap& __ummap,
    1254             :                          const allocator_type& __a)
    1255             :       : _M_h(__ummap._M_h, __a)
    1256             :       { }
    1257             : 
    1258             :       /*
    1259             :        *  @brief  Move constructor with allocator argument.
    1260             :        *  @param  __uset Input %unordered_multimap to move.
    1261             :        *  @param  __a    An allocator object.
    1262             :        */
    1263             :       unordered_multimap(unordered_multimap&& __ummap,
    1264             :                          const allocator_type& __a)
    1265             :       : _M_h(std::move(__ummap._M_h), __a)
    1266             :       { }
    1267             : 
    1268             :       /**
    1269             :        *  @brief  Builds an %unordered_multimap from an initializer_list.
    1270             :        *  @param  __l  An initializer_list.
    1271             :        *  @param __n  Minimal initial number of buckets.
    1272             :        *  @param __hf  A hash functor.
    1273             :        *  @param __eql  A key equality functor.
    1274             :        *  @param  __a  An allocator object.
    1275             :        *
    1276             :        *  Create an %unordered_multimap consisting of copies of the elements in
    1277             :        *  the list. This is linear in N (where N is @a __l.size()).
    1278             :        */
    1279             :       unordered_multimap(initializer_list<value_type> __l,
    1280             :                          size_type __n = 0,
    1281             :                          const hasher& __hf = hasher(),
    1282             :                          const key_equal& __eql = key_equal(),
    1283             :                          const allocator_type& __a = allocator_type())
    1284             :       : _M_h(__l, __n, __hf, __eql, __a)
    1285             :       { }
    1286             : 
    1287             :       unordered_multimap(size_type __n, const allocator_type& __a)
    1288             :       : unordered_multimap(__n, hasher(), key_equal(), __a)
    1289             :       { }
    1290             : 
    1291             :       unordered_multimap(size_type __n, const hasher& __hf,
    1292             :                          const allocator_type& __a)
    1293             :       : unordered_multimap(__n, __hf, key_equal(), __a)
    1294             :       { }
    1295             : 
    1296             :       template<typename _InputIterator>
    1297             :         unordered_multimap(_InputIterator __first, _InputIterator __last,
    1298             :                            size_type __n,
    1299             :                            const allocator_type& __a)
    1300             :         : unordered_multimap(__first, __last, __n, hasher(), key_equal(), __a)
    1301             :         { }
    1302             : 
    1303             :       template<typename _InputIterator>
    1304             :         unordered_multimap(_InputIterator __first, _InputIterator __last,
    1305             :                            size_type __n, const hasher& __hf,
    1306             :                            const allocator_type& __a)
    1307             :         : unordered_multimap(__first, __last, __n, __hf, key_equal(), __a)
    1308             :         { }
    1309             : 
    1310             :       unordered_multimap(initializer_list<value_type> __l,
    1311             :                          size_type __n,
    1312             :                          const allocator_type& __a)
    1313             :       : unordered_multimap(__l, __n, hasher(), key_equal(), __a)
    1314             :       { }
    1315             : 
    1316             :       unordered_multimap(initializer_list<value_type> __l,
    1317             :                          size_type __n, const hasher& __hf,
    1318             :                          const allocator_type& __a)
    1319             :       : unordered_multimap(__l, __n, __hf, key_equal(), __a)
    1320             :       { }
    1321             : 
    1322             :       /// Copy assignment operator.
    1323             :       unordered_multimap&
    1324             :       operator=(const unordered_multimap&) = default;
    1325             : 
    1326             :       /// Move assignment operator.
    1327             :       unordered_multimap&
    1328             :       operator=(unordered_multimap&&) = default;
    1329             : 
    1330             :       /**
    1331             :        *  @brief  %Unordered_multimap list assignment operator.
    1332             :        *  @param  __l  An initializer_list.
    1333             :        *
    1334             :        *  This function fills an %unordered_multimap with copies of the
    1335             :        *  elements in the initializer list @a __l.
    1336             :        *
    1337             :        *  Note that the assignment completely changes the %unordered_multimap
    1338             :        *  and that the resulting %unordered_multimap's size is the same as the
    1339             :        *  number of elements assigned.
    1340             :        */
    1341             :       unordered_multimap&
    1342             :       operator=(initializer_list<value_type> __l)
    1343             :       {
    1344             :         _M_h = __l;
    1345             :         return *this;
    1346             :       }
    1347             : 
    1348             :       ///  Returns the allocator object used by the %unordered_multimap.
    1349             :       allocator_type
    1350             :       get_allocator() const noexcept
    1351             :       { return _M_h.get_allocator(); }
    1352             : 
    1353             :       // size and capacity:
    1354             : 
    1355             :       ///  Returns true if the %unordered_multimap is empty.
    1356             :       bool
    1357             :       empty() const noexcept
    1358             :       { return _M_h.empty(); }
    1359             : 
    1360             :       ///  Returns the size of the %unordered_multimap.
    1361             :       size_type
    1362             :       size() const noexcept
    1363             :       { return _M_h.size(); }
    1364             : 
    1365             :       ///  Returns the maximum size of the %unordered_multimap.
    1366             :       size_type
    1367             :       max_size() const noexcept
    1368             :       { return _M_h.max_size(); }
    1369             : 
    1370             :       // iterators.
    1371             : 
    1372             :       /**
    1373             :        *  Returns a read/write iterator that points to the first element in the
    1374             :        *  %unordered_multimap.
    1375             :        */
    1376             :       iterator
    1377             :       begin() noexcept
    1378             :       { return _M_h.begin(); }
    1379             : 
    1380             :       //@{
    1381             :       /**
    1382             :        *  Returns a read-only (constant) iterator that points to the first
    1383             :        *  element in the %unordered_multimap.
    1384             :        */
    1385             :       const_iterator
    1386             :       begin() const noexcept
    1387             :       { return _M_h.begin(); }
    1388             : 
    1389             :       const_iterator
    1390             :       cbegin() const noexcept
    1391             :       { return _M_h.begin(); }
    1392             :       //@}
    1393             : 
    1394             :       /**
    1395             :        *  Returns a read/write iterator that points one past the last element in
    1396             :        *  the %unordered_multimap.
    1397             :        */
    1398             :       iterator
    1399             :       end() noexcept
    1400             :       { return _M_h.end(); }
    1401             : 
    1402             :       //@{
    1403             :       /**
    1404             :        *  Returns a read-only (constant) iterator that points one past the last
    1405             :        *  element in the %unordered_multimap.
    1406             :        */
    1407             :       const_iterator
    1408             :       end() const noexcept
    1409             :       { return _M_h.end(); }
    1410             : 
    1411             :       const_iterator
    1412             :       cend() const noexcept
    1413             :       { return _M_h.end(); }
    1414             :       //@}
    1415             : 
    1416             :       // modifiers.
    1417             : 
    1418             :       /**
    1419             :        *  @brief Attempts to build and insert a std::pair into the
    1420             :        *  %unordered_multimap.
    1421             :        *
    1422             :        *  @param __args  Arguments used to generate a new pair instance (see
    1423             :        *                std::piecewise_contruct for passing arguments to each
    1424             :        *                part of the pair constructor).
    1425             :        *
    1426             :        *  @return  An iterator that points to the inserted pair.
    1427             :        *
    1428             :        *  This function attempts to build and insert a (key, value) %pair into
    1429             :        *  the %unordered_multimap.
    1430             :        *
    1431             :        *  Insertion requires amortized constant time.
    1432             :        */
    1433             :       template<typename... _Args>
    1434             :         iterator
    1435             :         emplace(_Args&&... __args)
    1436             :         { return _M_h.emplace(std::forward<_Args>(__args)...); }
    1437             : 
    1438             :       /**
    1439             :        *  @brief Attempts to build and insert a std::pair into the
    1440             :        *  %unordered_multimap.
    1441             :        *
    1442             :        *  @param  __pos  An iterator that serves as a hint as to where the pair
    1443             :        *                should be inserted.
    1444             :        *  @param  __args  Arguments used to generate a new pair instance (see
    1445             :        *                 std::piecewise_contruct for passing arguments to each
    1446             :        *                 part of the pair constructor).
    1447             :        *  @return An iterator that points to the element with key of the
    1448             :        *          std::pair built from @a __args.
    1449             :        *
    1450             :        *  Note that the first parameter is only a hint and can potentially
    1451             :        *  improve the performance of the insertion process. A bad hint would
    1452             :        *  cause no gains in efficiency.
    1453             :        *
    1454             :        *  See
    1455             :        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
    1456             :        *  for more on @a hinting.
    1457             :        *
    1458             :        *  Insertion requires amortized constant time.
    1459             :        */
    1460             :       template<typename... _Args>
    1461             :         iterator
    1462             :         emplace_hint(const_iterator __pos, _Args&&... __args)
    1463             :         { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
    1464             : 
    1465             :       //@{
    1466             :       /**
    1467             :        *  @brief Inserts a std::pair into the %unordered_multimap.
    1468             :        *  @param __x Pair to be inserted (see std::make_pair for easy
    1469             :        *             creation of pairs).
    1470             :        *
    1471             :        *  @return  An iterator that points to the inserted pair.
    1472             :        *
    1473             :        *  Insertion requires amortized constant time.
    1474             :        */
    1475             :       iterator
    1476             :       insert(const value_type& __x)
    1477             :       { return _M_h.insert(__x); }
    1478             : 
    1479             :       iterator
    1480             :       insert(value_type&& __x)
    1481             :       { return _M_h.insert(std::move(__x)); }
    1482             : 
    1483             :       template<typename _Pair>
    1484             :         __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
    1485             :         insert(_Pair&& __x)
    1486             :         { return _M_h.emplace(std::forward<_Pair>(__x)); }
    1487             :       //@}
    1488             : 
    1489             :       //@{
    1490             :       /**
    1491             :        *  @brief Inserts a std::pair into the %unordered_multimap.
    1492             :        *  @param  __hint  An iterator that serves as a hint as to where the
    1493             :        *                 pair should be inserted.
    1494             :        *  @param  __x  Pair to be inserted (see std::make_pair for easy creation
    1495             :        *               of pairs).
    1496             :        *  @return An iterator that points to the element with key of
    1497             :        *           @a __x (may or may not be the %pair passed in).
    1498             :        *
    1499             :        *  Note that the first parameter is only a hint and can potentially
    1500             :        *  improve the performance of the insertion process.  A bad hint would
    1501             :        *  cause no gains in efficiency.
    1502             :        *
    1503             :        *  See
    1504             :        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
    1505             :        *  for more on @a hinting.
    1506             :        *
    1507             :        *  Insertion requires amortized constant time.
    1508             :        */
    1509             :       iterator
    1510             :       insert(const_iterator __hint, const value_type& __x)
    1511             :       { return _M_h.insert(__hint, __x); }
    1512             : 
    1513             :       // _GLIBCXX_RESOLVE_LIB_DEFECTS
    1514             :       // 2354. Unnecessary copying when inserting into maps with braced-init
    1515             :       iterator
    1516             :       insert(const_iterator __hint, value_type&& __x)
    1517             :       { return _M_h.insert(__hint, std::move(__x)); }
    1518             : 
    1519             :       template<typename _Pair>
    1520             :         __enable_if_t<is_constructible<value_type, _Pair&&>::value, iterator>
    1521             :         insert(const_iterator __hint, _Pair&& __x)
    1522             :         { return _M_h.emplace_hint(__hint, std::forward<_Pair>(__x)); }
    1523             :       //@}
    1524             : 
    1525             :       /**
    1526             :        *  @brief A template function that attempts to insert a range of
    1527             :        *  elements.
    1528             :        *  @param  __first  Iterator pointing to the start of the range to be
    1529             :        *                   inserted.
    1530             :        *  @param  __last  Iterator pointing to the end of the range.
    1531             :        *
    1532             :        *  Complexity similar to that of the range constructor.
    1533             :        */
    1534             :       template<typename _InputIterator>
    1535             :         void
    1536             :         insert(_InputIterator __first, _InputIterator __last)
    1537             :         { _M_h.insert(__first, __last); }
    1538             : 
    1539             :       /**
    1540             :        *  @brief Attempts to insert a list of elements into the
    1541             :        *  %unordered_multimap.
    1542             :        *  @param  __l  A std::initializer_list<value_type> of elements
    1543             :        *               to be inserted.
    1544             :        *
    1545             :        *  Complexity similar to that of the range constructor.
    1546             :        */
    1547             :       void
    1548             :       insert(initializer_list<value_type> __l)
    1549             :       { _M_h.insert(__l); }
    1550             : 
    1551             : #if __cplusplus > 201402L
    1552             :       /// Extract a node.
    1553             :       node_type
    1554             :       extract(const_iterator __pos)
    1555             :       {
    1556             :         __glibcxx_assert(__pos != end());
    1557             :         return _M_h.extract(__pos);
    1558             :       }
    1559             : 
    1560             :       /// Extract a node.
    1561             :       node_type
    1562             :       extract(const key_type& __key)
    1563             :       { return _M_h.extract(__key); }
    1564             : 
    1565             :       /// Re-insert an extracted node.
    1566             :       iterator
    1567             :       insert(node_type&& __nh)
    1568             :       { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
    1569             : 
    1570             :       /// Re-insert an extracted node.
    1571             :       iterator
    1572             :       insert(const_iterator __hint, node_type&& __nh)
    1573             :       { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
    1574             : #endif // C++17
    1575             : 
    1576             :       //@{
    1577             :       /**
    1578             :        *  @brief Erases an element from an %unordered_multimap.
    1579             :        *  @param  __position  An iterator pointing to the element to be erased.
    1580             :        *  @return An iterator pointing to the element immediately following
    1581             :        *          @a __position prior to the element being erased. If no such
    1582             :        *          element exists, end() is returned.
    1583             :        *
    1584             :        *  This function erases an element, pointed to by the given iterator,
    1585             :        *  from an %unordered_multimap.
    1586             :        *  Note that this function only erases the element, and that if the
    1587             :        *  element is itself a pointer, the pointed-to memory is not touched in
    1588             :        *  any way.  Managing the pointer is the user's responsibility.
    1589             :        */
    1590             :       iterator
    1591             :       erase(const_iterator __position)
    1592             :       { return _M_h.erase(__position); }
    1593             : 
    1594             :       // LWG 2059.
    1595             :       iterator
    1596             :       erase(iterator __position)
    1597             :       { return _M_h.erase(__position); }
    1598             :       //@}
    1599             : 
    1600             :       /**
    1601             :        *  @brief Erases elements according to the provided key.
    1602             :        *  @param  __x  Key of elements to be erased.
    1603             :        *  @return  The number of elements erased.
    1604             :        *
    1605             :        *  This function erases all the elements located by the given key from
    1606             :        *  an %unordered_multimap.
    1607             :        *  Note that this function only erases the element, and that if the
    1608             :        *  element is itself a pointer, the pointed-to memory is not touched in
    1609             :        *  any way.  Managing the pointer is the user's responsibility.
    1610             :        */
    1611             :       size_type
    1612             :       erase(const key_type& __x)
    1613             :       { return _M_h.erase(__x); }
    1614             : 
    1615             :       /**
    1616             :        *  @brief Erases a [__first,__last) range of elements from an
    1617             :        *  %unordered_multimap.
    1618             :        *  @param  __first  Iterator pointing to the start of the range to be
    1619             :        *                  erased.
    1620             :        *  @param __last  Iterator pointing to the end of the range to
    1621             :        *                be erased.
    1622             :        *  @return The iterator @a __last.
    1623             :        *
    1624             :        *  This function erases a sequence of elements from an
    1625             :        *  %unordered_multimap.
    1626             :        *  Note that this function only erases the elements, and that if
    1627             :        *  the element is itself a pointer, the pointed-to memory is not touched
    1628             :        *  in any way.  Managing the pointer is the user's responsibility.
    1629             :        */
    1630             :       iterator
    1631             :       erase(const_iterator __first, const_iterator __last)
    1632             :       { return _M_h.erase(__first, __last); }
    1633             : 
    1634             :       /**
    1635             :        *  Erases all elements in an %unordered_multimap.
    1636             :        *  Note that this function only erases the elements, and that if the
    1637             :        *  elements themselves are pointers, the pointed-to memory is not touched
    1638             :        *  in any way.  Managing the pointer is the user's responsibility.
    1639             :        */
    1640             :       void
    1641             :       clear() noexcept
    1642             :       { _M_h.clear(); }
    1643             : 
    1644             :       /**
    1645             :        *  @brief  Swaps data with another %unordered_multimap.
    1646             :        *  @param  __x  An %unordered_multimap of the same element and allocator
    1647             :        *  types.
    1648             :        *
    1649             :        *  This exchanges the elements between two %unordered_multimap in
    1650             :        *  constant time.
    1651             :        *  Note that the global std::swap() function is specialized such that
    1652             :        *  std::swap(m1,m2) will feed to this function.
    1653             :        */
    1654             :       void
    1655             :       swap(unordered_multimap& __x)
    1656             :       noexcept( noexcept(_M_h.swap(__x._M_h)) )
    1657             :       { _M_h.swap(__x._M_h); }
    1658             : 
    1659             : #if __cplusplus > 201402L
    1660             :       template<typename, typename, typename>
    1661             :         friend class _Hash_merge_helper;
    1662             : 
    1663             :       template<typename _H2, typename _P2>
    1664             :         void
    1665             :         merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
    1666             :         {
    1667             :           using _Merge_helper
    1668             :             = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
    1669             :           _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
    1670             :         }
    1671             : 
    1672             :       template<typename _H2, typename _P2>
    1673             :         void
    1674             :         merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
    1675             :         { merge(__source); }
    1676             : 
    1677             :       template<typename _H2, typename _P2>
    1678             :         void
    1679             :         merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
    1680             :         {
    1681             :           using _Merge_helper
    1682             :             = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
    1683             :           _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
    1684             :         }
    1685             : 
    1686             :       template<typename _H2, typename _P2>
    1687             :         void
    1688             :         merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
    1689             :         { merge(__source); }
    1690             : #endif // C++17
    1691             : 
    1692             :       // observers.
    1693             : 
    1694             :       ///  Returns the hash functor object with which the %unordered_multimap
    1695             :       ///  was constructed.
    1696             :       hasher
    1697             :       hash_function() const
    1698             :       { return _M_h.hash_function(); }
    1699             : 
    1700             :       ///  Returns the key comparison object with which the %unordered_multimap
    1701             :       ///  was constructed.
    1702             :       key_equal
    1703             :       key_eq() const
    1704             :       { return _M_h.key_eq(); }
    1705             : 
    1706             :       // lookup.
    1707             : 
    1708             :       //@{
    1709             :       /**
    1710             :        *  @brief Tries to locate an element in an %unordered_multimap.
    1711             :        *  @param  __x  Key to be located.
    1712             :        *  @return  Iterator pointing to sought-after element, or end() if not
    1713             :        *           found.
    1714             :        *
    1715             :        *  This function takes a key and tries to locate the element with which
    1716             :        *  the key matches.  If successful the function returns an iterator
    1717             :        *  pointing to the sought after element.  If unsuccessful it returns the
    1718             :        *  past-the-end ( @c end() ) iterator.
    1719             :        */
    1720             :       iterator
    1721             :       find(const key_type& __x)
    1722             :       { return _M_h.find(__x); }
    1723             : 
    1724             :       const_iterator
    1725             :       find(const key_type& __x) const
    1726             :       { return _M_h.find(__x); }
    1727             :       //@}
    1728             : 
    1729             :       /**
    1730             :        *  @brief  Finds the number of elements.
    1731             :        *  @param  __x  Key to count.
    1732             :        *  @return  Number of elements with specified key.
    1733             :        */
    1734             :       size_type
    1735             :       count(const key_type& __x) const
    1736             :       { return _M_h.count(__x); }
    1737             : 
    1738             :       //@{
    1739             :       /**
    1740             :        *  @brief Finds a subsequence matching given key.
    1741             :        *  @param  __x  Key to be located.
    1742             :        *  @return  Pair of iterators that possibly points to the subsequence
    1743             :        *           matching given key.
    1744             :        */
    1745             :       std::pair<iterator, iterator>
    1746             :       equal_range(const key_type& __x)
    1747             :       { return _M_h.equal_range(__x); }
    1748             : 
    1749             :       std::pair<const_iterator, const_iterator>
    1750             :       equal_range(const key_type& __x) const
    1751             :       { return _M_h.equal_range(__x); }
    1752             :       //@}
    1753             : 
    1754             :       // bucket interface.
    1755             : 
    1756             :       /// Returns the number of buckets of the %unordered_multimap.
    1757             :       size_type
    1758             :       bucket_count() const noexcept
    1759             :       { return _M_h.bucket_count(); }
    1760             : 
    1761             :       /// Returns the maximum number of buckets of the %unordered_multimap.
    1762             :       size_type
    1763             :       max_bucket_count() const noexcept
    1764             :       { return _M_h.max_bucket_count(); }
    1765             : 
    1766             :       /*
    1767             :        * @brief  Returns the number of elements in a given bucket.
    1768             :        * @param  __n  A bucket index.
    1769             :        * @return  The number of elements in the bucket.
    1770             :        */
    1771             :       size_type
    1772             :       bucket_size(size_type __n) const
    1773             :       { return _M_h.bucket_size(__n); }
    1774             : 
    1775             :       /*
    1776             :        * @brief  Returns the bucket index of a given element.
    1777             :        * @param  __key  A key instance.
    1778             :        * @return  The key bucket index.
    1779             :        */
    1780             :       size_type
    1781             :       bucket(const key_type& __key) const
    1782             :       { return _M_h.bucket(__key); }
    1783             :       
    1784             :       /**
    1785             :        *  @brief  Returns a read/write iterator pointing to the first bucket
    1786             :        *         element.
    1787             :        *  @param  __n The bucket index.
    1788             :        *  @return  A read/write local iterator.
    1789             :        */
    1790             :       local_iterator
    1791             :       begin(size_type __n)
    1792             :       { return _M_h.begin(__n); }
    1793             : 
    1794             :       //@{
    1795             :       /**
    1796             :        *  @brief  Returns a read-only (constant) iterator pointing to the first
    1797             :        *         bucket element.
    1798             :        *  @param  __n The bucket index.
    1799             :        *  @return  A read-only local iterator.
    1800             :        */
    1801             :       const_local_iterator
    1802             :       begin(size_type __n) const
    1803             :       { return _M_h.begin(__n); }
    1804             : 
    1805             :       const_local_iterator
    1806             :       cbegin(size_type __n) const
    1807             :       { return _M_h.cbegin(__n); }
    1808             :       //@}
    1809             : 
    1810             :       /**
    1811             :        *  @brief  Returns a read/write iterator pointing to one past the last
    1812             :        *         bucket elements.
    1813             :        *  @param  __n The bucket index.
    1814             :        *  @return  A read/write local iterator.
    1815             :        */
    1816             :       local_iterator
    1817             :       end(size_type __n)
    1818             :       { return _M_h.end(__n); }
    1819             : 
    1820             :       //@{
    1821             :       /**
    1822             :        *  @brief  Returns a read-only (constant) iterator pointing to one past
    1823             :        *         the last bucket elements.
    1824             :        *  @param  __n The bucket index.
    1825             :        *  @return  A read-only local iterator.
    1826             :        */
    1827             :       const_local_iterator
    1828             :       end(size_type __n) const
    1829             :       { return _M_h.end(__n); }
    1830             : 
    1831             :       const_local_iterator
    1832             :       cend(size_type __n) const
    1833             :       { return _M_h.cend(__n); }
    1834             :       //@}
    1835             : 
    1836             :       // hash policy.
    1837             : 
    1838             :       /// Returns the average number of elements per bucket.
    1839             :       float
    1840             :       load_factor() const noexcept
    1841             :       { return _M_h.load_factor(); }
    1842             : 
    1843             :       /// Returns a positive number that the %unordered_multimap tries to keep
    1844             :       /// the load factor less than or equal to.
    1845             :       float
    1846             :       max_load_factor() const noexcept
    1847             :       { return _M_h.max_load_factor(); }
    1848             : 
    1849             :       /**
    1850             :        *  @brief  Change the %unordered_multimap maximum load factor.
    1851             :        *  @param  __z The new maximum load factor.
    1852             :        */
    1853             :       void
    1854             :       max_load_factor(float __z)
    1855             :       { _M_h.max_load_factor(__z); }
    1856             : 
    1857             :       /**
    1858             :        *  @brief  May rehash the %unordered_multimap.
    1859             :        *  @param  __n The new number of buckets.
    1860             :        *
    1861             :        *  Rehash will occur only if the new number of buckets respect the
    1862             :        *  %unordered_multimap maximum load factor.
    1863             :        */
    1864             :       void
    1865             :       rehash(size_type __n)
    1866             :       { _M_h.rehash(__n); }
    1867             : 
    1868             :       /**
    1869             :        *  @brief  Prepare the %unordered_multimap for a specified number of
    1870             :        *          elements.
    1871             :        *  @param  __n Number of elements required.
    1872             :        *
    1873             :        *  Same as rehash(ceil(n / max_load_factor())).
    1874             :        */
    1875             :       void
    1876             :       reserve(size_type __n)
    1877             :       { _M_h.reserve(__n); }
    1878             : 
    1879             :       template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
    1880             :                typename _Alloc1>
    1881             :         friend bool
    1882             :         operator==(const unordered_multimap<_Key1, _Tp1,
    1883             :                                             _Hash1, _Pred1, _Alloc1>&,
    1884             :                    const unordered_multimap<_Key1, _Tp1,
    1885             :                                             _Hash1, _Pred1, _Alloc1>&);
    1886             :     };
    1887             : 
    1888             :   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
    1889             :     inline void
    1890             :     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
    1891             :          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
    1892             :     noexcept(noexcept(__x.swap(__y)))
    1893             :     { __x.swap(__y); }
    1894             : 
    1895             :   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
    1896             :     inline void
    1897             :     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
    1898             :          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
    1899             :     noexcept(noexcept(__x.swap(__y)))
    1900             :     { __x.swap(__y); }
    1901             : 
    1902             :   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
    1903             :     inline bool
    1904             :     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
    1905             :                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
    1906             :     { return __x._M_h._M_equal(__y._M_h); }
    1907             : 
    1908             :   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
    1909             :     inline bool
    1910             :     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
    1911             :                const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
    1912             :     { return !(__x == __y); }
    1913             : 
    1914             :   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
    1915             :     inline bool
    1916             :     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
    1917             :                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
    1918             :     { return __x._M_h._M_equal(__y._M_h); }
    1919             : 
    1920             :   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
    1921             :     inline bool
    1922             :     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
    1923             :                const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
    1924             :     { return !(__x == __y); }
    1925             : 
    1926             : _GLIBCXX_END_NAMESPACE_CONTAINER
    1927             : 
    1928             : #if __cplusplus > 201402L
    1929             : _GLIBCXX_BEGIN_NAMESPACE_VERSION
    1930             :   // Allow std::unordered_map access to internals of compatible maps.
    1931             :   template<typename _Key, typename _Val, typename _Hash1, typename _Eq1,
    1932             :            typename _Alloc, typename _Hash2, typename _Eq2>
    1933             :     struct _Hash_merge_helper<
    1934             :       _GLIBCXX_STD_C::unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>,
    1935             :       _Hash2, _Eq2>
    1936             :     {
    1937             :     private:
    1938             :       template<typename... _Tp>
    1939             :         using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
    1940             :       template<typename... _Tp>
    1941             :         using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
    1942             : 
    1943             :       friend unordered_map<_Key, _Val, _Hash1, _Eq1, _Alloc>;
    1944             : 
    1945             :       static auto&
    1946             :       _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
    1947             :       { return __map._M_h; }
    1948             : 
    1949             :       static auto&
    1950             :       _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
    1951             :       { return __map._M_h; }
    1952             :     };
    1953             : 
    1954             :   // Allow std::unordered_multimap access to internals of compatible maps.
    1955             :   template<typename _Key, typename _Val, typename _Hash1, typename _Eq1,
    1956             :            typename _Alloc, typename _Hash2, typename _Eq2>
    1957             :     struct _Hash_merge_helper<
    1958             :       _GLIBCXX_STD_C::unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>,
    1959             :       _Hash2, _Eq2>
    1960             :     {
    1961             :     private:
    1962             :       template<typename... _Tp>
    1963             :         using unordered_map = _GLIBCXX_STD_C::unordered_map<_Tp...>;
    1964             :       template<typename... _Tp>
    1965             :         using unordered_multimap = _GLIBCXX_STD_C::unordered_multimap<_Tp...>;
    1966             : 
    1967             :       friend unordered_multimap<_Key, _Val, _Hash1, _Eq1, _Alloc>;
    1968             : 
    1969             :       static auto&
    1970             :       _S_get_table(unordered_map<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
    1971             :       { return __map._M_h; }
    1972             : 
    1973             :       static auto&
    1974             :       _S_get_table(unordered_multimap<_Key, _Val, _Hash2, _Eq2, _Alloc>& __map)
    1975             :       { return __map._M_h; }
    1976             :     };
    1977             : _GLIBCXX_END_NAMESPACE_VERSION
    1978             : #endif // C++17
    1979             : 
    1980             : } // namespace std
    1981             : 
    1982             : #endif /* _UNORDERED_MAP_H */

Generated by: LCOV version 1.13