File view_vector_sparse_set.hpp

template<typename T, typename ValueArray = std::vector<IndexedValue<T>>, typename IndexType = uint32>
class SparseSetVector
#include <view_vector_sparse_set.hpp>

An one-dimensional view that provides random read and write access, as well as read and write access via iterators, to sparse elements, consisting of an index and a value, stored in a dynamic array. Compared to the view SparseArrayVector, the ability to provide random access to the elements in the view comes at the expense of memory efficiency, as it does not only require to store the sparse elements, but also a fixed-size array that stores for each position the index of the corresponding element in the dynamic array, if available.

This data structure is often referred to as an “unordered sparse set”. It was originally proposed in “An efficient

representation for sparse sets”, Briggs, Torczon, 1993.

Template Parameters:

  • T – The type of the values, the view provides access to

  • ValueArray – The type of the dynamic array that stores the sparse elements

  • IndexType – the type of the fixed-size array that stores for each position the index of the corresponding element in the dynamic array

Public Types

using value_type = IndexedValue<T>

The type of the values in the view.

using const_iterator = ValueArray::const_iterator

An iterator that provides read-only access to the sparse elements in the view.

using iterator = ValueArray::iterator

An iterator that provides access to the sparse elements in the row and allows to modify them.

Public Functions

inline explicit SparseSetVector(ValueArray *values, IndexType *indices, uint32 numElements)
Parameters:

  • values – A pointer to an object of template type ValueArray that stores the sparse elements

  • indices – A pointer to an array of template type IndexType that stores for each position the index of the corresponding element in values

  • numElements – The number of elements in the view

inline SparseSetVector(const SparseSetVector<T, ValueArray, IndexType> &other)
Parameters:

other – A reference to an object of type SparseSetVector that should be copied

inline SparseSetVector(SparseSetVector<T, ValueArray, IndexType> &&other)
Parameters:

other – A reference to an object of type SparseSetVector that should be moved

inline virtual ~SparseSetVector()
inline const_iterator cbegin() const

Returns a const_iterator to the beginning of the view.

Returns:

A const_iterator to the beginning

inline const_iterator cend() const

Returns a const_iterator to the end of the view.

Returns:

A const_iterator to the end

inline iterator begin()

Returns an iterator to the beginning of the view.

Returns:

An iterator to the beginning

inline iterator end()

Returns an iterator to the end of the view.

Returns:

An iterator to the end

inline const value_type *operator[](uint32 index) const

Returns a pointer to the element that corresponds to a specific index.

Parameters:

index – The index of the element to be returned

Returns:

A pointer to the element that corresponds to the given index or a null pointer, if no such element is available

inline value_type *operator[](uint32 index)

Returns a pointer to the element that corresponds to a specific index.

Parameters:

index – The index of the element to be returned

Returns:

A pointer to the element that corresponds to the given index or a null pointer, if no such element is available

inline value_type &emplace(uint32 index)

Returns a reference to the element that corresponds to a specific index. If no such element is available, it is inserted into the vector.

Parameters:

index – The index of the element to be returned or inserted

Returns:

A reference to the element that corresponds to the given index

inline value_type &emplace(uint32 index, const T &defaultValue)

Returns a reference to the element that corresponds to a specific index. If no such element is available, it is inserted into the vector using a specific default value.

Parameters:

  • index – The index of the element to be returned or inserted

  • defaultValue – The default value to be used if a new element is inserted

Returns:

A reference to the element that corresponds to the given index

inline void erase(uint32 index)

Removes the element that corresponds to a specific index, if available.

Parameters:

index – The index of the element to be removed

inline void clear()

Removes all elements from the row.

inline ValueArray *releaseValues()

Releases the ownership of the dynamic array that stores the sparse elements in the view. As a result, the behavior of this view becomes undefined and it should not be used anymore. The caller is responsible for freeing the memory that is occupied by the array.

Returns:

A pointer to an object of template type ValueArray that stores the sparse elements in the view

inline IndexType *releaseIndices()

Releases the ownership of the fixed-size array that stores for each position the index of the corresponding element in the dynamic array. As a result, the behavior of this view becomes undefined and it should not be used anymore. The caller is responsible for freeing the memory that is occupied by the array.

Returns:

A pointer to an array of template type IndexType that stores for each position the index of the corresponding element in the dynamic array

Public Members

ValueArray *values

A pointer to the dynamic array that stores the sparse elements.

IndexType *indices

A pointer to the fixed-size array that stores for each position the index of the corresponding element in the dynamic array, if available.

uint32 numElements

The number of elements in the view.

Public Static Attributes

static uint32 MAX_INDEX = std::numeric_limits<IndexType>::max()

The index that is used to indicate that the value of a specific elements is zero.