Template Class sparse_set

Class Documentation

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

Quick lookup contiguous set. A sparse set uses a dense and a sparse array to allow quick lookup of it’s values whilst maintaining contiguous iteration.

Note

Inserting items with large value differences does explode the sparse array and thus increases memory size. If you need support for items with large value differences such as hashes then please use the sparse_map. legion::core::sparse_map

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

  • atomic_type: The type to be used as the value (must be unsigned).

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

  • sparse_type: Container to be used to store the index mapping into dense container.

Public Types

using sparse_container = sparse_type<value_type>
using dense_container = dense_type<value_type>
using reference = value_type&
using const_reference = const value_type&
using iterator = typename dense_container::iterator
using const_iterator = typename dense_container::const_iterator

Public Functions

inline iterator begin()
inline const_iterator begin() const
inline const_iterator cbegin() const
inline iterator end()
inline const_iterator end() const
inline const_iterator cend() const
inline size_type size() const noexcept

Returns the amount of items in the sparse_set.

Return

size_type Current amount of items contained in sparse_set.

inline size_type capacity() const noexcept

Returns the capacity of items the sparse_set 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_set 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_set is empty.

Return

bool True if the sparse_set is empty, otherwise false.

inline void clear() noexcept

Clears sparse_set.

Note

Will not update capacity.

inline void reserve(size_type size)

Reserves space in sparse_set 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(const_reference val) const

Returns the amount of items of a certain value.

Return

size_type Amount of items found (either 0 or 1).

Note

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

Parameters

  • val: Value to look for.

inline size_type count(value_type &&val) const

Returns the amount of items of a certain value.

Return

size_type Amount of items found (either 0 or 1).

Note

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

Parameters

  • val: Value to look for.

inline bool contains(const_reference val) const

Checks whether a certain value is contained in the sparse_set.

Return

bool True if the value was found, otherwise false.

Parameters

  • val: Value to check for.

inline bool contains(value_type &&val) const

Checks whether a certain value is contained in the sparse_set.

Return

bool True if the value was found, otherwise false.

Parameters

  • val: Value to check for.

inline bool contains(const sparse_set<value_type> &other) const

Checks if all items in sparse_set are inside this set as well.

Return

bool True if all items in other are also in this sparse_set, otherwise false.

Parameters

inline bool equals(const sparse_set<value_type> &other) const

Checks if all items are the same for both sparse_sets.

Return

bool True if both sets are the same size and contain the same items, otherwise false.

Parameters

inline bool operator==(const sparse_set<value_type> &other) const

Checks if all items are the same for both sparse_sets.

Return

bool True if both sets are the same size and contain the same items, otherwise false.

Parameters

inline iterator find(const_reference val)

Finds the iterator of a value.

Return

Iterator to the value if found, otherwise end.

Parameters

  • val: Value to find.

inline const_iterator find(const_reference val) const

Finds the iterator of a value.

Return

Iterator to the value if found, otherwise end.

Parameters

  • val: Value to find.

inline std::pair<iterator, bool> insert(const_reference val)

Inserts new item into sparse_set.

Return

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

Parameters

  • val: Value to insert.

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

Inserts new item into sparse_set.

Return

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

Parameters

  • val: Value to insert.

inline reference operator[](size_type &&index)

Returns item from dense container.

Parameters

  • index: Index of item in dense container.

inline reference operator[](const size_type &index)

Returns item from dense container.

Parameters

  • index: Index of item in dense container.

inline const_reference operator[](size_type &&index) const

Returns item from dense container.

Parameters

  • index: Index of item in dense container.

inline const_reference operator[](const size_type &index) const

Returns item from dense container.

Parameters

  • index: Index of item in dense container.

inline size_type erase(const_reference val)

Erases item from sparse_set.

Parameters

  • val: Value that needs to be erased.