Boost logo

Glas :

Re: [glas] return type of operator[](size_type) for sparse vectors?

From: Toon Knapen (toon.knapen_at_[hidden])
Date: 2006-04-27 15:53:29

Peter Gottschling wrote:
> I also prefer option 3 and I don't believe that it would cause much
> overhead. Also, I think that vectors are expected to change often in
> applications (much more than matrices) and need the ability to change
> the sparsity pattern and insert non-zeros.
> Another question is how to keep the sparsity pattern small.
> - When v[i]= 0, should v[i] be removed from the structure?
> - What if v[i]= f(x) with f(x)~0? One could provide user-defined
> predicates that decide when an element can be dropped. How much would
> this complicate the implementation?
> - Do have typical sparse vector applications regular assignments v= 0
> so that an element-wise cancellation is not needed?
> - Should v= 0 automatically empty the structure or do we prefer to have
> something like v.reset() to do this? For dense vectors v.reset() would
> set all elements to 0 to keep an unified interface.

if option 3 is taken and thus if operator[] can have an effect on the
structure, the questions above are difficult to answer and semantics
will become even more subtle (and thus unclear for the user).

> Having no operator[] access would be strange for a vector and makes
> many implementations more difficult. The behavior of operator[] should
> be consistent with dense vectors.

That is impossible. Even if operator[] can change the structure (as in
option 3), operator[] might change the structure and therefore will
invalidate the iterators. The iterators for a dense-vector are however
not invalidated when using operator[] so I think it will never be
possible to have the same behavior as dense.

Anyway we also foresee to have other members to insert non-zero's
explicitly so operator[] is not the only way. The discussion about
operator[] is purely about convenience, not about features.

> For efficiency reasons, the
> preferred access to vectors which are possibly sparse should be with
> iterators (cursors) over non-zero elements (if the vector is the driven
> data structure).


> Speaking of iterations over sparse data structures. Karl, Toon and I
> had the idea to provide different traversal tags for begin and end
> functions. This idea works fine to distinguish for instance between
> row-wise, column-wise or element-wise matrix traversal (under the
> condition that the matrix allows such traversal). Recently, I intended
> to implement dense traversal for sparse matrices, i.e. to go over all
> elements including structural zeros. The reason I hesitated was that
> the cursors/iterators need conceptionally different information,
> offsets within internal data structures versus matrix indices. While
> this is still implementable, kind of, it would introduce a lot of
> overloading and complicating the implementation significantly. As an
> alternative, I find it clearer to have a dense_view of a sparse matrix
> or vector and use the cursor/iterator of this view to traverse all
> elements. (Loops over all matrix or vector indices and using
> operator[] or operator() would be equivalent but less generic.) Better
> we have dense_matrix_view and dense_vector_view which should be both
> implementable generically (without specialization).

The one does not exclude the other. The dense-views seem indeed
interesting but we can play around with both (if we really want) and see
what is most convenient/performant.