Template Class sparse_map

Class Documentation

template<typename key_type, typename value_type, template<typename...> typename dense_type = std::vector, template<typename...> typename sparse_type = std::unordered_map>
class legion::core::sparse_map

Quick lookup contiguous map. The map is based on the concept of a sparse set and thus inherits it’s lookup complexity and contiguous nature.

Note

With default container parameters iterators may be invalidated upon resize. See reference of std::vector.

Note

Removing item might invalidate the iterator of the last item in the dense container.

Template Parameters
  • key_type: The type to be used as the key.

  • value_type: The type to be used as the value.

  • dense_type: Container to be used to store the values.

  • sparse_type: Container to be used to store the keys.

Public Types

using self_type = sparse_map<key_type, value_type, dense_type, sparse_type>
using self_reference = self_type&
using self_const_reference = const self_type&
using key_reference = key_type&
using key_const_reference = const key_type&
using key_pointer = key_type*
using value_reference = value_type&
using value_const_reference = const value_type&
using value_pointer = value_type*
using sparse_container = sparse_type<key_type, size_type>
using dense_value_container = dense_type<value_type>
using dense_key_container = dense_type<key_type>
using iterator = core::key_value_pair_iterator<typename dense_key_container::iterator, typename dense_value_container::iterator>
using const_iterator = core::key_value_pair_iterator<typename dense_key_container::const_iterator, typename dense_value_container::const_iterator>

Public Functions

inline dense_value_container &values() noexcept
inline const dense_value_container &values() const noexcept
inline dense_key_container &keys() noexcept
inline const dense_key_container &keys() const noexcept
inline iterator begin() noexcept
inline const_iterator begin() const noexcept
inline const_iterator cbegin() const noexcept
inline iterator end() noexcept
inline const_iterator end() const noexcept
inline const_iterator cend() const noexcept
inline size_type size() const noexcept

Returns the amount of items in the sparse_map.

Return

size_type Current amount of items contained in sparse_map.

inline size_type capacity() const noexcept

Returns the capacity of items the sparse_map could at least store without invalidating the iterators.

Return

size_type Current capacity of the dense container.

inline size_type max_size() const noexcept

Returns the maximum number of items the sparse_map could at most store without crashing.

Note

This value typically reflects the theoretical limit on the size of the container, at most std::numeric_limits<difference_type>::max(). At runtime, the size of the container may be limited to a value smaller than max_size() by the amount of RAM available.

Return

size_type

inline bool empty() const noexcept

Returns whether the sparse_map is empty.

Return

bool True if the sparse_map is empty, otherwise false.

inline void clear() noexcept

Clears sparse_map.

Note

Will not update capacity.

inline void reserve(size_type size)

Reserves space in dense container for more items.

Note

Will update capacity if resize happened.

Parameters
  • size: Amount of items to reserve space for (would be the new capacity).

inline size_type count(key_const_reference key) const

Returns the amount of items linked to a certain key.

Return

size_type Amount of items linked to the key (either 0 or 1).

Note

Function is only available for compatibility reasons, it is advised to use contains instead. legion::core::sparse_map::contains

Parameters
  • key: Key to look for.

inline size_type count(key_type &&key) const

Returns the amount of items linked to a certain key.

Return

size_type Amount of items linked to the key (either 0 or 1).

Note

Function is only available for compatibility reasons, it is advised to use contains instead. legion::core::sparse_map::contains

Parameters
  • key: Key to look for.

inline bool contains(key_const_reference key) const

Checks whether a certain key is contained in the sparse_map.

Return

bool true if the key was found, otherwise false.

Parameters
  • key: Key to check for.

inline bool contains(key_type &&key) const

Checks whether a certain key is contained in the sparse_map.

Return

bool true if the key was found, otherwise false.

Parameters
  • key: Key to check for.

template<typename T>
inline bool contains(const sparse_map<key_type, T> &other) const

Checks if all keys in sparse_map are inside this map as well.

Return

bool True if all keys in other are also in this sparse_map, otherwise false.

