mCRL2
|
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_type > | value_type |
typedef Equals | key_equal |
typedef Hash | hasher |
typedef value_type & | reference |
typedef const value_type & | const_reference |
typedef value_type * | pointer |
typedef const value_type * | const_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. | |
A set that assigns each element an unique index.
Definition at line 26 of file hashtable.h.
typedef std::vector<Key>::const_iterator mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::const_iterator |
Definition at line 41 of file hashtable.h.
typedef const value_type* mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::const_pointer |
Definition at line 38 of file hashtable.h.
typedef const value_type& mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::const_reference |
Definition at line 36 of file hashtable.h.
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.
typedef std::ptrdiff_t mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::difference_type |
Definition at line 46 of file hashtable.h.
typedef Hash mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::hasher |
Definition at line 33 of file hashtable.h.
typedef std::vector<Key>::iterator mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::iterator |
Definition at line 40 of file hashtable.h.
typedef Equals mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::key_equal |
Definition at line 32 of file hashtable.h.
typedef Key mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::key_type |
Definition at line 29 of file hashtable.h.
typedef value_type* mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::pointer |
Definition at line 37 of file hashtable.h.
typedef value_type& mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::reference |
Definition at line 35 of file hashtable.h.
typedef std::vector<Key>::reverse_iterator mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::reverse_iterator |
Definition at line 43 of file hashtable.h.
typedef std::size_t mcrl2::utilities::hashtable< Key, Hash, Equals, Allocator >::size_type |
Definition at line 30 of file hashtable.h.
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.
|
inline |
Constructor of an empty indexed set. Starts with a hashtable of size 128.
Definition at line 54 of file hashtable.h.
|
inline |
Constructor of an empty index set. Starts with a hashtable of the indicated size.
initial_hashtable_size | The initial size of the hashtable. |
hash | The hash function. |
equals | The comparison function for its elements. |
Definition at line 60 of file hashtable.h.
|
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.
|
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.
|
inline |
const_iterator going through the elements in the set numbered from zero upwards.
Definition at line 86 of file hashtable.h.
|
inline |
End of the forward const_iterator.
Definition at line 92 of file hashtable.h.
|
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.
|
inline |
Reverse const_iterator going through the elements from the highest to the lowest numbered element.
Definition at line 110 of file hashtable.h.
|
inline |
End of the reverse const_iterator.
Definition at line 116 of file hashtable.h.
|
inline |
End of the forward iterator.
Definition at line 67 of file hashtable.h.
|
inline |
End of the forward iterator.
Definition at line 80 of file hashtable.h.
|
inline |
Erases the key assuming that this key is present in the hashtable..
Definition at line 118 of file hashtable.h.
|
inline |
Find the given key and returns an iterator to that position.
Definition at line 150 of file hashtable.h.
|
inlineprivate |
Definition at line 166 of file hashtable.h.
|
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.
key | The key to be inserted in the set. |
Definition at line 90 of file hashtable.h.
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.
|
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.
|
inlineprivate |
Resizes the hash table to the given power of two size.
Definition at line 24 of file hashtable.h.
|
inline |
End of the reverse iterator.
Definition at line 104 of file hashtable.h.
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.
|
inline |
The number of elements in the indexed set.
Definition at line 140 of file hashtable.h.
|
private |
Always equal to m_hashtable.size() - 1.
Definition at line 164 of file hashtable.h.
|
private |
Definition at line 159 of file hashtable.h.
|
private |
Definition at line 158 of file hashtable.h.
|
private |
Definition at line 156 of file hashtable.h.
|
private |
Definition at line 161 of file hashtable.h.