Template Class DenseHashMap

Nested Relationships

Nested Types

Class Documentation

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

a hash map with its pairs in a dense vector and an index of positions

Public Types

using Key = K

the type of the keys

using Value = V

the type of the values

using value_type = std::pair<K, V>
using size_type = std::size_t
using difference_type = std::ptrdiff_t
using reference = const std::pair<K, V>&
using const_reference = const std::pair<K, V>&
using const_iterator = typename std::vector<std::pair<K, V>>::const_iterator
using iterator = const_iterator

Public Functions

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

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

DenseHashMap(const DenseHashMap &o)
DenseHashMap(DenseHashMap &&o) noexcept

leaves o empty, with no places

DenseHashMap &operator=(DenseHashMap o) noexcept
~DenseHashMap() = default
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 map

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, moving the last pair into its position; true if it was

Post:

k is not in the map

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 of the index, 12 times 0 or a power of 2 at least 2

double load(void) const

the load factor n / m of the index, 0 with no places

std::size_t deleted(void) const

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

void reserve(std::size_t n)

room for n pairs before the map 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, in the order of the vector

const std::pair<K, V> *data(void) const

the pairs, in the order of the vector

void swap(DenseHashMap &o) noexcept
inline const_iterator begin(void) const
inline const_iterator end(void) const
inline const_iterator cbegin(void) const
inline const_iterator cend(void) const