Class mata::utils::SparseSet

template<typename Number>
class SparseSet

Implementation of a set of non-negative numbers using sparse-set.

This class implements the interface of a set (similar to std::set) using sparse-set date structure, that is, a pair of vectors dense and sparse (… google it). Importantly

• Insertion and removal are constant time.

• Iteration is linear in the number of stored elements.

• It takes a lot of space, the sparse and dense vectors allocate as many indexes as the maximal stored number.

Template Parameters:

Number – Number type: type of numbers contained in the container.

Public Functions

inline void erase_nocheck(const Number number)

Erase number from the set without checking for its existence.

Parameters:

number – Number to be erased.

Pre:

number exists in the set.

SparseSet() = default

New Mata code.

inline explicit SparseSet(Number domain_size)

Basic constructor where you may reserve a domain size.

inline bool operator[](Number q) const

Returns:

True if predicate for q is set. False otherwise (even if q is out of range of the predicate).

inline Number max()

Maximal Number in set.

Expensive operation as it has to compute the maximal Number in linear time.