"++--rng.end() == rng.end()" can fail for strided ranges

[Michel Morin]

Attached a test case for which "++--rng.end() == rng.end()" fails.

Due to this bug, libc++'s deque<T>::insert function misunderstands the size of strided ranges. For example,

using boost::strided_range;
using boost::adaptors::strided;

int ar[3] = {0, 1, 2};
strided_range<int[3]> rng = ar | strided(3);

std::deque<int> cont;
cont.insert(cont.begin(), rng.begin(), rng.end());

std::cout << cont.size() << std::endl;

outputs 2 (not 1) with libc++. You can see libs/range/test/adaptor_test/strided.cpp fails on test runners with libc++.

[Michel Morin]

A test case for which "++--rng.end() == rng.end()" fails.

[Michel Morin]

Just for reference, here is a sample implementation of strided_iterator for Random Access Range (without zero-stride support), which can pass strided.cpp test (other than strided_test_zero_stride).

// for Random Access Range (without zero-stride support)
template <typename BaseIterator>
class strided_iterator<BaseIterator, boost::random_access_traversal_tag>
  : public iterator_facade<  
        strided_iterator<BaseIterator, boost::random_access_traversal_tag>
      , typename std::iterator_traits<BaseIterator>::value_type
      , boost::random_access_traversal_tag
      , typename std::iterator_traits<BaseIterator>::reference
      , typename std::iterator_traits<BaseIterator>::difference_type
    >
{
public:
    // types
    typedef typename std::iterator_traits<BaseIterator>::reference reference;
    typedef typename std::iterator_traits<BaseIterator>::difference_type difference_type;
    
    // ctors
    strided_iterator() {}
    strided_iterator(
        BaseIterator first
      , BaseIterator it
      , BaseIterator last
      , difference_type stride
    )
      : m_begin(first)
      , m_offset((it - first) % stride == 0 ? (it - first) / stride : (it - first) / stride + 1)
      , m_stride(stride)
    {}

private:
    // iterator_facade core operations
    friend class boost::iterator_core_access;
    
    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
    { return 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;
};

[Neil Groves]

Thanks for the report. The posted implementation does fix this problem but would introduce a number of others. I have reimplemented the strided iterators and eliminated this issue.

I apologise for the nuisance this defect has caused you. Thanks for helping.