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.TodoDoes not implement std::unordered_map equal_range and swap.

Private types

type bucket_iterator

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

type bucket_type

typedef for detail::bucket_list< Key, Allocator >

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

type const_bucket_iterator

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

Public types

type allocator_type

typedef for typename bucket_type::NodeAllocator

type const_iterator

typedef for unordered_set_iterator< key_type, bucket_type, Allocator, true >

type const_local_iterator

typedef for typename bucket_type::const_iterator

type const_pointer

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

type const_reference

typedef for const value_type &

type difference_type

typedef for std::ptrdiff_t

type hasher

typedef for Hash

type iterator

typedef for unordered_set_iterator< key_type, bucket_type, Allocator, false >

type key_equal

typedef for Equals

type key_type

typedef for Key

type local_iterator

typedef for typename bucket_type::iterator

type pointer

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

type reference

typedef for value_type &

type size_type

typedef for std::size_t

type value_type

typedef for Key

Private attributes

allocator_type m_allocator
std::vector<bucket_type> m_buckets
size_type m_buckets_mask

Always equal to m_buckets.size() - 1.

key_equal m_equals
hasher m_hash
float m_max_load_factor
size_type 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.

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

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(key_type &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_type(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)
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 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(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(const unordered_set &set)
unordered_set(unordered_set &&other) = default
~unordered_set()

Private member functions

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

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

const_bucket_iterator 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_iterator find_bucket(const Args&... args)
const_iterator find_impl(const_bucket_iterator bucket_iterator, const Args&... args) const

Searches for the element in the given bucket.

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

Inserts a bucket node into the hash table.

Does not increment the m_number_of_elements.

void rehash_if_needed()

Resizes the hash table if required.