AXOM
Axom provides a robust, flexible software infrastructure for the development of multi-physics applications and computational tools.
axom::FlatMap< KeyType, ValueType, Hash > Class Template Reference

Provides a generic associative key-value container. More...

#include </home/docs/checkouts/readthedocs.org/user_builds/axom/checkouts/develop/src/axom/core/FlatMap.hpp>

Inherits detail::flat_map::SequentialLookupPolicy< Hash::result_type >.

Public Types

using key_type = KeyType
 
using mapped_type = ValueType
 
using size_type = IndexType
 
using value_type = KeyValuePair
 
using iterator = IteratorImpl< false >
 
using const_iterator = IteratorImpl< true >
 

Public Member Functions

 FlatMap ()
 Constructs a FlatMap with no elements. More...
 
 FlatMap (IndexType bucket_count)
 Constructs a FlatMap with at least a given number of buckets. More...
 
template<typename InputIt >
 FlatMap (InputIt first, InputIt last, IndexType bucket_count=-1)
 Constructs a FlatMap with a range of elements. More...
 
 FlatMap (std::initializer_list< value_type > init, IndexType bucket_count=-1)
 Constructs a FlatMap with a range of elements. More...
 
 FlatMap (FlatMap &&other)
 Move constructor for a FlatMap instance. More...
 
FlatMapoperator= (FlatMap &&other)
 Move assignment operator for a FlatMap instance. More...
 
 FlatMap (const FlatMap &other)
 Copy constructor for a FlatMap instance. More...
 
FlatMapoperator= (const FlatMap &other)
 Copy assignment operator for a FlatMap instance. More...
 
 ~FlatMap ()
 Destructor for a FlatMap instance. More...
 
void swap (FlatMap &other)
 Swaps the contents of one FlatMap with another. More...
 
bool empty () const
 Returns true if there are no entries in the FlatMap, false otherwise. More...
 
IndexType size () const
 Returns the number of entries stored in the FlatMap. More...
 
IndexType count (const KeyType &key) const
 Return the number of entries matching a given key. More...
 
bool contains (const KeyType &key) const
 Return true if the FlatMap contains a key, false otherwise. More...
 
void clear ()
 Erases all elements from the FlatMap. More...
 
template<typename InputIt >
void insert (InputIt first, InputIt last)
 Inserts a range of key-value pairs into the FlatMap. More...
 
template<typename... Args>
std::pair< iterator, bool > insert_or_assign (const KeyType &key, Args &&... args)
 Inserts a key-value pair into the FlatMap. More...
 
template<typename... Args>
std::pair< iterator, bool > insert_or_assign (KeyType &&key, Args &&... args)
 
template<typename... Args>
std::pair< iterator, bool > try_emplace (const KeyType &key, Args &&... args)
 Inserts a key-value pair into the FlatMap. More...
 
template<typename... Args>
std::pair< iterator, bool > try_emplace (KeyType &&key, Args &&... args)
 
iterator erase (iterator pos)
 Remove a key-value pair from the FlatMap, specified by iterator. More...
 
iterator erase (const_iterator pos)
 
IndexType erase (const KeyType &key)
 Remove a key-value pair from the FlatMap, specified by key. More...
 
IndexType bucket_count () const
 Returns the number of buckets allocated in the FlatMap. More...
 
double load_factor () const
 Returns the current load factor of the FlatMap. More...
 
double max_load_factor () const
 Returns the maximum load factor of the FlatMap. More...
 
void rehash (IndexType count)
 Explicitly rehash the FlatMap with a given number of buckets. More...
 
void reserve (IndexType count)
 Reallocate and rehash the FlatMap, such that up to the specified number of elements may be inserted without a rehash. More...
 
iterator begin ()
 Returns an iterator to the first valid object in the bucket array. More...
 
const_iterator begin () const
 
const_iterator cbegin () const
 
iterator end ()
 Returns an iterator to "one past" the last valid object in the bucket array. More...
 
const_iterator end () const
 
const_iterator cend () const
 
iterator find (const KeyType &key)
 Try to find an entry with a given key. More...
 
const_iterator find (const KeyType &key) const
 
ValueType & at (const KeyType &key)
 Try to find an entry with a given key. More...
 
