// -*- C++ -*-
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef _LIBCPP_HASH_SET
#define _LIBCPP_HASH_SET
/*
hash_set synopsis
namespace __gnu_cxx
{
template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
class Alloc = allocator<Value>>
class hash_set
{
public:
// types
typedef Value key_type;
typedef key_type value_type;
typedef Hash hasher;
typedef Pred key_equal;
typedef Alloc allocator_type;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef typename allocator_traits<allocator_type>::pointer pointer;
typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
typedef typename allocator_traits<allocator_type>::size_type size_type;
typedef typename allocator_traits<allocator_type>::difference_type difference_type;
typedef /unspecified/ iterator;
typedef /unspecified/ const_iterator;
explicit hash_set(size_type n = 193, const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template <class InputIterator>
hash_set(InputIterator f, InputIterator l,
size_type n = 193, const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
hash_set(const hash_set&);
~hash_set();
hash_set& operator=(const hash_set&);
allocator_type get_allocator() const;
bool empty() const;
size_type size() const;
size_type max_size() const;
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
pair<iterator, bool> insert(const value_type& obj);
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
void erase(const_iterator position);
size_type erase(const key_type& k);
void erase(const_iterator first, const_iterator last);
void clear();
void swap(hash_set&);
hasher hash_funct() const;
key_equal key_eq() const;
iterator find(const key_type& k);
const_iterator find(const key_type& k) const;
size_type count(const key_type& k) const;
pair<iterator, iterator> equal_range(const key_type& k);
pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
size_type bucket_count() const;
size_type max_bucket_count() const;
size_type elems_in_bucket(size_type n) const;
void resize(size_type n);
};
template <class Value, class Hash, class Pred, class Alloc>
void swap(hash_set<Value, Hash, Pred, Alloc>& x,
hash_set<Value, Hash, Pred, Alloc>& y);
template <class Value, class Hash, class Pred, class Alloc>
bool
operator==(const hash_set<Value, Hash, Pred, Alloc>& x,
const hash_set<Value, Hash, Pred, Alloc>& y);
template <class Value, class Hash, class Pred, class Alloc>
bool
operator!=(const hash_set<Value, Hash, Pred, Alloc>& x,
const hash_set<Value, Hash, Pred, Alloc>& y);
template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
class Alloc = allocator<Value>>
class hash_multiset
{
public:
// types
typedef Value key_type;
typedef key_type value_type;
typedef Hash hasher;
typedef Pred key_equal;
typedef Alloc allocator_type;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef typename allocator_traits<allocator_type>::pointer pointer;
typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
typedef typename allocator_traits<allocator_type>::size_type size_type;
typedef typename allocator_traits<allocator_type>::difference_type difference_type;
typedef /unspecified/ iterator;
typedef /unspecified/ const_iterator;
explicit hash_multiset(size_type n = 193, const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
template <class InputIterator>
hash_multiset(InputIterator f, InputIterator l,
size_type n = 193, const hasher& hf = hasher(),
const key_equal& eql = key_equal(),
const allocator_type& a = allocator_type());
hash_multiset(const hash_multiset&);
~hash_multiset();
hash_multiset& operator=(const hash_multiset&);
allocator_type get_allocator() const;
bool empty() const;
size_type size() const;
size_type max_size() const;
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
iterator insert(const value_type& obj);
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
void erase(const_iterator position);
size_type erase(const key_type& k);
void erase(const_iterator first, const_iterator last);
void clear();
void swap(hash_multiset&);
hasher hash_funct() const;
key_equal key_eq() const;
iterator find(const key_type& k);
const_iterator find(const key_type& k) const;
size_type count(const key_type& k) const;
pair<iterator, iterator> equal_range(const key_type& k);
pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
size_type bucket_count() const;
size_type max_bucket_count() const;
size_type elems_in_bucket(size_type n) const;
void resize(size_type n);
};
template <class Value, class Hash, class Pred, class Alloc>
void swap(hash_multiset<Value, Hash, Pred, Alloc>& x,
hash_multiset<Value, Hash, Pred, Alloc>& y);
template <class Value, class Hash, class Pred, class Alloc>
bool
operator==(const hash_multiset<Value, Hash, Pred, Alloc>& x,
const hash_multiset<Value, Hash, Pred, Alloc>& y);
template <class Value, class Hash, class Pred, class Alloc>
bool
operator!=(const hash_multiset<Value, Hash, Pred, Alloc>& x,
const hash_multiset<Value, Hash, Pred, Alloc>& y);
} // __gnu_cxx
*/
#include <__config>
#include <__hash_table>
#include <algorithm>
#include <ext/__hash>
#include <functional>
#if defined(__DEPRECATED) && __DEPRECATED
# if defined(_LIBCPP_WARNING)
_LIBCPP_WARNING("Use of the header <ext/hash_set> is deprecated. Migrate to <unordered_set>")
# else
# warning Use of the header <ext/hash_set> is deprecated. Migrate to <unordered_set>
# endif
#endif
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
# pragma GCC system_header
#endif
namespace __gnu_cxx {
template <class _Value,
class _Hash = hash<_Value>,
class _Pred = std::equal_to<_Value>,
class _Alloc = std::allocator<_Value> >
class _LIBCPP_TEMPLATE_VIS hash_set {
public:
// types
typedef _Value key_type;
typedef key_type value_type;
typedef _Hash hasher;
typedef _Pred key_equal;
typedef _Alloc allocator_type;
typedef value_type& reference;
typedef const value_type& const_reference;
private:
typedef std::__hash_table<value_type, hasher, key_equal, allocator_type> __table;
__table __table_;
public:
typedef typename __table::pointer pointer;
typedef typename __table::const_pointer const_pointer;
typedef typename __table::size_type size_type;
typedef typename __table::difference_type difference_type;
typedef typename __table::const_iterator iterator;
typedef typename __table::const_iterator const_iterator;
_LIBCPP_HIDE_FROM_ABI hash_set() {}
_LIBCPP_HIDE_FROM_ABI explicit hash_set(
size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
_LIBCPP_HIDE_FROM_ABI hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
template <class _InputIterator>
_LIBCPP_HIDE_FROM_ABI hash_set(_InputIterator __first, _InputIterator __last);
template <class _InputIterator>
_LIBCPP_HIDE_FROM_ABI
hash_set(_InputIterator __first,
_InputIterator __last,
size_type __n,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal());
template <class _InputIterator>
_LIBCPP_HIDE_FROM_ABI
hash_set(_InputIterator __first,
_InputIterator __last,
size_type __n,
const hasher& __hf,
const key_equal& __eql,
const allocator_type& __a);
_LIBCPP_HIDE_FROM_ABI hash_set(const hash_set& __u);
_LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); }
_LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; }
_LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); }
_LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); }
_LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); }
_LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); }
_LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); }
_LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); }
_LIBCPP_HIDE_FROM_ABI std::pair<iterator, bool> insert(const value_type& __x) {
return __table_.__insert_unique(__x);
}
_LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x).first; }
template <class _InputIterator>
_LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
_LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p); }
_LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_unique(__k); }
_LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) { __table_.erase(__first, __last); }
_LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); }
_LIBCPP_HIDE_FROM_ABI void swap(hash_set& __u) { __table_.swap(__u.__table_); }
_LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function(); }
_LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
_LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
_LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
_LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_unique(__k); }
_LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) {
return __table_.__equal_range_unique(__k);
}
_LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
return __table_.__equal_range_unique(__k);
}
_LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); }
_LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); }
_LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); }
_LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_unique(__n); }
};
template <class _Value, class _Hash, class _Pred, class _Alloc>
hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(size_type __n, const hasher& __hf, const key_equal& __eql)
: __table_(__hf, __eql) {
__table_.__rehash_unique(__n);
}
template <class _Value, class _Hash, class _Pred, class _Alloc>
hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
: __table_(__hf, __eql, __a) {
__table_.__rehash_unique(__n);
}
template <class _Value, class _Hash, class _Pred, class _Alloc>
template <class _InputIterator>
hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(_InputIterator __first, _InputIterator __last) {
insert(__first, __last);
}
template <class _Value, class _Hash, class _Pred, class _Alloc>
template <class _InputIterator>
hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
: __table_(__hf, __eql) {
__table_.__rehash_unique(__n);
insert(__first, __last);
}
template <class _Value, class _Hash, class _Pred, class _Alloc>
template <class _InputIterator>
hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(
_InputIterator __first,
_InputIterator __last,
size_type __n,
const hasher& __hf,
const key_equal& __eql,
const allocator_type& __a)
: __table_(__hf, __eql, __a) {
__table_.__rehash_unique(__n);
insert(__first, __last);
}
template <class _Value, class _Hash, class _Pred, class _Alloc>
hash_set<_Value, _Hash, _Pred, _Alloc>::hash_set(const hash_set& __u) : __table_(__u.__table_) {
__table_.__rehash_unique(__u.bucket_count());
insert(__u.begin(), __u.end());
}
template <class _Value, class _Hash, class _Pred, class _Alloc>
template <class _InputIterator>
inline void hash_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
for (; __first != __last; ++__first)
__table_.__insert_unique(*__first);
}
template <class _Value, class _Hash, class _Pred, class _Alloc>
inline _LIBCPP_HIDE_FROM_ABI void
swap(hash_set<_Value, _Hash, _Pred, _Alloc>& __x, hash_set<_Value, _Hash, _Pred, _Alloc>& __y) {
__x.swap(__y);
}
template <class _Value, class _Hash, class _Pred, class _Alloc>
_LIBCPP_HIDE_FROM_ABI bool
operator==(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) {
if (__x.size() != __y.size())
return false;
typedef typename hash_set<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); __i != __ex; ++__i) {
const_iterator __j = __y.find(*__i);
if (__j == __ey || !(*__i == *__j))
return false;
}
return true;
}
template <class _Value, class _Hash, class _Pred, class _Alloc>
inline _LIBCPP_HIDE_FROM_ABI bool
operator!=(const hash_set<_Value, _Hash, _Pred, _Alloc>& __x, const hash_set<_Value, _Hash, _Pred, _Alloc>& __y) {
return !(__x == __y);
}
template <class _Value,
class _Hash = hash<_Value>,
class _Pred = std::equal_to<_Value>,
class _Alloc = std::allocator<_Value> >
class _LIBCPP_TEMPLATE_VIS hash_multiset {
public:
// types
typedef _Value key_type;
typedef key_type value_type;
typedef _Hash hasher;
typedef _Pred key_equal;
typedef _Alloc allocator_type;
typedef value_type& reference;
typedef const value_type& const_reference;
private:
typedef std::__hash_table<value_type, hasher, key_equal, allocator_type> __table;
__table __table_;
public:
typedef typename __table::pointer pointer;
typedef typename __table::const_pointer const_pointer;
typedef typename __table::size_type size_type;
typedef typename __table::difference_type difference_type;
typedef typename __table::const_iterator iterator;
typedef typename __table::const_iterator const_iterator;
_LIBCPP_HIDE_FROM_ABI hash_multiset() {}
explicit _LIBCPP_HIDE_FROM_ABI
hash_multiset(size_type __n, const hasher& __hf = hasher(), const key_equal& __eql = key_equal());
_LIBCPP_HIDE_FROM_ABI
hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a);
template <class _InputIterator>
_LIBCPP_HIDE_FROM_ABI hash_multiset(_InputIterator __first, _InputIterator __last);
template <class _InputIterator>
_LIBCPP_HIDE_FROM_ABI
hash_multiset(_InputIterator __first,
_InputIterator __last,
size_type __n,
const hasher& __hf = hasher(),
const key_equal& __eql = key_equal());
template <class _InputIterator>
_LIBCPP_HIDE_FROM_ABI hash_multiset(
_InputIterator __first,
_InputIterator __last,
size_type __n,
const hasher& __hf,
const key_equal& __eql,
const allocator_type& __a);
_LIBCPP_HIDE_FROM_ABI hash_multiset(const hash_multiset& __u);
_LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const { return allocator_type(__table_.__node_alloc()); }
_LIBCPP_HIDE_FROM_ABI bool empty() const { return __table_.size() == 0; }
_LIBCPP_HIDE_FROM_ABI size_type size() const { return __table_.size(); }
_LIBCPP_HIDE_FROM_ABI size_type max_size() const { return __table_.max_size(); }
_LIBCPP_HIDE_FROM_ABI iterator begin() { return __table_.begin(); }
_LIBCPP_HIDE_FROM_ABI iterator end() { return __table_.end(); }
_LIBCPP_HIDE_FROM_ABI const_iterator begin() const { return __table_.begin(); }
_LIBCPP_HIDE_FROM_ABI const_iterator end() const { return __table_.end(); }
_LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __x) { return __table_.__insert_multi(__x); }
_LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator, const value_type& __x) { return insert(__x); }
template <class _InputIterator>
_LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last);
_LIBCPP_HIDE_FROM_ABI void erase(const_iterator __p) { __table_.erase(__p); }
_LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __table_.__erase_multi(__k); }
_LIBCPP_HIDE_FROM_ABI void erase(const_iterator __first, const_iterator __last) { __table_.erase(__first, __last); }
_LIBCPP_HIDE_FROM_ABI void clear() { __table_.clear(); }
_LIBCPP_HIDE_FROM_ABI void swap(hash_multiset& __u) { __table_.swap(__u.__table_); }
_LIBCPP_HIDE_FROM_ABI hasher hash_funct() const { return __table_.hash_function(); }
_LIBCPP_HIDE_FROM_ABI key_equal key_eq() const { return __table_.key_eq(); }
_LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __table_.find(__k); }
_LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __table_.find(__k); }
_LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __table_.__count_multi(__k); }
_LIBCPP_HIDE_FROM_ABI std::pair<iterator, iterator> equal_range(const key_type& __k) {
return __table_.__equal_range_multi(__k);
}
_LIBCPP_HIDE_FROM_ABI std::pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
return __table_.__equal_range_multi(__k);
}
_LIBCPP_HIDE_FROM_ABI size_type bucket_count() const { return __table_.bucket_count(); }
_LIBCPP_HIDE_FROM_ABI size_type max_bucket_count() const { return __table_.max_bucket_count(); }
_LIBCPP_HIDE_FROM_ABI size_type elems_in_bucket(size_type __n) const { return __table_.bucket_size(__n); }
_LIBCPP_HIDE_FROM_ABI void resize(size_type __n) { __table_.__rehash_multi(__n); }
};
template <class _Value, class _Hash, class _Pred, class _Alloc>
hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql)
: __table_(__hf, __eql) {
__table_.__rehash_multi(__n);
}
template <class _Value, class _Hash, class _Pred, class _Alloc>
hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
: __table_(__hf, __eql, __a) {
__table_.__rehash_multi(__n);
}
template <class _Value, class _Hash, class _Pred, class _Alloc>
template <class _InputIterator>
hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(_InputIterator __first, _InputIterator __last) {
insert(__first, __last);
}
template <class _Value, class _Hash, class _Pred, class _Alloc>
template <class _InputIterator>
hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
_InputIterator __first, _InputIterator __last, size_type __n, const hasher& __hf, const key_equal& __eql)
: __table_(__hf, __eql) {
__table_.__rehash_multi(__n);
insert(__first, __last);
}
template <class _Value, class _Hash, class _Pred, class _Alloc>
template <class _InputIterator>
hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(
_InputIterator __first,
_InputIterator __last,
size_type __n,
const hasher& __hf,
const key_equal& __eql,
const allocator_type& __a)
: __table_(__hf, __eql, __a) {
__table_.__rehash_multi(__n);
insert(__first, __last);
}
template <class _Value, class _Hash, class _Pred, class _Alloc>
hash_multiset<_Value, _Hash, _Pred, _Alloc>::hash_multiset(const hash_multiset& __u) : __table_(__u.__table_) {
__table_.__rehash_multi(__u.bucket_count());
insert(__u.begin(), __u.end());
}
template <class _Value, class _Hash, class _Pred, class _Alloc>
template <class _InputIterator>
inline void hash_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, _InputIterator __last) {
for (; __first != __last; ++__first)
__table_.__insert_multi(*__first);
}
template <class _Value, class _Hash, class _Pred, class _Alloc>
inline _LIBCPP_HIDE_FROM_ABI void
swap(hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x, hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
__x.swap(__y);
}
template <class _Value, class _Hash, class _Pred, class _Alloc>
_LIBCPP_HIDE_FROM_ABI bool operator==(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
if (__x.size() != __y.size())
return false;
typedef typename hash_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator const_iterator;
typedef std::pair<const_iterator, const_iterator> _EqRng;
for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) {
_EqRng __xeq = __x.equal_range(*__i);
_EqRng __yeq = __y.equal_range(*__i);
if (std::distance(__xeq.first, __xeq.second) != std::distance(__yeq.first, __yeq.second) ||
!std::is_permutation(__xeq.first, __xeq.second, __yeq.first))
return false;
__i = __xeq.second;
}
return true;
}
template <class _Value, class _Hash, class _Pred, class _Alloc>
inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
const hash_multiset<_Value, _Hash, _Pred, _Alloc>& __y) {
return !(__x == __y);
}
} // namespace __gnu_cxx
#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
# include <concepts>
# include <iterator>
# include <type_traits>
#endif
#endif // _LIBCPP_HASH_SET
Codebase Browser
llvm