Template Class ChainedHashTable

Nested Relationships

Nested Types

Class Documentation

template<class K, class V, Chain C = Chain::FRONT, class H = std::hash<K>>
class ChainedHashTable

a hash table with lists of overflow

Public Types

using Key = K

the type of the keys

using Value = V

the type of the values

using value_type = Pair
using size_type = std::size_t
using difference_type = std::ptrdiff_t
using reference = const Pair&
using const_reference = const Pair&
using iterator = const_iterator

Public Functions

explicit ChainedHashTable(std::size_t m, bool restructure = false, H h = H())

the empty table of m lists, which restructures itself or not

Pre:

m > 0

std::optional<V> lookup(const K &k) const

the value of the key k, or nothing

void insert(const K &k, const V &v)

associates the value v to the key k

Post:

k is in the table

void remove(const K &k)

removes the key k, if it is there

Post:

k is not in the table

bool contains(const K &k) const
std::size_t size(void) const
bool empty(void) const
std::size_t capacity(void) const

the number m of lists

double load(void) const

the load factor n / m

template<class F>
void forEach(F &&f) const

the foreach of the book: f( k , v ) on the pairs, list after list, O( m + n ) time

std::vector<K> chain(std::size_t i) const

the keys of the list i, from its head

Pre:

i < capacity()

std::size_t probes(void) const

the cells of the list examined by the last operation, plus one for the nil that ends an unsuccessful search

std::size_t restructures(void) const

the number of restructurings so far

std::size_t moved(void) const

the number of pairs moved by the restructurings so far

inline const_iterator begin(void) const
inline const_iterator end(void) const
inline const_iterator cbegin(void) const
inline const_iterator cend(void) const
class const_iterator

Public Types

using iterator_category = std::forward_iterator_tag
using value_type = Pair
using difference_type = std::ptrdiff_t
using reference = const Pair&
using pointer = const Pair*

Public Functions

const_iterator(void) = default
inline const_iterator(const Lists *T, std::size_t b)

on the first pair from the list b, or at the end

inline reference operator*(void) const
inline pointer operator->(void) const
inline const_iterator &operator++(void)
inline const_iterator operator++(int)
inline bool operator==(const const_iterator &o) const