libstdc++
unordered_set.h
Go to the documentation of this file.
00001 // unordered_set implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2010-2019 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       _GLIBCXX_NODISCARD 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 #if __cplusplus > 201703L
00671       /**
00672        *  @brief  Finds whether an element with the given key exists.
00673        *  @param  __x  Key of elements to be located.
00674        *  @return  True if there is any element with the specified key.
00675        */
00676       bool
00677       contains(const key_type& __x) const
00678       { return _M_h.find(__x) != _M_h.end(); }
00679 #endif
00680 
00681       //@{
00682       /**
00683        *  @brief Finds a subsequence matching given key.
00684        *  @param  __x  Key to be located.
00685        *  @return  Pair of iterators that possibly points to the subsequence
00686        *           matching given key.
00687        *
00688        *  This function probably only makes sense for multisets.
00689        */
00690       std::pair<iterator, iterator>
00691       equal_range(const key_type& __x)
00692       { return _M_h.equal_range(__x); }
00693 
00694       std::pair<const_iterator, const_iterator>
00695       equal_range(const key_type& __x) const
00696       { return _M_h.equal_range(__x); }
00697       //@}
00698 
00699       // bucket interface.
00700 
00701       /// Returns the number of buckets of the %unordered_set.
00702       size_type
00703       bucket_count() const noexcept
00704       { return _M_h.bucket_count(); }
00705 
00706       /// Returns the maximum number of buckets of the %unordered_set.
00707       size_type
00708       max_bucket_count() const noexcept
00709       { return _M_h.max_bucket_count(); }
00710 
00711       /*
00712        * @brief  Returns the number of elements in a given bucket.
00713        * @param  __n  A bucket index.
00714        * @return  The number of elements in the bucket.
00715        */
00716       size_type
00717       bucket_size(size_type __n) const
00718       { return _M_h.bucket_size(__n); }
00719 
00720       /*
00721        * @brief  Returns the bucket index of a given element.
00722        * @param  __key  A key instance.
00723        * @return  The key bucket index.
00724        */
00725       size_type
00726       bucket(const key_type& __key) const
00727       { return _M_h.bucket(__key); }
00728 
00729       //@{
00730       /**
00731        *  @brief  Returns a read-only (constant) iterator pointing to the first
00732        *         bucket element.
00733        *  @param  __n The bucket index.
00734        *  @return  A read-only local iterator.
00735        */
00736       local_iterator
00737       begin(size_type __n)
00738       { return _M_h.begin(__n); }
00739 
00740       const_local_iterator
00741       begin(size_type __n) const
00742       { return _M_h.begin(__n); }
00743 
00744       const_local_iterator
00745       cbegin(size_type __n) const
00746       { return _M_h.cbegin(__n); }
00747       //@}
00748 
00749       //@{
00750       /**
00751        *  @brief  Returns a read-only (constant) iterator pointing to one past
00752        *         the last bucket elements.
00753        *  @param  __n The bucket index.
00754        *  @return  A read-only local iterator.
00755        */
00756       local_iterator
00757       end(size_type __n)
00758       { return _M_h.end(__n); }
00759 
00760       const_local_iterator
00761       end(size_type __n) const
00762       { return _M_h.end(__n); }
00763 
00764       const_local_iterator
00765       cend(size_type __n) const
00766       { return _M_h.cend(__n); }
00767       //@}
00768 
00769       // hash policy.
00770 
00771       /// Returns the average number of elements per bucket.
00772       float
00773       load_factor() const noexcept
00774       { return _M_h.load_factor(); }
00775 
00776       /// Returns a positive number that the %unordered_set tries to keep the
00777       /// load factor less than or equal to.
00778       float
00779       max_load_factor() const noexcept
00780       { return _M_h.max_load_factor(); }
00781 
00782       /**
00783        *  @brief  Change the %unordered_set maximum load factor.
00784        *  @param  __z The new maximum load factor.
00785        */
00786       void
00787       max_load_factor(float __z)
00788       { _M_h.max_load_factor(__z); }
00789 
00790       /**
00791        *  @brief  May rehash the %unordered_set.
00792        *  @param  __n The new number of buckets.
00793        *
00794        *  Rehash will occur only if the new number of buckets respect the
00795        *  %unordered_set maximum load factor.
00796        */
00797       void
00798       rehash(size_type __n)
00799       { _M_h.rehash(__n); }
00800 
00801       /**
00802        *  @brief  Prepare the %unordered_set for a specified number of
00803        *          elements.
00804        *  @param  __n Number of elements required.
00805        *
00806        *  Same as rehash(ceil(n / max_load_factor())).
00807        */
00808       void
00809       reserve(size_type __n)
00810       { _M_h.reserve(__n); }
00811 
00812       template<typename _Value1, typename _Hash1, typename _Pred1,
00813                typename _Alloc1>
00814         friend bool
00815         operator==(const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&,
00816                    const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&);
00817     };
00818 
00819 #if __cpp_deduction_guides >= 201606
00820 
00821   template<typename _InputIterator,
00822            typename _Hash =
00823              hash<typename iterator_traits<_InputIterator>::value_type>,
00824            typename _Pred =
00825              equal_to<typename iterator_traits<_InputIterator>::value_type>,
00826            typename _Allocator =
00827              allocator<typename iterator_traits<_InputIterator>::value_type>,
00828            typename = _RequireInputIter<_InputIterator>,
00829            typename = _RequireNotAllocatorOrIntegral<_Hash>,
00830            typename = _RequireNotAllocator<_Pred>,
00831            typename = _RequireAllocator<_Allocator>>
00832     unordered_set(_InputIterator, _InputIterator,
00833                   unordered_set<int>::size_type = {},
00834                   _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
00835     -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
00836                      _Hash, _Pred, _Allocator>;
00837 
00838   template<typename _Tp, typename _Hash = hash<_Tp>,
00839            typename _Pred = equal_to<_Tp>,
00840            typename _Allocator = allocator<_Tp>,
00841            typename = _RequireNotAllocatorOrIntegral<_Hash>,
00842            typename = _RequireNotAllocator<_Pred>,
00843            typename = _RequireAllocator<_Allocator>>
00844     unordered_set(initializer_list<_Tp>,
00845                   unordered_set<int>::size_type = {},
00846                   _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
00847     -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
00848 
00849   template<typename _InputIterator, typename _Allocator,
00850            typename = _RequireInputIter<_InputIterator>,
00851            typename = _RequireAllocator<_Allocator>>
00852     unordered_set(_InputIterator, _InputIterator,
00853                   unordered_set<int>::size_type, _Allocator)
00854     -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
00855                      hash<
00856                        typename iterator_traits<_InputIterator>::value_type>,
00857                      equal_to<
00858                        typename iterator_traits<_InputIterator>::value_type>,
00859                      _Allocator>;
00860 
00861   template<typename _InputIterator, typename _Hash, typename _Allocator,
00862            typename = _RequireInputIter<_InputIterator>,
00863            typename = _RequireNotAllocatorOrIntegral<_Hash>,
00864            typename = _RequireAllocator<_Allocator>>
00865     unordered_set(_InputIterator, _InputIterator,
00866                   unordered_set<int>::size_type,
00867                   _Hash, _Allocator)
00868     -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
00869                      _Hash,
00870                      equal_to<
00871                        typename iterator_traits<_InputIterator>::value_type>,
00872                      _Allocator>;
00873 
00874   template<typename _Tp, typename _Allocator,
00875            typename = _RequireAllocator<_Allocator>>
00876     unordered_set(initializer_list<_Tp>,
00877                   unordered_set<int>::size_type, _Allocator)
00878     -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
00879 
00880   template<typename _Tp, typename _Hash, typename _Allocator,
00881            typename = _RequireNotAllocatorOrIntegral<_Hash>,
00882            typename = _RequireAllocator<_Allocator>>
00883     unordered_set(initializer_list<_Tp>,
00884                   unordered_set<int>::size_type, _Hash, _Allocator)
00885     -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
00886 
00887 #endif
00888 
00889   /**
00890    *  @brief A standard container composed of equivalent keys
00891    *  (possibly containing multiple of each key value) in which the
00892    *  elements' keys are the elements themselves.
00893    *
00894    *  @ingroup unordered_associative_containers
00895    *
00896    *  @tparam  _Value  Type of key objects.
00897    *  @tparam  _Hash  Hashing function object type, defaults to hash<_Value>.
00898    *  @tparam  _Pred  Predicate function object type, defaults
00899    *                  to equal_to<_Value>.
00900    *  @tparam  _Alloc  Allocator type, defaults to allocator<_Key>.
00901    *
00902    *  Meets the requirements of a <a href="tables.html#65">container</a>, and
00903    *  <a href="tables.html#xx">unordered associative container</a>
00904    *
00905    *  Base is _Hashtable, dispatched at compile time via template
00906    *  alias __umset_hashtable.
00907    */
00908   template<typename _Value,
00909            typename _Hash = hash<_Value>,
00910            typename _Pred = equal_to<_Value>,
00911            typename _Alloc = allocator<_Value>>
00912     class unordered_multiset
00913     {
00914       typedef __umset_hashtable<_Value, _Hash, _Pred, _Alloc>  _Hashtable;
00915       _Hashtable _M_h;
00916 
00917     public:
00918       // typedefs:
00919       //@{
00920       /// Public typedefs.
00921       typedef typename _Hashtable::key_type     key_type;
00922       typedef typename _Hashtable::value_type   value_type;
00923       typedef typename _Hashtable::hasher       hasher;
00924       typedef typename _Hashtable::key_equal    key_equal;
00925       typedef typename _Hashtable::allocator_type allocator_type;
00926       //@}
00927 
00928       //@{
00929       ///  Iterator-related typedefs.
00930       typedef typename _Hashtable::pointer              pointer;
00931       typedef typename _Hashtable::const_pointer        const_pointer;
00932       typedef typename _Hashtable::reference            reference;
00933       typedef typename _Hashtable::const_reference      const_reference;
00934       typedef typename _Hashtable::iterator             iterator;
00935       typedef typename _Hashtable::const_iterator       const_iterator;
00936       typedef typename _Hashtable::local_iterator       local_iterator;
00937       typedef typename _Hashtable::const_local_iterator const_local_iterator;
00938       typedef typename _Hashtable::size_type            size_type;
00939       typedef typename _Hashtable::difference_type      difference_type;
00940       //@}
00941 
00942 #if __cplusplus > 201402L
00943       using node_type = typename _Hashtable::node_type;
00944 #endif
00945 
00946       // construct/destroy/copy
00947 
00948       /// Default constructor.
00949       unordered_multiset() = default;
00950 
00951       /**
00952        *  @brief  Default constructor creates no elements.
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       explicit
00959       unordered_multiset(size_type __n,
00960                          const hasher& __hf = hasher(),
00961                          const key_equal& __eql = key_equal(),
00962                          const allocator_type& __a = allocator_type())
00963       : _M_h(__n, __hf, __eql, __a)
00964       { }
00965 
00966       /**
00967        *  @brief  Builds an %unordered_multiset from a range.
00968        *  @param  __first  An input iterator.
00969        *  @param  __last   An input iterator.
00970        *  @param __n       Minimal initial number of buckets.
00971        *  @param __hf      A hash functor.
00972        *  @param __eql     A key equality functor.
00973        *  @param __a       An allocator object.
00974        *
00975        *  Create an %unordered_multiset consisting of copies of the elements
00976        *  from [__first,__last).  This is linear in N (where N is
00977        *  distance(__first,__last)).
00978        */
00979       template<typename _InputIterator>
00980         unordered_multiset(_InputIterator __first, _InputIterator __last,
00981                            size_type __n = 0,
00982                            const hasher& __hf = hasher(),
00983                            const key_equal& __eql = key_equal(),
00984                            const allocator_type& __a = allocator_type())
00985         : _M_h(__first, __last, __n, __hf, __eql, __a)
00986         { }
00987 
00988       /// Copy constructor.
00989       unordered_multiset(const unordered_multiset&) = default;
00990 
00991       /// Move constructor.
00992       unordered_multiset(unordered_multiset&&) = default;
00993 
00994       /**
00995        *  @brief  Builds an %unordered_multiset from an initializer_list.
00996        *  @param  __l  An initializer_list.
00997        *  @param __n  Minimal initial number of buckets.
00998        *  @param __hf  A hash functor.
00999        *  @param __eql  A key equality functor.
01000        *  @param  __a  An allocator object.
01001        *
01002        *  Create an %unordered_multiset consisting of copies of the elements in
01003        *  the list. This is linear in N (where N is @a __l.size()).
01004        */
01005       unordered_multiset(initializer_list<value_type> __l,
01006                          size_type __n = 0,
01007                          const hasher& __hf = hasher(),
01008                          const key_equal& __eql = key_equal(),
01009                          const allocator_type& __a = allocator_type())
01010       : _M_h(__l, __n, __hf, __eql, __a)
01011       { }
01012 
01013       /// Copy assignment operator.
01014       unordered_multiset&
01015       operator=(const unordered_multiset&) = default;
01016 
01017       /// Move assignment operator.
01018       unordered_multiset&
01019       operator=(unordered_multiset&&) = default;
01020 
01021       /**
01022        *  @brief Creates an %unordered_multiset with no elements.
01023        *  @param __a An allocator object.
01024        */
01025       explicit
01026       unordered_multiset(const allocator_type& __a)
01027       : _M_h(__a)
01028       { }
01029 
01030       /*
01031        *  @brief Copy constructor with allocator argument.
01032        * @param  __uset  Input %unordered_multiset to copy.
01033        * @param  __a  An allocator object.
01034        */
01035       unordered_multiset(const unordered_multiset& __umset,
01036                          const allocator_type& __a)
01037       : _M_h(__umset._M_h, __a)
01038       { }
01039 
01040       /*
01041        *  @brief  Move constructor with allocator argument.
01042        *  @param  __umset  Input %unordered_multiset to move.
01043        *  @param  __a  An allocator object.
01044        */
01045       unordered_multiset(unordered_multiset&& __umset,
01046                          const allocator_type& __a)
01047       : _M_h(std::move(__umset._M_h), __a)
01048       { }
01049 
01050       unordered_multiset(size_type __n, const allocator_type& __a)
01051       : unordered_multiset(__n, hasher(), key_equal(), __a)
01052       { }
01053 
01054       unordered_multiset(size_type __n, const hasher& __hf,
01055                          const allocator_type& __a)
01056       : unordered_multiset(__n, __hf, key_equal(), __a)
01057       { }
01058 
01059       template<typename _InputIterator>
01060         unordered_multiset(_InputIterator __first, _InputIterator __last,
01061                            size_type __n,
01062                            const allocator_type& __a)
01063         : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
01064         { }
01065 
01066       template<typename _InputIterator>
01067         unordered_multiset(_InputIterator __first, _InputIterator __last,
01068                            size_type __n, const hasher& __hf,
01069                            const allocator_type& __a)
01070         : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
01071         { }
01072 
01073       unordered_multiset(initializer_list<value_type> __l,
01074                          size_type __n,
01075                          const allocator_type& __a)
01076       : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
01077       { }
01078 
01079       unordered_multiset(initializer_list<value_type> __l,
01080                          size_type __n, const hasher& __hf,
01081                          const allocator_type& __a)
01082       : unordered_multiset(__l, __n, __hf, key_equal(), __a)
01083       { }
01084 
01085       /**
01086        *  @brief  %Unordered_multiset list assignment operator.
01087        *  @param  __l  An initializer_list.
01088        *
01089        *  This function fills an %unordered_multiset with copies of the elements
01090        *  in the initializer list @a __l.
01091        *
01092        *  Note that the assignment completely changes the %unordered_multiset
01093        *  and that the resulting %unordered_multiset's size is the same as the
01094        *  number of elements assigned.
01095        */
01096       unordered_multiset&
01097       operator=(initializer_list<value_type> __l)
01098       {
01099         _M_h = __l;
01100         return *this;
01101       }
01102 
01103       ///  Returns the allocator object used by the %unordered_multiset.
01104       allocator_type
01105       get_allocator() const noexcept
01106       { return _M_h.get_allocator(); }
01107 
01108       // size and capacity:
01109 
01110       ///  Returns true if the %unordered_multiset is empty.
01111       _GLIBCXX_NODISCARD bool
01112       empty() const noexcept
01113       { return _M_h.empty(); }
01114 
01115       ///  Returns the size of the %unordered_multiset.
01116       size_type
01117       size() const noexcept
01118       { return _M_h.size(); }
01119 
01120       ///  Returns the maximum size of the %unordered_multiset.
01121       size_type
01122       max_size() const noexcept
01123       { return _M_h.max_size(); }
01124 
01125       // iterators.
01126 
01127       //@{
01128       /**
01129        *  Returns a read-only (constant) iterator that points to the first
01130        *  element in the %unordered_multiset.
01131        */
01132       iterator
01133       begin() noexcept
01134       { return _M_h.begin(); }
01135 
01136       const_iterator
01137       begin() const noexcept
01138       { return _M_h.begin(); }
01139       //@}
01140 
01141       //@{
01142       /**
01143        *  Returns a read-only (constant) iterator that points one past the last
01144        *  element in the %unordered_multiset.
01145        */
01146       iterator
01147       end() noexcept
01148       { return _M_h.end(); }
01149 
01150       const_iterator
01151       end() const noexcept
01152       { return _M_h.end(); }
01153       //@}
01154 
01155       /**
01156        *  Returns a read-only (constant) iterator that points to the first
01157        *  element in the %unordered_multiset.
01158        */
01159       const_iterator
01160       cbegin() const noexcept
01161       { return _M_h.begin(); }
01162 
01163       /**
01164        *  Returns a read-only (constant) iterator that points one past the last
01165        *  element in the %unordered_multiset.
01166        */
01167       const_iterator
01168       cend() const noexcept
01169       { return _M_h.end(); }
01170 
01171       // modifiers.
01172 
01173       /**
01174        *  @brief Builds and insert an element into the %unordered_multiset.
01175        *  @param __args  Arguments used to generate an element.
01176        *  @return  An iterator that points to the inserted element.
01177        *
01178        *  Insertion requires amortized constant time.
01179        */
01180       template<typename... _Args>
01181         iterator
01182         emplace(_Args&&... __args)
01183         { return _M_h.emplace(std::forward<_Args>(__args)...); }
01184 
01185       /**
01186        *  @brief Inserts an element into the %unordered_multiset.
01187        *  @param  __pos  An iterator that serves as a hint as to where the
01188        *                element should be inserted.
01189        *  @param  __args  Arguments used to generate the element to be
01190        *                 inserted.
01191        *  @return An iterator that points to the inserted element.
01192        *
01193        *  Note that the first parameter is only a hint and can potentially
01194        *  improve the performance of the insertion process.  A bad hint would
01195        *  cause no gains in efficiency.
01196        *
01197        *  For more on @a hinting, see:
01198        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
01199        *
01200        *  Insertion requires amortized constant time.
01201        */
01202       template<typename... _Args>
01203         iterator
01204         emplace_hint(const_iterator __pos, _Args&&... __args)
01205         { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
01206 
01207       //@{
01208       /**
01209        *  @brief Inserts an element into the %unordered_multiset.
01210        *  @param  __x  Element to be inserted.
01211        *  @return  An iterator that points to the inserted element.
01212        *
01213        *  Insertion requires amortized constant time.
01214        */
01215       iterator
01216       insert(const value_type& __x)
01217       { return _M_h.insert(__x); }
01218 
01219       iterator
01220       insert(value_type&& __x)
01221       { return _M_h.insert(std::move(__x)); }
01222       //@}
01223 
01224       //@{
01225       /**
01226        *  @brief Inserts an element into the %unordered_multiset.
01227        *  @param  __hint  An iterator that serves as a hint as to where the
01228        *                 element should be inserted.
01229        *  @param  __x  Element to be inserted.
01230        *  @return An iterator that points to the inserted element.
01231        *
01232        *  Note that the first parameter is only a hint and can potentially
01233        *  improve the performance of the insertion process.  A bad hint would
01234        *  cause no gains in efficiency.
01235        *
01236        *  For more on @a hinting, see:
01237        *  https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
01238        *
01239        *  Insertion requires amortized constant.
01240        */
01241       iterator
01242       insert(const_iterator __hint, const value_type& __x)
01243       { return _M_h.insert(__hint, __x); }
01244 
01245       iterator
01246       insert(const_iterator __hint, value_type&& __x)
01247       { return _M_h.insert(__hint, std::move(__x)); }
01248       //@}
01249 
01250       /**
01251        *  @brief A template function that inserts a range of elements.
01252        *  @param  __first  Iterator pointing to the start of the range to be
01253        *                   inserted.
01254        *  @param  __last  Iterator pointing to the end of the range.
01255        *
01256        *  Complexity similar to that of the range constructor.
01257        */
01258       template<typename _InputIterator>
01259         void
01260         insert(_InputIterator __first, _InputIterator __last)
01261         { _M_h.insert(__first, __last); }
01262 
01263       /**
01264        *  @brief Inserts a list of elements into the %unordered_multiset.
01265        *  @param  __l  A std::initializer_list<value_type> of elements to be
01266        *              inserted.
01267        *
01268        *  Complexity similar to that of the range constructor.
01269        */
01270       void
01271       insert(initializer_list<value_type> __l)
01272       { _M_h.insert(__l); }
01273 
01274 #if __cplusplus > 201402L
01275       /// Extract a node.
01276       node_type
01277       extract(const_iterator __pos)
01278       {
01279         __glibcxx_assert(__pos != end());
01280         return _M_h.extract(__pos);
01281       }
01282 
01283       /// Extract a node.
01284       node_type
01285       extract(const key_type& __key)
01286       { return _M_h.extract(__key); }
01287 
01288       /// Re-insert an extracted node.
01289       iterator
01290       insert(node_type&& __nh)
01291       { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
01292 
01293       /// Re-insert an extracted node.
01294       iterator
01295       insert(const_iterator __hint, node_type&& __nh)
01296       { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
01297 #endif // C++17
01298 
01299       //@{
01300       /**
01301        *  @brief Erases an element from an %unordered_multiset.
01302        *  @param  __position  An iterator pointing to the element to be erased.
01303        *  @return An iterator pointing to the element immediately following
01304        *          @a __position prior to the element being erased. If no such
01305        *          element exists, end() is returned.
01306        *
01307        *  This function erases an element, pointed to by the given iterator,
01308        *  from an %unordered_multiset.
01309        *
01310        *  Note that this function only erases the element, and that if the
01311        *  element is itself a pointer, the pointed-to memory is not touched in
01312        *  any way.  Managing the pointer is the user's responsibility.
01313        */
01314       iterator
01315       erase(const_iterator __position)
01316       { return _M_h.erase(__position); }
01317 
01318       // LWG 2059.
01319       iterator
01320       erase(iterator __position)
01321       { return _M_h.erase(__position); }
01322       //@}
01323 
01324 
01325       /**
01326        *  @brief Erases elements according to the provided key.
01327        *  @param  __x  Key of element to be erased.
01328        *  @return  The number of elements erased.
01329        *
01330        *  This function erases all the elements located by the given key from
01331        *  an %unordered_multiset.
01332        *
01333        *  Note that this function only erases the element, and that if the
01334        *  element is itself a pointer, the pointed-to memory is not touched in
01335        *  any way.  Managing the pointer is the user's responsibility.
01336        */
01337       size_type
01338       erase(const key_type& __x)
01339       { return _M_h.erase(__x); }
01340 
01341       /**
01342        *  @brief Erases a [__first,__last) range of elements from an
01343        *  %unordered_multiset.
01344        *  @param  __first  Iterator pointing to the start of the range to be
01345        *                  erased.
01346        *  @param __last  Iterator pointing to the end of the range to
01347        *                be erased.
01348        *  @return The iterator @a __last.
01349        *
01350        *  This function erases a sequence of elements from an
01351        *  %unordered_multiset.
01352        *
01353        *  Note that this function only erases the element, and that if
01354        *  the element is itself a pointer, the pointed-to memory is not touched
01355        *  in any way.  Managing the pointer is the user's responsibility.
01356        */
01357       iterator
01358       erase(const_iterator __first, const_iterator __last)
01359       { return _M_h.erase(__first, __last); }
01360 
01361       /**
01362        *  Erases all elements in an %unordered_multiset.
01363        *
01364        *  Note that this function only erases the elements, and that if the
01365        *  elements themselves are pointers, the pointed-to memory is not touched
01366        *  in any way. Managing the pointer is the user's responsibility.
01367        */
01368       void
01369       clear() noexcept
01370       { _M_h.clear(); }
01371 
01372       /**
01373        *  @brief  Swaps data with another %unordered_multiset.
01374        *  @param  __x  An %unordered_multiset of the same element and allocator
01375        *  types.
01376        *
01377        *  This exchanges the elements between two sets in constant time.
01378        *  Note that the global std::swap() function is specialized such that
01379        *  std::swap(s1,s2) will feed to this function.
01380        */
01381       void
01382       swap(unordered_multiset& __x)
01383       noexcept( noexcept(_M_h.swap(__x._M_h)) )
01384       { _M_h.swap(__x._M_h); }
01385 
01386 #if __cplusplus > 201402L
01387       template<typename, typename, typename>
01388         friend class std::_Hash_merge_helper;
01389 
01390       template<typename _H2, typename _P2>
01391         void
01392         merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
01393         {
01394           using _Merge_helper
01395             = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
01396           _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
01397         }
01398 
01399       template<typename _H2, typename _P2>
01400         void
01401         merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
01402         { merge(__source); }
01403 
01404       template<typename _H2, typename _P2>
01405         void
01406         merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
01407         {
01408           using _Merge_helper
01409             = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
01410           _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
01411         }
01412 
01413       template<typename _H2, typename _P2>
01414         void
01415         merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
01416         { merge(__source); }
01417 #endif // C++17
01418 
01419       // observers.
01420 
01421       ///  Returns the hash functor object with which the %unordered_multiset
01422       ///  was constructed.
01423       hasher
01424       hash_function() const
01425       { return _M_h.hash_function(); }
01426 
01427       ///  Returns the key comparison object with which the %unordered_multiset
01428       ///  was constructed.
01429       key_equal
01430       key_eq() const
01431       { return _M_h.key_eq(); }
01432 
01433       // lookup.
01434 
01435       //@{
01436       /**
01437        *  @brief Tries to locate an element in an %unordered_multiset.
01438        *  @param  __x  Element to be located.
01439        *  @return  Iterator pointing to sought-after element, or end() if not
01440        *           found.
01441        *
01442        *  This function takes a key and tries to locate the element with which
01443        *  the key matches.  If successful the function returns an iterator
01444        *  pointing to the sought after element.  If unsuccessful it returns the
01445        *  past-the-end ( @c end() ) iterator.
01446        */
01447       iterator
01448       find(const key_type& __x)
01449       { return _M_h.find(__x); }
01450 
01451       const_iterator
01452       find(const key_type& __x) const
01453       { return _M_h.find(__x); }
01454       //@}
01455 
01456       /**
01457        *  @brief  Finds the number of elements.
01458        *  @param  __x  Element to located.
01459        *  @return  Number of elements with specified key.
01460        */
01461       size_type
01462       count(const key_type& __x) const
01463       { return _M_h.count(__x); }
01464 
01465 #if __cplusplus > 201703L
01466       /**
01467        *  @brief  Finds whether an element with the given key exists.
01468        *  @param  __x  Key of elements to be located.
01469        *  @return  True if there is any element with the specified key.
01470        */
01471       bool
01472       contains(const key_type& __x) const
01473       { return _M_h.find(__x) != _M_h.end(); }
01474 #endif
01475 
01476       //@{
01477       /**
01478        *  @brief Finds a subsequence matching given key.
01479        *  @param  __x  Key to be located.
01480        *  @return  Pair of iterators that possibly points to the subsequence
01481        *           matching given key.
01482        */
01483       std::pair<iterator, iterator>
01484       equal_range(const key_type& __x)
01485       { return _M_h.equal_range(__x); }
01486 
01487       std::pair<const_iterator, const_iterator>
01488       equal_range(const key_type& __x) const
01489       { return _M_h.equal_range(__x); }
01490       //@}
01491 
01492       // bucket interface.
01493 
01494       /// Returns the number of buckets of the %unordered_multiset.
01495       size_type
01496       bucket_count() const noexcept
01497       { return _M_h.bucket_count(); }
01498 
01499       /// Returns the maximum number of buckets of the %unordered_multiset.
01500       size_type
01501       max_bucket_count() const noexcept
01502       { return _M_h.max_bucket_count(); }
01503 
01504       /*
01505        * @brief  Returns the number of elements in a given bucket.
01506        * @param  __n  A bucket index.
01507        * @return  The number of elements in the bucket.
01508        */
01509       size_type
01510       bucket_size(size_type __n) const
01511       { return _M_h.bucket_size(__n); }
01512 
01513       /*
01514        * @brief  Returns the bucket index of a given element.
01515        * @param  __key  A key instance.
01516        * @return  The key bucket index.
01517        */
01518       size_type
01519       bucket(const key_type& __key) const
01520       { return _M_h.bucket(__key); }
01521 
01522       //@{
01523       /**
01524        *  @brief  Returns a read-only (constant) iterator pointing to the first
01525        *         bucket element.
01526        *  @param  __n The bucket index.
01527        *  @return  A read-only local iterator.
01528        */
01529       local_iterator
01530       begin(size_type __n)
01531       { return _M_h.begin(__n); }
01532 
01533       const_local_iterator
01534       begin(size_type __n) const
01535       { return _M_h.begin(__n); }
01536 
01537       const_local_iterator
01538       cbegin(size_type __n) const
01539       { return _M_h.cbegin(__n); }
01540       //@}
01541 
01542       //@{
01543       /**
01544        *  @brief  Returns a read-only (constant) iterator pointing to one past
01545        *         the last bucket elements.
01546        *  @param  __n The bucket index.
01547        *  @return  A read-only local iterator.
01548        */
01549       local_iterator
01550       end(size_type __n)
01551       { return _M_h.end(__n); }
01552 
01553       const_local_iterator
01554       end(size_type __n) const
01555       { return _M_h.end(__n); }
01556 
01557       const_local_iterator
01558       cend(size_type __n) const
01559       { return _M_h.cend(__n); }
01560       //@}
01561 
01562       // hash policy.
01563 
01564       /// Returns the average number of elements per bucket.
01565       float
01566       load_factor() const noexcept
01567       { return _M_h.load_factor(); }
01568 
01569       /// Returns a positive number that the %unordered_multiset tries to keep the
01570       /// load factor less than or equal to.
01571       float
01572       max_load_factor() const noexcept
01573       { return _M_h.max_load_factor(); }
01574 
01575       /**
01576        *  @brief  Change the %unordered_multiset maximum load factor.
01577        *  @param  __z The new maximum load factor.
01578        */
01579       void
01580       max_load_factor(float __z)
01581       { _M_h.max_load_factor(__z); }
01582 
01583       /**
01584        *  @brief  May rehash the %unordered_multiset.
01585        *  @param  __n The new number of buckets.
01586        *
01587        *  Rehash will occur only if the new number of buckets respect the
01588        *  %unordered_multiset maximum load factor.
01589        */
01590       void
01591       rehash(size_type __n)
01592       { _M_h.rehash(__n); }
01593 
01594       /**
01595        *  @brief  Prepare the %unordered_multiset for a specified number of
01596        *          elements.
01597        *  @param  __n Number of elements required.
01598        *
01599        *  Same as rehash(ceil(n / max_load_factor())).
01600        */
01601       void
01602       reserve(size_type __n)
01603       { _M_h.reserve(__n); }
01604 
01605       template<typename _Value1, typename _Hash1, typename _Pred1,
01606                typename _Alloc1>
01607         friend bool
01608       operator==(const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&,
01609                  const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&);
01610     };
01611 
01612 
01613 #if __cpp_deduction_guides >= 201606
01614 
01615   template<typename _InputIterator,
01616            typename _Hash =
01617              hash<typename iterator_traits<_InputIterator>::value_type>,
01618            typename _Pred =
01619              equal_to<typename iterator_traits<_InputIterator>::value_type>,
01620            typename _Allocator =
01621              allocator<typename iterator_traits<_InputIterator>::value_type>,
01622            typename = _RequireInputIter<_InputIterator>,
01623            typename = _RequireNotAllocatorOrIntegral<_Hash>,
01624            typename = _RequireNotAllocator<_Pred>,
01625            typename = _RequireAllocator<_Allocator>>
01626     unordered_multiset(_InputIterator, _InputIterator,
01627                        unordered_multiset<int>::size_type = {},
01628                        _Hash = _Hash(), _Pred = _Pred(),
01629                        _Allocator = _Allocator())
01630     -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
01631                           _Hash, _Pred, _Allocator>;
01632 
01633   template<typename _Tp, typename _Hash = hash<_Tp>,
01634            typename _Pred = equal_to<_Tp>,
01635            typename _Allocator = allocator<_Tp>,
01636            typename = _RequireNotAllocatorOrIntegral<_Hash>,
01637            typename = _RequireNotAllocator<_Pred>,
01638            typename = _RequireAllocator<_Allocator>>
01639     unordered_multiset(initializer_list<_Tp>,
01640                        unordered_multiset<int>::size_type = {},
01641                        _Hash = _Hash(), _Pred = _Pred(),
01642                        _Allocator = _Allocator())
01643     -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
01644 
01645   template<typename _InputIterator, typename _Allocator,
01646            typename = _RequireInputIter<_InputIterator>,
01647            typename = _RequireAllocator<_Allocator>>
01648     unordered_multiset(_InputIterator, _InputIterator,
01649                        unordered_multiset<int>::size_type, _Allocator)
01650     -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
01651                           hash<typename
01652                                iterator_traits<_InputIterator>::value_type>,
01653                           equal_to<typename
01654                                    iterator_traits<_InputIterator>::value_type>,
01655                           _Allocator>;
01656 
01657   template<typename _InputIterator, typename _Hash, typename _Allocator,
01658            typename = _RequireInputIter<_InputIterator>,
01659            typename = _RequireNotAllocatorOrIntegral<_Hash>,
01660            typename = _RequireAllocator<_Allocator>>
01661     unordered_multiset(_InputIterator, _InputIterator,
01662                        unordered_multiset<int>::size_type,
01663                        _Hash, _Allocator)
01664     -> unordered_multiset<typename
01665                           iterator_traits<_InputIterator>::value_type,
01666                           _Hash,
01667                           equal_to<
01668                             typename
01669                             iterator_traits<_InputIterator>::value_type>,
01670                           _Allocator>;
01671 
01672   template<typename _Tp, typename _Allocator,
01673            typename = _RequireAllocator<_Allocator>>
01674     unordered_multiset(initializer_list<_Tp>,
01675                        unordered_multiset<int>::size_type, _Allocator)
01676     -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
01677 
01678   template<typename _Tp, typename _Hash, typename _Allocator,
01679            typename = _RequireNotAllocatorOrIntegral<_Hash>,
01680            typename = _RequireAllocator<_Allocator>>
01681     unordered_multiset(initializer_list<_Tp>,
01682                        unordered_multiset<int>::size_type, _Hash, _Allocator)
01683     -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
01684 
01685 #endif
01686 
01687   template<class _Value, class _Hash, class _Pred, class _Alloc>
01688     inline void
01689     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
01690          unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
01691     noexcept(noexcept(__x.swap(__y)))
01692     { __x.swap(__y); }
01693 
01694   template<class _Value, class _Hash, class _Pred, class _Alloc>
01695     inline void
01696     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
01697          unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
01698     noexcept(noexcept(__x.swap(__y)))
01699     { __x.swap(__y); }
01700 
01701   template<class _Value, class _Hash, class _Pred, class _Alloc>
01702     inline bool
01703     operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
01704                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
01705     { return __x._M_h._M_equal(__y._M_h); }
01706 
01707   template<class _Value, class _Hash, class _Pred, class _Alloc>
01708     inline bool
01709     operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
01710                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
01711     { return !(__x == __y); }
01712 
01713   template<class _Value, class _Hash, class _Pred, class _Alloc>
01714     inline bool
01715     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
01716                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
01717     { return __x._M_h._M_equal(__y._M_h); }
01718 
01719   template<class _Value, class _Hash, class _Pred, class _Alloc>
01720     inline bool
01721     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
01722                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
01723     { return !(__x == __y); }
01724 
01725 _GLIBCXX_END_NAMESPACE_CONTAINER
01726 
01727 #if __cplusplus > 201402L
01728   // Allow std::unordered_set access to internals of compatible sets.
01729   template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc,
01730            typename _Hash2, typename _Eq2>
01731     struct _Hash_merge_helper<
01732       _GLIBCXX_STD_C::unordered_set<_Val, _Hash1, _Eq1, _Alloc>, _Hash2, _Eq2>
01733     {
01734     private:
01735       template<typename... _Tp>
01736         using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
01737       template<typename... _Tp>
01738         using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
01739 
01740       friend unordered_set<_Val, _Hash1, _Eq1, _Alloc>;
01741 
01742       static auto&
01743       _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
01744       { return __set._M_h; }
01745 
01746       static auto&
01747       _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
01748       { return __set._M_h; }
01749     };
01750 
01751   // Allow std::unordered_multiset access to internals of compatible sets.
01752   template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc,
01753            typename _Hash2, typename _Eq2>
01754     struct _Hash_merge_helper<
01755       _GLIBCXX_STD_C::unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>,
01756       _Hash2, _Eq2>
01757     {
01758     private:
01759       template<typename... _Tp>
01760         using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
01761       template<typename... _Tp>
01762         using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
01763 
01764       friend unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>;
01765 
01766       static auto&
01767       _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
01768       { return __set._M_h; }
01769 
01770       static auto&
01771       _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
01772       { return __set._M_h; }
01773     };
01774 #endif // C++17
01775 
01776 _GLIBCXX_END_NAMESPACE_VERSION
01777 } // namespace std
01778 
01779 #endif /* _UNORDERED_SET_H */