Reference/Containers

Containers

CHashSet

A hash-based collection of unique keys.

C++23 mc/CHashSet.h
#include <mc/CHashSet.h>

Standard-style names retain their familiar container meaning. The notes below explain lookup results, mutation, ownership, and Catalyst conveniences; only entirely obvious operations are left as declarations.

Exceptions escaping container operations are translated to CError. Direct iterator operations, element references, and calls through .std() follow the underlying type’s contracts.

Jump to a declaration · 82
<deduction guide for CHashSet> CHashSet CHashSet::allocator_type CHashSet::begin CHashSet::bucket CHashSet::bucket_count CHashSet::bucket_size CHashSet::cbegin CHashSet::cend CHashSet::CHashSet CHashSet::clear CHashSet::clearExcept CHashSet::complement CHashSet::const_iterator CHashSet::const_local_iterator CHashSet::const_pointer CHashSet::const_reference CHashSet::contains CHashSet::count CHashSet::difference_type CHashSet::dump CHashSet::emplace CHashSet::emplace_hint CHashSet::empty CHashSet::end CHashSet::equal_range CHashSet::erase CHashSet::extract CHashSet::find CHashSet::first CHashSet::get_allocator CHashSet::has CHashSet::hash_function CHashSet::hasher CHashSet::HashSet CHashSet::insert CHashSet::insert_range CHashSet::insert_return_type CHashSet::intersect CHashSet::intersects CHashSet::iterator CHashSet::key_eq CHashSet::key_equal CHashSet::key_type CHashSet::load_factor CHashSet::local_iterator CHashSet::max_bucket_count CHashSet::max_load_factor CHashSet::max_size CHashSet::merge CHashSet::node_type CHashSet::operator const HashSet& CHashSet::operator HashSet& CHashSet::operator<< CHashSet::operator= CHashSet::operator[] CHashSet::pointer CHashSet::range CHashSet::reference CHashSet::rehash CHashSet::replace CHashSet::reserve CHashSet::size CHashSet::size_type CHashSet::span CHashSet::std CHashSet::store CHashSet::swap CHashSet::unite CHashSet::value_type CHashSet::~CHashSet cOutputSet erase_if operator!= operator< operator<< operator<= operator== operator> operator>= pmr::CHashSet swap

CHashSet

template<class K, class Hash = std::hash<K>, class Pred = std::equal_to<K>, class Alloc = std::allocator<K>> class CHashSet

Types, constants & data

using HashSet = std::unordered_set<K, Hash, Pred, Alloc>;
using key_type = typename HashSet::key_type;
using value_type = typename HashSet::value_type;
using allocator_type = typename HashSet::allocator_type;
using reference = typename HashSet::reference;
using const_reference = typename HashSet::const_reference;
using pointer = typename HashSet::pointer;
using const_pointer = typename HashSet::const_pointer;
using size_type = typename HashSet::size_type;
using difference_type = typename HashSet::difference_type;
using iterator = typename HashSet::iterator;
using const_iterator = typename HashSet::const_iterator;
using node_type = typename HashSet::node_type;
using insert_return_type = typename HashSet::insert_return_type;
using hasher = typename HashSet::hasher;
using key_equal = typename HashSet::key_equal;
using local_iterator = typename HashSet::local_iterator;
using const_local_iterator = typename HashSet::const_local_iterator;

Methods

CHashSet

