[boost] Re: Re: stride iterators and matricies

From: Ian McCulloch (ianmcc_at_[hidden])
Date: 2005-06-03 21:17:46

christopher diggins wrote:

> ----- Original Message -----
> From: "Ian McCulloch" <ianmcc_at_[hidden]>
> To: <boost_at_[hidden]>
> 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