## 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

**Next message:**Karl Meerbergen: "Re: [glas] return type of operator[](size_type) for sparse vectors?"**Previous message:**Peter Gottschling: "Re: [glas] A few more thoughts about return type of operator[](size_type) for sparse vectors"**In reply to:**Peter Gottschling: "Re: [glas] return type of operator[](size_type) for sparse vectors?"**Next in thread:**Karl Meerbergen: "Re: [glas] return type of operator[](size_type) for sparse vectors?"**Reply:**Karl Meerbergen: "Re: [glas] return type of operator[](size_type) for sparse vectors?"

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).

agreed

>

> 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.

**Next message:**Karl Meerbergen: "Re: [glas] return type of operator[](size_type) for sparse vectors?"**Previous message:**Peter Gottschling: "Re: [glas] A few more thoughts about return type of operator[](size_type) for sparse vectors"**In reply to:**Peter Gottschling: "Re: [glas] return type of operator[](size_type) for sparse vectors?"**Next in thread:**Karl Meerbergen: "Re: [glas] return type of operator[](size_type) for sparse vectors?"**Reply:**Karl Meerbergen: "Re: [glas] return type of operator[](size_type) for sparse vectors?"