30 #ifndef _UNORDERED_SET_H 31 #define _UNORDERED_SET_H 33 namespace std _GLIBCXX_VISIBILITY(default)
35 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
41 template<
typename _Value,
47 __detail::_Identity, _Pred, _Hash,
56 template<
typename _Value,
64 __detail::_Mod_range_hashing,
65 __detail::_Default_ranged_hash,
66 __detail::_Prime_rehash_policy, _Tr>;
89 template<
class _Value,
104 typedef typename _Hashtable::hasher
hasher;
111 typedef typename allocator_type::pointer
pointer;
133 const hasher& __hf =
hasher(),
136 : _M_h(__n, __hf, __eql, __a)
152 template<
typename _InputIterator>
155 const hasher& __hf =
hasher(),
158 : _M_h(__f, __l, __n, __hf, __eql, __a)
180 const hasher& __hf =
hasher(),
183 : _M_h(__l, __n, __hf, __eql, __a)
216 {
return _M_h.get_allocator(); }
223 {
return _M_h.empty(); }
228 {
return _M_h.size(); }
233 {
return _M_h.max_size(); }
244 {
return _M_h.begin(); }
248 {
return _M_h.begin(); }
258 {
return _M_h.end(); }
262 {
return _M_h.end(); }
271 {
return _M_h.begin(); }
279 {
return _M_h.end(); }
298 template<
typename... _Args>
301 {
return _M_h.emplace(std::forward<_Args>(__args)...); }
324 template<
typename... _Args>
327 {
return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
345 {
return _M_h.insert(__x); }
373 insert(const_iterator __hint,
const value_type& __x)
374 {
return _M_h.insert(__hint, __x); }
377 insert(const_iterator __hint, value_type&& __x)
378 {
return _M_h.insert(__hint,
std::move(__x)); }
390 template<
typename _InputIterator>
392 insert(_InputIterator __first, _InputIterator __last)
393 { _M_h.insert(__first, __last); }
404 { _M_h.insert(__l); }
422 {
return _M_h.erase(__position); }
427 {
return _M_h.erase(__it); }
444 {
return _M_h.erase(__x); }
461 erase(const_iterator __first, const_iterator __last)
462 {
return _M_h.erase(__first, __last); }
485 { _M_h.swap(__x._M_h); }
493 {
return _M_h.hash_function(); }
499 {
return _M_h.key_eq(); }
517 {
return _M_h.find(__x); }
520 find(
const key_type& __x)
const 521 {
return _M_h.find(__x); }
535 {
return _M_h.count(__x); }
548 {
return _M_h.equal_range(__x); }
552 {
return _M_h.equal_range(__x); }
560 {
return _M_h.bucket_count(); }
565 {
return _M_h.max_bucket_count(); }
573 bucket_size(size_type __n)
const 574 {
return _M_h.bucket_size(__n); }
582 bucket(
const key_type& __key)
const 583 {
return _M_h.bucket(__key); }
594 {
return _M_h.begin(__n); }
598 {
return _M_h.begin(__n); }
602 {
return _M_h.cbegin(__n); }
614 {
return _M_h.end(__n); }
618 {
return _M_h.end(__n); }
622 {
return _M_h.cend(__n); }
630 {
return _M_h.load_factor(); }
636 {
return _M_h.max_load_factor(); }
644 { _M_h.max_load_factor(__z); }
655 { _M_h.rehash(__n); }
666 { _M_h.reserve(__n); }
668 template<
typename _Value1,
typename _Hash1,
typename _Pred1,
694 template<
class _Value,
709 typedef typename _Hashtable::hasher
hasher;
716 typedef typename allocator_type::pointer
pointer;
738 const hasher& __hf =
hasher(),
741 : _M_h(__n, __hf, __eql, __a)
757 template<
typename _InputIterator>
760 const hasher& __hf =
hasher(),
763 : _M_h(__f, __l, __n, __hf, __eql, __a)
785 const hasher& __hf =
hasher(),
788 : _M_h(__l, __n, __hf, __eql, __a)
821 {
return _M_h.get_allocator(); }
828 {
return _M_h.empty(); }
833 {
return _M_h.size(); }
838 {
return _M_h.max_size(); }
849 {
return _M_h.begin(); }
853 {
return _M_h.begin(); }
863 {
return _M_h.end(); }
867 {
return _M_h.end(); }
876 {
return _M_h.begin(); }
884 {
return _M_h.end(); }
895 template<
typename... _Args>
898 {
return _M_h.emplace(std::forward<_Args>(__args)...); }
917 template<
typename... _Args>
920 {
return _M_h.emplace_hint(__pos, std::forward<_Args>(__args)...); }
932 {
return _M_h.insert(__x); }
957 insert(const_iterator __hint,
const value_type& __x)
958 {
return _M_h.insert(__hint, __x); }
961 insert(const_iterator __hint, value_type&& __x)
962 {
return _M_h.insert(__hint,
std::move(__x)); }
973 template<
typename _InputIterator>
975 insert(_InputIterator __first, _InputIterator __last)
976 { _M_h.insert(__first, __last); }
987 { _M_h.insert(__l); }
1006 {
return _M_h.erase(__position); }
1011 {
return _M_h.erase(__it); }
1029 {
return _M_h.erase(__x); }
1048 erase(const_iterator __first, const_iterator __last)
1049 {
return _M_h.erase(__first, __last); }
1073 { _M_h.swap(__x._M_h); }
1081 {
return _M_h.hash_function(); }
1087 {
return _M_h.key_eq(); }
1105 {
return _M_h.find(__x); }
1109 {
return _M_h.find(__x); }
1119 {
return _M_h.count(__x); }
1130 {
return _M_h.equal_range(__x); }
1134 {
return _M_h.equal_range(__x); }
1142 {
return _M_h.bucket_count(); }
1147 {
return _M_h.max_bucket_count(); }
1155 bucket_size(size_type __n)
const 1156 {
return _M_h.bucket_size(__n); }
1164 bucket(
const key_type& __key)
const 1165 {
return _M_h.bucket(__key); }
1176 {
return _M_h.begin(__n); }
1178 const_local_iterator
1180 {
return _M_h.begin(__n); }
1182 const_local_iterator
1184 {
return _M_h.cbegin(__n); }
1196 {
return _M_h.end(__n); }
1198 const_local_iterator
1200 {
return _M_h.end(__n); }
1202 const_local_iterator
1204 {
return _M_h.cend(__n); }
1212 {
return _M_h.load_factor(); }
1218 {
return _M_h.max_load_factor(); }
1226 { _M_h.max_load_factor(__z); }
1237 { _M_h.rehash(__n); }
1248 { _M_h.reserve(__n); }
1250 template<
typename _Value1,
typename _Hash1,
typename _Pred1,
1257 template<
class _Value,
class _Hash,
class _Pred,
class _Alloc>
1263 template<
class _Value,
class _Hash,
class _Pred,
class _Alloc>
1269 template<
class _Value,
class _Hash,
class _Pred,
class _Alloc>
1273 {
return __x._M_h._M_equal(__y._M_h); }
1275 template<
class _Value,
class _Hash,
class _Pred,
class _Alloc>
1279 {
return !(__x == __y); }
1281 template<
class _Value,
class _Hash,
class _Pred,
class _Alloc>
1285 {
return __x._M_h._M_equal(__y._M_h); }
1287 template<
class _Value,
class _Hash,
class _Pred,
class _Alloc>
1291 {
return !(__x == __y); }
1293 _GLIBCXX_END_NAMESPACE_CONTAINER
void insert(initializer_list< value_type > __l)
Attempts to insert a list of elements into the unordered_set.
iterator begin() noexcept
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_multiset.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
hasher hash_function() const
Returns the hash functor object with which the unordered_multiset was constructed.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
std::pair< iterator, bool > insert(const value_type &__x)
Attempts to insert an element into the unordered_set.
void insert(initializer_list< value_type > __l)
Inserts a list of elements into the unordered_multiset.
allocator_type::const_reference const_reference
Iterator-related typedefs.
iterator begin() noexcept
_Hashtable::size_type size_type
Iterator-related typedefs.
iterator erase(iterator __it)
Erases an element from an unordered_set.
_Hashtable::key_equal key_equal
Public typedefs.
void rehash(size_type __n)
May rehash the unordered_set.
std::pair< iterator, iterator > equal_range(const key_type &__x)
Finds a subsequence matching given key.
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_set.
unordered_set(_InputIterator __f, _InputIterator __l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_set from a range.
size_type count(const key_type &__x) const
Finds the number of elements.
iterator insert(const_iterator __hint, const value_type &__x)
Attempts to insert an element into the unordered_set.
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
float load_factor() const noexcept
Returns the average number of elements per bucket.
Default range hashing function: use division to fold a large number into the range [0...
_Hashtable::key_type key_type
Public typedefs.
_Hashtable::key_type key_type
Public typedefs.
bool empty() const noexcept
Returns true if the unordered_multiset is empty.
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
const_iterator end() const noexcept
const_iterator cbegin() const noexcept
ISO C++ entities toplevel namespace is std.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
size_type size() const noexcept
Returns the size of the unordered_multiset.
unordered_multiset(size_type __n=10, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Default constructor creates no elements.
iterator emplace_hint(const_iterator __pos, _Args &&...__args)
Inserts an element into the unordered_multiset.
key_equal key_eq() const
Returns the key comparison object with which the unordered_multiset was constructed.
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
unordered_multiset(_InputIterator __f, _InputIterator __l, size_type __n=0, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Builds an unordered_multiset from a range.
unordered_set(size_type __n=10, const hasher &__hf=hasher(), const key_equal &__eql=key_equal(), const allocator_type &__a=allocator_type())
Default constructor creates no elements.
const_iterator begin() const noexcept
void swap(unordered_multiset &__x)
Swaps data with another unordered_multiset.
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_set.
allocator_type get_allocator() const noexcept
Returns the allocator object with which the unordered_multiset was constructed.
iterator insert(value_type &&__x)
Inserts an element into the unordered_multiset.
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_set.
const_iterator cend() const noexcept
float load_factor() const noexcept
Returns the average number of elements per bucket.
_Hashtable::iterator iterator
Iterator-related typedefs.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
size_type max_size() const noexcept
Returns the maximum size of the unordered_set.
_Hashtable::value_type value_type
Public typedefs.
void insert(_InputIterator __first, _InputIterator __last)
A template function that inserts a range of elements.
_Hashtable::allocator_type allocator_type
Public typedefs.
size_type size() const noexcept
Returns the size of the unordered_set.
hasher hash_function() const
Returns the hash functor object with which the unordered_set was constructed.
iterator find(const key_type &__x)
Tries to locate an element in an unordered_multiset.
void rehash(size_type __n)
May rehash the unordered_multiset.
float max_load_factor() const noexcept
Returns a positive number that the unordered_set tries to keep the load factor less than or equal to...
allocator_type get_allocator() const noexcept
Returns the allocator object with which the unordered_set was constructed.
allocator_type::pointer pointer
Iterator-related typedefs.
A standard container composed of unique keys (containing at most one of each key value) in which the ...
size_type bucket_count() const noexcept
Returns the number of buckets of the unordered_set.
_Hashtable::difference_type difference_type
Iterator-related typedefs.
iterator erase(const_iterator __position)
Erases an element from an unordered_set.
key_equal key_eq() const
Returns the key comparison object with which the unordered_set was constructed.
const_iterator end() const noexcept
_Hashtable::hasher hasher
Public typedefs.
iterator insert(const value_type &__x)
Inserts an element into the unordered_multiset.
void swap(unordered_set &__x)
Swaps data with another unordered_set.
void insert(_InputIterator __first, _InputIterator __last)
A template function that attempts to insert a range of elements.
Struct holding two objects of arbitrary type.
iterator emplace(_Args &&...__args)
Builds and insert an element into the unordered_multiset.
bool empty() const noexcept
Returns true if the unordered_set is empty.
local_iterator end(size_type __n)
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
Default value for rehash policy. Bucket size is (usually) the smallest prime that keeps the load fact...
The standard allocator, as per [20.4].
std::pair< iterator, bool > insert(value_type &&__x)
Attempts to insert an element into the unordered_set.
void reserve(size_type __n)
Prepare the unordered_set for a specified number of elements.
_Hashtable::value_type value_type
Public typedefs.
unordered_set & operator=(initializer_list< value_type > __l)
Unordered_set list assignment operator.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
std::pair< iterator, bool > emplace(_Args &&...__args)
Attempts to build and insert an element into the unordered_set.
local_iterator begin(size_type __n)
Returns a read-only (constant) iterator pointing to the first bucket element.
allocator_type::const_pointer const_pointer
Iterator-related typedefs.
_Hashtable::hasher hasher
Public typedefs.
size_type erase(const key_type &__x)
Erases elements according to the provided key.
local_iterator end(size_type __n)
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
Primary class template hash.
local_iterator begin(size_type __n)
Returns a read-only (constant) iterator pointing to the first bucket element.
iterator find(const key_type &__x)
Tries to locate an element in an unordered_set.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
_Hashtable::local_iterator local_iterator
Iterator-related typedefs.
allocator_type::const_reference const_reference
Iterator-related typedefs.
_Hashtable::allocator_type allocator_type
Public typedefs.
size_type max_bucket_count() const noexcept
Returns the maximum number of buckets of the unordered_multiset.
A standard container composed of equivalent keys (possibly containing multiple of each key value) in ...
size_type max_size() const noexcept
Returns the maximum size of the unordered_multiset.
const_local_iterator cbegin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
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())
Builds an unordered_multiset from an initializer_list.
void max_load_factor(float __z)
Change the unordered_multiset maximum load factor.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
allocator_type::reference reference
Iterator-related typedefs.
_Hashtable::const_local_iterator const_local_iterator
Iterator-related typedefs.
unordered_set & operator=(const unordered_set &)=default
Copy assignment operator.
size_type count(const key_type &__x) const
Finds the number of elements.
iterator emplace_hint(const_iterator __pos, _Args &&...__args)
Attempts to insert an element into the unordered_set.
Default ranged hash function H. In principle it should be a function object composed from objects of ...
const_iterator cend() const noexcept
const_local_iterator end(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
iterator insert(const_iterator __hint, value_type &&__x)
Attempts to insert an element into the unordered_set.
iterator erase(const_iterator __first, const_iterator __last)
Erases a [__first,__last) range of elements from an unordered_multiset.
const_iterator find(const key_type &__x) const
Tries to locate an element in an unordered_multiset.
One of the comparison functors.
void reserve(size_type __n)
Prepare the unordered_multiset for a specified number of elements.
_Hashtable::size_type size_type
Iterator-related typedefs.
iterator insert(const_iterator __hint, const value_type &__x)
Inserts an element into the unordered_multiset.
void max_load_factor(float __z)
Change the unordered_set maximum load factor.
unordered_multiset & operator=(initializer_list< value_type > __l)
Unordered_multiset list assignment operator.
std::pair< const_iterator, const_iterator > equal_range(const key_type &__x) const
Finds a subsequence matching given key.
const_local_iterator begin(size_type __n) const
Returns a read-only (constant) iterator pointing to the first bucket element.
_Hashtable::iterator iterator
Iterator-related typedefs.
const_local_iterator cend(size_type __n) const
Returns a read-only (constant) iterator pointing to one past the last bucket elements.
const_iterator cbegin() const noexcept
_Hashtable::const_iterator const_iterator
Iterator-related typedefs.
float max_load_factor() const noexcept
Returns a positive number that the unordered_multiset tries to keep the load factor less than or equa...
allocator_type::pointer pointer
Iterator-related typedefs.
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())
Builds an unordered_set from an initializer_list.
const_iterator begin() const noexcept
allocator_type::const_pointer const_pointer
Iterator-related typedefs.
iterator erase(iterator __it)
Erases an element from an unordered_multiset.
iterator erase(const_iterator __position)
Erases an element from an unordered_multiset.
_Hashtable::key_equal key_equal
Public typedefs.
allocator_type::reference reference
Iterator-related typedefs.
iterator insert(const_iterator __hint, value_type &&__x)
Inserts an element into the unordered_multiset.