Boost logo

Glas :

Re: [glas] using (boost)range or STL style interface [was: dense and sparse vectors]

From: Ian McCulloch (ianmcc_at_[hidden])
Date: 2005-08-05 11:08:25

On Fri, 5 Aug 2005, Toon Knapen wrote:

> Neal Becker wrote:
> >>> some_algorithm(transpose_view(m))
> >>>
> >>>as opposed to:
> >>>
> >>> some_algorithm(transpose_view(m).begin(), transpose_view(m).end())
> >>
> >
> > The issue I run into is where transpose_view(m) is a function that can't be or
> > shouldn't be called twice - it might, for example, modify it's argument, or
> > it might be expensive.
> >
> I agree. OTOH the problem can be worked around by writing:
> <code>
> some_type tv( transpose_view(m) ) ;
> some_algorithm( tv.begin(), tv.end() ) ;
> </code>

But this is problematic because you might not know what some_type actually
needs to be. Also, if it is a proxy it might refer to a container that
is a temporary, in which case it is not only problematic, it is completely

> Of course it's very difficult to warn users at compile time that they
> can't write the expression as you wrote it so it's an accident waiting
> to happen, I realise that.
> A point that needs to be taken into account though is that the
> iterators-as-everyone-knows-them can be just plain pointers in many
> cases and compilers are in general more capable of optimising
> compiler-arithmetic than some user-defined-iterator-object.
> But again, don't get me wrong: I see the value of a range or
> cursor-and-property-map style interface, I'm just saying that IMO we
> need 'scientific' proof of the best approach before deciding.

I agree - but also it is possible to take iterators way too seriously:
sure, you need some kind of iterator to actually implement the fundamental
operations, but for linear algebra, arithmetic operations, dot products
etc are the level to aim for. For example, an iterator for distributed
containers that has the same interface as an iterator for a purely local
container, seems difficult to achieve. The level at which to implement
distributed containers is probably at operator+, inner_prod, etc.

For another example, I have a lot of uses for a sparse matrix for complex
numbers, implemented as the sum of a pure real matrix and a pure imaginary
matrix. I have some applications where I want to allow complex arithmetic
without penalizing too much the real case, and even in the complex case
many of the matrix elements will be purely real. This begs for something

template <typename T>
class ComplexSparseMatrix
   // ....

   SparseMatrix<T> RealPart;
   SparseMatrix<T> ImaginaryPart;

It is trivial to implement the basic arithmetic operations, but I would
very much like to see an efficient iterator design for this type!

FWIW, the iterator model I ended up with uses a single iterator (no
begin/end pair) with a conversion to bool that becomes false once the
iterator hits the end, and an index() member (for matrices, a two level
segmented iterator with index1()/index2() on the inner iterator).
Iterator categories distinguish between unordered(sparse),
ordered(sparse), and dense indices. This is all done with free functions,
so it works for std::vector too. Since examples seem to be the order of
the day,

template <typename T>
void print_vector(T const& v)
   typename iterator<T>::type I = iterate(v);
   while (I)
      cout << "v[" << I.index() << "] = " << (*I) << '\n';