UBLAS Matrix Iterators

current state

As of today (2006-07-06) ublas' matrix iterators look like this:

const_iterator1 moves from one row to another for a fixed column.

const_iterator2 moves from one column to another for a fixed row.

One can always switch from one iterator to the other (called dual iterator) by calling the begin() or end() member function. Both iterators store the current row and column index and have to implement the movement in both fast (inner loop) and slow (outer loop) direction. Thus the code is complex and the memory footprint is not optimal. On the other hand the design of generic algorithms is easy because you can arbitrarily choose which iterator is outer or inner loop (but this is typically a bad design).

current implementation

quick survey

Does anyone use the duality feature?

edit by Gunter: Up to now I got only negative answers.

ideas for a better design

Drop the strong duality and provide a major (outer loop) and minor (inner loop) iterator. The major iterator could always be a random access dense iterator that only stores an index. The minor iterator holds a copy of the major index and can use an optimized way to traverse along matrix elements. The minor iterator should have an advance_to_index(k) function that moves the iterator at the first element with index >= k (like std::lower_bound). This way traversal orthogonal to the storage layout can be emulated and we don't need any find functions.

The advance_to_index(k) function could be implemented as a free function specialized for different iterator types (bidirectional, random access). Syntax: iterator& advance_to_index(iterator& it, iterator const& it_end, size_type index).

The mapping of the pair (major index, minor index) to the pair (row index, column index) can be implemented using a traits class and the orientation category of the matrix. The existing index_M and index_m in the row/column_major storage layout types provide such a mapping. Thus we should make layout_type public.

sample implementation

Download the source files from [1].

other issues with iterators

Dense matrices allow for a simple definition of iterators operating over all elements. When sparse and special matrices are considered the definition is not so clear. For sparse matrices operation over the non-zeros is required.

However for symmetric and triangular special matrices there are other choices. In particular when using a mutable iterator we can only iterate over the primary mutable elements. This does not define all iterators as 'iterating over non-zeros' as there may be over non-zero elements.