mcrl2::utilities::hashtable

Include file:

#include "mcrl2/utilities/hashtable.h

class mcrl2::utilities::hashtable

A set that assigns each element an unique index.

Public types

type mcrl2::utilities::hashtable::const_iterator

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

type mcrl2::utilities::hashtable::const_reverse_iterator

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

type mcrl2::utilities::hashtable::difference_type

typedef for std::ptrdiff_t

type mcrl2::utilities::hashtable::hasher

typedef for Hash

type mcrl2::utilities::hashtable::iterator

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

type mcrl2::utilities::hashtable::key_equal

typedef for Equals

type mcrl2::utilities::hashtable::key_type

typedef for Key

type mcrl2::utilities::hashtable::pointer

typedef for value_type *

type mcrl2::utilities::hashtable::reference

typedef for value_type &

type mcrl2::utilities::hashtable::reverse_iterator

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

type mcrl2::utilities::hashtable::size_type

typedef for std::size_t

type mcrl2::utilities::hashtable::value_type

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

Public attributes

const typedef value_type * mcrl2::utilities::hashtable::const_pointer

const typedef value_type & mcrl2::utilities::hashtable::const_reference

Private attributes

size_type mcrl2::utilities::hashtable::m_buckets_mask

Always equal to m_hashtable.size() - 1.

Equals mcrl2::utilities::hashtable::m_equals

Hash mcrl2::utilities::hashtable::m_hasher

std::vector<Key> mcrl2::utilities::hashtable::m_hashtable

std::size_t mcrl2::utilities::hashtable::m_number_of_elements

Public member functions

iterator begin()

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

Complexity is constant per operation.

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.

iterator end() const

End of the forward iterator.

iterator erase(const key_type &key)

Erases the key assuming that this key is present in the hashtable..

Returns: An iterator to the next key.

iterator find(const key_type &key)

Find the given key and returns an iterator to that position.

hashtable()

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

hashtable(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<iterator, 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.

bool must_resize()

Check whether the hashtable must be resized. This is not automatic and must be done explicitly.

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.

void resize()

Resize the hashtable. This is not done automatically.

size_type size() const

The number of elements in the indexed set.

Returns: The number of elements in the indexed set.

Private member functions

std::size_t get_index(const key_type &key)

Returns: The index where this key should be stored.

void rehash(std::size_t size)

Resizes the hash table to the given power of two size.