Template Class FlatHashTable

Nested Relationships

Nested Types

Class Documentation

template<class K, class V, class H = DefaultHash<K>, class Eq = std::equal_to<K>>
class FlatHashTable

a hash table with open addressing and control bytes in groups of 15

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 iterator = const_iterator

Public Functions

explicit FlatHashTable(std::size_t n = 0, H h = H(), Eq eq = Eq())

the empty table, with room for n pairs before it grows

FlatHashTable(const FlatHashTable &o)
FlatHashTable(FlatHashTable &&o) noexcept

leaves o empty, with no places

FlatHashTable &operator=(FlatHashTable o) noexcept
~FlatHashTable()
std::optional<V> lookup(const K &k) const

the value of the key k, or nothing

const V *find(const K &k) const

the value of the key k, nil if it is not there

V *find(const K &k)

the value of the key k, to change in place, nil if it is not there

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

associates the value v to the key k; true if k was not there

Post:

k is in the table

bool insert(K &&k, V &&v)

as insert( k , v ), moving the key and the value

bool remove(const K &k)

removes the key k, if it is there, emptying its place; true if it was

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 of places, 15 times 0 or a power of 2 at least 2

double load(void) const

the load factor n / m, 0 with no places

std::size_t deleted(void) const

the places emptied by remove() in groups that some inspection went past, which count as full until the table is rebuilt; O( m ) time, by a scan of the groups

void reserve(std::size_t n)

room for n pairs before the table grows

void clear(void)

removes all the pairs, keeping the places

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

f( k , v ) on the pairs, place after place

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

f( k , v ) on the pairs, place after place, v to change in place

void swap(FlatHashTable &o) noexcept
const_iterator begin(void) const
const_iterator end(void) const
inline const_iterator cbegin(void) const
inline const_iterator cend(void) const
const_iterator erase(const_iterator it)

removes the pair of it, and returns the iterator on the next one

Pre:

it is on a pair of the table

class const_iterator

the iterator on the full places, by its group, the slot of the first place of the group and the mask of the full places of the group from its own on, the lowest bit its place: a step clears that bit and keeps the places still full in the control bytes, so that the next place depends on the previous one by two operations on the mask and a place emptied meanwhile is skipped; past the group it skips the empty groups whole, up to a sentinel group after the last, whose byte 0 is full and whose first place is the end, so that a step tests no bound

Public Types

using value_type = std::pair<const K&, const V&>
using reference = value_type
using difference_type = std::ptrdiff_t
using iterator_concept = std::bidirectional_iterator_tag
using iterator_category = std::input_iterator_tag

Public Functions

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