Flat, memory-conscious hash map optimized for small collections. More...

#include <flat_small_hash_map.h>

Inheritance diagram for roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >:

Collaboration diagram for roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >:

Public Types
using	mapped_type = Value

using	Base = FlatSmallHashtable< std::pair< Key, Value >, Key, HashFn, MapKeyFn< Key, Value >, KeyCmpFn >

using	key_type = typename Base::key_type

using	value_type = typename Base::value_type

using	hasher = typename Base::hasher

using	key_equal = typename Base::key_equal

using	iterator = typename Base::iterator

using	const_iterator = typename Base::const_iterator

Public Types inherited from roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >
using	key_type = Key

using	value_type = Entry

using	hasher = HashFn

using	key_equal = KeyCmpFn

using	iterator = Iterator

using	const_iterator = ConstIterator

Public Member Functions
	FlatSmallHashMap (HashFn hash_fn=HashFn(), KeyCmpFn key_cmp_fn=KeyCmpFn())
	Creates an empty hash map.

	FlatSmallHashMap (uint16_t size_hint, HashFn hash_fn=HashFn(), KeyCmpFn key_cmp_fn=KeyCmpFn())
	Creates a hash map with capacity for approximately `size_hint` elements without rehashing.

template<typename InputIt >
	FlatSmallHashMap (InputIt first, InputIt last, HashFn hash_fn=HashFn(), KeyCmpFn key_cmp_fn=KeyCmpFn())
	Builds a map from an iterator range.

	FlatSmallHashMap (std::initializer_list< value_type > init, HashFn hash_fn=HashFn(), KeyCmpFn key_cmp_fn=KeyCmpFn())
	Builds a map from an initializer list.

	FlatSmallHashMap (const FlatSmallHashMap &other)
	Copy constructor.

const Value &	at (const Key &key) const
	Returns a const reference to the mapped value for `key`.

template<typename K , typename = has_is_transparent_t<HashFn, K>, typename = has_is_transparent_t<KeyCmpFn, K>>
const Value &	at (const K &key) const
	Returns a const reference to the mapped value for `key`.

Value &	at (const Key &key)
	Returns a mutable reference to the mapped value for `key`.

template<typename K , typename = has_is_transparent_t<HashFn, K>, typename = has_is_transparent_t<KeyCmpFn, K>>
Value &	at (const K &key)
	Returns a mutable reference to the mapped value for `key`.

Base::Iterator	find (const Key &key)
	Finds `key` and returns an iterator to the entry, or `end()`.

template<typename K , typename = has_is_transparent_t<HashFn, K>, typename = has_is_transparent_t<KeyCmpFn, K>>
Base::Iterator	find (const K &key)
	Heterogeneous lookup overload of `find`.

Base::ConstIterator	find (const Key &key) const
	Finds `key` and returns a const iterator to the entry, or `end()`.

template<typename K , typename = has_is_transparent_t<HashFn, K>, typename = has_is_transparent_t<KeyCmpFn, K>>
Base::ConstIterator	find (const K &key) const
	Heterogeneous const lookup overload of `find`.

const Value &	operator[] (const Key &key) const
	Returns a const reference to the value for `key`.

template<typename K , typename = has_is_transparent_t<HashFn, K>, typename = has_is_transparent_t<KeyCmpFn, K>>
const Value &	operator[] (const K &key) const
	Heterogeneous const lookup overload of `operator[]`.

Value &	operator[] (const Key &key)
	Returns a mutable reference to the value for `key`.

template<typename K , typename = has_is_transparent_t<HashFn, K>, typename = has_is_transparent_t<KeyCmpFn, K>>
Value &	operator[] (const K &key)
	Heterogeneous mutable overload of `operator[]`.