CHashSet() noexcept(std::is_nothrow_default_constructible_v<HashSet>);
explicit CHashSet(size_type n, const hasher& hash = cContainerDefault<hasher>(), const key_equal& equal = cContainerDefault<key_equal>(), const allocator_type& a = cContainerDefault<allocator_type>());
explicit CHashSet(const allocator_type& a);
CHashSet(size_type n, const allocator_type& a);
CHashSet(size_type n, const hasher& hash, const allocator_type& a);
template<CInputIterator I> CHashSet(I first, I last, size_type n = 0, const hasher& hash = cContainerDefault<hasher>(), const key_equal& equal = cContainerDefault<key_equal>(), const allocator_type& a = cContainerDefault<allocator_type>());
template<CInputIterator I> CHashSet(I first, I last, size_type n, const allocator_type& a);
template<CInputIterator I> CHashSet(I first, I last, size_type n, const hasher& hash, const allocator_type& a);
template<CContainerRange<value_type> R> CHashSet(std::from_range_t, R&& range, size_type n = 0, const hasher& hash = cContainerDefault<hasher>(), const key_equal& equal = cContainerDefault<key_equal>(), const allocator_type& a = cContainerDefault<allocator_type>());
template<CContainerRange<value_type> R> CHashSet(std::from_range_t, R&& range, size_type n, const allocator_type& a);
template<CContainerRange<value_type> R> CHashSet(std::from_range_t, R&& range, size_type n, const hasher& hash, const allocator_type& a);
CHashSet(std::initializer_list<value_type> values, size_type n = 0, const hasher& hash = cContainerDefault<hasher>(), const key_equal& equal = cContainerDefault<key_equal>(), const allocator_type& a = cContainerDefault<allocator_type>());
CHashSet(std::initializer_list<value_type> values, size_type n, const allocator_type& a);
CHashSet(std::initializer_list<value_type> values, size_type n, const hasher& hash, const allocator_type& a);
CHashSet(const CHashSet& other);
CHashSet(CHashSet&& other) noexcept(std::is_nothrow_move_constructible_v<HashSet>);
CHashSet(const CHashSet& other, const allocator_type& a);
CHashSet(CHashSet&& other, const allocator_type& a);
CHashSet(const HashSet& other);
CHashSet(HashSet&& other) noexcept(std::is_nothrow_move_constructible_v<HashSet>);
CHashSet(const HashSet& other, const allocator_type& a);
CHashSet(HashSet&& other, const allocator_type& a);
CHashSet(CBuffer& b);

Creates an empty container or copies entries from a range, initializer list, or compatible container. Equivalent keys are stored once. The CBuffer overload restores the corresponding typed container format. Copy constructors preserve the hash function, equality predicate, and maximum load factor. Without an explicit allocator, copying uses select_on_container_copy_construction; allocator-taking copies use the supplied allocator. A failed copy releases partially constructed elements and leaves the source unchanged.

range

static CHashSet range(int64_t a, int64_t b);
static CHashSet range(size_t size);

Builds the consecutive values in [a, b), or [0, size). An empty interval produces an empty set.

begin

iterator begin() noexcept;
const_iterator begin() const noexcept;
local_iterator begin(size_type n);
const_local_iterator begin(size_type n) const;

cbegin

const_iterator cbegin() const noexcept;
const_local_iterator cbegin(size_type n) const;

end

iterator end() noexcept;
const_iterator end() const noexcept;
local_iterator end(size_type n);
const_local_iterator end(size_type n) const;

cend

const_iterator cend() const noexcept;
const_local_iterator cend(size_type n) const;

span

cspan span() const noexcept;
cspan span(size_t start) const noexcept;
cspan span(size_t start, size_t endOffset) const noexcept;

Returns numeric indices from zero to size(), optionally excluding an initial or trailing portion. It does not return key/value pairs or an element view.

empty

bool empty() const noexcept;

size

size_type size() const noexcept;

max_size

size_type max_size() const noexcept;

operator[]

const key_type& operator[](size_t i) const;

Returns the element at a zero-based position in iteration order; it is not a key lookup. The position must be valid. For tree and hash sets, finding it requires walking the iterators.

first

const key_type& first() const;
const_reference first();

Returns the first element in iteration order; the set must be nonempty. For a hash set this is not necessarily the smallest value.

find

iterator find(const key_type& k);
const_iterator find(const key_type& k) const;
template<class Q> requires(CTransparent<hasher> && CTransparent<key_equal>) iterator find(const Q& key);
template<class Q> requires(CTransparent<hasher> && CTransparent<key_equal>) const_iterator find(const Q& key) const;

Returns an iterator to an equivalent key or element, or end() when none is present. This lookup does not insert a missing entry.

has

bool has(const key_type& x) const;

Reports whether an equivalent key or element is present, without inserting anything.

contains

bool contains(const key_type& x) const;
template<class Q> requires(CTransparent<hasher> && CTransparent<key_equal>) bool contains(const Q& key) const;

Reports whether an equivalent key is present. This is the standard-style spelling of a membership lookup.

count

size_type count(const key_type& k) const;
template<class Q> requires(CTransparent<hasher> && CTransparent<key_equal>) size_type count(const Q& key) const;

Returns the number of elements equivalent to the key. A unique-key container returns either zero or one.

equal_range

std::pair<iterator, iterator> equal_range(const key_type& k);
std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
template<class Q> requires(CTransparent<hasher> && CTransparent<key_equal>) std::pair<iterator, iterator> equal_range(const Q& key);
template<class Q> requires(CTransparent<hasher> && CTransparent<key_equal>) std::pair<const_iterator, const_iterator> equal_range(const Q& key) const;

Returns the half-open iterator range of equivalent keys. A missing key produces an empty range.

