Sets

template<typename K, typename... Properties>
using Set = Store<set<K>, Properties...>;        // written out as Store<set<K>, ...> in code
class Set

A set: Store<set<K>, Properties...>. The name Set stands for the resolved Store type on this page.

A set holds each key once (unique is what a set means). Its order, keys, references, memory, threads and lifecycle are what the request says; the registry picks the container (What a request resolves to).

Request

Representation

Store<set<K>>

gtl::flat_hash_set (open addressing)

Store<set<K>, sorted>

std::set

Store<set<K>, sorted, frozen>

boost::container::flat_set (a sorted vector)

Store<set<K>, stable_refs>

std::unordered_set

Store<set<K>, stable_refs, retains>

RecyclingSet over std::unordered_set (over std::set with sorted): erased nodes are kept for the next elements

Store<set<I>, dense>

DenseSet (a bitset), with proportional_clear one that clears only the words it set

Store<set<I>, dense, constant_clear>

SparseSet (Briggs–Torczon)

Store<set<K>, insertion_ordered>, positional

IndexedSet (a vector plus a hash table of positions); with monotone, an interner

Store<set<K>, positional, monotone, stable_refs>

StableIndexedSet: the elements in segments that never move, no lock

Store<set<K>, concurrent>

gtl::parallel_flat_hash_set (16 shards, a mutex each); with stable_refs, parallel_node_hash_set (a node per element); positional, monotone, concurrent: ConcurrentIndexedSet

Template parameters

K

The key type. hashable by default, orderable with sorted, indexable with dense. A Store whose contents fix its order (sorted, canonical, a sequence) is a key; an unordered Store is not.

Member types

representation

the container chosen

value_type, key_type

K

mapped_type

void

size_type, difference_type

std::size_t, std::ptrdiff_t

iterator, const_iterator, reference, const_reference

the representation’s; a set’s elements never change in place, so iterator is const_iterator

index_type

index<K> (positional only)

Member functions

Construction and assignment

Set()

Empty. Not offered with nonempty.

template<std::input_iterator InputIt>
Set(InputIt first, InputIt last)
Set(std::initializer_list<value_type> elements)

From any elements, each kept once. With nonempty, asserts one.

explicit Set(layer number)
template<std::input_iterator InputIt>
Set(layer number, InputIt first, InputIt last)
Set(layer number, std::initializer_list<value_type> elements)

The same, numbered (urd::layer): a set that hands out positions (positional, insertion_ordered) is built only so, and its views are identified by index and number.

void swap(Set &other) noexcept

Capacity

size_type size() const
bool empty() const
void reserve(std::size_t count)

Hints how many elements will be inserted. Only where the representation can reserve; growable Stores only (not frozen).

Iterators

const_iterator begin() const
const_iterator end() const
const_iterator cbegin() const
const_iterator cend() const

In the set’s order: ascending with sorted (and for a dense bitset), in insertion order with insertion_ordered, unspecified otherwise.

auto rbegin() const
auto rend() const

With an order (sorted or insertion_ordered).

Lookup

const_iterator find(const key_type &key) const
size_type count(const key_type &key) const
bool contains(const key_type &key) const

O(1) expected for hashed keys, O(log n) sorted, O(1) dense (a key that is no index finds nothing).

const_iterator lower_bound(const key_type &key) const
const_iterator upper_bound(const key_type &key) const
std::pair<const_iterator, const_iterator> equal_range(const key_type &key) const

sorted only.

Modifiers

Growable Stores (not frozen):

std::pair<iterator, bool> insert(const value_type &element)
std::pair<iterator, bool> insert(value_type &&element)
iterator insert(const_iterator hint, const value_type &element)
template<std::input_iterator InputIt>
void insert(InputIt first, InputIt last)
void insert(std::initializer_list<value_type> elements)
template<typename ...Args>
std::pair<iterator, bool> emplace(Args&&... args)

Inserts the element unless an equal one is held; the iterator to it and whether it was inserted. In an interner (positional, monotone) the element’s position is its index and never shifts.

Shrinkable Stores (neither frozen nor monotone; monotone_until_clear keeps clear only):

iterator erase(const_iterator pos)
iterator erase(const_iterator first, const_iterator last)
size_type erase(const key_type &key)
void clear()
template<typename Pred>
friend size_type erase_if(Set &store, Pred pred)

Found by argument-dependent lookup, as std::erase_if. clear costs O(capacity), O(elements present) with proportional_clear, O(1) with constant_clear.

Set algebra

bool includes(const Set &other) const

Whether every element of other is in this set.

bool intersects(const Set &other) const

Whether the two share an element.

Both, and |=, &= and -=, are done by whole words: a set has them where its representation is dense and canonical (a bitset), and no other set has them. merge, as std::set::merge, every set has.

Words (dense, a bitset)

Where the set is a bitset (DenseSet), its words (urd::word_t, urd::word_bits bits each, urd/config.hpp): key k at bit k % word_bits of word k / word_bits. A pool of such sets as trees of blocks (Pools) takes and gives rows by them.

std::span<const urd::word_t> significant_words() const noexcept

The words up to the last one with a bit set: equal sets give equal words, however many each keeps.

void assign_words(std::span<const urd::word_t> words)

Makes this the set whose bits words set, its storage reused: a whole assignment, as operator= is, so a frozen set takes it too.

template<typename Fill>
void assign_words(std::size_t count, Fill fill)

The same, written in place: count words, zeroed, then fill(std::span<urd::word_t>) sets their bits. Nothing is copied; nothing is allocated where the set holds count words already.

