mCRL2
Loading...
Searching...
No Matches
mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator > Class Template Reference

A set that assigns each element an unique index. More...

#include <hashtable.h>

Public Types

typedef Key key_type
 
typedef std::size_t size_type
 
typedef std::pair< const key_type, size_typevalue_type
 
typedef Equals key_equal
 
typedef Hash hasher
 
typedef value_typereference
 
typedef const value_typeconst_reference
 
typedef value_typepointer
 
typedef const value_typeconst_pointer
 
typedef std::vector< Key >::iterator iterator
 
typedef std::vector< Key >::const_iterator const_iterator
 
typedef std::vector< Key >::reverse_iterator reverse_iterator
 
typedef std::vector< Key >::const_reverse_iterator const_reverse_iterator
 
typedef std::ptrdiff_t difference_type
 

Public Member Functions

 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.
 
iterator begin ()
 Forward iterator which runs through the elements from the lowest to the largest number.
 
iterator end ()
 End of the forward iterator.
 
iterator begin () const
 Forward iterator which runs through the elements from the lowest to the largest number.
 
iterator end () const
 End of the forward iterator.
 
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.
 
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.
 
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.
 
void clear ()
 Clears the indexed set by removing all its elements. It is not guaranteed that the memory is released too.
 
std::pair< iterator, bool > insert (const key_type &key)
 Insert a key in the indexed set and return its index.
 
iterator erase (const key_type &key)
 Erases the key assuming that this key is present in the hashtable..
 
iterator find (const key_type &key)
 Find the given key and returns an iterator to that position.
 
size_type size () const
 The number of elements in the indexed set.
 
bool must_resize ()
 Check whether the hashtable must be resized. This is not automatic and must be done explicitly.
 
void resize ()
 Resize the hashtable. This is not done automatically.
 

Private Member Functions

std::size_t get_index (const key_type &key)
 
void rehash (std::size_t size)
 Resizes the hash table to the given power of two size.
 

Private Attributes

std::vector< Key > m_hashtable
 
Hash m_hasher
 
Equals m_equals
 
std::size_t m_number_of_elements = 0
 
size_type m_buckets_mask
 Always equal to m_hashtable.size() - 1.
 

Detailed Description

template<typename Key, typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
class mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >

A set that assigns each element an unique index.

Definition at line 26 of file hashtable.h.

Member Typedef Documentation

◆ const_iterator

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
typedef std::vector<Key>::const_iterator mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::const_iterator

Definition at line 41 of file hashtable.h.

◆ const_pointer

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
typedef const value_type* mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::const_pointer

Definition at line 38 of file hashtable.h.

◆ const_reference

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
typedef const value_type& mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::const_reference

Definition at line 36 of file hashtable.h.

◆ const_reverse_iterator

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
typedef std::vector<Key>::const_reverse_iterator mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::const_reverse_iterator

Definition at line 44 of file hashtable.h.

◆ difference_type

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
typedef std::ptrdiff_t mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::difference_type

Definition at line 46 of file hashtable.h.

◆ hasher

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
typedef Hash mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::hasher

Definition at line 33 of file hashtable.h.

◆ iterator

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
typedef std::vector<Key>::iterator mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::iterator

Definition at line 40 of file hashtable.h.

◆ key_equal

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
typedef Equals mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::key_equal

Definition at line 32 of file hashtable.h.

◆ key_type

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
typedef Key mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::key_type

Definition at line 29 of file hashtable.h.

◆ pointer

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
typedef value_type* mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::pointer

Definition at line 37 of file hashtable.h.

◆ reference

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
typedef value_type& mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::reference

Definition at line 35 of file hashtable.h.

◆ reverse_iterator

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
typedef std::vector<Key>::reverse_iterator mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::reverse_iterator

Definition at line 43 of file hashtable.h.

◆ size_type

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
typedef std::size_t mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::size_type

Definition at line 30 of file hashtable.h.

◆ value_type

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
typedef std::pair<const key_type, size_type> mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::value_type

Definition at line 31 of file hashtable.h.

Constructor & Destructor Documentation

◆ hashtable() [1/2]

template<class Key , typename Hash , typename Equals , typename Allocator >
mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::hashtable
inline

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

Definition at line 54 of file hashtable.h.

◆ hashtable() [2/2]

template<class Key , typename Hash , typename Equals , typename Allocator >
mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::hashtable ( std::size_t  initial_hashtable_size,
const hasher hash = hasher(),
const key_equal equals = key_equal() 
)
inline

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