insert

std::pair<iterator, bool> insert(const value_type& obj);
std::pair<iterator, bool> insert(value_type&& obj);
iterator insert(const_iterator hint, const value_type& obj);
iterator insert(const_iterator hint, value_type&& obj);
template<CInputIterator InputIterator> void insert(InputIterator first, InputIterator last);
void insert(std::initializer_list<value_type> il);
insert_return_type insert(node_type&& node);
iterator insert(const_iterator hint, node_type&& node);

Inserts entries without replacing an equivalent existing key. For a single value, the pair-returning overload gives an iterator to the existing or inserted entry and a boolean indicating insertion.

insert_range

template<CContainerRange<value_type> R> void insert_range(R&& range);

Inserts elements from a C++ range using the container’s duplicate-key policy. It does not clear the existing contents.

emplace

template<class... Args> std::pair<iterator, bool> emplace(Args&&... args);

Constructs an entry from forwarded arguments and attempts insertion. For unique keys, the pair-returning overload reports whether insertion took place; construction may occur even when the key already exists.

emplace_hint

template<class... Args> iterator emplace_hint(const_iterator position, Args&&... args);

Attempts emplacement using the supplied position as a lookup hint and returns an iterator to the result. The hint does not change the key ordering or duplicate policy.

operator<<

template<class S> CHashSet& operator<<(S&& x);

Inserts one element and returns this set for chaining. Equivalent elements are retained only once.

erase

iterator erase(iterator position) requires(!std::same_as<iterator, const_iterator>);
iterator erase(const_iterator position);
size_type erase(const key_type& k);
iterator erase(const_iterator first, const_iterator last);
template<class Q> requires(CTransparent<hasher> && CTransparent<key_equal> && !std::is_convertible_v<Q, iterator> && !std::is_convertible_v<Q, const_iterator>) size_type erase(Q&& key);

Erases an iterator, a half-open iterator range, or all entries equivalent to a key. Iterator forms return the following iterator; key forms return the number removed.

clear

void clear() noexcept;

clearExcept

template<class S> void clearExcept(const S& s);

Removes entries whose keys are not present in s, as tested by s.has(key).

swap

void swap(CHashSet& s) noexcept(noexcept(s_.swap(s.s_)));
void swap(HashSet& s);

extract

node_type extract(const_iterator position);
node_type extract(const key_type& key);
template<class Q> requires(CTransparent<hasher> && CTransparent<key_equal> && !std::is_convertible_v<Q, iterator> && !std::is_convertible_v<Q, const_iterator>) node_type extract(Q&& key);

Detaches one element into an owning node handle without copying its value. Key lookup returns an empty handle if absent; the node may be inserted into a compatible container.

replace

bool replace(const key_type& xf, const key_type& xr);
bool replace(const key_type& xf, key_type&& xr);

Removes xf and inserts xr if xf exists, returning whether removal took place. If xr was already present, the set becomes one element smaller.

merge

template<class H2, class P2> void merge(CHashSet<K, H2, P2, Alloc>& source);
template<class H2, class P2> void merge(CHashSet<K, H2, P2, Alloc>&& source);
template<class H2, class P2> void merge(std::unordered_set<K, H2, P2, Alloc>& source);
template<class H2, class P2> void merge(std::unordered_set<K, H2, P2, Alloc>&& source);
template<class H2, class P2> void merge(std::unordered_multiset<K, H2, P2, Alloc>& source);
template<class H2, class P2> void merge(std::unordered_multiset<K, H2, P2, Alloc>&& source);

Transfers nodes with keys not already in this set from the source. Duplicates remain in the source; node transfer requires compatible allocators.

intersect

void intersect(const CHashSet& s);

Replaces this set with the elements shared by both sets. The supplied set is unchanged.

intersects

bool intersects(const CHashSet& s) const;

Reports whether the sets share any element. The implementation forms an intersection and may allocate temporary storage.

unite

void unite(const CHashSet& s);

Adds the other set’s elements to this set, retaining each distinct value once. The supplied set is unchanged.

complement

void complement(const CHashSet& s);

Removes from this set every element present in the supplied set. This is the directional difference: this set minus the argument.

std

const HashSet& std() const noexcept;
HashSet& std() noexcept;

Returns a reference to the underlying container for interoperation. Changes affect this object directly; operations through that reference bypass Catalyst exception translation.

operator const HashSet&

operator const HashSet&() const noexcept;

Borrows the underlying container for interoperability. This does not copy storage; references and iterators follow that container’s lifetime and invalidation rules.

