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

16 Nov 2006

      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;
}

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

Markus Werle