[Boost-users] [iterator] std::distance ignores random_access_traversal_tag

From: Markus Werle (numerical.simulation_at_[hidden])
Date: 2006-11-16 04:11:20

Hi!

This was detected by profiling. I expected the code below
to have a rather cheap std::distance call because my iterator
was tagged as random_access. 

gcc-4.0.3 (cygwin) and VC8 IMHO choose the wrong std::distance algorithm,
but why? The stuff compiles even when distance_to is not defined.
Maybe I misunderstood the docs, especially the passage

<cite url="http://boost.org/libs/iterator/doc/iterator_facade.html">
[...]
where iterator-category is defined as follows:

iterator-category(C,R,V) :=
   if (C is convertible to std::input_iterator_tag
       || C is convertible to std::output_iterator_tag
   )
       return C

   else if (C is not convertible to incrementable_traversal_tag)
       the program is ill-formed

   else return a type X satisfying the following two constraints:
[..]
</cite>

Please explain and fix the code below.

Markus

#include <boost/iterator/iterator_facade.hpp>
#include <boost/bind.hpp>

#include <cstddef>
#include <iterator>
#include <iostream>

template <typename ValueT, typename SizeT, typename IndexOperatorT>
class signal_iter
        : public boost::iterator_facade
        <signal_iter<ValueT, SizeT, IndexOperatorT>,
         ValueT,
         // !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
         boost::random_access_traversal_tag,
         ValueT,
         SizeT>
{
public:
        typedef signal_iter<ValueT, SizeT, IndexOperatorT> my_own_t;

        inline signal_iter(IndexOperatorT IndexOperator, SizeT index) 
                : m_IndexOperator(IndexOperator)
                , m_index(index)
        {}

        // quick and dirty with a dangling reference :-(
        inline signal_iter() 
                : m_IndexOperator(IndexOperatorT())
                , m_index(0)
        {}

        inline SizeT index() const 
        { 
                return m_index; 
        }

private:
        friend class boost::iterator_core_access;

        inline void increment() 
        {
                ++m_index;
        }

        inline void decrement() 
        {
                --m_index;
        }

        inline void advance(SizeT i)
        {
                m_index += i;
        }

        inline SizeT distance_to(signal_iter const& other) const
        {
                return other.index() - m_index;
        }

        inline bool equal(signal_iter const& other) const
    {
                return (other.index() == m_index);
        }

        inline ValueT dereference() const 
        { 
                return m_IndexOperator(m_index); 
        }
        
protected:
        IndexOperatorT m_IndexOperator;
        SizeT m_index;
};

// stripped down demo
class Demo
{
        static const std::size_t mysize_ = 20;
        typedef std::size_t size_type;
        typedef double value_type;

        double data_[mysize_];

public:
        double operator[](std::size_t i)
        {
                return data_[i];
        }

        typedef boost::_bi::bind_t
        <double, boost::_mfi::mf1<double, Demo, unsigned int>, 
         boost::_bi::list2<boost::_bi::value<Demo*>, 
                                           boost::arg<1> > > bind_type;

        typedef signal_iter<const value_type, size_type, bind_type> 
        const_iterator;

        const_iterator begin()
        {
                return const_iterator
                        (boost::bind(&Demo::operator[], this, _1), 0);
        }

        const_iterator end()
        {
                return const_iterator
                        (boost::bind(&Demo::operator[], this, _1), mysize_);
        }
};

int main()
{
        Demo demo;
        
        std::cout << std::distance(demo.begin(), demo.end())<< std::endl;
}