Template Class CuckooHashTable

Nested Relationships

Nested Types

Class Documentation

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

a DICTIONARY on the cuckoo hashing, with a stash

Public Types

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<CuckooHashTable, Places>
using iterator = const_iterator

Public Functions

explicit CuckooHashTable(std::size_t m = 16, double maxLoad = 0.4, std::size_t s = 0, std::uint64_t seed = 1, H h = H())

the empty table of m places and a stash of s places

Pre:

m >= 2 and 0 < maxLoad < 1 / 2

std::optional<V> lookup(const K &k) const
void insert(const K &k, const V &v)
Post:

k has the value v

void remove(const K &k)
Post:

k is not there

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

the number m of places, the stash excluded

std::size_t rehashes(void) const

the rebuilds with new functions after a failed insertion

std::size_t evictions(void) const

the evictions made by the insertions

std::size_t stashed(void) const

the keys in the stash

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 and the stash, 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)