mcrl2::utilities::unordered_set

Include file:

#include "mcrl2/utilities/unordered_set.h
class mcrl2::utilities::unordered_set

A unordered_set with a subset of the interface of std::unordered_set that only stores a single pointer for each element.

Only supports input iterators (not bidirectional) compared to std::unordered_set. Furthermore, iterating over all elements in the set is O(n + m), where n is the number of elements in the set and m the number of empty buckets. Also incrementing the iterator is O(m) as opposed to O(1) as the standard mandates. Finally, the unordered_set supports allocators that have a specialized allocate_args(args...) to vary the allocation size based on the arguments used. This is required to store _aterm_appl classes with the function symbol arity determined at runtime.

Private types

type Bucket

typedef for lockable_bucket

type bucket_const_it

typedef for typename std::vector< Bucket >::const_iterator

type bucket_it

typedef for typename std::vector< Bucket >::iterator

type NodeAllocator

typedef for typename Bucket::NodeAllocator

Private attributes

NodeAllocator m_allocator
std::vector<Bucket> m_buckets
std::size_t m_buckets_mask

Always equal to m_buckets.size() - 1.

std::size_t m_number_of_elements

The number of elements stored in this set.

Public member functions

const NodeAllocator &allocator() const noexcept

Returns: A reference to the local node allocator.

NodeAllocator &allocator() noexcept
iterator begin()

Returns: An iterator over all keys.

const_iterator begin() const

Returns: A const iterator over all keys.

std::size_t capacity() const noexcept

Returns: The number of elements that can be present in the set before resizing.

void clear()

Removes all elements from the set.

Does not free the vector of buckets itself.

std::size_t count(const Args&... args) const

Counts the number of occurrences of the given key (1 when it exists and 0 otherwise).

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

Inserts an element Key(args...) into the set if it did not already exist.

Returns: A pair of the iterator pointing to the element and a boolean that is true iff a new element was inserted (as opposed to it already existing in the set).

iterator end()
const_iterator end() const
void erase(Key &key)

Erases the given key from the unordered set.

Needs to find the key first.

iterator erase(iterator it)

Erases the element pointed to by the iterator.

Returns: An iterator to the next key.

const_iterator find(const Args&... args) const

Searches whether an object Key(args...) occurs in the set.

Returns: An iterator to the matching element or the end when this object does not exist.

iterator find(const Args&... args)
unordered_set &operator=(const unordered_set &set)
unordered_set &operator=(unordered_set &&other) = default
void print_performance_statistics() const

Prints various information about the underlying buckets.

std::size_t size() const noexcept

Returns: The amount of elements stored in this set.

unordered_set(std::size_t initial_size)

Constructs an unordered_set that can store initial_size number of elements before resizing.

unordered_set()
unordered_set(const unordered_set &set)
unordered_set(unordered_set &&other) = default
~unordered_set()

Private member functions

std::pair<iterator, bool> emplace_impl(bucket_it bucket_it, Args&&... args)

Inserts T(args...) into the given bucket, assumes that it did not exists before.

bucket_const_it find_bucket(const Args&... args) const

Returns: An iterator to the bucket that might contain the element constructed by the given arguments.

The returned iterator always points to a valid bucket.

bucket_it find_bucket(const Args&... args)
const_iterator find_impl(bucket_const_it bucket_it, const Args&... args) const

Searches for the element in the given bucket.

iterator find_impl(bucket_it bucket_it, const Args&... args)
void insert(typename Bucket::node *node)

Inserts a bucket node into the hash table.

Does not increment the m_number_of_elements.

void resize(std::size_t new_size)

Resizes the set to the given number of elements.

void resize_if_needed()

Resizes the hash table if required.