StrideIterator: a valid concept?

[c.m.]

Hi,

I'm implementing a multidimensional array class and I want to let the
user call algorithms like std::sort along any dimension. As an example,
users shall be able to sort a 2D array along the columns as well as the
rows.

So in most cases the elements to be sorted will not be laid out
contiguously in memory. To work around this, the O'Reilly C++ Cookbook
introduces the StrideIterator Template that adapts another iterator.
Here's the gist of it:

StrideIterator(RandomAccessIterator iterToAdapt, difference_type step) :
adaptedIter(iterToAdapt),
step(step)
{
}

self& operator++()
{
adaptedIter += step;
return *this;
}

The trouble with this is the one-past-the-last-element semantics for
specifying the end of a sequence. The last ++iter call would make the
underlying pointer point outside the array. According to 5.7.5 of the
standard, the behaviour of the += step addition is undefined in that
case. With VC2008 it fails an assertion when adapting a
std::vector::iterator.

Is there an elegant way to make this work? Obviously, one could put an

if (underlyingArray.end() - adaptedIter < step) {
adaptedIter = underlyingArray.end();
return;
}

into operator++ to "clamp" the iterator to one-past-the-last-element but
from a performance point-of-view, having a conditional in there is not
an attractive solution.

Thanks,
Chris

 

[tonydee]

Hi,

I'm implementing a multidimensional array class and I want to let the
user call algorithms like std::sort along any dimension. As an example,
users shall be able to sort a 2D array along the columns as well as the
rows.

So in most cases the elements to be sorted will not be laid out
contiguously in memory. To work around this, the O'Reilly C++ Cookbook
introduces the StrideIterator Template that adapts another iterator.
Here's the gist of it:

StrideIterator(RandomAccessIterator iterToAdapt, difference_type step) :
        adaptedIter(iterToAdapt),
        step(step)
{

}

self& operator++()
{
        adaptedIter += step;
        return *this;

}

The trouble with this is the one-past-the-last-element semantics for
specifying the end of a sequence. The last ++iter call would make the
underlying pointer point outside the array. According to 5.7.5 of the
standard, the behaviour of the += step addition is undefined in that
case. With VC2008 it fails an assertion when adapting a
std::vector::iterator.

Is there an elegant way to make this work? Obviously, one could put an

if (underlyingArray.end() - adaptedIter < step) {
        adaptedIter = underlyingArray.end();
        return;

}

into operator++ to "clamp" the iterator to one-past-the-last-element but
from a performance point-of-view, having a conditional in there is not
an attractive solution.

Could you change the constructor to accept an end() iterator too, then
subtract iterToAdapt from it to get the number of remaining elements,
then decrement it as you step along, comparing against 0?
Alternatively, don't decrement it or increment adaptedIter, but
increment an additional "offset" member and give access to adaptedIter
+ offset....

But, will that help you sort? A naive application of std::sort()
would then sort the column or row, not the 2D matrix....

Cheers,
Tony

 

[c.m.]

Hi,

Could you change the constructor to accept an end() iterator too, then
subtract iterToAdapt from it to get the number of remaining elements,
then decrement it as you step along, comparing against 0?

Yes, but then I'd need a conditional in operator++ just like the one
above, except it would be if (remainingElements != 0) {...}

Alternatively, don't decrement it or increment adaptedIter, but
increment an additional "offset" member and give access to adaptedIter
+ offset....

I like this idea and I'll give it a try. Right now I can't see any
drawbacks.

But, will that help you sort? A naive application of std::sort()
would then sort the column or row, not the 2D matrix....

Yes, sorting a column or a row (and using similar algorithms on columns
and rows) is precisely what I want. If i wanted to sort all the columns
I'd simply call one sort() for each column...each time with a properly
set up StrideIterator.

Thanks,
Christian

 

[tonydee]

Yes, but then I'd need a conditional in operator++ just like the one
above, except it would be if (remainingElements != 0) {...}

Yes, sorting a column or a row (and using similar algorithms on columns
and rows) is precisely what I want. If i wanted to sort all the columns
I'd simply call one sort() for each column...each time with a properly
set up StrideIterator.

Can't quite follow you there, but glad if there's no problem....

Cheers,
Tony