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.Additionally, 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.Threadsafe enables concurrent emplace calls, and Resize enables automatically resizing if needed.TodoDoes not implement std::unordered_map equal_range and swap.

Private types

type mcrl2::utilities::unordered_set::bucket_iterator

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

type mcrl2::utilities::unordered_set::bucket_type

typedef for detail::bucket_list< Key, Allocator >

Combine the bucket list and a lock that locks modifications to the bucket list.

type mcrl2::utilities::unordered_set::const_bucket_iterator

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

type mcrl2::utilities::unordered_set::mutex_type

typedef for std::mutex

Public types

type mcrl2::utilities::unordered_set::allocator_type

typedef for typename bucket_type::NodeAllocator

type mcrl2::utilities::unordered_set::const_iterator

typedef for unordered_set_iterator< bucket_type, true >

type mcrl2::utilities::unordered_set::const_local_iterator

typedef for typename bucket_type::const_iterator

type mcrl2::utilities::unordered_set::const_pointer

typedef for typename std::allocator_traits< Allocator >::const_pointer

type mcrl2::utilities::unordered_set::const_reference

typedef for const value_type &

type mcrl2::utilities::unordered_set::difference_type

typedef for std::ptrdiff_t

type mcrl2::utilities::unordered_set::hasher

typedef for Hash

type mcrl2::utilities::unordered_set::iterator

typedef for const_iterator

type mcrl2::utilities::unordered_set::key_equal

typedef for Equals

type mcrl2::utilities::unordered_set::key_type

typedef for Key

type mcrl2::utilities::unordered_set::local_iterator

typedef for typename bucket_type::const_iterator

type mcrl2::utilities::unordered_set::pointer

typedef for typename std::allocator_traits< Allocator >::pointer

type mcrl2::utilities::unordered_set::reference

typedef for value_type &

type mcrl2::utilities::unordered_set::size_type

typedef for std::size_t

type mcrl2::utilities::unordered_set::value_type

typedef for Key

Friends

friend class mcrl2::utilities::unordered_set::unordered_map

friend class mcrl2::utilities::unordered_set::unordered_map

Private static attributes

constexpr bool mcrl2::utilities::unordered_set::allow_transparent

True iff the hash and equals functions allow transparent lookup,.

Private attributes

allocator_type mcrl2::utilities::unordered_set::m_allocator

std::vector<std::mutex> mcrl2::utilities::unordered_set::m_bucket_mutexes

std::vector<bucket_type> mcrl2::utilities::unordered_set::m_buckets

size_type mcrl2::utilities::unordered_set::m_buckets_mask

Always equal to m_buckets.size() - 1.

key_equal mcrl2::utilities::unordered_set::m_equals

hasher mcrl2::utilities::unordered_set::m_hash

float mcrl2::utilities::unordered_set::m_max_load_factor

std::conditional_t<ThreadSafe, std::atomic<size_type>, size_type> mcrl2::utilities::unordered_set::m_number_of_elements

The number of elements stored in this set.

Public member functions

iterator begin()

Returns: An iterator over all keys.

const_iterator begin() const

Returns: A const iterator over all keys.

local_iterator begin(size_type n)

Returns: An iterator to the elements in the given bucket with index n.

const_local_iterator begin(size_type n) const

size_type bucket(const key_type &key) const noexcept

size_type bucket_count() const noexcept

Returns: The number of buckets.

size_type bucket_size(size_type n) const noexcept

size_type capacity() const noexcept

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

Not standard.

const_iterator cbegin() const

Returns: A const iterator over all keys.

const_local_iterator cbegin(size_type n) const

const_iterator cend() const

const_local_iterator cend(size_type n) const

void clear()

Removes all elements from the set.

Does not free the vector of buckets itself.

size_type 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). threadsafe

bool empty() const noexcept

Returns: True iff the set is empty.

iterator end()

const_iterator end() const

local_iterator end(size_type n)

const_local_iterator end(size_type n) const

void erase(const Args&... args)

Erases the given key_type(args…) from the unordered set.

iterator erase(const_iterator it)

Erases the element pointed to by the iterator.

Returns: An iterator to the next key.

iterator find(const Args&... args)

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

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

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

const allocator_type &get_allocator() const noexcept

Returns: A reference to the local node allocator.

allocator_type &get_allocator() noexcept

hasher hash_function() const

key_equal key_eq() const

float load_factor() const

size_type max_bucket_count() const noexcept

float max_load_factor() const

void max_load_factor(float factor)

size_type max_size() const noexcept

unordered_set &operator=(const unordered_set &set)

unordered_set &operator=(unordered_set &&other) = default

void rehash(size_type number_of_buckets)

Resize the number buckets to at least number_of_buckets.

void rehash_if_needed()

Resizes the hash table if necessary.

Not standard.

void reserve(size_type count)

Resizes the set to the given number of elements.

size_type size() const noexcept

Returns: The amount of elements stored in this set.

unordered_set()

unordered_set(const unordered_set &set)

unordered_set(size_type bucket_count, const hasher &hash = hasher(), const key_equal &equals = key_equal())

Constructs an unordered_set that contains bucket_count number of buckets.

unordered_set(unordered_set &&other) = default

~unordered_set()

Private member functions

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

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

void erase_impl(const Args&... args)

Removes T(args…) from the set.

size_type find_bucket_index(const Args&... args) const

Returns: The index of the bucket that might contain the element constructed by the given arguments.

const_iterator find_impl(size_type bucket_index, const Args&... args) const

Searches for the element in the given bucket.