const ValueType & at (const KeyType &key) const
 
ValueType & operator[] (const KeyType &key)
 Find an entry with a given key. More...
 
const ValueType & operator[] (const KeyType &key) const
 
std::pair< iterator, bool > insert (const value_type &value)
 Inserts a key-value pair into the FlatMap. More...
 
std::pair< iterator, bool > insert (value_type &&value)
 
template<typename InputPair >
std::pair< iterator, bool > insert (InputPair &&pair)
 
template<typename... InputArgs>
std::pair< iterator, bool > emplace (InputArgs &&... pair)
 

Friends

template<bool Const>
class IteratorImpl
 

Detailed Description

template<typename KeyType, typename ValueType, typename Hash = std::hash<KeyType>>
class axom::FlatMap< KeyType, ValueType, Hash >

Provides a generic associative key-value container.

The FlatMap class is a container which maps unique keys to a single value. It supports insertion, removal, and lookup of key-value pairs in amortized constant time.

Note
FlatMap is designed to be a largely drop-in replacement for std::unordered_map. However, FlatMap is internally represented as an open- addressing, quadratic probing hash map; thus, the API differs from unordered_map in certain regards:
  • Operations which insert a new element may invalidate references and iterators to existing elements in the container, if a resize of the underlying array is triggered.
  • Methods which only make sense for a closed-addressing hash map, such as begin/end(bucket_index), or bucket(key), are not implemented.
Template Parameters
KeyTypethe type of the keys to hold
ValueTypethe type of the values to hold
Hashthe hash to use with the key type
Precondition
KeyType must be EqualityComparable
Hash is invocable with an instance of KeyType, and returns an integer value (32- or 64-bit)

Member Typedef Documentation

◆ key_type

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
using axom::FlatMap< KeyType, ValueType, Hash >::key_type = KeyType

◆ mapped_type

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
using axom::FlatMap< KeyType, ValueType, Hash >::mapped_type = ValueType

◆ size_type

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
using axom::FlatMap< KeyType, ValueType, Hash >::size_type = IndexType

◆ value_type

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
using axom::FlatMap< KeyType, ValueType, Hash >::value_type = KeyValuePair

◆ iterator

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
using axom::FlatMap< KeyType, ValueType, Hash >::iterator = IteratorImpl<false>

◆ const_iterator

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
using axom::FlatMap< KeyType, ValueType, Hash >::const_iterator = IteratorImpl<true>

Constructor & Destructor Documentation

◆ FlatMap() [1/6]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
axom::FlatMap< KeyType, ValueType, Hash >::FlatMap ( )
inline

Constructs a FlatMap with no elements.

◆ FlatMap() [2/6]

template<typename KeyType , typename ValueType , typename Hash >
axom::FlatMap< KeyType, ValueType, Hash >::FlatMap ( IndexType  bucket_count)
explicit

Constructs a FlatMap with at least a given number of buckets.

Parameters
[in]bucket_countthe minimum number of buckets to allocate

References axom::FlatMap< KeyType, ValueType, Hash >::bucket_count(), axom::utilities::ceil(), axom::utilities::countl_zero(), axom::utilities::max(), and axom::Array< T, DIM, SPACE >::resize().

◆ FlatMap() [3/6]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
template<typename InputIt >
axom::FlatMap< KeyType, ValueType, Hash >::FlatMap ( InputIt  first,
InputIt  last,
IndexType  bucket_count = -1 
)
inline

Constructs a FlatMap with a range of elements.

Parameters
[in]firstiterator pointing to the beginning of the range
[in]lastiterator pointing to the end of the range
[in]bucket_countminimum number of buckets to allocate (optional)

◆ FlatMap() [4/6]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
axom::FlatMap< KeyType, ValueType, Hash >::FlatMap ( std::initializer_list< value_type init,
IndexType  bucket_count = -1 
)
inlineexplicit

Constructs a FlatMap with a range of elements.

Parameters
[in]inita list of pairs to initialize the map with
[in]bucket_countminimum number of buckets to allocate (optional)

◆ FlatMap() [5/6]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
axom::FlatMap< KeyType, ValueType, Hash >::FlatMap ( FlatMap< KeyType, ValueType, Hash > &&  other)
inline

