Template Class CoalescedHashTable

• Defined in File KnuthHashing.h

Nested Relationships

Nested Types

• Struct CoalescedHashTable::Places

• Struct CoalescedHashTable::Slot

Class Documentation

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

a hash table with coalesced lists in the table and a cellar

Public Types

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<CoalescedHashTable, Places>

using iterator = const_iterator

Public Functions

explicit CoalescedHashTable(std::size_t m, std::size_t cellar = 0, H h = H())

a table of m places addressed by the hash and of cellar more

Pre:

m >= 1

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

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

associates v to k

Pre:

k is there, or the table is not full

Post:

k has the value v

std::size_t size(void) const

std::size_t probes(void) const

the places examined by the last lookup() or insert()

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)