Modify

Opened 9 years ago

Last modified 22 months ago

#2539 new Bugs

advance() and distance() for new iterator concepts

Reported by: debionne@… Owned by: jeffrey.hellrung
Milestone: Boost 1.38.0 Component: iterator
Version: Boost 1.37.0 Severity: Problem
Keywords: Cc:

Description

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).

Attachments (0)

Change History (4)

comment:1 Changed 9 years ago by viboes

Component: Noneiterator
Owner: set to Dave Abrahams

comment:2 Changed 8 years ago by 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;
};


comment:3 Changed 5 years ago by Dave Abrahams

Owner: changed from Dave Abrahams to jeffrey.hellrung

comment:4 Changed 22 months ago by 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

Modify Ticket

Change Properties
Set your email in Preferences
Action
as new The owner will remain jeffrey.hellrung.

Add Comment


E-mail address and name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.