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