christopher diggins wrote:
----- Original Message ----- From: "Ian McCulloch" <ianmcc@physik.rwth-aachen.de> To: <boost@lists.boost.org> Sent: Friday, June 03, 2005 2:09 PM Subject: [boost] Re: stride iterators and matricies
christopher diggins wrote:
Well all of this talk of matricies, and what not got me thinking that perhaps we should get back to basics and introduce stride iterators into Boost which properly model the Random Access Iterator concept (unless they are already existant somewhere and I simplty overlooked them :-p ) I would suggest that we introduce a mini-library simply for stride iterators (and k-stride iterators, where the stride factor is a compile-time constant.) Any interest in seeing the following stride iterators submitted to boost as a mini-library?
That would be useful, however your sample code has a problem with the end iterator. To iterate over every second element of a container that has an even length, the one-past-the-end stride-2 iterator is actually TWO past the end of the original container. Unless you have a special container where incrementing beyond the one-past-the-end is allowed, you need another solution (indexing?).
Would indexing not lead to a similar problem? I would have thought the only way out is to pass a size parameter to the iterator. Do any iterators exist which do not allow incrementing past one past the end?
The solution using indexing is to store an integer index and a base iterator. Then operator== on the stride iterator simply checks whether the indices are equal, although it gets more 'interesting' if it is allowed to have such iterators pointing to the same container but with different bases. In principle, incrementing beyond one past the end is disallowed for all iterators. In practice you can probably get away with it for pointers (I think POSIX guarantees it too [unless it overflows], but not sure of that). I would not be surprised at all if it failed for deque::iterator.
How about if == was defined as :
friend bool operator==(const self& x, const self& y) { return (y - x) < step; }
and similarly for operator<() ?
The more fundamental problem is how to avoid incrementing beyond one past the end.
[...]
template<class Iter_T> class stride_iter
[...]
template<class Iter_T, int Step_N> class kstride_iter
May I suggest
struct VariableStride {};
template <class Iter_T, class Stride /* = VariableStride ? */ > class stride_iterator // ...
use as
stride_iterator<T, VariableStride> x; stride_iterator<T, boost::mpl::int_<2> > y;
Interesting idea, and more elegant. I would not do it that way, but I would be willing to be it would be more popular to implement as you suggest.
The reason I suggested that is because for algorithms that you might want to provide specialized implementations for stride iterators, you probably want to work for both compile-time and runtime strides, and to avoid having to write the algorithm twice (or more). template <typename T, typename Stride> void fill(stride_iterator<T, Stride> first, stride_iterator<T, Stride> last) { // optimized implementation using first.base(), first.stride(), ... } and if you really do want to restrict it to compile-time strides you can still do that: template <typename T, int N> void foo(stride_iterator<T, boost::mpl::int_<N> > iter) // ... Cheers, Ian