Glas List: 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 
wrong.

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

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';
      ++I;
   }
}

Cheers,
Ian