A SparseVector stores a vector with possibly many empty elements as efficiently as possible. More...
#include <SparseVector.hpp>
Public Member Functions | |
SparseVector () | |
Default constructor. Yields an empty SparseVector. | |
SparseVector (int sz) | |
Constructs a SparseVector with a given size, but no nonzero elements. More... | |
template<typename DataIter , typename IntegerIter > | |
SparseVector (int sz, DataIter data_beg, DataIter data_end, IntegerIter index_beg, IntegerIter index_end) | |
A constructor taking all the element data for the vector and their indices. More... | |
void | addElement (const T &elem, int index) |
Appends an element to the vector. More... | |
bool | empty () const |
int | size () const |
Returns the size of the vector. More... | |
int | nonzeroSize () const |
Returns the number of nonzero data elements. | |
void | clear () |
Makes the vector empty(). | |
bool | operator== (const SparseVector &other) const |
Equality. | |
const T & | element (int index) const |
O(log n) element access. More... | |
const T & | nonzeroElement (int nzindex) const |
O(1) element access. More... | |
int | nonzeroIndex (int nzindex) const |
O(1) index access. More... | |
A SparseVector stores a vector with possibly many empty elements as efficiently as possible.
It is supposed to behave similarly to a standard vector, but since direct indexing is a O(log n) operation instead of O(1), we do not supply it as operator[].
|
inlineexplicit |
Constructs a SparseVector with a given size, but no nonzero elements.
|
inline |
A constructor taking all the element data for the vector and their indices.
data_beg | The start of the element data. |
data_end | One-beyond-end of the element data. |
rowsize_beg | The start of the index data. |
rowsize_end | One beyond the end of the index data. |
|
inline |
Appends an element to the vector.
Note that this function does not increase the size() of the vector, it just adds another nonzero element. Elements must be added in index order.
|
inline |
O(log n) element access.
index | the proper vector index |
|
inline |
|
inline |
O(1) element access.
nzindex | an index counting only nonzero elements. |
|
inline |
O(1) index access.
nzindex | an index counting only nonzero elements. |
|
inline |
Returns the size of the vector.
Recall that most or all of the vector may be default/zero.