Positions (positional, and insertion_ordered)

Every insertion-ordered set is kept in one array, so it has positions whether the request names them or not (not with reclaims).

const_reference operator[](std::size_t pos) const
const_reference at(std::size_t pos) const
const_reference front() const
const_reference back() const
std::size_t position(const_iterator it) const

The position of the element at it; size() for end(), as find gives for an absent one.

const_reference operator[](index_type at) const
const_reference at(index_type at) const
index_type index(const_iterator it) const

The same, through index<K>: what an interner mints. at throws std::out_of_range for none or a position past the end.

index_view<K, Store> view(index_type at) const

A index_view<K, Store> of the element, through this Store (urd/elements/view.hpp included).

std::size_t layer() const

The number it was built with (urd::layer): a positional set has no constructor without one.

Least and greatest (sorted, not dense)

front() and back(), as above, give a sorted set’s least and greatest elements (a map’s entries with the least and greatest keys), O(1) in a tree or a sorted array; the Store must not be empty. Dense keys find their first by a scan of the key range, so a dense set reads *begin() where that cost is meant.

Comparison

friend bool operator==(const Set &lhs, const Set &rhs)

Equal contents: by the representation’s == where it has one, else element by element in iteration order.

friend auto operator<=>(const Set &lhs, const Set &rhs)

Lexicographic, where the Store has an order and its elements compare three ways.

Complexity

Representation

ordered lookup

access

iterate

lookup

insert

erase

clear

memory

holds

unordered_flat_set: gtl::flat_hash_set (open-addressing hash table)

—

—

O(capacity)

O(1)~

O(1)*~

O(1)~

O(capacity)

O(capacity), 1.3 words

~n/0.875 slots + 1 byte each; retains

unordered_set: std::unordered_set (hash table)

—

—

O(n)

O(1)~

O(1)*~

O(1)~

O(n)

O(n), 4.8 words

a node per element + buckets; stable references

set: std::set (balanced tree)

O(log n)

—

O(n)

O(log n)

O(log n)

O(log n)

O(n)

O(n), 5 words

a node per element; reclaims

indexed_set: indexed set (a vector in insertion order, plus a hash table of positions)

—

O(1)

O(n)

O(1)~

O(1)*~

O(n)

O(capacity)

O(capacity), 2.5 words

n elements in order + a table of positions

flat_set: boost::container::flat_set (sorted vector)

O(log n)

O(1)

O(n)

O(log n)

O(n)

O(n)

O(n)

O(n), 1.5 words

n elements in one array; retains

recycling_hash_set: recycling hash set (std::unordered_set that keeps erased nodes for reuse)

—

—

as its part

as its part

as its part

as its part

O(n)

O(n), 4.5 words

erased nodes kept for reuse

recycling_tree_set: recycling tree set (std::set that keeps erased nodes for reuse)

as its part

—

as its part

as its part

as its part

as its part

O(n)

O(n), 5.5 words

erased nodes kept for reuse

parallel_hash_set: parallel hash set (gtl: shards, each behind its mutex)

—

—

O(capacity)

O(1)~

O(1)*~

O(1)~

O(capacity)

O(capacity), 1.3 words

16 shards of open addressing, a lock each

parallel_node_hash_set: parallel node hash set (gtl: shards behind mutexes, a node per element that never moves)

—

—

O(capacity)

O(1)~

O(1)*~

O(1)~

O(capacity)

O(n), 3 words

16 shards, a node per element; stable references

stable_indexed_set: stable indexed set (segments that never move, a hash table of positions; no lock)

—

O(1)

O(n)

O(1)~

O(1)*~

—

—

O(capacity), 2.5 words

segments that never move + a table of positions

concurrent_indexed_set: concurrent indexed set (segments that never move, a concurrent table of positions)

—

O(1)

O(n)

O(1)~

O(1)*~

—

—

O(capacity), 4.3 words

segments that never move + a table of positions; new elements under a lock

dense_set: dense set (a bitset over indices)

O(U)

—

O(U)

O(1)

O(1)*

O(1)

O(U)

O(U), 0.03 words

U bits

tracked_dense_set: dense set tracking its words (a bitset over indices, cleared by the words it touched)

O(U)

—

O(U)

O(1)

O(1)*

O(1)

O(n)

O(U), 0.08 words

U bits + the indices of the words in use

sparse_set: sparse set (members array plus index positions, O(1) clear)

—

—

O(n)

O(1)

O(1)*

O(1)

O(1)

O(U), 2.7 words

n members + U positions

ordered_sparse_set: sparse set keeping insertion order (erase shifts the members after it)

—

O(1)

O(n)

O(1)

O(1)*

O(n)

O(1)

O(U), 2.7 words

n members in insertion order + U positions

* amortized, ~ expected; n elements, U the key range, r a row’s length, k a delta’s changes. Memory is the heap it holds (urd::memory_usage): what it grows in, and per element (or key, or slot) at most so many words, each the size of an element and at least a machine word. The declared costs; what they measure to is in Benchmarks.

Example

using Seen = Store<set<User>, dense>;                 // a bitset: User 17 is bit 17
auto seen = Seen { start };
if (seen.insert(next).second) frontier.push(next);

using Names = Store<set<std::string>, positional, monotone>;   // an interner
auto names = Names(urd::layer { 0 });                         // numbered: its views are (index, 0)
const auto [it, fresh] = names.insert("block");
const urd::index<std::string> block = names.index(it);         // 0
names[block];                                                  // "block"