Parameters
initial_hashtable_sizeThe initial size of the hashtable.
hashThe hash function.
equalsThe comparison function for its elements.

Definition at line 60 of file hashtable.h.

Member Function Documentation

◆ begin() [1/2]

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
iterator mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::begin ( )
inline

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

Complexity is constant per operation.

Definition at line 61 of file hashtable.h.

◆ begin() [2/2]

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
iterator mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::begin ( ) const
inline

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

Complexity is constant per operation.

Definition at line 74 of file hashtable.h.

◆ cbegin()

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
const_iterator mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::cbegin ( ) const
inline

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

Definition at line 86 of file hashtable.h.

◆ cend()

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
const_iterator mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::cend ( ) const
inline

End of the forward const_iterator.

Definition at line 92 of file hashtable.h.

◆ clear()

template<class Key , typename Hash , typename Equals , typename Allocator >
void mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::clear
inline

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

Definition at line 72 of file hashtable.h.

◆ crbegin()

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
const_iterator mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::crbegin ( ) const
inline

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

Definition at line 110 of file hashtable.h.

◆ crend()

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
const_iterator mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::crend ( ) const
inline

End of the reverse const_iterator.

Definition at line 116 of file hashtable.h.

◆ end() [1/2]

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
iterator mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::end ( )
inline

End of the forward iterator.

Definition at line 67 of file hashtable.h.

◆ end() [2/2]

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
iterator mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::end ( ) const
inline

End of the forward iterator.

Definition at line 80 of file hashtable.h.

◆ erase()

template<class Key , typename Hash , typename Equals , typename Allocator >
hashtable< Key, Hash, Equals, Allocator >::iterator mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::erase ( const key_type key)
inline

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

Returns
An iterator to the next key.

Definition at line 118 of file hashtable.h.

◆ find()

template<class Key , typename Hash , typename Equals , typename Allocator >
hashtable< Key, Hash, Equals, Allocator >::iterator mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::find ( const key_type key)
inline

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

Definition at line 150 of file hashtable.h.

◆ get_index()

template<class Key , typename Hash , typename Equals , typename Allocator >
std::size_t mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::get_index ( const key_type key)
inlineprivate
Returns
The index where this key should be stored.

Definition at line 166 of file hashtable.h.

◆ insert()

template<class Key , typename Hash , typename Equals , typename Allocator >
std::pair< typename hashtable< Key, Hash, Equals, Allocator >::iterator, bool > mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::insert ( const key_type key)
inline

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
keyThe key to be inserted in the set.
Returns
The index of the key and a boolean indicating whether the element was actually inserted.

Definition at line 90 of file hashtable.h.

◆ must_resize()

template<class Key , typename Hash , typename Equals , typename Allocator >
bool mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::must_resize

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

Definition at line 78 of file hashtable.h.

◆ rbegin()

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
iterator mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::rbegin ( )
inline

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

Definition at line 98 of file hashtable.h.

◆ rehash()

template<class Key , typename Hash , typename Equals , typename Allocator >
void mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::rehash ( std::size_t  size)
inlineprivate

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

Definition at line 24 of file hashtable.h.

◆ rend()

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
iterator mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::rend ( )
inline

End of the reverse iterator.

Definition at line 104 of file hashtable.h.

◆ resize()

template<class Key , typename Hash , typename Equals , typename Allocator >
void mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::resize

Resize the hashtable. This is not done automatically.

Definition at line 84 of file hashtable.h.

◆ size()

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
size_type mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::size ( ) const
inline

The number of elements in the indexed set.

Returns
The number of elements in the indexed set.

Definition at line 140 of file hashtable.h.

Member Data Documentation

◆ m_buckets_mask

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
size_type mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::m_buckets_mask
private

Always equal to m_hashtable.size() - 1.

Definition at line 164 of file hashtable.h.

◆ m_equals

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
Equals mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::m_equals
private

Definition at line 159 of file hashtable.h.

◆ m_hasher

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
Hash mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::m_hasher
private

Definition at line 158 of file hashtable.h.

◆ m_hashtable

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
std::vector<Key> mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::m_hashtable
private

Definition at line 156 of file hashtable.h.

◆ m_number_of_elements

template<typename Key , typename Hash = std::hash<Key>, typename Equals = std::equal_to<Key>, typename Allocator = std::allocator<Key>>
std::size_t mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::m_number_of_elements = 0
private

Definition at line 161 of file hashtable.h.


The documentation for this class was generated from the following files: