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