Public Member Functions inherited from roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >
template<typename InputIt >
	FlatSmallHashtable (InputIt first, InputIt last, HashFn hash_fn=HashFn(), KeyFn key_fn=KeyFn(), KeyCmpFn key_cmp_fn=KeyCmpFn())
	Constructs a table from an iterator range.

	FlatSmallHashtable (std::initializer_list< Entry > init, HashFn hash_fn=HashFn(), KeyFn key_fn=KeyFn(), KeyCmpFn key_cmp_fn=KeyCmpFn())
	Constructs a table from an initializer list.

	FlatSmallHashtable (HashFn hash_fn=HashFn(), KeyFn key_fn=KeyFn(), KeyCmpFn key_cmp_fn=KeyCmpFn())
	Constructs an empty table with default initial capacity.

	FlatSmallHashtable (uint16_t size_hint, HashFn hash_fn=HashFn(), KeyFn key_fn=KeyFn(), KeyCmpFn key_cmp_fn=KeyCmpFn())
	Constructs an empty table sized for `size_hint` elements.

	FlatSmallHashtable (FlatSmallHashtable &&other)
	Move constructor.

	FlatSmallHashtable (const FlatSmallHashtable &other)
	Copy constructor.

	~FlatSmallHashtable ()
	Destructor.

FlatSmallHashtable &	operator= (FlatSmallHashtable &&other)
	Move assignment.

FlatSmallHashtable &	operator= (const FlatSmallHashtable &other)
	Copy assignment.

bool	operator== (const FlatSmallHashtable &other) const
	Equality comparison by key/value content.

bool	operator!= (const FlatSmallHashtable &other)

uint16_t	ht_len () const
	Returns the internal bucket array length.

ConstIterator	begin () const
	Returns an iterator to the first element.

Iterator	begin ()
	Returns a mutable iterator to the first element.

Iterator	end ()
	Returns iterator past the end.

ConstIterator	end () const
	Returns const iterator past the end.

uint16_t	size () const
	Returns the number of stored elements.

bool	empty () const
	Returns whether the table is empty.

uint16_t	capacity () const
	Returns the number of elements insertable before rehashing.

ConstIterator	find (const Key &key) const
	Finds `key` and returns a const iterator to the matching entry.

template<typename K , typename = has_is_transparent_t<HashFn, K>, typename = has_is_transparent_t<KeyCmpFn, K>>
ConstIterator	find (const K &key) const
	Heterogeneous lookup overload of `find`.

bool	erase (const Key &key)
	Removes an entry by key.

template<typename K , typename = has_is_transparent_t<HashFn, K>, typename = has_is_transparent_t<KeyCmpFn, K>>
bool	erase (const K &key)
	Heterogeneous key overload of `erase`.

Iterator	erase (const ConstIterator &itr)
	Removes the entry at `itr` and returns iterator to the next entry.

void	clear ()
	Removes all entries while preserving current allocated capacity.

void	compact ()
	Rebuilds the table to remove tombstones and shrink capacity.

bool	contains (const Key &key) const
	Returns whether `key` exists in the table.

template<typename K , typename = has_is_transparent_t<HashFn, K>, typename = has_is_transparent_t<KeyCmpFn, K>>
bool	contains (const K &key) const
	Heterogeneous key overload of `contains`.

std::pair< Iterator, bool >	insert (Entry val)
	Inserts `val` if key is not present.

Additional Inherited Members
Protected Member Functions inherited from roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >
Iterator	lookup (const Key &key)

template<typename K , typename = has_is_transparent_t<HashFn, K>, typename = has_is_transparent_t<KeyCmpFn, K>>
Iterator	lookup (const K &key)

Detailed Description

template<typename Key, typename Value, typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>
class roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >

Flat, memory-conscious hash map optimized for small collections.

Uses FlatSmallHashtable as the underlying storage and provides a map-like interface over key-value pairs.

Template Parameters

Key	Key type.
Value	Mapped value type.
HashFn	Hash function type.
KeyCmpFn	Key equality predicate type.

Definition at line 43 of file flat_small_hash_map.h.

Member Typedef Documentation

◆ Base

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

using roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::Base = FlatSmallHashtable<std::pair<Key, Value>, Key, HashFn, MapKeyFn<Key, Value>, KeyCmpFn>

