SpECTRE  v2024.04.12
Public Types | Public Member Functions | Friends | List of all members
FixedHashMap< MaxSize, Key, ValueType, Hash, KeyEqual > Class Template Reference
Data Structures

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 = FixedHashMapIterator< MaxSize, key_type, value_type, hasher, key_equal >
 
using const_iterator = FixedHashMapIterator< MaxSize, key_type, const value_type, hasher, key_equal >
 

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.
 

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.
The documentation for this class was generated from the following file: