FixedHashMap< MaxSize, Key, ValueType, Hash, KeyEqual > Class Template Reference

A hash table with a compile-time specified maximum size and ability to efficiently handle perfect hashes. More...

#include <FixedHashMap.hpp>

Public Types
using	key_type = Key
using	mapped_type = ValueType
using	value_type = std::pair<const key_type, mapped_type>
using	size_type = size_t
using	difference_type = ptrdiff_t
using	hasher = Hash
using	key_equal = KeyEqual
using	reference = value_type&
using	const_reference = const value_type&
using	pointer = value_type*
using	const_pointer = const value_type*
using	iterator
using	const_iterator

Public Member Functions
	FixedHashMap (std::initializer_list< value_type > init)
	FixedHashMap (const FixedHashMap &)=default
FixedHashMap &	operator= (const FixedHashMap &other)
	FixedHashMap (FixedHashMap &&)=default
FixedHashMap &	operator= (FixedHashMap &&other)
iterator	begin ()
const_iterator	begin () const
const_iterator	cbegin () const
iterator	end ()
const_iterator	end () const
const_iterator	cend () const
bool	empty () const
size_t	size () const
void	clear ()
iterator	erase (const const_iterator &pos)
size_t	erase (const key_type &key)
mapped_type &	at (const key_type &key)
const mapped_type &	at (const key_type &key) const
mapped_type &	operator[] (const key_type &key)
size_t	count (const key_type &key) const
iterator	find (const key_type &key)
const_iterator	find (const key_type &key) const
bool	contains (const key_type &key) const
	Check if key is in the map.
key_equal	key_eq () const
	Get key equal function object.
hasher	hash_function () const
	Get hash function object.
void	pup (PUP::er &p)
template<bool Assign, class M>
auto	insert_or_assign_impl (key_type &&key, M &&obj) -> std::pair< iterator, bool >
template<bool IsInserting>
auto	get_data_entry (const Key &key) -> typename storage_type::iterator
std::pair< iterator, bool >	insert (const value_type &value)
	Inserts the element if it does not exists.
std::pair< iterator, bool >	insert (value_type &&value)
	Inserts the element if it does not exists.
template<typename... Args>
std::pair< iterator, bool >	emplace (Args &&... args)
	Inserts the element if it does not exists.
template<class M>
std::pair< iterator, bool >	insert_or_assign (const key_type &key, M &&obj)
	Inserts the element if it does not exists, otherwise assigns to it the new value.
template<class M>
std::pair< iterator, bool >	insert_or_assign (key_type &&key, M &&obj)
	Inserts the element if it does not exists, otherwise assigns to it the new value.

Static Public Attributes
static constexpr bool	hash_is_perfect

Friends
template<size_t FMaxSize, class FKey, class FValueType, class FHash, class FKeyEqual>
bool	operator== (const FixedHashMap< FMaxSize, FKey, FValueType, FHash, FKeyEqual > &a, const FixedHashMap< FMaxSize, FKey, FValueType, FHash, FKeyEqual > &b)

Detailed Description

template<size_t MaxSize, class Key, class ValueType, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
class FixedHashMap< MaxSize, Key, ValueType, Hash, KeyEqual >

A hash table with a compile-time specified maximum size and ability to efficiently handle perfect hashes.

There are a few requirements on the types passed to FixedHashMap. These are:

• Key is CopyConstructible for copy and move semantics, as well as serialization
• ValueType is MoveConstructible
• If Hash is a perfect hash for some values of MaxSize then in order to use the perfect hashing improvements Hash must have a member variable template is_perfect that takes as its only template parameter a size_t equal to MaxSize. A perfect hash must map each Key to [0, MaxSize) uniquely.
• Keys are distinct.

The interface is similar to std::unordered_map, so see the documentation for that for details.

Implementation Details

• Uses linear probing for non-perfect hashes.
• The hash Hash is assumed to be a perfect hash for MaxSize if Hash::template is_perfect<MaxSize> is true.

Member Typedef Documentation

const_iterator

template<size_t MaxSize, class Key, class ValueType, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>

using FixedHashMap< MaxSize, Key, ValueType, Hash, KeyEqual >::const_iterator

Initial value:

 
      FixedHashMapIterator<MaxSize, key_type, const value_type, hasher,
                           key_equal>

iterator

template<size_t MaxSize, class Key, class ValueType, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>

using FixedHashMap< MaxSize, Key, ValueType, Hash, KeyEqual >::iterator

Initial value:

 
      FixedHashMapIterator<MaxSize, key_type, value_type, hasher, key_equal>

Member Data Documentation

hash_is_perfect

template<size_t MaxSize, class Key, class ValueType, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>

bool FixedHashMap< MaxSize, Key, ValueType, Hash, KeyEqual >::hash_is_perfect

staticconstexpr

Initial value:

=
      FixedHashMap_detail::is_perfect<Hash, MaxSize>

---

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

• src/DataStructures/FixedHashMap.hpp