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