123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884 |
- // unordered_set implementation -*- C++ -*-
- // Copyright (C) 2010-2022 Free Software Foundation, Inc.
- //
- // This file is part of the GNU ISO C++ Library. This library is free
- // software; you can redistribute it and/or modify it under the
- // terms of the GNU General Public License as published by the
- // Free Software Foundation; either version 3, or (at your option)
- // any later version.
- // This library is distributed in the hope that it will be useful,
- // but WITHOUT ANY WARRANTY; without even the implied warranty of
- // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- // GNU General Public License for more details.
- // Under Section 7 of GPL version 3, you are granted additional
- // permissions described in the GCC Runtime Library Exception, version
- // 3.1, as published by the Free Software Foundation.
- // You should have received a copy of the GNU General Public License and
- // a copy of the GCC Runtime Library Exception along with this program;
- // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
- // <http://www.gnu.org/licenses/>.
- /** @file bits/unordered_set.h
- * This is an internal header file, included by other library headers.
- * Do not attempt to use it directly. @headername{unordered_set}
- */
- #ifndef _UNORDERED_SET_H
- #define _UNORDERED_SET_H
- namespace std _GLIBCXX_VISIBILITY(default)
- {
- _GLIBCXX_BEGIN_NAMESPACE_VERSION
- _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
- /// Base types for unordered_set.
- template<bool _Cache>
- using __uset_traits = __detail::_Hashtable_traits<_Cache, true, true>;
- template<typename _Value,
- typename _Hash = hash<_Value>,
- typename _Pred = std::equal_to<_Value>,
- typename _Alloc = std::allocator<_Value>,
- typename _Tr = __uset_traits<__cache_default<_Value, _Hash>::value>>
- using __uset_hashtable = _Hashtable<_Value, _Value, _Alloc,
- __detail::_Identity, _Pred, _Hash,
- __detail::_Mod_range_hashing,
- __detail::_Default_ranged_hash,
- __detail::_Prime_rehash_policy, _Tr>;
- /// Base types for unordered_multiset.
- template<bool _Cache>
- using __umset_traits = __detail::_Hashtable_traits<_Cache, true, false>;
- template<typename _Value,
- typename _Hash = hash<_Value>,
- typename _Pred = std::equal_to<_Value>,
- typename _Alloc = std::allocator<_Value>,
- typename _Tr = __umset_traits<__cache_default<_Value, _Hash>::value>>
- using __umset_hashtable = _Hashtable<_Value, _Value, _Alloc,
- __detail::_Identity,
- _Pred, _Hash,
- __detail::_Mod_range_hashing,
- __detail::_Default_ranged_hash,
- __detail::_Prime_rehash_policy, _Tr>;
- template<class _Value, class _Hash, class _Pred, class _Alloc>
- class unordered_multiset;
- /**
- * @brief A standard container composed of unique keys (containing
- * at most one of each key value) in which the elements' keys are
- * the elements themselves.
- *
- * @ingroup unordered_associative_containers
- *
- * @tparam _Value Type of key objects.
- * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
- * @tparam _Pred Predicate function object type, defaults to
- * equal_to<_Value>.
- *
- * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
- *
- * Meets the requirements of a <a href="tables.html#65">container</a>, and
- * <a href="tables.html#xx">unordered associative container</a>
- *
- * Base is _Hashtable, dispatched at compile time via template
- * alias __uset_hashtable.
- */
- template<typename _Value,
- typename _Hash = hash<_Value>,
- typename _Pred = equal_to<_Value>,
- typename _Alloc = allocator<_Value>>
- class unordered_set
- {
- typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
- _Hashtable _M_h;
- public:
- // typedefs:
- ///@{
- /// Public typedefs.
- typedef typename _Hashtable::key_type key_type;
- typedef typename _Hashtable::value_type value_type;
- typedef typename _Hashtable::hasher hasher;
- typedef typename _Hashtable::key_equal key_equal;
- typedef typename _Hashtable::allocator_type allocator_type;
- ///@}
- ///@{
- /// Iterator-related typedefs.
- typedef typename _Hashtable::pointer pointer;
- typedef typename _Hashtable::const_pointer const_pointer;
- typedef typename _Hashtable::reference reference;
- typedef typename _Hashtable::const_reference const_reference;
- typedef typename _Hashtable::iterator iterator;
- typedef typename _Hashtable::const_iterator const_iterator;
- typedef typename _Hashtable::local_iterator local_iterator;
- typedef typename _Hashtable::const_local_iterator const_local_iterator;
- typedef typename _Hashtable::size_type size_type;
- typedef typename _Hashtable::difference_type difference_type;
- ///@}
- #if __cplusplus > 201402L
- using node_type = typename _Hashtable::node_type;
- using insert_return_type = typename _Hashtable::insert_return_type;
- #endif
- // construct/destroy/copy
- /// Default constructor.
- unordered_set() = default;
- /**
- * @brief Default constructor creates no elements.
- * @param __n Minimal initial number of buckets.
- * @param __hf A hash functor.
- * @param __eql A key equality functor.
- * @param __a An allocator object.
- */
- explicit
- unordered_set(size_type __n,
- const hasher& __hf = hasher(),
- const key_equal& __eql = key_equal(),
- const allocator_type& __a = allocator_type())
- : _M_h(__n, __hf, __eql, __a)
- { }
- /**
- * @brief Builds an %unordered_set from a range.
- * @param __first An input iterator.
- * @param __last An input iterator.
- * @param __n Minimal initial number of buckets.
- * @param __hf A hash functor.
- * @param __eql A key equality functor.
- * @param __a An allocator object.
- *
- * Create an %unordered_set consisting of copies of the elements from
- * [__first,__last). This is linear in N (where N is
- * distance(__first,__last)).
- */
- template<typename _InputIterator>
- unordered_set(_InputIterator __first, _InputIterator __last,
- size_type __n = 0,
- const hasher& __hf = hasher(),
- const key_equal& __eql = key_equal(),
- const allocator_type& __a = allocator_type())
- : _M_h(__first, __last, __n, __hf, __eql, __a)
- { }
- /// Copy constructor.
- unordered_set(const unordered_set&) = default;
- /// Move constructor.
- unordered_set(unordered_set&&) = default;
- /**
- * @brief Creates an %unordered_set with no elements.
- * @param __a An allocator object.
- */
- explicit
- unordered_set(const allocator_type& __a)
- : _M_h(__a)
- { }
- /*
- * @brief Copy constructor with allocator argument.
- * @param __uset Input %unordered_set to copy.
- * @param __a An allocator object.
- */
- unordered_set(const unordered_set& __uset,
- const allocator_type& __a)
- : _M_h(__uset._M_h, __a)
- { }
- /*
- * @brief Move constructor with allocator argument.
- * @param __uset Input %unordered_set to move.
- * @param __a An allocator object.
- */
- unordered_set(unordered_set&& __uset,
- const allocator_type& __a)
- noexcept( noexcept(_Hashtable(std::move(__uset._M_h), __a)) )
- : _M_h(std::move(__uset._M_h), __a)
- { }
- /**
- * @brief Builds an %unordered_set from an initializer_list.
- * @param __l An initializer_list.
- * @param __n Minimal initial number of buckets.
- * @param __hf A hash functor.
- * @param __eql A key equality functor.
- * @param __a An allocator object.
- *
- * Create an %unordered_set consisting of copies of the elements in the
- * list. This is linear in N (where N is @a __l.size()).
- */
- unordered_set(initializer_list<value_type> __l,
- size_type __n = 0,
- const hasher& __hf = hasher(),
- const key_equal& __eql = key_equal(),
- const allocator_type& __a = allocator_type())
- : _M_h(__l, __n, __hf, __eql, __a)
- { }
- unordered_set(size_type __n, const allocator_type& __a)
- : unordered_set(__n, hasher(), key_equal(), __a)
- { }
- unordered_set(size_type __n, const hasher& __hf,
- const allocator_type& __a)
- : unordered_set(__n, __hf, key_equal(), __a)
- { }
- template<typename _InputIterator>
- unordered_set(_InputIterator __first, _InputIterator __last,
- size_type __n,
- const allocator_type& __a)
- : unordered_set(__first, __last, __n, hasher(), key_equal(), __a)
- { }
- template<typename _InputIterator>
- unordered_set(_InputIterator __first, _InputIterator __last,
- size_type __n, const hasher& __hf,
- const allocator_type& __a)
- : unordered_set(__first, __last, __n, __hf, key_equal(), __a)
- { }
- unordered_set(initializer_list<value_type> __l,
- size_type __n,
- const allocator_type& __a)
- : unordered_set(__l, __n, hasher(), key_equal(), __a)
- { }
- unordered_set(initializer_list<value_type> __l,
- size_type __n, const hasher& __hf,
- const allocator_type& __a)
- : unordered_set(__l, __n, __hf, key_equal(), __a)
- { }
- /// Copy assignment operator.
- unordered_set&
- operator=(const unordered_set&) = default;
- /// Move assignment operator.
- unordered_set&
- operator=(unordered_set&&) = default;
- /**
- * @brief %Unordered_set list assignment operator.
- * @param __l An initializer_list.
- *
- * This function fills an %unordered_set with copies of the elements in
- * the initializer list @a __l.
- *
- * Note that the assignment completely changes the %unordered_set and
- * that the resulting %unordered_set's size is the same as the number
- * of elements assigned.
- */
- unordered_set&
- operator=(initializer_list<value_type> __l)
- {
- _M_h = __l;
- return *this;
- }
- /// Returns the allocator object used by the %unordered_set.
- allocator_type
- get_allocator() const noexcept
- { return _M_h.get_allocator(); }
- // size and capacity:
- /// Returns true if the %unordered_set is empty.
- _GLIBCXX_NODISCARD bool
- empty() const noexcept
- { return _M_h.empty(); }
- /// Returns the size of the %unordered_set.
- size_type
- size() const noexcept
- { return _M_h.size(); }
- /// Returns the maximum size of the %unordered_set.
- size_type
- max_size() const noexcept
- { return _M_h.max_size(); }
- // iterators.
- ///@{
- /**
- * Returns a read-only (constant) iterator that points to the first
- * element in the %unordered_set.
- */
- iterator
- begin() noexcept
- { return _M_h.begin(); }
- const_iterator
- begin() const noexcept
- { return _M_h.begin(); }
- ///@}
- ///@{
- /**
- * Returns a read-only (constant) iterator that points one past the last
- * element in the %unordered_set.
- */
- iterator
- end() noexcept
- { return _M_h.end(); }
- const_iterator
- end() const noexcept
- { return _M_h.end(); }
- ///@}
- /**
- * Returns a read-only (constant) iterator that points to the first
- * element in the %unordered_set.
- */
- const_iterator
- cbegin() const noexcept
- { return _M_h.begin(); }
- /**
- * Returns a read-only (constant) iterator that points one past the last
- * element in the %unordered_set.
- */
- const_iterator
- cend() const noexcept
- { return _M_h.end(); }
- // modifiers.
- /**
- * @brief Attempts to build and insert an element into the
- * %unordered_set.
- * @param __args Arguments used to generate an element.
- * @return A pair, of which the first element is an iterator that points
- * to the possibly inserted element, and the second is a bool
- * that is true if the element was actually inserted.
- *
- * This function attempts to build and insert an element into the
- * %unordered_set. An %unordered_set relies on unique keys and thus an
- * element is only inserted if it is not already present in the
- * %unordered_set.
- *
- * Insertion requires amortized constant time.
- */
- template<typename... _Args>
- std::pair<iterator, bool>
- emplace(_Args&&... __args)
- { return _M_h.emplace(std::forward<_Args>(__args)...); }
- /**
- * @brief Attempts to insert an element into the %unordered_set.
- * @param __pos An iterator that serves as a hint as to where the
- * element should be inserted.
- * @param __args Arguments used to generate the element to be
- * inserted.
- * @return An iterator that points to the element with key equivalent to
- * the one generated from @a __args (may or may not be the
- * element itself).
- *
- * This function is not concerned about whether the insertion took place,
- * and thus does not return a boolean like the single-argument emplace()
- * does. Note that the first parameter is only a hint and can
- * potentially improve the performance of the insertion process. A bad
- * hint would cause no gains in efficiency.
- *
- * For more on @a hinting, see:
- * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
- *
- * Insertion requires amortized constant time.
- */
- template<typename... _Args>
- iterator
- emplace_hint(const_iterator __pos, _Args&&... __args)
- { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
- ///@{
- /**
- * @brief Attempts to insert an element into the %unordered_set.
- * @param __x Element to be inserted.
- * @return A pair, of which the first element is an iterator that points
- * to the possibly inserted element, and the second is a bool
- * that is true if the element was actually inserted.
- *
- * This function attempts to insert an element into the %unordered_set.
- * An %unordered_set relies on unique keys and thus an element is only
- * inserted if it is not already present in the %unordered_set.
- *
- * Insertion requires amortized constant time.
- */
- std::pair<iterator, bool>
- insert(const value_type& __x)
- { return _M_h.insert(__x); }
- std::pair<iterator, bool>
- insert(value_type&& __x)
- { return _M_h.insert(std::move(__x)); }
- ///@}
- ///@{
- /**
- * @brief Attempts to insert an element into the %unordered_set.
- * @param __hint An iterator that serves as a hint as to where the
- * element should be inserted.
- * @param __x Element to be inserted.
- * @return An iterator that points to the element with key of
- * @a __x (may or may not be the element passed in).
- *
- * This function is not concerned about whether the insertion took place,
- * and thus does not return a boolean like the single-argument insert()
- * does. Note that the first parameter is only a hint and can
- * potentially improve the performance of the insertion process. A bad
- * hint would cause no gains in efficiency.
- *
- * For more on @a hinting, see:
- * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
- *
- * Insertion requires amortized constant.
- */
- iterator
- insert(const_iterator __hint, const value_type& __x)
- { return _M_h.insert(__hint, __x); }
- iterator
- insert(const_iterator __hint, value_type&& __x)
- { return _M_h.insert(__hint, std::move(__x)); }
- ///@}
- /**
- * @brief A template function that attempts to insert a range of
- * elements.
- * @param __first Iterator pointing to the start of the range to be
- * inserted.
- * @param __last Iterator pointing to the end of the range.
- *
- * Complexity similar to that of the range constructor.
- */
- template<typename _InputIterator>
- void
- insert(_InputIterator __first, _InputIterator __last)
- { _M_h.insert(__first, __last); }
- /**
- * @brief Attempts to insert a list of elements into the %unordered_set.
- * @param __l A std::initializer_list<value_type> of elements
- * to be inserted.
- *
- * Complexity similar to that of the range constructor.
- */
- void
- insert(initializer_list<value_type> __l)
- { _M_h.insert(__l); }
- #if __cplusplus > 201402L
- /// Extract a node.
- node_type
- extract(const_iterator __pos)
- {
- __glibcxx_assert(__pos != end());
- return _M_h.extract(__pos);
- }
- /// Extract a node.
- node_type
- extract(const key_type& __key)
- { return _M_h.extract(__key); }
- /// Re-insert an extracted node.
- insert_return_type
- insert(node_type&& __nh)
- { return _M_h._M_reinsert_node(std::move(__nh)); }
- /// Re-insert an extracted node.
- iterator
- insert(const_iterator, node_type&& __nh)
- { return _M_h._M_reinsert_node(std::move(__nh)).position; }
- #endif // C++17
- ///@{
- /**
- * @brief Erases an element from an %unordered_set.
- * @param __position An iterator pointing to the element to be erased.
- * @return An iterator pointing to the element immediately following
- * @a __position prior to the element being erased. If no such
- * element exists, end() is returned.
- *
- * This function erases an element, pointed to by the given iterator,
- * from an %unordered_set. Note that this function only erases the
- * element, and that if the element is itself a pointer, the pointed-to
- * memory is not touched in any way. Managing the pointer is the user's
- * responsibility.
- */
- iterator
- erase(const_iterator __position)
- { return _M_h.erase(__position); }
- // LWG 2059.
- iterator
- erase(iterator __position)
- { return _M_h.erase(__position); }
- ///@}
- /**
- * @brief Erases elements according to the provided key.
- * @param __x Key of element to be erased.
- * @return The number of elements erased.
- *
- * This function erases all the elements located by the given key from
- * an %unordered_set. For an %unordered_set the result of this function
- * can only be 0 (not present) or 1 (present).
- * Note that this function only erases the element, and that if
- * the element is itself a pointer, the pointed-to memory is not touched
- * in any way. Managing the pointer is the user's responsibility.
- */
- size_type
- erase(const key_type& __x)
- { return _M_h.erase(__x); }
- /**
- * @brief Erases a [__first,__last) range of elements from an
- * %unordered_set.
- * @param __first Iterator pointing to the start of the range to be
- * erased.
- * @param __last Iterator pointing to the end of the range to
- * be erased.
- * @return The iterator @a __last.
- *
- * This function erases a sequence of elements from an %unordered_set.
- * Note that this function only erases the element, and that if
- * the element is itself a pointer, the pointed-to memory is not touched
- * in any way. Managing the pointer is the user's responsibility.
- */
- iterator
- erase(const_iterator __first, const_iterator __last)
- { return _M_h.erase(__first, __last); }
- /**
- * Erases all elements in an %unordered_set. Note that this function only
- * erases the elements, and that if the elements themselves are pointers,
- * the pointed-to memory is not touched in any way. Managing the pointer
- * is the user's responsibility.
- */
- void
- clear() noexcept
- { _M_h.clear(); }
- /**
- * @brief Swaps data with another %unordered_set.
- * @param __x An %unordered_set of the same element and allocator
- * types.
- *
- * This exchanges the elements between two sets in constant time.
- * Note that the global std::swap() function is specialized such that
- * std::swap(s1,s2) will feed to this function.
- */
- void
- swap(unordered_set& __x)
- noexcept( noexcept(_M_h.swap(__x._M_h)) )
- { _M_h.swap(__x._M_h); }
- #if __cplusplus > 201402L
- template<typename, typename, typename>
- friend class std::_Hash_merge_helper;
- template<typename _H2, typename _P2>
- void
- merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
- {
- using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
- _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
- }
- template<typename _H2, typename _P2>
- void
- merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
- { merge(__source); }
- template<typename _H2, typename _P2>
- void
- merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
- {
- using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
- _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
- }
- template<typename _H2, typename _P2>
- void
- merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
- { merge(__source); }
- #endif // C++17
- // observers.
- /// Returns the hash functor object with which the %unordered_set was
- /// constructed.
- hasher
- hash_function() const
- { return _M_h.hash_function(); }
- /// Returns the key comparison object with which the %unordered_set was
- /// constructed.
- key_equal
- key_eq() const
- { return _M_h.key_eq(); }
- // lookup.
- ///@{
- /**
- * @brief Tries to locate an element in an %unordered_set.
- * @param __x Element to be located.
- * @return Iterator pointing to sought-after element, or end() if not
- * found.
- *
- * This function takes a key and tries to locate the element with which
- * the key matches. If successful the function returns an iterator
- * pointing to the sought after element. If unsuccessful it returns the
- * past-the-end ( @c end() ) iterator.
- */
- iterator
- find(const key_type& __x)
- { return _M_h.find(__x); }
- #if __cplusplus > 201703L
- template<typename _Kt>
- auto
- find(const _Kt& __k)
- -> decltype(_M_h._M_find_tr(__k))
- { return _M_h._M_find_tr(__k); }
- #endif
- const_iterator
- find(const key_type& __x) const
- { return _M_h.find(__x); }
- #if __cplusplus > 201703L
- template<typename _Kt>
- auto
- find(const _Kt& __k) const
- -> decltype(_M_h._M_find_tr(__k))
- { return _M_h._M_find_tr(__k); }
- #endif
- ///@}
- ///@{
- /**
- * @brief Finds the number of elements.
- * @param __x Element to located.
- * @return Number of elements with specified key.
- *
- * This function only makes sense for unordered_multisets; for
- * unordered_set the result will either be 0 (not present) or 1
- * (present).
- */
- size_type
- count(const key_type& __x) const
- { return _M_h.count(__x); }
- #if __cplusplus > 201703L
- template<typename _Kt>
- auto
- count(const _Kt& __k) const
- -> decltype(_M_h._M_count_tr(__k))
- { return _M_h._M_count_tr(__k); }
- #endif
- ///@}
- #if __cplusplus > 201703L
- ///@{
- /**
- * @brief Finds whether an element with the given key exists.
- * @param __x Key of elements to be located.
- * @return True if there is any element with the specified key.
- */
- bool
- contains(const key_type& __x) const
- { return _M_h.find(__x) != _M_h.end(); }
- template<typename _Kt>
- auto
- contains(const _Kt& __k) const
- -> decltype(_M_h._M_find_tr(__k), void(), true)
- { return _M_h._M_find_tr(__k) != _M_h.end(); }
- ///@}
- #endif
- ///@{
- /**
- * @brief Finds a subsequence matching given key.
- * @param __x Key to be located.
- * @return Pair of iterators that possibly points to the subsequence
- * matching given key.
- *
- * This function probably only makes sense for multisets.
- */
- std::pair<iterator, iterator>
- equal_range(const key_type& __x)
- { return _M_h.equal_range(__x); }
- #if __cplusplus > 201703L
- template<typename _Kt>
- auto
- equal_range(const _Kt& __k)
- -> decltype(_M_h._M_equal_range_tr(__k))
- { return _M_h._M_equal_range_tr(__k); }
- #endif
- std::pair<const_iterator, const_iterator>
- equal_range(const key_type& __x) const
- { return _M_h.equal_range(__x); }
- #if __cplusplus > 201703L
- template<typename _Kt>
- auto
- equal_range(const _Kt& __k) const
- -> decltype(_M_h._M_equal_range_tr(__k))
- { return _M_h._M_equal_range_tr(__k); }
- #endif
- ///@}
- // bucket interface.
- /// Returns the number of buckets of the %unordered_set.
- size_type
- bucket_count() const noexcept
- { return _M_h.bucket_count(); }
- /// Returns the maximum number of buckets of the %unordered_set.
- size_type
- max_bucket_count() const noexcept
- { return _M_h.max_bucket_count(); }
- /*
- * @brief Returns the number of elements in a given bucket.
- * @param __n A bucket index.
- * @return The number of elements in the bucket.
- */
- size_type
- bucket_size(size_type __n) const
- { return _M_h.bucket_size(__n); }
- /*
- * @brief Returns the bucket index of a given element.
- * @param __key A key instance.
- * @return The key bucket index.
- */
- size_type
- bucket(const key_type& __key) const
- { return _M_h.bucket(__key); }
- ///@{
- /**
- * @brief Returns a read-only (constant) iterator pointing to the first
- * bucket element.
- * @param __n The bucket index.
- * @return A read-only local iterator.
- */
- local_iterator
- begin(size_type __n)
- { return _M_h.begin(__n); }
- const_local_iterator
- begin(size_type __n) const
- { return _M_h.begin(__n); }
- const_local_iterator
- cbegin(size_type __n) const
- { return _M_h.cbegin(__n); }
- ///@}
- ///@{
- /**
- * @brief Returns a read-only (constant) iterator pointing to one past
- * the last bucket elements.
- * @param __n The bucket index.
- * @return A read-only local iterator.
- */
- local_iterator
- end(size_type __n)
- { return _M_h.end(__n); }
- const_local_iterator
- end(size_type __n) const
- { return _M_h.end(__n); }
- const_local_iterator
- cend(size_type __n) const
- { return _M_h.cend(__n); }
- ///@}
- // hash policy.
- /// Returns the average number of elements per bucket.
- float
- load_factor() const noexcept
- { return _M_h.load_factor(); }
- /// Returns a positive number that the %unordered_set tries to keep the
- /// load factor less than or equal to.
- float
- max_load_factor() const noexcept
- { return _M_h.max_load_factor(); }
- /**
- * @brief Change the %unordered_set maximum load factor.
- * @param __z The new maximum load factor.
- */
- void
- max_load_factor(float __z)
- { _M_h.max_load_factor(__z); }
- /**
- * @brief May rehash the %unordered_set.
- * @param __n The new number of buckets.
- *
- * Rehash will occur only if the new number of buckets respect the
- * %unordered_set maximum load factor.
- */
- void
- rehash(size_type __n)
- { _M_h.rehash(__n); }
- /**
- * @brief Prepare the %unordered_set for a specified number of
- * elements.
- * @param __n Number of elements required.
- *
- * Same as rehash(ceil(n / max_load_factor())).
- */
- void
- reserve(size_type __n)
- { _M_h.reserve(__n); }
- template<typename _Value1, typename _Hash1, typename _Pred1,
- typename _Alloc1>
- friend bool
- operator==(const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&,
- const unordered_set<_Value1, _Hash1, _Pred1, _Alloc1>&);
- };
- #if __cpp_deduction_guides >= 201606
- template<typename _InputIterator,
- typename _Hash =
- hash<typename iterator_traits<_InputIterator>::value_type>,
- typename _Pred =
- equal_to<typename iterator_traits<_InputIterator>::value_type>,
- typename _Allocator =
- allocator<typename iterator_traits<_InputIterator>::value_type>,
- typename = _RequireInputIter<_InputIterator>,
- typename = _RequireNotAllocatorOrIntegral<_Hash>,
- typename = _RequireNotAllocator<_Pred>,
- typename = _RequireAllocator<_Allocator>>
- unordered_set(_InputIterator, _InputIterator,
- unordered_set<int>::size_type = {},
- _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
- -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
- _Hash, _Pred, _Allocator>;
- template<typename _Tp, typename _Hash = hash<_Tp>,
- typename _Pred = equal_to<_Tp>,
- typename _Allocator = allocator<_Tp>,
- typename = _RequireNotAllocatorOrIntegral<_Hash>,
- typename = _RequireNotAllocator<_Pred>,
- typename = _RequireAllocator<_Allocator>>
- unordered_set(initializer_list<_Tp>,
- unordered_set<int>::size_type = {},
- _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator())
- -> unordered_set<_Tp, _Hash, _Pred, _Allocator>;
- template<typename _InputIterator, typename _Allocator,
- typename = _RequireInputIter<_InputIterator>,
- typename = _RequireAllocator<_Allocator>>
- unordered_set(_InputIterator, _InputIterator,
- unordered_set<int>::size_type, _Allocator)
- -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
- hash<
- typename iterator_traits<_InputIterator>::value_type>,
- equal_to<
- typename iterator_traits<_InputIterator>::value_type>,
- _Allocator>;
- template<typename _InputIterator, typename _Hash, typename _Allocator,
- typename = _RequireInputIter<_InputIterator>,
- typename = _RequireNotAllocatorOrIntegral<_Hash>,
- typename = _RequireAllocator<_Allocator>>
- unordered_set(_InputIterator, _InputIterator,
- unordered_set<int>::size_type,
- _Hash, _Allocator)
- -> unordered_set<typename iterator_traits<_InputIterator>::value_type,
- _Hash,
- equal_to<
- typename iterator_traits<_InputIterator>::value_type>,
- _Allocator>;
- template<typename _Tp, typename _Allocator,
- typename = _RequireAllocator<_Allocator>>
- unordered_set(initializer_list<_Tp>,
- unordered_set<int>::size_type, _Allocator)
- -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
- template<typename _Tp, typename _Hash, typename _Allocator,
- typename = _RequireNotAllocatorOrIntegral<_Hash>,
- typename = _RequireAllocator<_Allocator>>
- unordered_set(initializer_list<_Tp>,
- unordered_set<int>::size_type, _Hash, _Allocator)
- -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
- #endif
- /**
- * @brief A standard container composed of equivalent keys
- * (possibly containing multiple of each key value) in which the
- * elements' keys are the elements themselves.
- *
- * @ingroup unordered_associative_containers
- *
- * @tparam _Value Type of key objects.
- * @tparam _Hash Hashing function object type, defaults to hash<_Value>.
- * @tparam _Pred Predicate function object type, defaults
- * to equal_to<_Value>.
- * @tparam _Alloc Allocator type, defaults to allocator<_Key>.
- *
- * Meets the requirements of a <a href="tables.html#65">container</a>, and
- * <a href="tables.html#xx">unordered associative container</a>
- *
- * Base is _Hashtable, dispatched at compile time via template
- * alias __umset_hashtable.
- */
- template<typename _Value,
- typename _Hash = hash<_Value>,
- typename _Pred = equal_to<_Value>,
- typename _Alloc = allocator<_Value>>
- class unordered_multiset
- {
- typedef __umset_hashtable<_Value, _Hash, _Pred, _Alloc> _Hashtable;
- _Hashtable _M_h;
- public:
- // typedefs:
- ///@{
- /// Public typedefs.
- typedef typename _Hashtable::key_type key_type;
- typedef typename _Hashtable::value_type value_type;
- typedef typename _Hashtable::hasher hasher;
- typedef typename _Hashtable::key_equal key_equal;
- typedef typename _Hashtable::allocator_type allocator_type;
- ///@}
- ///@{
- /// Iterator-related typedefs.
- typedef typename _Hashtable::pointer pointer;
- typedef typename _Hashtable::const_pointer const_pointer;
- typedef typename _Hashtable::reference reference;
- typedef typename _Hashtable::const_reference const_reference;
- typedef typename _Hashtable::iterator iterator;
- typedef typename _Hashtable::const_iterator const_iterator;
- typedef typename _Hashtable::local_iterator local_iterator;
- typedef typename _Hashtable::const_local_iterator const_local_iterator;
- typedef typename _Hashtable::size_type size_type;
- typedef typename _Hashtable::difference_type difference_type;
- ///@}
- #if __cplusplus > 201402L
- using node_type = typename _Hashtable::node_type;
- #endif
- // construct/destroy/copy
- /// Default constructor.
- unordered_multiset() = default;
- /**
- * @brief Default constructor creates no elements.
- * @param __n Minimal initial number of buckets.
- * @param __hf A hash functor.
- * @param __eql A key equality functor.
- * @param __a An allocator object.
- */
- explicit
- unordered_multiset(size_type __n,
- const hasher& __hf = hasher(),
- const key_equal& __eql = key_equal(),
- const allocator_type& __a = allocator_type())
- : _M_h(__n, __hf, __eql, __a)
- { }
- /**
- * @brief Builds an %unordered_multiset from a range.
- * @param __first An input iterator.
- * @param __last An input iterator.
- * @param __n Minimal initial number of buckets.
- * @param __hf A hash functor.
- * @param __eql A key equality functor.
- * @param __a An allocator object.
- *
- * Create an %unordered_multiset consisting of copies of the elements
- * from [__first,__last). This is linear in N (where N is
- * distance(__first,__last)).
- */
- template<typename _InputIterator>
- unordered_multiset(_InputIterator __first, _InputIterator __last,
- size_type __n = 0,
- const hasher& __hf = hasher(),
- const key_equal& __eql = key_equal(),
- const allocator_type& __a = allocator_type())
- : _M_h(__first, __last, __n, __hf, __eql, __a)
- { }
- /// Copy constructor.
- unordered_multiset(const unordered_multiset&) = default;
- /// Move constructor.
- unordered_multiset(unordered_multiset&&) = default;
- /**
- * @brief Builds an %unordered_multiset from an initializer_list.
- * @param __l An initializer_list.
- * @param __n Minimal initial number of buckets.
- * @param __hf A hash functor.
- * @param __eql A key equality functor.
- * @param __a An allocator object.
- *
- * Create an %unordered_multiset consisting of copies of the elements in
- * the list. This is linear in N (where N is @a __l.size()).
- */
- unordered_multiset(initializer_list<value_type> __l,
- size_type __n = 0,
- const hasher& __hf = hasher(),
- const key_equal& __eql = key_equal(),
- const allocator_type& __a = allocator_type())
- : _M_h(__l, __n, __hf, __eql, __a)
- { }
- /// Copy assignment operator.
- unordered_multiset&
- operator=(const unordered_multiset&) = default;
- /// Move assignment operator.
- unordered_multiset&
- operator=(unordered_multiset&&) = default;
- /**
- * @brief Creates an %unordered_multiset with no elements.
- * @param __a An allocator object.
- */
- explicit
- unordered_multiset(const allocator_type& __a)
- : _M_h(__a)
- { }
- /*
- * @brief Copy constructor with allocator argument.
- * @param __uset Input %unordered_multiset to copy.
- * @param __a An allocator object.
- */
- unordered_multiset(const unordered_multiset& __umset,
- const allocator_type& __a)
- : _M_h(__umset._M_h, __a)
- { }
- /*
- * @brief Move constructor with allocator argument.
- * @param __umset Input %unordered_multiset to move.
- * @param __a An allocator object.
- */
- unordered_multiset(unordered_multiset&& __umset,
- const allocator_type& __a)
- noexcept( noexcept(_Hashtable(std::move(__umset._M_h), __a)) )
- : _M_h(std::move(__umset._M_h), __a)
- { }
- unordered_multiset(size_type __n, const allocator_type& __a)
- : unordered_multiset(__n, hasher(), key_equal(), __a)
- { }
- unordered_multiset(size_type __n, const hasher& __hf,
- const allocator_type& __a)
- : unordered_multiset(__n, __hf, key_equal(), __a)
- { }
- template<typename _InputIterator>
- unordered_multiset(_InputIterator __first, _InputIterator __last,
- size_type __n,
- const allocator_type& __a)
- : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a)
- { }
- template<typename _InputIterator>
- unordered_multiset(_InputIterator __first, _InputIterator __last,
- size_type __n, const hasher& __hf,
- const allocator_type& __a)
- : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a)
- { }
- unordered_multiset(initializer_list<value_type> __l,
- size_type __n,
- const allocator_type& __a)
- : unordered_multiset(__l, __n, hasher(), key_equal(), __a)
- { }
- unordered_multiset(initializer_list<value_type> __l,
- size_type __n, const hasher& __hf,
- const allocator_type& __a)
- : unordered_multiset(__l, __n, __hf, key_equal(), __a)
- { }
- /**
- * @brief %Unordered_multiset list assignment operator.
- * @param __l An initializer_list.
- *
- * This function fills an %unordered_multiset with copies of the elements
- * in the initializer list @a __l.
- *
- * Note that the assignment completely changes the %unordered_multiset
- * and that the resulting %unordered_multiset's size is the same as the
- * number of elements assigned.
- */
- unordered_multiset&
- operator=(initializer_list<value_type> __l)
- {
- _M_h = __l;
- return *this;
- }
- /// Returns the allocator object used by the %unordered_multiset.
- allocator_type
- get_allocator() const noexcept
- { return _M_h.get_allocator(); }
- // size and capacity:
- /// Returns true if the %unordered_multiset is empty.
- _GLIBCXX_NODISCARD bool
- empty() const noexcept
- { return _M_h.empty(); }
- /// Returns the size of the %unordered_multiset.
- size_type
- size() const noexcept
- { return _M_h.size(); }
- /// Returns the maximum size of the %unordered_multiset.
- size_type
- max_size() const noexcept
- { return _M_h.max_size(); }
- // iterators.
- ///@{
- /**
- * Returns a read-only (constant) iterator that points to the first
- * element in the %unordered_multiset.
- */
- iterator
- begin() noexcept
- { return _M_h.begin(); }
- const_iterator
- begin() const noexcept
- { return _M_h.begin(); }
- ///@}
- ///@{
- /**
- * Returns a read-only (constant) iterator that points one past the last
- * element in the %unordered_multiset.
- */
- iterator
- end() noexcept
- { return _M_h.end(); }
- const_iterator
- end() const noexcept
- { return _M_h.end(); }
- ///@}
- /**
- * Returns a read-only (constant) iterator that points to the first
- * element in the %unordered_multiset.
- */
- const_iterator
- cbegin() const noexcept
- { return _M_h.begin(); }
- /**
- * Returns a read-only (constant) iterator that points one past the last
- * element in the %unordered_multiset.
- */
- const_iterator
- cend() const noexcept
- { return _M_h.end(); }
- // modifiers.
- /**
- * @brief Builds and insert an element into the %unordered_multiset.
- * @param __args Arguments used to generate an element.
- * @return An iterator that points to the inserted element.
- *
- * Insertion requires amortized constant time.
- */
- template<typename... _Args>
- iterator
- emplace(_Args&&... __args)
- { return _M_h.emplace(std::forward<_Args>(__args)...); }
- /**
- * @brief Inserts an element into the %unordered_multiset.
- * @param __pos An iterator that serves as a hint as to where the
- * element should be inserted.
- * @param __args Arguments used to generate the element to be
- * inserted.
- * @return An iterator that points to the inserted element.
- *
- * Note that the first parameter is only a hint and can potentially
- * improve the performance of the insertion process. A bad hint would
- * cause no gains in efficiency.
- *
- * For more on @a hinting, see:
- * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
- *
- * Insertion requires amortized constant time.
- */
- template<typename... _Args>
- iterator
- emplace_hint(const_iterator __pos, _Args&&... __args)
- { return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
- ///@{
- /**
- * @brief Inserts an element into the %unordered_multiset.
- * @param __x Element to be inserted.
- * @return An iterator that points to the inserted element.
- *
- * Insertion requires amortized constant time.
- */
- iterator
- insert(const value_type& __x)
- { return _M_h.insert(__x); }
- iterator
- insert(value_type&& __x)
- { return _M_h.insert(std::move(__x)); }
- ///@}
- ///@{
- /**
- * @brief Inserts an element into the %unordered_multiset.
- * @param __hint An iterator that serves as a hint as to where the
- * element should be inserted.
- * @param __x Element to be inserted.
- * @return An iterator that points to the inserted element.
- *
- * Note that the first parameter is only a hint and can potentially
- * improve the performance of the insertion process. A bad hint would
- * cause no gains in efficiency.
- *
- * For more on @a hinting, see:
- * https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
- *
- * Insertion requires amortized constant.
- */
- iterator
- insert(const_iterator __hint, const value_type& __x)
- { return _M_h.insert(__hint, __x); }
- iterator
- insert(const_iterator __hint, value_type&& __x)
- { return _M_h.insert(__hint, std::move(__x)); }
- ///@}
- /**
- * @brief A template function that inserts a range of elements.
- * @param __first Iterator pointing to the start of the range to be
- * inserted.
- * @param __last Iterator pointing to the end of the range.
- *
- * Complexity similar to that of the range constructor.
- */
- template<typename _InputIterator>
- void
- insert(_InputIterator __first, _InputIterator __last)
- { _M_h.insert(__first, __last); }
- /**
- * @brief Inserts a list of elements into the %unordered_multiset.
- * @param __l A std::initializer_list<value_type> of elements to be
- * inserted.
- *
- * Complexity similar to that of the range constructor.
- */
- void
- insert(initializer_list<value_type> __l)
- { _M_h.insert(__l); }
- #if __cplusplus > 201402L
- /// Extract a node.
- node_type
- extract(const_iterator __pos)
- {
- __glibcxx_assert(__pos != end());
- return _M_h.extract(__pos);
- }
- /// Extract a node.
- node_type
- extract(const key_type& __key)
- { return _M_h.extract(__key); }
- /// Re-insert an extracted node.
- iterator
- insert(node_type&& __nh)
- { return _M_h._M_reinsert_node_multi(cend(), std::move(__nh)); }
- /// Re-insert an extracted node.
- iterator
- insert(const_iterator __hint, node_type&& __nh)
- { return _M_h._M_reinsert_node_multi(__hint, std::move(__nh)); }
- #endif // C++17
- ///@{
- /**
- * @brief Erases an element from an %unordered_multiset.
- * @param __position An iterator pointing to the element to be erased.
- * @return An iterator pointing to the element immediately following
- * @a __position prior to the element being erased. If no such
- * element exists, end() is returned.
- *
- * This function erases an element, pointed to by the given iterator,
- * from an %unordered_multiset.
- *
- * Note that this function only erases the element, and that if the
- * element is itself a pointer, the pointed-to memory is not touched in
- * any way. Managing the pointer is the user's responsibility.
- */
- iterator
- erase(const_iterator __position)
- { return _M_h.erase(__position); }
- // LWG 2059.
- iterator
- erase(iterator __position)
- { return _M_h.erase(__position); }
- ///@}
- /**
- * @brief Erases elements according to the provided key.
- * @param __x Key of element to be erased.
- * @return The number of elements erased.
- *
- * This function erases all the elements located by the given key from
- * an %unordered_multiset.
- *
- * Note that this function only erases the element, and that if the
- * element is itself a pointer, the pointed-to memory is not touched in
- * any way. Managing the pointer is the user's responsibility.
- */
- size_type
- erase(const key_type& __x)
- { return _M_h.erase(__x); }
- /**
- * @brief Erases a [__first,__last) range of elements from an
- * %unordered_multiset.
- * @param __first Iterator pointing to the start of the range to be
- * erased.
- * @param __last Iterator pointing to the end of the range to
- * be erased.
- * @return The iterator @a __last.
- *
- * This function erases a sequence of elements from an
- * %unordered_multiset.
- *
- * Note that this function only erases the element, and that if
- * the element is itself a pointer, the pointed-to memory is not touched
- * in any way. Managing the pointer is the user's responsibility.
- */
- iterator
- erase(const_iterator __first, const_iterator __last)
- { return _M_h.erase(__first, __last); }
- /**
- * Erases all elements in an %unordered_multiset.
- *
- * Note that this function only erases the elements, and that if the
- * elements themselves are pointers, the pointed-to memory is not touched
- * in any way. Managing the pointer is the user's responsibility.
- */
- void
- clear() noexcept
- { _M_h.clear(); }
- /**
- * @brief Swaps data with another %unordered_multiset.
- * @param __x An %unordered_multiset of the same element and allocator
- * types.
- *
- * This exchanges the elements between two sets in constant time.
- * Note that the global std::swap() function is specialized such that
- * std::swap(s1,s2) will feed to this function.
- */
- void
- swap(unordered_multiset& __x)
- noexcept( noexcept(_M_h.swap(__x._M_h)) )
- { _M_h.swap(__x._M_h); }
- #if __cplusplus > 201402L
- template<typename, typename, typename>
- friend class std::_Hash_merge_helper;
- template<typename _H2, typename _P2>
- void
- merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
- {
- using _Merge_helper
- = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
- _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
- }
- template<typename _H2, typename _P2>
- void
- merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
- { merge(__source); }
- template<typename _H2, typename _P2>
- void
- merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
- {
- using _Merge_helper
- = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
- _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
- }
- template<typename _H2, typename _P2>
- void
- merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
- { merge(__source); }
- #endif // C++17
- // observers.
- /// Returns the hash functor object with which the %unordered_multiset
- /// was constructed.
- hasher
- hash_function() const
- { return _M_h.hash_function(); }
- /// Returns the key comparison object with which the %unordered_multiset
- /// was constructed.
- key_equal
- key_eq() const
- { return _M_h.key_eq(); }
- // lookup.
- ///@{
- /**
- * @brief Tries to locate an element in an %unordered_multiset.
- * @param __x Element to be located.
- * @return Iterator pointing to sought-after element, or end() if not
- * found.
- *
- * This function takes a key and tries to locate the element with which
- * the key matches. If successful the function returns an iterator
- * pointing to the sought after element. If unsuccessful it returns the
- * past-the-end ( @c end() ) iterator.
- */
- iterator
- find(const key_type& __x)
- { return _M_h.find(__x); }
- #if __cplusplus > 201703L
- template<typename _Kt>
- auto
- find(const _Kt& __x)
- -> decltype(_M_h._M_find_tr(__x))
- { return _M_h._M_find_tr(__x); }
- #endif
- const_iterator
- find(const key_type& __x) const
- { return _M_h.find(__x); }
- #if __cplusplus > 201703L
- template<typename _Kt>
- auto
- find(const _Kt& __x) const
- -> decltype(_M_h._M_find_tr(__x))
- { return _M_h._M_find_tr(__x); }
- #endif
- ///@}
- ///@{
- /**
- * @brief Finds the number of elements.
- * @param __x Element to located.
- * @return Number of elements with specified key.
- */
- size_type
- count(const key_type& __x) const
- { return _M_h.count(__x); }
- #if __cplusplus > 201703L
- template<typename _Kt>
- auto
- count(const _Kt& __x) const -> decltype(_M_h._M_count_tr(__x))
- { return _M_h._M_count_tr(__x); }
- #endif
- ///@}
- #if __cplusplus > 201703L
- ///@{
- /**
- * @brief Finds whether an element with the given key exists.
- * @param __x Key of elements to be located.
- * @return True if there is any element with the specified key.
- */
- bool
- contains(const key_type& __x) const
- { return _M_h.find(__x) != _M_h.end(); }
- template<typename _Kt>
- auto
- contains(const _Kt& __x) const
- -> decltype(_M_h._M_find_tr(__x), void(), true)
- { return _M_h._M_find_tr(__x) != _M_h.end(); }
- ///@}
- #endif
- ///@{
- /**
- * @brief Finds a subsequence matching given key.
- * @param __x Key to be located.
- * @return Pair of iterators that possibly points to the subsequence
- * matching given key.
- */
- std::pair<iterator, iterator>
- equal_range(const key_type& __x)
- { return _M_h.equal_range(__x); }
- #if __cplusplus > 201703L
- template<typename _Kt>
- auto
- equal_range(const _Kt& __x)
- -> decltype(_M_h._M_equal_range_tr(__x))
- { return _M_h._M_equal_range_tr(__x); }
- #endif
- std::pair<const_iterator, const_iterator>
- equal_range(const key_type& __x) const
- { return _M_h.equal_range(__x); }
- #if __cplusplus > 201703L
- template<typename _Kt>
- auto
- equal_range(const _Kt& __x) const
- -> decltype(_M_h._M_equal_range_tr(__x))
- { return _M_h._M_equal_range_tr(__x); }
- #endif
- ///@}
- // bucket interface.
- /// Returns the number of buckets of the %unordered_multiset.
- size_type
- bucket_count() const noexcept
- { return _M_h.bucket_count(); }
- /// Returns the maximum number of buckets of the %unordered_multiset.
- size_type
- max_bucket_count() const noexcept
- { return _M_h.max_bucket_count(); }
- /*
- * @brief Returns the number of elements in a given bucket.
- * @param __n A bucket index.
- * @return The number of elements in the bucket.
- */
- size_type
- bucket_size(size_type __n) const
- { return _M_h.bucket_size(__n); }
- /*
- * @brief Returns the bucket index of a given element.
- * @param __key A key instance.
- * @return The key bucket index.
- */
- size_type
- bucket(const key_type& __key) const
- { return _M_h.bucket(__key); }
- ///@{
- /**
- * @brief Returns a read-only (constant) iterator pointing to the first
- * bucket element.
- * @param __n The bucket index.
- * @return A read-only local iterator.
- */
- local_iterator
- begin(size_type __n)
- { return _M_h.begin(__n); }
- const_local_iterator
- begin(size_type __n) const
- { return _M_h.begin(__n); }
- const_local_iterator
- cbegin(size_type __n) const
- { return _M_h.cbegin(__n); }
- ///@}
- ///@{
- /**
- * @brief Returns a read-only (constant) iterator pointing to one past
- * the last bucket elements.
- * @param __n The bucket index.
- * @return A read-only local iterator.
- */
- local_iterator
- end(size_type __n)
- { return _M_h.end(__n); }
- const_local_iterator
- end(size_type __n) const
- { return _M_h.end(__n); }
- const_local_iterator
- cend(size_type __n) const
- { return _M_h.cend(__n); }
- ///@}
- // hash policy.
- /// Returns the average number of elements per bucket.
- float
- load_factor() const noexcept
- { return _M_h.load_factor(); }
- /// Returns a positive number that the %unordered_multiset tries to keep the
- /// load factor less than or equal to.
- float
- max_load_factor() const noexcept
- { return _M_h.max_load_factor(); }
- /**
- * @brief Change the %unordered_multiset maximum load factor.
- * @param __z The new maximum load factor.
- */
- void
- max_load_factor(float __z)
- { _M_h.max_load_factor(__z); }
- /**
- * @brief May rehash the %unordered_multiset.
- * @param __n The new number of buckets.
- *
- * Rehash will occur only if the new number of buckets respect the
- * %unordered_multiset maximum load factor.
- */
- void
- rehash(size_type __n)
- { _M_h.rehash(__n); }
- /**
- * @brief Prepare the %unordered_multiset for a specified number of
- * elements.
- * @param __n Number of elements required.
- *
- * Same as rehash(ceil(n / max_load_factor())).
- */
- void
- reserve(size_type __n)
- { _M_h.reserve(__n); }
- template<typename _Value1, typename _Hash1, typename _Pred1,
- typename _Alloc1>
- friend bool
- operator==(const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&,
- const unordered_multiset<_Value1, _Hash1, _Pred1, _Alloc1>&);
- };
- #if __cpp_deduction_guides >= 201606
- template<typename _InputIterator,
- typename _Hash =
- hash<typename iterator_traits<_InputIterator>::value_type>,
- typename _Pred =
- equal_to<typename iterator_traits<_InputIterator>::value_type>,
- typename _Allocator =
- allocator<typename iterator_traits<_InputIterator>::value_type>,
- typename = _RequireInputIter<_InputIterator>,
- typename = _RequireNotAllocatorOrIntegral<_Hash>,
- typename = _RequireNotAllocator<_Pred>,
- typename = _RequireAllocator<_Allocator>>
- unordered_multiset(_InputIterator, _InputIterator,
- unordered_multiset<int>::size_type = {},
- _Hash = _Hash(), _Pred = _Pred(),
- _Allocator = _Allocator())
- -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
- _Hash, _Pred, _Allocator>;
- template<typename _Tp, typename _Hash = hash<_Tp>,
- typename _Pred = equal_to<_Tp>,
- typename _Allocator = allocator<_Tp>,
- typename = _RequireNotAllocatorOrIntegral<_Hash>,
- typename = _RequireNotAllocator<_Pred>,
- typename = _RequireAllocator<_Allocator>>
- unordered_multiset(initializer_list<_Tp>,
- unordered_multiset<int>::size_type = {},
- _Hash = _Hash(), _Pred = _Pred(),
- _Allocator = _Allocator())
- -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>;
- template<typename _InputIterator, typename _Allocator,
- typename = _RequireInputIter<_InputIterator>,
- typename = _RequireAllocator<_Allocator>>
- unordered_multiset(_InputIterator, _InputIterator,
- unordered_multiset<int>::size_type, _Allocator)
- -> unordered_multiset<typename iterator_traits<_InputIterator>::value_type,
- hash<typename
- iterator_traits<_InputIterator>::value_type>,
- equal_to<typename
- iterator_traits<_InputIterator>::value_type>,
- _Allocator>;
- template<typename _InputIterator, typename _Hash, typename _Allocator,
- typename = _RequireInputIter<_InputIterator>,
- typename = _RequireNotAllocatorOrIntegral<_Hash>,
- typename = _RequireAllocator<_Allocator>>
- unordered_multiset(_InputIterator, _InputIterator,
- unordered_multiset<int>::size_type,
- _Hash, _Allocator)
- -> unordered_multiset<typename
- iterator_traits<_InputIterator>::value_type,
- _Hash,
- equal_to<
- typename
- iterator_traits<_InputIterator>::value_type>,
- _Allocator>;
- template<typename _Tp, typename _Allocator,
- typename = _RequireAllocator<_Allocator>>
- unordered_multiset(initializer_list<_Tp>,
- unordered_multiset<int>::size_type, _Allocator)
- -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>;
- template<typename _Tp, typename _Hash, typename _Allocator,
- typename = _RequireNotAllocatorOrIntegral<_Hash>,
- typename = _RequireAllocator<_Allocator>>
- unordered_multiset(initializer_list<_Tp>,
- unordered_multiset<int>::size_type, _Hash, _Allocator)
- -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>;
- #endif
- template<class _Value, class _Hash, class _Pred, class _Alloc>
- inline void
- swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
- unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
- noexcept(noexcept(__x.swap(__y)))
- { __x.swap(__y); }
- template<class _Value, class _Hash, class _Pred, class _Alloc>
- inline void
- swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
- unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
- noexcept(noexcept(__x.swap(__y)))
- { __x.swap(__y); }
- template<class _Value, class _Hash, class _Pred, class _Alloc>
- inline bool
- operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
- const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
- { return __x._M_h._M_equal(__y._M_h); }
- #if __cpp_impl_three_way_comparison < 201907L
- template<class _Value, class _Hash, class _Pred, class _Alloc>
- inline bool
- operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
- const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
- { return !(__x == __y); }
- #endif
- template<class _Value, class _Hash, class _Pred, class _Alloc>
- inline bool
- operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
- const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
- { return __x._M_h._M_equal(__y._M_h); }
- #if __cpp_impl_three_way_comparison < 201907L
- template<class _Value, class _Hash, class _Pred, class _Alloc>
- inline bool
- operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
- const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
- { return !(__x == __y); }
- #endif
- _GLIBCXX_END_NAMESPACE_CONTAINER
- #if __cplusplus > 201402L
- // Allow std::unordered_set access to internals of compatible sets.
- template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc,
- typename _Hash2, typename _Eq2>
- struct _Hash_merge_helper<
- _GLIBCXX_STD_C::unordered_set<_Val, _Hash1, _Eq1, _Alloc>, _Hash2, _Eq2>
- {
- private:
- template<typename... _Tp>
- using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
- template<typename... _Tp>
- using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
- friend unordered_set<_Val, _Hash1, _Eq1, _Alloc>;
- static auto&
- _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
- { return __set._M_h; }
- static auto&
- _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
- { return __set._M_h; }
- };
- // Allow std::unordered_multiset access to internals of compatible sets.
- template<typename _Val, typename _Hash1, typename _Eq1, typename _Alloc,
- typename _Hash2, typename _Eq2>
- struct _Hash_merge_helper<
- _GLIBCXX_STD_C::unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>,
- _Hash2, _Eq2>
- {
- private:
- template<typename... _Tp>
- using unordered_set = _GLIBCXX_STD_C::unordered_set<_Tp...>;
- template<typename... _Tp>
- using unordered_multiset = _GLIBCXX_STD_C::unordered_multiset<_Tp...>;
- friend unordered_multiset<_Val, _Hash1, _Eq1, _Alloc>;
- static auto&
- _S_get_table(unordered_set<_Val, _Hash2, _Eq2, _Alloc>& __set)
- { return __set._M_h; }
- static auto&
- _S_get_table(unordered_multiset<_Val, _Hash2, _Eq2, _Alloc>& __set)
- { return __set._M_h; }
- };
- #endif // C++17
- _GLIBCXX_END_NAMESPACE_VERSION
- } // namespace std
- #endif /* _UNORDERED_SET_H */
|