mcrl2::utilities::indexed_set

Include file:

#include "mcrl2/utilities/indexed_set.h

class mcrl2::utilities::indexed_set

A set that assigns each element an unique index.

Public types

type mcrl2::utilities::indexed_set::const_iterator

typedef for std::deque< Key >::const_iterator

type mcrl2::utilities::indexed_set::const_pointer

typedef for const value_type *

type mcrl2::utilities::indexed_set::const_reference

typedef for const value_type &

type mcrl2::utilities::indexed_set::const_reverse_iterator

typedef for std::deque< Key >::const_reverse_iterator

type mcrl2::utilities::indexed_set::difference_type

typedef for std::ptrdiff_t

type mcrl2::utilities::indexed_set::hasher

typedef for Hash

type mcrl2::utilities::indexed_set::iterator

typedef for std::deque< Key >::iterator

type mcrl2::utilities::indexed_set::key_equal

typedef for Equals

type mcrl2::utilities::indexed_set::key_type

typedef for Key

type mcrl2::utilities::indexed_set::pointer

typedef for value_type *

type mcrl2::utilities::indexed_set::reference

typedef for value_type &

type mcrl2::utilities::indexed_set::reverse_iterator

typedef for std::deque< Key >::reverse_iterator

type mcrl2::utilities::indexed_set::size_type

typedef for std::size_t

type mcrl2::utilities::indexed_set::value_type

typedef for std::pair< const key_type, size_type >

Private attributes

Equals mcrl2::utilities::indexed_set::m_equals

Hash mcrl2::utilities::indexed_set::m_hasher

std::vector<std::size_t> mcrl2::utilities::indexed_set::m_hashtable

std::deque<Key, Allocator> mcrl2::utilities::indexed_set::m_keys

public-static-attrib

constexpr size_type mcrl2::utilities::indexed_set::npos

Value returned when an element does not exist in the set.

Returns: Value indicating non existing element, equal to std::numeric_limits<std::size_t>::max().

Private member functions

std::size_t put_in_hashtable(const Key &key, std::size_t n)

Inserts the given (key, n) pair into the indexed set.

void resize_hashtable()

Resizes the hash table to twice its current size.

Public member functions

const key_type &at(const size_type index) const

Returns a reference to the mapped value.

Returns an out_of_range exception if there is no element with the given key.

Parameters:

• index The position in the indexed set.

Returns: The value at position index.

iterator begin()

Forward iterator which runs through the elements from the lowest to the largest number.

Complexity is constant per operation.

const_iterator begin() const

Forward iterator which runs through the elements from the lowest to the largest number.

Complexity is constant per operation.

const_iterator cbegin() const

const_iterator going through the elements in the set numbered from zero upwards.

const_iterator cend() const

End of the forward const_iterator.

void clear()

Clears the indexed set by removing all its elements. It is not guaranteed that the memory is released too.

const_iterator crbegin() const

Reverse const_iterator going through the elements from the highest to the lowest numbered element.

const_iterator crend() const

End of the reverse const_iterator.

iterator end()

End of the forward iterator.

const_iterator end() const

End of the forward iterator.

const_iterator find(const key_type &key) const

Provides an iterator to the stored key in the indexed set.

Parameters:

• key The key that is sought.

Returns: An iterator to the key, otherwise end().

size_type index(const key_type &key) const

Returns a reference to the mapped value.

Returns an invalid value, larger or equal than the size of the indexed set, if there is no element with the given key.

indexed_set()

Constructor of an empty indexed set. Starts with a hashtable of size 128.

indexed_set(std::size_t initial_hashtable_size, const hasher &hash = hasher(), const key_equal &equals = key_equal())

Constructor of an empty index set. Starts with a hashtable of the indicated size.

Parameters:

• initial_hashtable_size The initial size of the hashtable.

• hash The hash function.

• equals The comparison function for its elements.

std::pair<size_type, bool> insert(const key_type &key)

Insert a key in the indexed set and return its index.

If the element was already in the set, the resulting bool is true, and the existing index is returned. Otherwise, the key is inserted in the set, and the next available index is assigned to it.

Parameters:

• key The key to be inserted in the set.

Returns: The index of the key and a boolean indicating whether the element was actually inserted.

const key_type &operator[](const size_type index) const

Operator that provides a const reference at the position indicated by index.

Parameters:

• index The position in the indexed set.

Returns: The value at position index.

iterator rbegin()

Reverse iterator going through the elements in the set from the largest to the smallest index.

iterator rend()

End of the reverse iterator.

size_type size() const

The number of elements in the indexed set.

Returns: The number of elements in the indexed set.