Definition at line 49 of file flat_small_hash_map.h.

◆ const_iterator

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

using roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::const_iterator = typename Base::const_iterator

Definition at line 57 of file flat_small_hash_map.h.

◆ hasher

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

using roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::hasher = typename Base::hasher

Definition at line 54 of file flat_small_hash_map.h.

◆ iterator

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

using roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::iterator = typename Base::iterator

Definition at line 56 of file flat_small_hash_map.h.

◆ key_equal

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

using roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::key_equal = typename Base::key_equal

Definition at line 55 of file flat_small_hash_map.h.

◆ key_type

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

using roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::key_type = typename Base::key_type

Definition at line 52 of file flat_small_hash_map.h.

◆ mapped_type

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

using roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::mapped_type = Value

Definition at line 47 of file flat_small_hash_map.h.

◆ value_type

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

using roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::value_type = typename Base::value_type

Definition at line 53 of file flat_small_hash_map.h.

Constructor & Destructor Documentation

◆ FlatSmallHashMap() [1/5]

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::FlatSmallHashMap	(	HashFn	hash_fn = `HashFn()`,
		KeyCmpFn	key_cmp_fn = `KeyCmpFn()`
	)

inline

Creates an empty hash map.

Definition at line 60 of file flat_small_hash_map.h.

◆ FlatSmallHashMap() [2/5]

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::FlatSmallHashMap	(	uint16_t	size_hint,
		HashFn	hash_fn = `HashFn()`,
		KeyCmpFn	key_cmp_fn = `KeyCmpFn()`
	)

inline

Creates a hash map with capacity for approximately size_hint elements without rehashing.

Parameters

size_hint Expected number of inserted items.

Definition at line 66 of file flat_small_hash_map.h.

◆ FlatSmallHashMap() [3/5]

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

template<typename InputIt >

roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::FlatSmallHashMap	(	InputIt	first,
		InputIt	last,
		HashFn	hash_fn = `HashFn()`,
		KeyCmpFn	key_cmp_fn = `KeyCmpFn()`
	)

inline

Builds a map from an iterator range.

Definition at line 72 of file flat_small_hash_map.h.

◆ FlatSmallHashMap() [4/5]

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::FlatSmallHashMap	(	std::initializer_list< value_type >	init,
		HashFn	hash_fn = `HashFn()`,
		KeyCmpFn	key_cmp_fn = `KeyCmpFn()`
	)

inline

Builds a map from an initializer list.

Definition at line 77 of file flat_small_hash_map.h.

◆ FlatSmallHashMap() [5/5]

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::FlatSmallHashMap ( const FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn > & other )

inline

Copy constructor.

Definition at line 82 of file flat_small_hash_map.h.

Member Function Documentation

◆ at() [1/4]

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

template<typename K , typename = has_is_transparent_t<HashFn, K>, typename = has_is_transparent_t<KeyCmpFn, K>>

Value & roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::at ( const K & key )

inline

Returns a mutable reference to the mapped value for key.

Heterogeneous overload enabled for transparent hash/equality functions.

Definition at line 118 of file flat_small_hash_map.h.

References roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::end(), and roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::lookup().

◆ at() [2/4]

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

template<typename K , typename = has_is_transparent_t<HashFn, K>, typename = has_is_transparent_t<KeyCmpFn, K>>

const Value & roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::at ( const K & key ) const

inline

Returns a const reference to the mapped value for key.

Heterogeneous overload enabled for transparent hash/equality functions.

Definition at line 98 of file flat_small_hash_map.h.

References roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::end(), and roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::find().

◆ at() [3/4]

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

Value & roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::at ( const Key & key )

inline

Returns a mutable reference to the mapped value for key.

Asserts in debug builds if key is not present.

Definition at line 107 of file flat_small_hash_map.h.

References roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::end(), and roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::lookup().

◆ at() [4/4]

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

const Value & roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::at ( const Key & key ) const

inline

Returns a const reference to the mapped value for key.