Move constructor for a FlatMap instance.

Parameters
otherthe FlatMap to move data from

References axom::FlatMap< KeyType, ValueType, Hash >::swap().

◆ FlatMap() [6/6]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
axom::FlatMap< KeyType, ValueType, Hash >::FlatMap ( const FlatMap< KeyType, ValueType, Hash > &  other)
inline

Copy constructor for a FlatMap instance.

Parameters
otherthe FlatMap to copy data from
Precondition
KeyType must be copy-constructible
ValueType must be copy-constructible

References axom::FlatMap< KeyType, ValueType, Hash >::bucket_count(), axom::Array< T, DIM, SPACE >::data(), and axom::Array< T, DIM, SPACE >::view().

◆ ~FlatMap()

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
axom::FlatMap< KeyType, ValueType, Hash >::~FlatMap ( )
inline

Member Function Documentation

◆ operator=() [1/2]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
FlatMap& axom::FlatMap< KeyType, ValueType, Hash >::operator= ( FlatMap< KeyType, ValueType, Hash > &&  other)
inline

Move assignment operator for a FlatMap instance.

Parameters
otherthe FlatMap to move data from

References axom::FlatMap< KeyType, ValueType, Hash >::swap().

◆ operator=() [2/2]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
FlatMap& axom::FlatMap< KeyType, ValueType, Hash >::operator= ( const FlatMap< KeyType, ValueType, Hash > &  other)
inline

Copy assignment operator for a FlatMap instance.

Parameters
otherthe FlatMap to copy data from
Precondition
KeyType must be copy-constructible
ValueType must be copy-constructible

References axom::FlatMap< KeyType, ValueType, Hash >::swap().

◆ swap()

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
void axom::FlatMap< KeyType, ValueType, Hash >::swap ( FlatMap< KeyType, ValueType, Hash > &  other)
inline

Swaps the contents of one FlatMap with another.

References axom::Array< T, DIM, SPACE >::swap(), and axom::utilities::swap().

◆ begin() [1/2]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
iterator axom::FlatMap< KeyType, ValueType, Hash >::begin ( )
inline

Returns an iterator to the first valid object in the bucket array.

◆ begin() [2/2]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
const_iterator axom::FlatMap< KeyType, ValueType, Hash >::begin ( ) const
inline

◆ cbegin()

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
const_iterator axom::FlatMap< KeyType, ValueType, Hash >::cbegin ( ) const
inline

◆ end() [1/2]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
iterator axom::FlatMap< KeyType, ValueType, Hash >::end ( )
inline

Returns an iterator to "one past" the last valid object in the bucket array.

References axom::FlatMap< KeyType, ValueType, Hash >::bucket_count().

◆ end() [2/2]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
const_iterator axom::FlatMap< KeyType, ValueType, Hash >::end ( ) const
inline

◆ cend()

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
const_iterator axom::FlatMap< KeyType, ValueType, Hash >::cend ( ) const
inline

◆ empty()

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
bool axom::FlatMap< KeyType, ValueType, Hash >::empty ( ) const
inline

Returns true if there are no entries in the FlatMap, false otherwise.

◆ size()

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
IndexType axom::FlatMap< KeyType, ValueType, Hash >::size ( ) const
inline

Returns the number of entries stored in the FlatMap.

◆ find() [1/2]

template<typename KeyType , typename ValueType , typename Hash >
auto axom::FlatMap< KeyType, ValueType, Hash >::find ( const KeyType &  key)

Try to find an entry with a given key.

Parameters
[in]keythe key to search for
Returns
An iterator pointing to the corresponding key-value pair, or end() if the key wasn't found.

References axom::utilities::annotations::end().

◆ find() [2/2]

template<typename KeyType , typename ValueType , typename Hash >
auto axom::FlatMap< KeyType, ValueType, Hash >::find ( const KeyType &  key) const

◆ at() [1/2]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
ValueType& axom::FlatMap< KeyType, ValueType, Hash >::at ( const KeyType &  key)
inline

Try to find an entry with a given key.

Parameters
[in]keythe key to search for
Returns
A reference to the corresponding value.
Exceptions
std::out_of_rangeif the key is not found.