operator HashSet&

operator HashSet&() noexcept;

Borrows the underlying container for interoperability. This does not copy storage; references and iterators follow that container’s lifetime and invalidation rules.

bucket_count

size_type bucket_count() const noexcept;

Returns the current number of hash buckets. Rehashing can change this independently of the element count.

max_bucket_count

size_type max_bucket_count() const noexcept;

Returns the implementation’s upper limit on the number of hash buckets.

bucket_size

size_type bucket_size(size_type n) const;

Returns the number of elements in the specified hash bucket. The bucket index must be below bucket_count().

bucket

size_type bucket(const key_type& k) const;

Returns the hash bucket index for a key, whether or not the key is currently stored.

load_factor

float load_factor() const noexcept;

Returns the average number of elements per hash bucket, size() / bucket_count().

max_load_factor

float max_load_factor() const noexcept;
void max_load_factor(float z);

Reads or sets the load-factor threshold used when growing the hash table. Supply a positive value; lowering it can require a later rehash.

rehash

void rehash(size_type n);

Requests at least the specified number of buckets while satisfying the load-factor requirement. Rehashing invalidates iterators but preserves references to elements.

reserve

void reserve(size_type n);

Reserves hash-table capacity for the requested number of elements under the current maximum load factor. A rehash can invalidate iterators.

store

void store(CBuffer& b) const;

Appends the container to a CBuffer; restore it with the buffer-taking constructor.

dump

cstr dump() const;

Returns the stream-formatted contents as a cstr. Use store() for binary serialization.

Free functions & types

Functions

swap

template <class K, class H, class P, class A> void swap(CHashSet<K, H, P, A>& x, CHashSet<K, H, P, A>& y) noexcept(noexcept(x.swap(y)));

operator==

template<class K, class H, class P, class A> bool operator==(const CHashSet<K, H, P, A>& x, const CHashSet<K, H, P, A>& y);

operator!=

template<class K, class H, class P, class A> bool operator!=(const CHashSet<K, H, P, A>& x, const CHashSet<K, H, P, A>& y);

operator<

template<class K, class H, class P, class A> bool operator<(const CHashSet<K, H, P, A>& x, const CHashSet<K, H, P, A>& y);

operator>

template<class K, class H, class P, class A> bool operator>(const CHashSet<K, H, P, A>& x, const CHashSet<K, H, P, A>& y);

operator<=

template<class K, class H, class P, class A> bool operator<=(const CHashSet<K, H, P, A>& x, const CHashSet<K, H, P, A>& y);

operator>=

template<class K, class H, class P, class A> bool operator>=(const CHashSet<K, H, P, A>& x, const CHashSet<K, H, P, A>& y);

cOutputSet

template<class K, class H, class P, class A> inline void cOutputSet(std::ostream& ostr, const CHashSet<K, H, P, A>& s);

operator<<

template<class K, class H, class P, class A> inline std::ostream& operator<<(std::ostream& ostr, const CHashSet<K, H, P, A>& v);

erase_if

template<class K, class H, class P, class A, class Predicate> typename CHashSet<K, H, P, A>::size_type erase_if(CHashSet<K, H, P, A>& container, Predicate predicate);

Removes every element for which the predicate returns true and returns the number removed.

<deduction guide for CHashSet>

template<class... Args, class S = decltype(std::unordered_set(std::declval<Args>()...))> CHashSet(Args&&...) -> CHashSet< typename S::key_type, typename S::hasher, typename S::key_equal, typename S::allocator_type>;
template<class K, class H = std::hash<K>, class P = std::equal_to<K>, CAllocator A = std::allocator<K>> requires(!std::is_integral_v<H> && !CAllocator<H> && !CAllocator<P>) CHashSet(std::initializer_list<K>, size_t = 0, H = H(), P = P(), A = A()) -> CHashSet<std::remove_const_t<K>, H, P, A>;
template<class K, CAllocator A> CHashSet(std::initializer_list<K>, size_t, A) -> CHashSet<std::remove_const_t<K>, std::hash<K>, std::equal_to<K>, A>;
template<class K, class H, CAllocator A> requires(!std::is_integral_v<H> && !CAllocator<H>) CHashSet(std::initializer_list<K>, size_t, H, A) -> CHashSet<std::remove_const_t<K>, H, std::equal_to<K>, A>;

pmr

Types, constants & data

template<class K, class H = std::hash<K>, class P = std::equal_to<K>> using CHashSet = mc::CHashSet<K, H, P, std::pmr::polymorphic_allocator<K>>;