Asserts in debug builds if key is not present.

Definition at line 87 of file flat_small_hash_map.h.

References roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::end(), and roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::find().

Referenced by roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::operator[](), and roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::operator[]().

◆ find() [1/4]

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

template<typename K , typename = has_is_transparent_t<HashFn, K>, typename = has_is_transparent_t<KeyCmpFn, K>>

Base::Iterator roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::find ( const K & key )

inline

Heterogeneous lookup overload of find.

Definition at line 130 of file flat_small_hash_map.h.

References roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::lookup().

◆ find() [2/4]

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

template<typename K , typename = has_is_transparent_t<HashFn, K>, typename = has_is_transparent_t<KeyCmpFn, K>>

Base::ConstIterator roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::find ( const K & key ) const

inline

Heterogeneous const lookup overload of find.

Definition at line 143 of file flat_small_hash_map.h.

References roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::find().

◆ find() [3/4]

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

Base::Iterator roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::find ( const Key & key )

inline

Finds key and returns an iterator to the entry, or end().

Definition at line 125 of file flat_small_hash_map.h.

References roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::lookup().

Referenced by roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::at(), and roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::at().

◆ find() [4/4]

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

Base::ConstIterator roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::find ( const Key & key ) const

inline

Finds key and returns a const iterator to the entry, or end().

Definition at line 136 of file flat_small_hash_map.h.

References roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::find().

◆ operator[]() [1/4]

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

template<typename K , typename = has_is_transparent_t<HashFn, K>, typename = has_is_transparent_t<KeyCmpFn, K>>

Value & roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::operator[] ( const K & key )

inline

Heterogeneous mutable overload of operator[].

Inserts a default-constructed value when key is not present.

Definition at line 174 of file flat_small_hash_map.h.

References roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::end(), roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::insert(), and roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::lookup().

◆ operator[]() [2/4]

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

template<typename K , typename = has_is_transparent_t<HashFn, K>, typename = has_is_transparent_t<KeyCmpFn, K>>

const Value & roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::operator[] ( const K & key ) const

inline

Heterogeneous const lookup overload of operator[].

Definition at line 153 of file flat_small_hash_map.h.

References roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::at().

◆ operator[]() [3/4]

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

Value & roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::operator[] ( const Key & key )

inline

Returns a mutable reference to the value for key.

Inserts a default-constructed value when key is not present.

Definition at line 160 of file flat_small_hash_map.h.

References roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::end(), roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::insert(), and roo_collections::FlatSmallHashtable< Entry, Key, HashFn, KeyFn, KeyCmpFn >::lookup().

◆ operator[]() [4/4]

template<typename Key , typename Value , typename HashFn = DefaultHashFn<Key>, typename KeyCmpFn = std::equal_to<Key>>

const Value & roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::operator[] ( const Key & key ) const

inline

Returns a const reference to the value for key.

Definition at line 148 of file flat_small_hash_map.h.

References roo_collections::FlatSmallHashMap< Key, Value, HashFn, KeyCmpFn >::at().

The documentation for this class was generated from the following file:

temp_repos/roo_collections/src/roo_collections/flat_small_hash_map.h

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Base

◆ const_iterator

◆ hasher

◆ iterator

◆ key_equal

◆ key_type

◆ mapped_type

◆ value_type

Constructor & Destructor Documentation

◆ FlatSmallHashMap() [1/5]

◆ FlatSmallHashMap() [2/5]

◆ FlatSmallHashMap() [3/5]

◆ FlatSmallHashMap() [4/5]

◆ FlatSmallHashMap() [5/5]

Member Function Documentation

◆ at() [1/4]

◆ at() [2/4]

◆ at() [3/4]

◆ at() [4/4]

◆ find() [1/4]

◆ find() [2/4]

◆ find() [3/4]

◆ find() [4/4]

◆ operator[]() [1/4]

◆ operator[]() [2/4]

◆ operator[]() [3/4]

◆ operator[]() [4/4]