advance() and distance() for new iterator concepts

[debionne@…]

I can't find a trace of a problem submitted by Sebastian Redl last year : ​http://lists.boost.org/Archives/boost/2007/09/127785.php

In brief, the std version of advance() and distance() functions does not dispatch accordingly to the traversal_tag. For instance a transform_iterator is categorized as std::input_iterator_tag, boost::random_access_traversal_tag and the chosen distance() implementation is O(n) while O(1) is expected.

The patch suggested by Sebastian works fine. The only thing is that names collides with Boost.Range (which already have boost::distance).

[paul]

Any update on this? I would like to add that this is not simply a effeciency issue, it leads to erroneous behavior if a boost iterator is used with std::advance and if nothing else there should be a strong warning in the documentation, i.e. the following test fails std::advance(some_boost_iterator.end(), -1) != some_boost_iterator.end().

Simple test,

int main()
{
        test_iter itr(0);

        itr++;
        assert(*itr == 1);

        ++itr;
        assert(*itr == 2);

        itr+=8;
        assert(*itr == 10);

        itr-=8;
        assert(*itr == 2);

        --itr;
        assert(*itr == 1);

        itr--;
        assert(*itr == 0);

        std::advance(itr, 5); // passes, but less efficient than expected
        assert(*itr == 5);

        std::advance(itr, -5); // iterator is not moved
        assert(*itr == 0); // FAILURE, *itr == 5
}



struct test_iter
  : public boost::iterator_facade<
        test_iter
      , int
      , boost::random_access_traversal_tag,
          int
    >
{

 public:
    test_iter() : m_value(0) {}
    explicit test_iter(int v) : m_value(v) {}

    test_iter(test_iter const& other) : m_value(other.m_value) {}

    bool equal(test_iter const& other) const
    {
        return this->m_value == other.m_value;
    }

    void increment() { ++m_value; }
    void decrement() { --m_value; }

    int dereference() const { 
                return m_value; 
        }

        void advance(difference_type offset)
        {
                m_value+=offset;
        }

        difference_type distance_to(const test_iter& rhs)
        {
                return m_value-rhs.m_value;
        }

        int m_value;
};

[anonymous]

My business partners wanted DA 31 earlier today and encountered a great service that hosts a searchable forms database . If you require DA 31 too , here's ​http://goo.gl/3IWMJu