Parameters

inline bool equals(self_const_reference other) const

Checks if all keys and values and relations between them are the same for both sparse_maps.

Return

bool True if both maps are the same size, contain the same keys, and all keys refer to the same value, otherwise false.

Parameters

inline bool operator==(self_const_reference other) const

Checks if all keys and values and relations between them are the same for both sparse_maps.

Return

bool True if both maps are the same size, contain the same keys, and all keys refer to the same value, otherwise false.

Parameters

inline iterator find(value_const_reference val)

Finds the iterator of a value using std::find.

Return

Iterator to the value if found, otherwise end.

Parameters
  • val: Value to find.

inline const_iterator find(value_const_reference val) const

Finds the iterator of a value using std::find.

Return

Iterator to the value if found, otherwise end.

Parameters
  • val: Value to find.

inline std::pair<iterator, bool> insert(key_const_reference key, value_const_reference val)

Inserts new item into sparse_map.

Return

std::pair<iterator, bool> Iterator at the location of the key and true if succeeded, end and false if it didn’t succeed.

Parameters
  • key: Key to insert the new item to.

  • val: Value to insert and link to the key.

inline std::pair<iterator, bool> insert(key_type &&key, value_const_reference val)

Inserts new item into sparse_map.

Return

std::pair<iterator, bool> Iterator at the location of the key and true if succeeded, end and false if it didn’t succeed.

Parameters
  • key: Key to insert the new item to.

  • val: Value to insert and link to the key.

inline std::pair<iterator, bool> insert(key_const_reference key, value_type &&val)

Inserts new item into sparse_map.

Return

std::pair<iterator, bool> Iterator at the location of the key and true if succeeded, end and false if it didn’t succeed.

Parameters
  • key: Key to insert the new item to.

  • val: Value to insert and link to the key.

inline std::pair<iterator, bool> insert(key_type &&key, value_type &&val)

Inserts new item into sparse_map.

Return

std::pair<iterator, bool> Iterator at the location of the key and true if succeeded, end and false if it didn’t succeed.

Parameters
  • key: Key to insert the new item to.

  • val: Value to insert and link to the key.

template<typename ...Arguments>
inline std::pair<iterator, bool> emplace(key_const_reference key, Arguments&&... arguments)

Construct item in place.

Parameters
  • key: Key to which the item should be created.

  • arguments: Arguments to pass to the item constructor.

template<typename ...Arguments>
inline std::pair<iterator, bool> emplace(key_type &&key, Arguments&&... arguments)

Construct item in place.

Parameters
  • key: Key to which the item should be created.

  • arguments: Arguments to pass to the item constructor.

inline value_reference operator[](key_type &&key)

Returns item from sparse_map, inserts default value if it doesn’t exist yet.

Parameters
  • key: Key value that needs to be retrieved.

inline value_reference operator[](key_const_reference key)

Returns item from sparse_map, inserts default value if it doesn’t exist yet.

Parameters
  • key: Key value that needs to be retrieved.

inline value_const_reference operator[](key_type &&key) const

Returns const item from const sparse_map.

Parameters
  • key: Key value that needs to be retrieved.

inline value_const_reference operator[](key_const_reference key) const

Returns const item from const sparse_map.

Parameters
  • key: Key value that needs to be retrieved.

inline value_reference at(key_type &&key)

Returns item from sparse_map, throws exception if it doesn’t exist yet.

Parameters
  • key: Key value that needs to be retrieved.

inline value_reference at(key_const_reference key)

Returns item from sparse_map, throws exception if it doesn’t exist yet.

Parameters
  • key: Key value that needs to be retrieved.

inline value_const_reference at(key_type &&key) const

Returns const item from const sparse_map.

Parameters
  • key: Key value that needs to be retrieved.

inline value_const_reference at(key_const_reference key) const

Returns const item from const sparse_map.

Parameters
  • key: Key value that needs to be retrieved.

inline size_type erase(key_const_reference key)

Erases item from sparse_map.

Parameters
  • key: Key value that needs to be erased.