All cursors and iterators are handled by:
They are all templated by a tag that determines the form of traversal. The following tags are currently available for cursors:
for (Cursor cursor(begin(x)), cend(end(x)); cursor != cend; ++cursor)
do_something(cursor);
In order to have more flexibility we templatized the begin and end functions:
for (Cursor cursor(begin<tag::all>(x)), cend(end<tag::all>(x)); cursor != cend; ++cursor)
do_something(cursor);
for (Cursor cursor(begin<tag::row>(x)), cend(end<tag::row>(x)); cursor != cend; ++cursor) for (ICursor icursor(begin<tag::nz>(cursor)), icend(end<tag::nz>(cursor)); icursor != icend; ++icursor) do_something(icursor);
for (Cursor cursor(begin<tag::major>(x)), cend(end<tag::major>(x)); cursor != cend; ++cursor) for (ICursor icursor(begin<tag::nz>(cursor)), icend(end<tag::nz>(cursor)); icursor != icend; ++icursor) do_something(icursor);
for (Cursor cursor(begin<tag::nz>(x)), cend(end<tag::nz>(x)); cursor != cend; ++cursor) cout << "matrix[" << row(*cursor) << ", " << col(*cursor) << "] = " << const_value(*cursor) << '\n';
value(*cursor, 7);
typedef typename traits::range_generator<tag::row, Matrix>::type c_type; typedef typename traits::range_generator<tag::nz, c_type>::type ic_type; for (c_type cursor(begin<tag::row>(x)), cend(end<tag::row>(x)); cursor != cend; ++cursor) for (ic_type icursor(begin<tag::nz>(cursor)), icend(end<tag::nz>(cursor)); icursor != icend; ++icursor) do_something(icursor);
The usage of iterators is very similar to those of cursors:
for (Iter iter(begin<tag::const_iter::nz>(x)), iend(end<tag::const_iter::nz>(x)); iter != iend; ++iter) cout << "matrix value = " << *iter << '\n';
for (Cursor cursor(begin<tag::major>(x)), cend(end<tag::major>(x)); cursor != cend; ++cursor) for (Iter iter(begin<tag::const_iter::nz>(cursor)), iend(end<tag::const_iter::nz>(cursor)); iter != iend; ++iter) cout << "matrix value = " << *iter << '\n';
Dense matrices are traversed with linear or cached_linear complexity. The latter is used for contiguous memory access over strided ones, which is also linear but considerably slower. This distinction is mathematically questionable but useful in practical contexts.
Sparse matrices have linear complexity when traversed along the orientation. Traversing compressed matrices perpendicular to the orientation (e.g. a CRS matrix column-wise) has infinite complexity because it is not implemented. Moreover, the default (non-spezialized) range_generator has infinite complexity so that it is per se defined for arbitrary collections and tags. Whether the range generator is actually really implemented can be tested by comparing the complexity with infinite (by using MPL functions).
The following example shows a simpler way to find out the best traversal:
// MTL4 example: minimize complexity of traversal #include <iostream> #include <boost/numeric/mtl/mtl.hpp> using namespace mtl; template <typename Matrix> void f(Matrix& m) { using traits::range_generator; using traits::range::min; // Set values in diagonal m= 7.0; // Choose between row and column traversal typedef typename min<range_generator<tag::row, Matrix>, range_generator<tag::col, Matrix> >::type range_type; range_type my_range; // Type of outer cursor typedef typename range_type::type c_type; // Type of inner cursor typedef typename traits::range_generator<tag::nz, c_type>::type ic_type; // Define the property maps typename traits::row<Matrix>::type row(m); typename traits::col<Matrix>::type col(m); typename traits::const_value<Matrix>::type value(m); // Now iterate over the matrix for (c_type cursor(my_range.begin(m)), cend(my_range.end(m)); cursor != cend; ++cursor) for (ic_type icursor(begin<tag::nz>(cursor)), icend(end<tag::nz>(cursor)); icursor != icend; ++icursor) std::cout << "matrix[" << row(*icursor) << ", " << col(*icursor) << "] = " << value(*icursor) << '\n'; } int main(int argc, char* argv[]) { // Define a CRS matrix compressed2D<double> A(3, 3); // And a CCS matrix compressed2D<double, matrix::parameters<col_major> > B(3, 3); f(A); f(B); return 0; }
Please not that the example uses compressed sparse matrices and not all forms of traversion are supported. Obviously a linear complexity is lower than an infinite and the range generator without implemenation is never used. As the free functions begin() and end() are internally always implemented by member functions of range_generator (free template functions cannot be spezialized partially) we used directly the member functions in the example.
The range generator can also be minimized recursively between three and more alternatives:
typedef typename min<range_generator<tag::row, Matrix>, typename min<range_generator<tag::col, Matrix>, range_generator<tag::major, Matrix> >::type >::type range_type;
In many cases there is no need for explicitly minimizing the complexity because tag::major usually will yield the same results (but this is not so cool).
Return to Using Predefined Linear Solvers Table of Content Proceed to Recursion
-----------------------------------------------------------
/*!
Iteration -- MTL 4 -- Peter Gottschling and Andrew Lumsdaine
-- Generated on 19 May 2009 by Doxygen 1.5.5 -- Copyright 2007 by the Trustees of Indiana University.