libstdc++
unordered_map.h
Go to the documentation of this file.
00001 // unordered_map implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2010-2014 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file bits/unordered_map.h
00026  *  This is an internal header file, included by other library headers.
00027  *  Do not attempt to use it directly. @headername{unordered_map}
00028  */
00029 
00030 #ifndef _UNORDERED_MAP_H
00031 #define _UNORDERED_MAP_H
00032 
00033 namespace std _GLIBCXX_VISIBILITY(default)
00034 {
00035 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
00036 
00037   /// Base types for unordered_map.
00038   template<bool _Cache>
00039     using __umap_traits = __detail::_Hashtable_traits<_Cache, false, true>;
00040 
00041   template<typename _Key,
00042        typename _Tp,
00043        typename _Hash = hash<_Key>,
00044        typename _Pred = std::equal_to<_Key>,
00045        typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
00046        typename _Tr = __umap_traits<__cache_default<_Key, _Hash>::value>>
00047     using __umap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>,
00048                                         _Alloc, __detail::_Select1st,
00049                         _Pred, _Hash,
00050                         __detail::_Mod_range_hashing,
00051                         __detail::_Default_ranged_hash,
00052                         __detail::_Prime_rehash_policy, _Tr>;
00053 
00054   /// Base types for unordered_multimap.
00055   template<bool _Cache>
00056     using __ummap_traits = __detail::_Hashtable_traits<_Cache, false, false>;
00057 
00058   template<typename _Key,
00059        typename _Tp,
00060        typename _Hash = hash<_Key>,
00061        typename _Pred = std::equal_to<_Key>,
00062        typename _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
00063        typename _Tr = __ummap_traits<__cache_default<_Key, _Hash>::value>>
00064     using __ummap_hashtable = _Hashtable<_Key, std::pair<const _Key, _Tp>,
00065                      _Alloc, __detail::_Select1st,
00066                      _Pred, _Hash,
00067                      __detail::_Mod_range_hashing,
00068                      __detail::_Default_ranged_hash,
00069                      __detail::_Prime_rehash_policy, _Tr>;
00070 
00071   /**
00072    *  @brief A standard container composed of unique keys (containing
00073    *  at most one of each key value) that associates values of another type
00074    *  with the keys.
00075    *
00076    *  @ingroup unordered_associative_containers
00077    *
00078    *  @tparam  _Key    Type of key objects.
00079    *  @tparam  _Tp     Type of mapped objects.
00080    *  @tparam  _Hash   Hashing function object type, defaults to hash<_Value>.
00081    *  @tparam  _Pred   Predicate function object type, defaults
00082    *                   to equal_to<_Value>.
00083    *  @tparam  _Alloc  Allocator type, defaults to 
00084    *                   std::allocator<std::pair<const _Key, _Tp>>.
00085    *
00086    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
00087    *  <a href="tables.html#xx">unordered associative container</a>
00088    *
00089    * The resulting value type of the container is std::pair<const _Key, _Tp>.
00090    *
00091    *  Base is _Hashtable, dispatched at compile time via template
00092    *  alias __umap_hashtable.
00093    */
00094   template<class _Key, class _Tp,
00095        class _Hash = hash<_Key>,
00096        class _Pred = std::equal_to<_Key>,
00097        class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
00098     class unordered_map
00099     {
00100       typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
00101       _Hashtable _M_h;
00102 
00103     public:
00104       // typedefs:
00105       //@{
00106       /// Public typedefs.
00107       typedef typename _Hashtable::key_type key_type;
00108       typedef typename _Hashtable::value_type   value_type;
00109       typedef typename _Hashtable::mapped_type  mapped_type;
00110       typedef typename _Hashtable::hasher   hasher;
00111       typedef typename _Hashtable::key_equal    key_equal;
00112       typedef typename _Hashtable::allocator_type allocator_type;
00113       //@}
00114 
00115       //@{
00116       ///  Iterator-related typedefs.
00117       typedef typename _Hashtable::pointer      pointer;
00118       typedef typename _Hashtable::const_pointer    const_pointer;
00119       typedef typename _Hashtable::reference        reference;
00120       typedef typename _Hashtable::const_reference  const_reference;
00121       typedef typename _Hashtable::iterator     iterator;
00122       typedef typename _Hashtable::const_iterator   const_iterator;
00123       typedef typename _Hashtable::local_iterator   local_iterator;
00124       typedef typename _Hashtable::const_local_iterator const_local_iterator;
00125       typedef typename _Hashtable::size_type        size_type;
00126       typedef typename _Hashtable::difference_type  difference_type;
00127       //@}
00128 
00129       //construct/destroy/copy
00130 
00131       /**
00132        *  @brief  Default constructor creates no elements.
00133        *  @param __n  Initial number of buckets.
00134        *  @param __hf  A hash functor.
00135        *  @param __eql  A key equality functor.
00136        *  @param __a  An allocator object.
00137        */
00138       explicit
00139       unordered_map(size_type __n = 10,
00140             const hasher& __hf = hasher(),
00141             const key_equal& __eql = key_equal(),
00142             const allocator_type& __a = allocator_type())
00143       : _M_h(__n, __hf, __eql, __a)
00144       { }
00145 
00146       /**
00147        *  @brief  Builds an %unordered_map from a range.
00148        *  @param  __first  An input iterator.
00149        *  @param  __last  An input iterator.
00150        *  @param __n  Minimal initial number of buckets.
00151        *  @param __hf  A hash functor.
00152        *  @param __eql  A key equality functor.
00153        *  @param __a  An allocator object.
00154        *
00155        *  Create an %unordered_map consisting of copies of the elements from
00156        *  [__first,__last).  This is linear in N (where N is
00157        *  distance(__first,__last)).
00158        */
00159       template<typename _InputIterator>
00160     unordered_map(_InputIterator __f, _InputIterator __l,
00161               size_type __n = 0,
00162               const hasher& __hf = hasher(),
00163               const key_equal& __eql = key_equal(),
00164               const allocator_type& __a = allocator_type())
00165     : _M_h(__f, __l, __n, __hf, __eql, __a)
00166     { }
00167 
00168       /// Copy constructor.
00169       unordered_map(const unordered_map&) = default;
00170 
00171       /// Move constructor.
00172       unordered_map(unordered_map&&) = default;
00173 
00174       /**
00175        *  @brief Creates an %unordered_map with no elements.
00176        *  @param __a An allocator object.
00177        */
00178       explicit
00179       unordered_map(const allocator_type& __a)
00180     : _M_h(__a)
00181       { }
00182 
00183       /*
00184        *  @brief Copy constructor with allocator argument.
00185        * @param  __uset  Input %unordered_map to copy.
00186        * @param  __a  An allocator object.
00187        */
00188       unordered_map(const unordered_map& __umap,
00189             const allocator_type& __a)
00190     : _M_h(__umap._M_h, __a)
00191       { }
00192 
00193       /*
00194        *  @brief  Move constructor with allocator argument.
00195        *  @param  __uset Input %unordered_map to move.
00196        *  @param  __a    An allocator object.
00197        */
00198       unordered_map(unordered_map&& __umap,
00199             const allocator_type& __a)
00200     : _M_h(std::move(__umap._M_h), __a)
00201       { }
00202 
00203       /**
00204        *  @brief  Builds an %unordered_map from an initializer_list.
00205        *  @param  __l  An initializer_list.
00206        *  @param __n  Minimal initial number of buckets.
00207        *  @param __hf  A hash functor.
00208        *  @param __eql  A key equality functor.
00209        *  @param  __a  An allocator object.
00210        *
00211        *  Create an %unordered_map consisting of copies of the elements in the
00212        *  list. This is linear in N (where N is @a __l.size()).
00213        */
00214       unordered_map(initializer_list<value_type> __l,
00215             size_type __n = 0,
00216             const hasher& __hf = hasher(),
00217             const key_equal& __eql = key_equal(),
00218             const allocator_type& __a = allocator_type())
00219     : _M_h(__l, __n, __hf, __eql, __a)
00220       { }
00221 
00222       /// Copy assignment operator.
00223       unordered_map&
00224       operator=(const unordered_map&) = default;
00225 
00226       /// Move assignment operator.
00227       unordered_map&
00228       operator=(unordered_map&&) = default;
00229 
00230       /**
00231        *  @brief  %Unordered_map list assignment operator.
00232        *  @param  __l  An initializer_list.
00233        *
00234        *  This function fills an %unordered_map with copies of the elements in
00235        *  the initializer list @a __l.
00236        *
00237        *  Note that the assignment completely changes the %unordered_map and
00238        *  that the resulting %unordered_map's size is the same as the number
00239        *  of elements assigned.  Old data may be lost.
00240        */
00241       unordered_map&
00242       operator=(initializer_list<value_type> __l)
00243       {
00244     _M_h = __l;
00245     return *this;
00246       }
00247 
00248       ///  Returns the allocator object with which the %unordered_map was
00249       ///  constructed.
00250       allocator_type
00251       get_allocator() const noexcept
00252       { return _M_h.get_allocator(); }
00253 
00254       // size and capacity:
00255 
00256       ///  Returns true if the %unordered_map is empty.
00257       bool
00258       empty() const noexcept
00259       { return _M_h.empty(); }
00260 
00261       ///  Returns the size of the %unordered_map.
00262       size_type
00263       size() const noexcept
00264       { return _M_h.size(); }
00265 
00266       ///  Returns the maximum size of the %unordered_map.
00267       size_type
00268       max_size() const noexcept
00269       { return _M_h.max_size(); }
00270 
00271       // iterators.
00272 
00273       /**
00274        *  Returns a read/write iterator that points to the first element in the
00275        *  %unordered_map.
00276        */
00277       iterator
00278       begin() noexcept
00279       { return _M_h.begin(); }
00280 
00281       //@{
00282       /**
00283        *  Returns a read-only (constant) iterator that points to the first
00284        *  element in the %unordered_map.
00285        */
00286       const_iterator
00287       begin() const noexcept
00288       { return _M_h.begin(); }
00289 
00290       const_iterator
00291       cbegin() const noexcept
00292       { return _M_h.begin(); }
00293       //@}
00294 
00295       /**
00296        *  Returns a read/write iterator that points one past the last element in
00297        *  the %unordered_map.
00298        */
00299       iterator
00300       end() noexcept
00301       { return _M_h.end(); }
00302 
00303       //@{
00304       /**
00305        *  Returns a read-only (constant) iterator that points one past the last
00306        *  element in the %unordered_map.
00307        */
00308       const_iterator
00309       end() const noexcept
00310       { return _M_h.end(); }
00311 
00312       const_iterator
00313       cend() const noexcept
00314       { return _M_h.end(); }
00315       //@}
00316 
00317       // modifiers.
00318 
00319       /**
00320        *  @brief Attempts to build and insert a std::pair into the %unordered_map.
00321        *
00322        *  @param __args  Arguments used to generate a new pair instance (see
00323        *            std::piecewise_contruct for passing arguments to each
00324        *            part of the pair constructor).
00325        *
00326        *  @return  A pair, of which the first element is an iterator that points
00327        *           to the possibly inserted pair, and the second is a bool that
00328        *           is true if the pair was actually inserted.
00329        *
00330        *  This function attempts to build and insert a (key, value) %pair into
00331        *  the %unordered_map.
00332        *  An %unordered_map relies on unique keys and thus a %pair is only
00333        *  inserted if its first element (the key) is not already present in the
00334        *  %unordered_map.
00335        *
00336        *  Insertion requires amortized constant time.
00337        */
00338       template<typename... _Args>
00339     std::pair<iterator, bool>
00340     emplace(_Args&&... __args)
00341     { return _M_h.emplace(std::forward<_Args>(__args)...); }
00342 
00343       /**
00344        *  @brief Attempts to build and insert a std::pair into the %unordered_map.
00345        *
00346        *  @param  __pos  An iterator that serves as a hint as to where the pair
00347        *                should be inserted.
00348        *  @param  __args  Arguments used to generate a new pair instance (see
00349        *             std::piecewise_contruct for passing arguments to each
00350        *             part of the pair constructor).
00351        *  @return An iterator that points to the element with key of the
00352        *          std::pair built from @a __args (may or may not be that
00353        *          std::pair).
00354        *
00355        *  This function is not concerned about whether the insertion took place,
00356        *  and thus does not return a boolean like the single-argument emplace()
00357        *  does.
00358        *  Note that the first parameter is only a hint and can potentially
00359        *  improve the performance of the insertion process. A bad hint would
00360        *  cause no gains in efficiency.
00361        *
00362        *  See
00363        *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
00364        *  for more on @a hinting.
00365        *
00366        *  Insertion requires amortized constant time.
00367        */
00368       template<typename... _Args>
00369     iterator
00370     emplace_hint(const_iterator __pos, _Args&&... __args)
00371     { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
00372 
00373       //@{
00374       /**
00375        *  @brief Attempts to insert a std::pair into the %unordered_map.
00376 
00377        *  @param __x Pair to be inserted (see std::make_pair for easy
00378        *         creation of pairs).
00379        *
00380        *  @return  A pair, of which the first element is an iterator that 
00381        *           points to the possibly inserted pair, and the second is 
00382        *           a bool that is true if the pair was actually inserted.
00383        *
00384        *  This function attempts to insert a (key, value) %pair into the
00385        *  %unordered_map. An %unordered_map relies on unique keys and thus a
00386        *  %pair is only inserted if its first element (the key) is not already
00387        *  present in the %unordered_map.
00388        *
00389        *  Insertion requires amortized constant time.
00390        */
00391       std::pair<iterator, bool>
00392       insert(const value_type& __x)
00393       { return _M_h.insert(__x); }
00394 
00395       template<typename _Pair, typename = typename
00396            std::enable_if<std::is_constructible<value_type,
00397                             _Pair&&>::value>::type>
00398     std::pair<iterator, bool>
00399     insert(_Pair&& __x)
00400         { return _M_h.insert(std::forward<_Pair>(__x)); }
00401       //@}
00402 
00403       //@{
00404       /**
00405        *  @brief Attempts to insert a std::pair into the %unordered_map.
00406        *  @param  __hint  An iterator that serves as a hint as to where the
00407        *                 pair should be inserted.
00408        *  @param  __x  Pair to be inserted (see std::make_pair for easy creation
00409        *               of pairs).
00410        *  @return An iterator that points to the element with key of
00411        *           @a __x (may or may not be the %pair passed in).
00412        *
00413        *  This function is not concerned about whether the insertion took place,
00414        *  and thus does not return a boolean like the single-argument insert()
00415        *  does.  Note that the first parameter is only a hint and can
00416        *  potentially improve the performance of the insertion process.  A bad
00417        *  hint would cause no gains in efficiency.
00418        *
00419        *  See
00420        *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
00421        *  for more on @a hinting.
00422        *
00423        *  Insertion requires amortized constant time.
00424        */
00425       iterator
00426       insert(const_iterator __hint, const value_type& __x)
00427       { return _M_h.insert(__hint, __x); }
00428 
00429       template<typename _Pair, typename = typename
00430            std::enable_if<std::is_constructible<value_type,
00431                             _Pair&&>::value>::type>
00432     iterator
00433     insert(const_iterator __hint, _Pair&& __x)
00434     { return _M_h.insert(__hint, std::forward<_Pair>(__x)); }
00435       //@}
00436 
00437       /**
00438        *  @brief A template function that attempts to insert a range of
00439        *  elements.
00440        *  @param  __first  Iterator pointing to the start of the range to be
00441        *                   inserted.
00442        *  @param  __last  Iterator pointing to the end of the range.
00443        *
00444        *  Complexity similar to that of the range constructor.
00445        */
00446       template<typename _InputIterator>
00447     void
00448     insert(_InputIterator __first, _InputIterator __last)
00449     { _M_h.insert(__first, __last); }
00450 
00451       /**
00452        *  @brief Attempts to insert a list of elements into the %unordered_map.
00453        *  @param  __l  A std::initializer_list<value_type> of elements
00454        *               to be inserted.
00455        *
00456        *  Complexity similar to that of the range constructor.
00457        */
00458       void
00459       insert(initializer_list<value_type> __l)
00460       { _M_h.insert(__l); }
00461 
00462       //@{
00463       /**
00464        *  @brief Erases an element from an %unordered_map.
00465        *  @param  __position  An iterator pointing to the element to be erased.
00466        *  @return An iterator pointing to the element immediately following
00467        *          @a __position prior to the element being erased. If no such
00468        *          element exists, end() is returned.
00469        *
00470        *  This function erases an element, pointed to by the given iterator,
00471        *  from an %unordered_map.
00472        *  Note that this function only erases the element, and that if the
00473        *  element is itself a pointer, the pointed-to memory is not touched in
00474        *  any way.  Managing the pointer is the user's responsibility.
00475        */
00476       iterator
00477       erase(const_iterator __position)
00478       { return _M_h.erase(__position); }
00479 
00480       // LWG 2059.
00481       iterator
00482       erase(iterator __it)
00483       { return _M_h.erase(__it); }
00484       //@}
00485 
00486       /**
00487        *  @brief Erases elements according to the provided key.
00488        *  @param  __x  Key of element to be erased.
00489        *  @return  The number of elements erased.
00490        *
00491        *  This function erases all the elements located by the given key from
00492        *  an %unordered_map. For an %unordered_map the result of this function
00493        *  can only be 0 (not present) or 1 (present).
00494        *  Note that this function only erases the element, and that if the
00495        *  element is itself a pointer, the pointed-to memory is not touched in
00496        *  any way.  Managing the pointer is the user's responsibility.
00497        */
00498       size_type
00499       erase(const key_type& __x)
00500       { return _M_h.erase(__x); }
00501 
00502       /**
00503        *  @brief Erases a [__first,__last) range of elements from an
00504        *  %unordered_map.
00505        *  @param  __first  Iterator pointing to the start of the range to be
00506        *                  erased.
00507        *  @param __last  Iterator pointing to the end of the range to
00508        *                be erased.
00509        *  @return The iterator @a __last.
00510        *
00511        *  This function erases a sequence of elements from an %unordered_map.
00512        *  Note that this function only erases the elements, and that if
00513        *  the element is itself a pointer, the pointed-to memory is not touched
00514        *  in any way.  Managing the pointer is the user's responsibility.
00515        */
00516       iterator
00517       erase(const_iterator __first, const_iterator __last)
00518       { return _M_h.erase(__first, __last); }
00519 
00520       /**
00521        *  Erases all elements in an %unordered_map.
00522        *  Note that this function only erases the elements, and that if the
00523        *  elements themselves are pointers, the pointed-to memory is not touched
00524        *  in any way.  Managing the pointer is the user's responsibility.
00525        */
00526       void
00527       clear() noexcept
00528       { _M_h.clear(); }
00529 
00530       /**
00531        *  @brief  Swaps data with another %unordered_map.
00532        *  @param  __x  An %unordered_map of the same element and allocator
00533        *  types.
00534        *
00535        *  This exchanges the elements between two %unordered_map in constant time.
00536        *  Note that the global std::swap() function is specialized such that
00537        *  std::swap(m1,m2) will feed to this function.
00538        */
00539       void
00540       swap(unordered_map& __x)
00541       noexcept( noexcept(_M_h.swap(__x._M_h)) )
00542       { _M_h.swap(__x._M_h); }
00543 
00544       // observers.
00545 
00546       ///  Returns the hash functor object with which the %unordered_map was
00547       ///  constructed.
00548       hasher
00549       hash_function() const
00550       { return _M_h.hash_function(); }
00551 
00552       ///  Returns the key comparison object with which the %unordered_map was
00553       ///  constructed.
00554       key_equal
00555       key_eq() const
00556       { return _M_h.key_eq(); }
00557 
00558       // lookup.
00559 
00560       //@{
00561       /**
00562        *  @brief Tries to locate an element in an %unordered_map.
00563        *  @param  __x  Key to be located.
00564        *  @return  Iterator pointing to sought-after element, or end() if not
00565        *           found.
00566        *
00567        *  This function takes a key and tries to locate the element with which
00568        *  the key matches.  If successful the function returns an iterator
00569        *  pointing to the sought after element.  If unsuccessful it returns the
00570        *  past-the-end ( @c end() ) iterator.
00571        */
00572       iterator
00573       find(const key_type& __x)
00574       { return _M_h.find(__x); }
00575 
00576       const_iterator
00577       find(const key_type& __x) const
00578       { return _M_h.find(__x); }
00579       //@}
00580 
00581       /**
00582        *  @brief  Finds the number of elements.
00583        *  @param  __x  Key to count.
00584        *  @return  Number of elements with specified key.
00585        *
00586        *  This function only makes sense for %unordered_multimap; for
00587        *  %unordered_map the result will either be 0 (not present) or 1
00588        *  (present).
00589        */
00590       size_type
00591       count(const key_type& __x) const
00592       { return _M_h.count(__x); }
00593 
00594       //@{
00595       /**
00596        *  @brief Finds a subsequence matching given key.
00597        *  @param  __x  Key to be located.
00598        *  @return  Pair of iterators that possibly points to the subsequence
00599        *           matching given key.
00600        *
00601        *  This function probably only makes sense for %unordered_multimap.
00602        */
00603       std::pair<iterator, iterator>
00604       equal_range(const key_type& __x)
00605       { return _M_h.equal_range(__x); }
00606 
00607       std::pair<const_iterator, const_iterator>
00608       equal_range(const key_type& __x) const
00609       { return _M_h.equal_range(__x); }
00610       //@}
00611 
00612       //@{
00613       /**
00614        *  @brief  Subscript ( @c [] ) access to %unordered_map data.
00615        *  @param  __k  The key for which data should be retrieved.
00616        *  @return  A reference to the data of the (key,data) %pair.
00617        *
00618        *  Allows for easy lookup with the subscript ( @c [] )operator.  Returns
00619        *  data associated with the key specified in subscript.  If the key does
00620        *  not exist, a pair with that key is created using default values, which
00621        *  is then returned.
00622        *
00623        *  Lookup requires constant time.
00624        */
00625       mapped_type&
00626       operator[](const key_type& __k)
00627       { return _M_h[__k]; }
00628 
00629       mapped_type&
00630       operator[](key_type&& __k)
00631       { return _M_h[std::move(__k)]; }
00632       //@}
00633 
00634       //@{
00635       /**
00636        *  @brief  Access to %unordered_map data.
00637        *  @param  __k  The key for which data should be retrieved.
00638        *  @return  A reference to the data whose key is equal to @a __k, if
00639        *           such a data is present in the %unordered_map.
00640        *  @throw  std::out_of_range  If no such data is present.
00641        */
00642       mapped_type&
00643       at(const key_type& __k)
00644       { return _M_h.at(__k); }
00645 
00646       const mapped_type&
00647       at(const key_type& __k) const
00648       { return _M_h.at(__k); }
00649       //@}
00650 
00651       // bucket interface.
00652 
00653       /// Returns the number of buckets of the %unordered_map.
00654       size_type
00655       bucket_count() const noexcept
00656       { return _M_h.bucket_count(); }
00657 
00658       /// Returns the maximum number of buckets of the %unordered_map.
00659       size_type
00660       max_bucket_count() const noexcept
00661       { return _M_h.max_bucket_count(); }
00662 
00663       /*
00664        * @brief  Returns the number of elements in a given bucket.
00665        * @param  __n  A bucket index.
00666        * @return  The number of elements in the bucket.
00667        */
00668       size_type
00669       bucket_size(size_type __n) const
00670       { return _M_h.bucket_size(__n); }
00671 
00672       /*
00673        * @brief  Returns the bucket index of a given element.
00674        * @param  __key  A key instance.
00675        * @return  The key bucket index.
00676        */
00677       size_type
00678       bucket(const key_type& __key) const
00679       { return _M_h.bucket(__key); }
00680       
00681       /**
00682        *  @brief  Returns a read/write iterator pointing to the first bucket
00683        *         element.
00684        *  @param  __n The bucket index.
00685        *  @return  A read/write local iterator.
00686        */
00687       local_iterator
00688       begin(size_type __n)
00689       { return _M_h.begin(__n); }
00690 
00691       //@{
00692       /**
00693        *  @brief  Returns a read-only (constant) iterator pointing to the first
00694        *         bucket element.
00695        *  @param  __n The bucket index.
00696        *  @return  A read-only local iterator.
00697        */
00698       const_local_iterator
00699       begin(size_type __n) const
00700       { return _M_h.begin(__n); }
00701 
00702       const_local_iterator
00703       cbegin(size_type __n) const
00704       { return _M_h.cbegin(__n); }
00705       //@}
00706 
00707       /**
00708        *  @brief  Returns a read/write iterator pointing to one past the last
00709        *         bucket elements.
00710        *  @param  __n The bucket index.
00711        *  @return  A read/write local iterator.
00712        */
00713       local_iterator
00714       end(size_type __n)
00715       { return _M_h.end(__n); }
00716 
00717       //@{
00718       /**
00719        *  @brief  Returns a read-only (constant) iterator pointing to one past
00720        *         the last bucket elements.
00721        *  @param  __n The bucket index.
00722        *  @return  A read-only local iterator.
00723        */
00724       const_local_iterator
00725       end(size_type __n) const
00726       { return _M_h.end(__n); }
00727 
00728       const_local_iterator
00729       cend(size_type __n) const
00730       { return _M_h.cend(__n); }
00731       //@}
00732 
00733       // hash policy.
00734 
00735       /// Returns the average number of elements per bucket.
00736       float
00737       load_factor() const noexcept
00738       { return _M_h.load_factor(); }
00739 
00740       /// Returns a positive number that the %unordered_map tries to keep the
00741       /// load factor less than or equal to.
00742       float
00743       max_load_factor() const noexcept
00744       { return _M_h.max_load_factor(); }
00745 
00746       /**
00747        *  @brief  Change the %unordered_map maximum load factor.
00748        *  @param  __z The new maximum load factor.
00749        */
00750       void
00751       max_load_factor(float __z)
00752       { _M_h.max_load_factor(__z); }
00753 
00754       /**
00755        *  @brief  May rehash the %unordered_map.
00756        *  @param  __n The new number of buckets.
00757        *
00758        *  Rehash will occur only if the new number of buckets respect the
00759        *  %unordered_map maximum load factor.
00760        */
00761       void
00762       rehash(size_type __n)
00763       { _M_h.rehash(__n); }
00764 
00765       /**
00766        *  @brief  Prepare the %unordered_map for a specified number of
00767        *          elements.
00768        *  @param  __n Number of elements required.
00769        *
00770        *  Same as rehash(ceil(n / max_load_factor())).
00771        */
00772       void
00773       reserve(size_type __n)
00774       { _M_h.reserve(__n); }
00775 
00776       template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
00777            typename _Alloc1>
00778         friend bool
00779       operator==(const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&,
00780          const unordered_map<_Key1, _Tp1, _Hash1, _Pred1, _Alloc1>&);
00781     };
00782 
00783   /**
00784    *  @brief A standard container composed of equivalent keys
00785    *  (possibly containing multiple of each key value) that associates
00786    *  values of another type with the keys.
00787    *
00788    *  @ingroup unordered_associative_containers
00789    *
00790    *  @tparam  _Key    Type of key objects.
00791    *  @tparam  _Tp     Type of mapped objects.
00792    *  @tparam  _Hash   Hashing function object type, defaults to hash<_Value>.
00793    *  @tparam  _Pred   Predicate function object type, defaults
00794    *                   to equal_to<_Value>.
00795    *  @tparam  _Alloc  Allocator type, defaults to
00796    *                   std::allocator<std::pair<const _Key, _Tp>>.
00797    *
00798    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
00799    *  <a href="tables.html#xx">unordered associative container</a>
00800    *
00801    * The resulting value type of the container is std::pair<const _Key, _Tp>.
00802    *
00803    *  Base is _Hashtable, dispatched at compile time via template
00804    *  alias __ummap_hashtable.
00805    */
00806   template<class _Key, class _Tp,
00807        class _Hash = hash<_Key>,
00808        class _Pred = std::equal_to<_Key>,
00809        class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
00810     class unordered_multimap
00811     {
00812       typedef __ummap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
00813       _Hashtable _M_h;
00814 
00815     public:
00816       // typedefs:
00817       //@{
00818       /// Public typedefs.
00819       typedef typename _Hashtable::key_type key_type;
00820       typedef typename _Hashtable::value_type   value_type;
00821       typedef typename _Hashtable::mapped_type  mapped_type;
00822       typedef typename _Hashtable::hasher   hasher;
00823       typedef typename _Hashtable::key_equal    key_equal;
00824       typedef typename _Hashtable::allocator_type allocator_type;
00825       //@}
00826 
00827       //@{
00828       ///  Iterator-related typedefs.
00829       typedef typename _Hashtable::pointer      pointer;
00830       typedef typename _Hashtable::const_pointer    const_pointer;
00831       typedef typename _Hashtable::reference        reference;
00832       typedef typename _Hashtable::const_reference  const_reference;
00833       typedef typename _Hashtable::iterator     iterator;
00834       typedef typename _Hashtable::const_iterator   const_iterator;
00835       typedef typename _Hashtable::local_iterator   local_iterator;
00836       typedef typename _Hashtable::const_local_iterator const_local_iterator;
00837       typedef typename _Hashtable::size_type        size_type;
00838       typedef typename _Hashtable::difference_type  difference_type;
00839       //@}
00840 
00841       //construct/destroy/copy
00842 
00843       /**
00844        *  @brief  Default constructor creates no elements.
00845        *  @param __n  Initial number of buckets.
00846        *  @param __hf  A hash functor.
00847        *  @param __eql  A key equality functor.
00848        *  @param __a  An allocator object.
00849        */
00850       explicit
00851       unordered_multimap(size_type __n = 10,
00852              const hasher& __hf = hasher(),
00853              const key_equal& __eql = key_equal(),
00854              const allocator_type& __a = allocator_type())
00855       : _M_h(__n, __hf, __eql, __a)
00856       { }
00857 
00858       /**
00859        *  @brief  Builds an %unordered_multimap from a range.
00860        *  @param  __first  An input iterator.
00861        *  @param  __last  An input iterator.
00862        *  @param __n  Minimal initial number of buckets.
00863        *  @param __hf  A hash functor.
00864        *  @param __eql  A key equality functor.
00865        *  @param __a  An allocator object.
00866        *
00867        *  Create an %unordered_multimap consisting of copies of the elements
00868        *  from [__first,__last).  This is linear in N (where N is
00869        *  distance(__first,__last)).
00870        */
00871       template<typename _InputIterator>
00872     unordered_multimap(_InputIterator __f, _InputIterator __l,
00873                size_type __n = 0,
00874                const hasher& __hf = hasher(),
00875                const key_equal& __eql = key_equal(),
00876                const allocator_type& __a = allocator_type())
00877     : _M_h(__f, __l, __n, __hf, __eql, __a)
00878     { }
00879 
00880       /// Copy constructor.
00881       unordered_multimap(const unordered_multimap&) = default;
00882 
00883       /// Move constructor.
00884       unordered_multimap(unordered_multimap&&) = default;
00885 
00886       /**
00887        *  @brief Creates an %unordered_multimap with no elements.
00888        *  @param __a An allocator object.
00889        */
00890       explicit
00891       unordered_multimap(const allocator_type& __a)
00892     : _M_h(__a)
00893       { }
00894 
00895       /*
00896        *  @brief Copy constructor with allocator argument.
00897        * @param  __uset  Input %unordered_multimap to copy.
00898        * @param  __a  An allocator object.
00899        */
00900       unordered_multimap(const unordered_multimap& __ummap,
00901              const allocator_type& __a)
00902     : _M_h(__ummap._M_h, __a)
00903       { }
00904 
00905       /*
00906        *  @brief  Move constructor with allocator argument.
00907        *  @param  __uset Input %unordered_multimap to move.
00908        *  @param  __a    An allocator object.
00909        */
00910       unordered_multimap(unordered_multimap&& __ummap,
00911              const allocator_type& __a)
00912     : _M_h(std::move(__ummap._M_h), __a)
00913       { }
00914 
00915       /**
00916        *  @brief  Builds an %unordered_multimap from an initializer_list.
00917        *  @param  __l  An initializer_list.
00918        *  @param __n  Minimal initial number of buckets.
00919        *  @param __hf  A hash functor.
00920        *  @param __eql  A key equality functor.
00921        *  @param  __a  An allocator object.
00922        *
00923        *  Create an %unordered_multimap consisting of copies of the elements in
00924        *  the list. This is linear in N (where N is @a __l.size()).
00925        */
00926       unordered_multimap(initializer_list<value_type> __l,
00927              size_type __n = 0,
00928              const hasher& __hf = hasher(),
00929              const key_equal& __eql = key_equal(),
00930              const allocator_type& __a = allocator_type())
00931     : _M_h(__l, __n, __hf, __eql, __a)
00932       { }
00933 
00934       /// Copy assignment operator.
00935       unordered_multimap&
00936       operator=(const unordered_multimap&) = default;
00937 
00938       /// Move assignment operator.
00939       unordered_multimap&
00940       operator=(unordered_multimap&&) = default;
00941 
00942       /**
00943        *  @brief  %Unordered_multimap list assignment operator.
00944        *  @param  __l  An initializer_list.
00945        *
00946        *  This function fills an %unordered_multimap with copies of the elements
00947        *  in the initializer list @a __l.
00948        *
00949        *  Note that the assignment completely changes the %unordered_multimap
00950        *  and that the resulting %unordered_multimap's size is the same as the
00951        *  number of elements assigned.  Old data may be lost.
00952        */
00953       unordered_multimap&
00954       operator=(initializer_list<value_type> __l)
00955       {
00956     _M_h = __l;
00957     return *this;
00958       }
00959 
00960       ///  Returns the allocator object with which the %unordered_multimap was
00961       ///  constructed.
00962       allocator_type
00963       get_allocator() const noexcept
00964       { return _M_h.get_allocator(); }
00965 
00966       // size and capacity:
00967 
00968       ///  Returns true if the %unordered_multimap is empty.
00969       bool
00970       empty() const noexcept
00971       { return _M_h.empty(); }
00972 
00973       ///  Returns the size of the %unordered_multimap.
00974       size_type
00975       size() const noexcept
00976       { return _M_h.size(); }
00977 
00978       ///  Returns the maximum size of the %unordered_multimap.
00979       size_type
00980       max_size() const noexcept
00981       { return _M_h.max_size(); }
00982 
00983       // iterators.
00984 
00985       /**
00986        *  Returns a read/write iterator that points to the first element in the
00987        *  %unordered_multimap.
00988        */
00989       iterator
00990       begin() noexcept
00991       { return _M_h.begin(); }
00992 
00993       //@{
00994       /**
00995        *  Returns a read-only (constant) iterator that points to the first
00996        *  element in the %unordered_multimap.
00997        */
00998       const_iterator
00999       begin() const noexcept
01000       { return _M_h.begin(); }
01001 
01002       const_iterator
01003       cbegin() const noexcept
01004       { return _M_h.begin(); }
01005       //@}
01006 
01007       /**
01008        *  Returns a read/write iterator that points one past the last element in
01009        *  the %unordered_multimap.
01010        */
01011       iterator
01012       end() noexcept
01013       { return _M_h.end(); }
01014 
01015       //@{
01016       /**
01017        *  Returns a read-only (constant) iterator that points one past the last
01018        *  element in the %unordered_multimap.
01019        */
01020       const_iterator
01021       end() const noexcept
01022       { return _M_h.end(); }
01023 
01024       const_iterator
01025       cend() const noexcept
01026       { return _M_h.end(); }
01027       //@}
01028 
01029       // modifiers.
01030 
01031       /**
01032        *  @brief Attempts to build and insert a std::pair into the
01033        *  %unordered_multimap.
01034        *
01035        *  @param __args  Arguments used to generate a new pair instance (see
01036        *            std::piecewise_contruct for passing arguments to each
01037        *            part of the pair constructor).
01038        *
01039        *  @return  An iterator that points to the inserted pair.
01040        *
01041        *  This function attempts to build and insert a (key, value) %pair into
01042        *  the %unordered_multimap.
01043        *
01044        *  Insertion requires amortized constant time.
01045        */
01046       template<typename... _Args>
01047     iterator
01048     emplace(_Args&&... __args)
01049     { return _M_h.emplace(std::forward<_Args>(__args)...); }
01050 
01051       /**
01052        *  @brief Attempts to build and insert a std::pair into the %unordered_multimap.
01053        *
01054        *  @param  __pos  An iterator that serves as a hint as to where the pair
01055        *                should be inserted.
01056        *  @param  __args  Arguments used to generate a new pair instance (see
01057        *             std::piecewise_contruct for passing arguments to each
01058        *             part of the pair constructor).
01059        *  @return An iterator that points to the element with key of the
01060        *          std::pair built from @a __args.
01061        *
01062        *  Note that the first parameter is only a hint and can potentially
01063        *  improve the performance of the insertion process. A bad hint would
01064        *  cause no gains in efficiency.
01065        *
01066        *  See
01067        *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
01068        *  for more on @a hinting.
01069        *
01070        *  Insertion requires amortized constant time.
01071        */
01072       template<typename... _Args>
01073     iterator
01074     emplace_hint(const_iterator __pos, _Args&&... __args)
01075     { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
01076 
01077       //@{
01078       /**
01079        *  @brief Inserts a std::pair into the %unordered_multimap.
01080        *  @param __x Pair to be inserted (see std::make_pair for easy
01081        *         creation of pairs).
01082        *
01083        *  @return  An iterator that points to the inserted pair.
01084        *
01085        *  Insertion requires amortized constant time.
01086        */
01087       iterator
01088       insert(const value_type& __x)
01089       { return _M_h.insert(__x); }
01090 
01091       template<typename _Pair, typename = typename
01092            std::enable_if<std::is_constructible<value_type,
01093                             _Pair&&>::value>::type>
01094     iterator
01095     insert(_Pair&& __x)
01096         { return _M_h.insert(std::forward<_Pair>(__x)); }
01097       //@}
01098 
01099       //@{
01100       /**
01101        *  @brief Inserts a std::pair into the %unordered_multimap.
01102        *  @param  __hint  An iterator that serves as a hint as to where the
01103        *                 pair should be inserted.
01104        *  @param  __x  Pair to be inserted (see std::make_pair for easy creation
01105        *               of pairs).
01106        *  @return An iterator that points to the element with key of
01107        *           @a __x (may or may not be the %pair passed in).
01108        *
01109        *  Note that the first parameter is only a hint and can potentially
01110        *  improve the performance of the insertion process.  A bad hint would
01111        *  cause no gains in efficiency.
01112        *
01113        *  See
01114        *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt07ch17.html
01115        *  for more on @a hinting.
01116        *
01117        *  Insertion requires amortized constant time.
01118        */
01119       iterator
01120       insert(const_iterator __hint, const value_type& __x)
01121       { return _M_h.insert(__hint, __x); }
01122 
01123       template<typename _Pair, typename = typename
01124            std::enable_if<std::is_constructible<value_type,
01125                             _Pair&&>::value>::type>
01126     iterator
01127     insert(const_iterator __hint, _Pair&& __x)
01128         { return _M_h.insert(__hint, std::forward<_Pair>(__x)); }
01129       //@}
01130 
01131       /**
01132        *  @brief A template function that attempts to insert a range of
01133        *  elements.
01134        *  @param  __first  Iterator pointing to the start of the range to be
01135        *                   inserted.
01136        *  @param  __last  Iterator pointing to the end of the range.
01137        *
01138        *  Complexity similar to that of the range constructor.
01139        */
01140       template<typename _InputIterator>
01141     void
01142     insert(_InputIterator __first, _InputIterator __last)
01143     { _M_h.insert(__first, __last); }
01144 
01145       /**
01146        *  @brief Attempts to insert a list of elements into the
01147        *  %unordered_multimap.
01148        *  @param  __l  A std::initializer_list<value_type> of elements
01149        *               to be inserted.
01150        *
01151        *  Complexity similar to that of the range constructor.
01152        */
01153       void
01154       insert(initializer_list<value_type> __l)
01155       { _M_h.insert(__l); }
01156 
01157       //@{
01158       /**
01159        *  @brief Erases an element from an %unordered_multimap.
01160        *  @param  __position  An iterator pointing to the element to be erased.
01161        *  @return An iterator pointing to the element immediately following
01162        *          @a __position prior to the element being erased. If no such
01163        *          element exists, end() is returned.
01164        *
01165        *  This function erases an element, pointed to by the given iterator,
01166        *  from an %unordered_multimap.
01167        *  Note that this function only erases the element, and that if the
01168        *  element is itself a pointer, the pointed-to memory is not touched in
01169        *  any way.  Managing the pointer is the user's responsibility.
01170        */
01171       iterator
01172       erase(const_iterator __position)
01173       { return _M_h.erase(__position); }
01174 
01175       // LWG 2059.
01176       iterator
01177       erase(iterator __it)
01178       { return _M_h.erase(__it); }
01179       //@}
01180 
01181       /**
01182        *  @brief Erases elements according to the provided key.
01183        *  @param  __x  Key of elements to be erased.
01184        *  @return  The number of elements erased.
01185        *
01186        *  This function erases all the elements located by the given key from
01187        *  an %unordered_multimap.
01188        *  Note that this function only erases the element, and that if the
01189        *  element is itself a pointer, the pointed-to memory is not touched in
01190        *  any way.  Managing the pointer is the user's responsibility.
01191        */
01192       size_type
01193       erase(const key_type& __x)
01194       { return _M_h.erase(__x); }
01195 
01196       /**
01197        *  @brief Erases a [__first,__last) range of elements from an
01198        *  %unordered_multimap.
01199        *  @param  __first  Iterator pointing to the start of the range to be
01200        *                  erased.
01201        *  @param __last  Iterator pointing to the end of the range to
01202        *                be erased.
01203        *  @return The iterator @a __last.
01204        *
01205        *  This function erases a sequence of elements from an
01206        *  %unordered_multimap.
01207        *  Note that this function only erases the elements, and that if
01208        *  the element is itself a pointer, the pointed-to memory is not touched
01209        *  in any way.  Managing the pointer is the user's responsibility.
01210        */
01211       iterator
01212       erase(const_iterator __first, const_iterator __last)
01213       { return _M_h.erase(__first, __last); }
01214 
01215       /**
01216        *  Erases all elements in an %unordered_multimap.
01217        *  Note that this function only erases the elements, and that if the
01218        *  elements themselves are pointers, the pointed-to memory is not touched
01219        *  in any way.  Managing the pointer is the user's responsibility.
01220        */
01221       void
01222       clear() noexcept
01223       { _M_h.clear(); }
01224 
01225       /**
01226        *  @brief  Swaps data with another %unordered_multimap.
01227        *  @param  __x  An %unordered_multimap of the same element and allocator
01228        *  types.
01229        *
01230        *  This exchanges the elements between two %unordered_multimap in
01231        *  constant time.
01232        *  Note that the global std::swap() function is specialized such that
01233        *  std::swap(m1,m2) will feed to this function.
01234        */
01235       void
01236       swap(unordered_multimap& __x)
01237       noexcept( noexcept(_M_h.swap(__x._M_h)) )
01238       { _M_h.swap(__x._M_h); }
01239 
01240       // observers.
01241 
01242       ///  Returns the hash functor object with which the %unordered_multimap
01243       ///  was constructed.
01244       hasher
01245       hash_function() const
01246       { return _M_h.hash_function(); }
01247 
01248       ///  Returns the key comparison object with which the %unordered_multimap
01249       ///  was constructed.
01250       key_equal
01251       key_eq() const
01252       { return _M_h.key_eq(); }
01253 
01254       // lookup.
01255 
01256       //@{
01257       /**
01258        *  @brief Tries to locate an element in an %unordered_multimap.
01259        *  @param  __x  Key to be located.
01260        *  @return  Iterator pointing to sought-after element, or end() if not
01261        *           found.
01262        *
01263        *  This function takes a key and tries to locate the element with which
01264        *  the key matches.  If successful the function returns an iterator
01265        *  pointing to the sought after element.  If unsuccessful it returns the
01266        *  past-the-end ( @c end() ) iterator.
01267        */
01268       iterator
01269       find(const key_type& __x)
01270       { return _M_h.find(__x); }
01271 
01272       const_iterator
01273       find(const key_type& __x) const
01274       { return _M_h.find(__x); }
01275       //@}
01276 
01277       /**
01278        *  @brief  Finds the number of elements.
01279        *  @param  __x  Key to count.
01280        *  @return  Number of elements with specified key.
01281        */
01282       size_type
01283       count(const key_type& __x) const
01284       { return _M_h.count(__x); }
01285 
01286       //@{
01287       /**
01288        *  @brief Finds a subsequence matching given key.
01289        *  @param  __x  Key to be located.
01290        *  @return  Pair of iterators that possibly points to the subsequence
01291        *           matching given key.
01292        */
01293       std::pair<iterator, iterator>
01294       equal_range(const key_type& __x)
01295       { return _M_h.equal_range(__x); }
01296 
01297       std::pair<const_iterator, const_iterator>
01298       equal_range(const key_type& __x) const
01299       { return _M_h.equal_range(__x); }
01300       //@}
01301 
01302       // bucket interface.
01303 
01304       /// Returns the number of buckets of the %unordered_multimap.
01305       size_type
01306       bucket_count() const noexcept
01307       { return _M_h.bucket_count(); }
01308 
01309       /// Returns the maximum number of buckets of the %unordered_multimap.
01310       size_type
01311       max_bucket_count() const noexcept
01312       { return _M_h.max_bucket_count(); }
01313 
01314       /*
01315        * @brief  Returns the number of elements in a given bucket.
01316        * @param  __n  A bucket index.
01317        * @return  The number of elements in the bucket.
01318        */
01319       size_type
01320       bucket_size(size_type __n) const
01321       { return _M_h.bucket_size(__n); }
01322 
01323       /*
01324        * @brief  Returns the bucket index of a given element.
01325        * @param  __key  A key instance.
01326        * @return  The key bucket index.
01327        */
01328       size_type
01329       bucket(const key_type& __key) const
01330       { return _M_h.bucket(__key); }
01331       
01332       /**
01333        *  @brief  Returns a read/write iterator pointing to the first bucket
01334        *         element.
01335        *  @param  __n The bucket index.
01336        *  @return  A read/write local iterator.
01337        */
01338       local_iterator
01339       begin(size_type __n)
01340       { return _M_h.begin(__n); }
01341 
01342       //@{
01343       /**
01344        *  @brief  Returns a read-only (constant) iterator pointing to the first
01345        *         bucket element.
01346        *  @param  __n The bucket index.
01347        *  @return  A read-only local iterator.
01348        */
01349       const_local_iterator
01350       begin(size_type __n) const
01351       { return _M_h.begin(__n); }
01352 
01353       const_local_iterator
01354       cbegin(size_type __n) const
01355       { return _M_h.cbegin(__n); }
01356       //@}
01357 
01358       /**
01359        *  @brief  Returns a read/write iterator pointing to one past the last
01360        *         bucket elements.
01361        *  @param  __n The bucket index.
01362        *  @return  A read/write local iterator.
01363        */
01364       local_iterator
01365       end(size_type __n)
01366       { return _M_h.end(__n); }
01367 
01368       //@{
01369       /**
01370        *  @brief  Returns a read-only (constant) iterator pointing to one past
01371        *         the last bucket elements.
01372        *  @param  __n The bucket index.
01373        *  @return  A read-only local iterator.
01374        */
01375       const_local_iterator
01376       end(size_type __n) const
01377       { return _M_h.end(__n); }
01378 
01379       const_local_iterator
01380       cend(size_type __n) const
01381       { return _M_h.cend(__n); }
01382       //@}
01383 
01384       // hash policy.
01385 
01386       /// Returns the average number of elements per bucket.
01387       float
01388       load_factor() const noexcept
01389       { return _M_h.load_factor(); }
01390 
01391       /// Returns a positive number that the %unordered_multimap tries to keep
01392       /// the load factor less than or equal to.
01393       float
01394       max_load_factor() const noexcept
01395       { return _M_h.max_load_factor(); }
01396 
01397       /**
01398        *  @brief  Change the %unordered_multimap maximum load factor.
01399        *  @param  __z The new maximum load factor.
01400        */
01401       void
01402       max_load_factor(float __z)
01403       { _M_h.max_load_factor(__z); }
01404 
01405       /**
01406        *  @brief  May rehash the %unordered_multimap.
01407        *  @param  __n The new number of buckets.
01408        *
01409        *  Rehash will occur only if the new number of buckets respect the
01410        *  %unordered_multimap maximum load factor.
01411        */
01412       void
01413       rehash(size_type __n)
01414       { _M_h.rehash(__n); }
01415 
01416       /**
01417        *  @brief  Prepare the %unordered_multimap for a specified number of
01418        *          elements.
01419        *  @param  __n Number of elements required.
01420        *
01421        *  Same as rehash(ceil(n / max_load_factor())).
01422        */
01423       void
01424       reserve(size_type __n)
01425       { _M_h.reserve(__n); }
01426 
01427       template<typename _Key1, typename _Tp1, typename _Hash1, typename _Pred1,
01428            typename _Alloc1>
01429         friend bool
01430     operator==(const unordered_multimap<_Key1, _Tp1,
01431                         _Hash1, _Pred1, _Alloc1>&,
01432            const unordered_multimap<_Key1, _Tp1,
01433                         _Hash1, _Pred1, _Alloc1>&);
01434     };
01435 
01436   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
01437     inline void
01438     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
01439      unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
01440     { __x.swap(__y); }
01441 
01442   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
01443     inline void
01444     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
01445      unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
01446     { __x.swap(__y); }
01447 
01448   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
01449     inline bool
01450     operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
01451            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
01452     { return __x._M_h._M_equal(__y._M_h); }
01453 
01454   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
01455     inline bool
01456     operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
01457            const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
01458     { return !(__x == __y); }
01459 
01460   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
01461     inline bool
01462     operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
01463            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
01464     { return __x._M_h._M_equal(__y._M_h); }
01465 
01466   template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
01467     inline bool
01468     operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
01469            const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
01470     { return !(__x == __y); }
01471 
01472 _GLIBCXX_END_NAMESPACE_CONTAINER
01473 } // namespace std
01474 
01475 #endif /* _UNORDERED_MAP_H */