References axom::FlatMap< KeyType, ValueType, Hash >::end(), and axom::FlatMap< KeyType, ValueType, Hash >::find().

◆ at() [2/2]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
const ValueType& axom::FlatMap< KeyType, ValueType, Hash >::at ( const KeyType &  key) const
inline

◆ operator[]() [1/2]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
ValueType& axom::FlatMap< KeyType, ValueType, Hash >::operator[] ( const KeyType &  key)
inline

Find an entry with a given key.

If a corresponding value does not exist, a default value for the value type will be inserted for the given key.

Parameters
[in]keythe key to search for
Returns
A reference to the corresponding value.
Precondition
ValueType is default-constructible

References axom::FlatMap< KeyType, ValueType, Hash >::try_emplace().

◆ operator[]() [2/2]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
const ValueType& axom::FlatMap< KeyType, ValueType, Hash >::operator[] ( const KeyType &  key) const
inline

◆ count()

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
IndexType axom::FlatMap< KeyType, ValueType, Hash >::count ( const KeyType &  key) const
inline

Return the number of entries matching a given key.

This method will always return 0 or 1.

Parameters
[in]keythe key to search for

References axom::FlatMap< KeyType, ValueType, Hash >::contains().

◆ contains()

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
bool axom::FlatMap< KeyType, ValueType, Hash >::contains ( const KeyType &  key) const
inline

Return true if the FlatMap contains a key, false otherwise.

Parameters
[in]keythe key to search for

References axom::FlatMap< KeyType, ValueType, Hash >::end(), and axom::FlatMap< KeyType, ValueType, Hash >::find().

◆ clear()

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
void axom::FlatMap< KeyType, ValueType, Hash >::clear ( )
inline

◆ insert() [1/4]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
std::pair<iterator, bool> axom::FlatMap< KeyType, ValueType, Hash >::insert ( const value_type value)
inline

Inserts a key-value pair into the FlatMap.

If the key already exists in the FlatMap, insertion is skipped. Otherwise, the key-value mapping is inserted into the FlatMap.

Parameters
[in]valuethe key-value pair to insert
Returns
A pair consisting of:
  • an iterator pointing to either the existing key-value pair, or the newly-inserted pair
  • true if a new pair was inserted, false otherwise

◆ insert() [2/4]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
std::pair<iterator, bool> axom::FlatMap< KeyType, ValueType, Hash >::insert ( value_type &&  value)
inline

◆ insert() [3/4]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
template<typename InputPair >
std::pair<iterator, bool> axom::FlatMap< KeyType, ValueType, Hash >::insert ( InputPair &&  pair)
inline

◆ emplace()

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
template<typename... InputArgs>
std::pair<iterator, bool> axom::FlatMap< KeyType, ValueType, Hash >::emplace ( InputArgs &&...  pair)
inline

◆ insert() [4/4]

template<typename KeyType , typename ValueType , typename Hash >
template<typename InputIt >
void axom::FlatMap< KeyType, ValueType, Hash >::insert ( InputIt  first,
InputIt  last 
)

Inserts a range of key-value pairs into the FlatMap.

If the key already exists in the FlatMap, insertion is skipped. Otherwise, the key-value mapping is inserted into the FlatMap.

Parameters
[in]firstthe beginning of the range of pairs
[in]lastthe end of the range of pairs

◆ insert_or_assign() [1/2]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
template<typename... Args>
std::pair<iterator, bool> axom::FlatMap< KeyType, ValueType, Hash >::insert_or_assign ( const KeyType &  key,
Args &&...  args 
)
inline

Inserts a key-value pair into the FlatMap.

If the key already exists, assigns the value to the existing key in the FlatMap.

