Re: [boost] [range][stride] broken?

Subject: Re: [boost] [range][stride] broken?
From: Michel MORIN (mimomorin_at_[hidden])
Date: 2010-12-23 14:31:08

Hi Neil,

Neil Groves wrote:
> I will submit a fix to boost-trunk today. After a couple
> of days of passes on boost-trunk I shall merge to boost-release.
>
The ticket (#5014) just has been closed, but the test case in the ticket
still prints out wrong results.

This is because, when constructing strided_range,
the end iterator of an input range should advance forward rather than backward.
Advancing the end iterator forward might cause overflow, so implementing
strided_iterator needs some care to handle "overflowed" end iterators.
I can think of the following implementation:

// Partial specialization (for Random Access Range)
template <typename BaseIterator>
class strided_iterator<BaseIterator, boost::random_access_traversal_tag>
  : public iterator_facade</* ... */>
{
public:
    // ...

private:
    // iterator_facade core operations
    reference dereference() const
    { return *(m_begin + m_stride * m_offset); }

    bool equal(strided_iterator const& other) const
    { return m_begin == other.m_begin && m_offset == other.m_offset; }

    void increment() { ++m_offset; }
    void decrement() { --m_offset; }
    void advance(difference_type n) { m_offset += n; }

    difference_type distance_to(strided_iterator const& other) const
    { other.m_offset - m_offset; }

    // data
    BaseIterator m_begin; // the begin iterator of an input range
    difference_type m_offset; // the number of strides taken by this iterator
    difference_type m_stride;
};

For Single Pass Range (including Forward and Bidirectional Ranges), I think
it's better to use a different implementation to avoid using size() function.
To achieve this, strided_iterator stores the end iterator of the input range:
(When constructing strided_range, the end iterator of an input range does not
need to be advanced anymore in this implementation.)

// Primary template (for Single Pass, Forward and Bidirectional Ranges)
template <typename BaseIterator, typename TraversalCategory>
class strided_iterator
  : public iterator_adaptor</* ... */>
{
public:
    // ...

private:
    // adapted core operations
    void increment() {
        difference_type i = 0;

        do {
            ++this->base_reference();
            ++i;
        } while (this->base_reference() != m_end && i < m_stride);
    }

    // data
    difference_type m_stride;
    BaseIterator m_end;
};

I don't know whether we should implement decrement() function for
Bidirectional Range.

Regards,
Michel