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