Parameters
[in]keythe key to insert or assign
[in]argsarguments to construct the value with
Returns
A pair consisting of:
  • an iterator pointing to either the existing key-value pair, or the newly-inserted pair
  • true if a new pair was inserted, false otherwise {@

◆ insert_or_assign() [2/2]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
template<typename... Args>
std::pair<iterator, bool> axom::FlatMap< KeyType, ValueType, Hash >::insert_or_assign ( KeyType &&  key,
Args &&...  args 
)
inline

◆ try_emplace() [1/2]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
template<typename... Args>
std::pair<iterator, bool> axom::FlatMap< KeyType, ValueType, Hash >::try_emplace ( const KeyType &  key,
Args &&...  args 
)
inline

Inserts a key-value pair into the FlatMap.

If the key already exists in the FlatMap, insertion is skipped. Otherwise, the key-value mapping is inserted into the FlatMap.

Compared to emplace(), this method only moves-from the value arguments if the key does not exist; otherwise, the input arguments are left as-is.

Parameters
[in]keythe key to insert or assign
[in]argsarguments to construct the value with.
Returns
A pair consisting of:
  • an iterator pointing to either the existing key-value pair, or the newly-inserted pair
  • true if a new pair was inserted, false otherwise {@

◆ try_emplace() [2/2]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
template<typename... Args>
std::pair<iterator, bool> axom::FlatMap< KeyType, ValueType, Hash >::try_emplace ( KeyType &&  key,
Args &&...  args 
)
inline

◆ erase() [1/3]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
iterator axom::FlatMap< KeyType, ValueType, Hash >::erase ( iterator  pos)
inline

Remove a key-value pair from the FlatMap, specified by iterator.

Parameters
posthe iterator pointing to the key-value pair to remove
Returns
an iterator to the next valid entry after the removed entry {@

References axom::FlatMap< KeyType, ValueType, Hash >::erase().

◆ erase() [2/3]

template<typename KeyType , typename ValueType , typename Hash >
auto axom::FlatMap< KeyType, ValueType, Hash >::erase ( const_iterator  pos)

◆ erase() [3/3]

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
IndexType axom::FlatMap< KeyType, ValueType, Hash >::erase ( const KeyType &  key)
inline

Remove a key-value pair from the FlatMap, specified by key.

If the key doesn't exist in the FlatMap, does nothing.

Parameters
keythe key to remove
Returns
1 if an entry was removed, 0 otherwise

References axom::FlatMap< KeyType, ValueType, Hash >::end(), axom::FlatMap< KeyType, ValueType, Hash >::erase(), and axom::FlatMap< KeyType, ValueType, Hash >::find().

◆ bucket_count()

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
IndexType axom::FlatMap< KeyType, ValueType, Hash >::bucket_count ( ) const
inline

Returns the number of buckets allocated in the FlatMap.

The maximum number of elements that can be stored in the FlatMap without resizing and rehashing is bucket_count() * max_load_factor().

References axom::Array< T, DIM, SPACE >::size().

◆ load_factor()

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
double axom::FlatMap< KeyType, ValueType, Hash >::load_factor ( ) const
inline

Returns the current load factor of the FlatMap.

References axom::FlatMap< KeyType, ValueType, Hash >::bucket_count().

◆ max_load_factor()

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
double axom::FlatMap< KeyType, ValueType, Hash >::max_load_factor ( ) const
inline

Returns the maximum load factor of the FlatMap.

◆ rehash()

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
void axom::FlatMap< KeyType, ValueType, Hash >::rehash ( IndexType  count)
inline

Explicitly rehash the FlatMap with a given number of buckets.

Parameters
countthe minimum number of buckets to allocate for the rehash

References axom::FlatMap< KeyType, ValueType, Hash >::begin(), axom::FlatMap< KeyType, ValueType, Hash >::count(), axom::FlatMap< KeyType, ValueType, Hash >::end(), and axom::FlatMap< KeyType, ValueType, Hash >::swap().

◆ reserve()

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
void axom::FlatMap< KeyType, ValueType, Hash >::reserve ( IndexType  count)
inline

Reallocate and rehash the FlatMap, such that up to the specified number of elements may be inserted without a rehash.

Parameters
countthe number of elements to fit without a rehash

References axom::utilities::ceil(), axom::FlatMap< KeyType, ValueType, Hash >::count(), and axom::FlatMap< KeyType, ValueType, Hash >::rehash().

Friends And Related Function Documentation

◆ IteratorImpl

template<typename KeyType , typename ValueType , typename Hash = std::hash<KeyType>>
template<bool Const>
friend class IteratorImpl
friend

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