Template Class OpenHashTable

• Defined in File OpenHashTable.h

Nested Relationships

Nested Types

• Struct OpenHashTable::Cell

• Struct OpenHashTable::Places

• Struct OpenHashTable::Probes

Class Documentation

template<class K, class V, class H = std::hash<K>>
class OpenHashTable

a hash table with open addressing

Public Types

enum class Slot

the state of a place

Values:

enumerator NIL

enumerator FULL

enumerator DELETED

using Key = K

the type of the keys

using Value = V

the type of the values

using value_type = std::pair<const K&, const V&>

using size_type = std::size_t

using difference_type = std::ptrdiff_t

using reference = std::pair<const K&, const V&>

using const_reference = std::pair<const K&, const V&>

using const_iterator = SlotIterator<OpenHashTable, Places>

using iterator = const_iterator

Public Functions

OpenHashTable(std::size_t m, Probing probe, bool restructure = false, H h = H())

the empty table of size m with the given inspection, which restructures itself or not

Pre:

m > 0 and probe.works( m )

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; throws std::overflow_error if the inspection finds no place

Post:

k is in the table

void remove(const K &k)

removes the key k, if it is there, leaving a deleted place

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 size m of the vector

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, place after place, O( m ) time

Slot slot(std::size_t i) const

the state of the place i

Pre:

i < capacity()

const K &keyAt(std::size_t i) const

the key in the place i

Pre:

i < capacity() and the place is full

std::size_t probes(void) const

the places examined by the last operation

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

struct Places

the places of the table, for SlotIterator

Public Static Functions

static inline std::size_t size(const auto &o)

static inline bool occupied(const auto &o, std::size_t i)

static inline auto read(const auto &o, std::size_t i)