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