[iterator] std::distance ignores random_access_traversal_tag
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; }
Markus Werle wrote:
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.
std::distance doesn't understand the new iterator categories, only the old, which merge the traversal and access traits into one. This means that even if your iterator has random_access_traversal, std::distance will not see it as a random_access iterator unless it also has lvalue semantics (forgot what that trait is called). Since your reference type is ValueT, not ValueT&, this is not the case. You could write a new-style distance() function that only cares about the traversal category. Or perhaps someone has already written it. (Dave: that might be a worthy addition to the iterator library: distance() and advance() for the new-style iterators. Like boost::TR1, the functions could just forward to implementations that are already updated.) Sebastian Redl
Sebastian Redl <sebastian.redl@getdesigned.at> writes:
(Dave: that might be a worthy addition to the iterator library: distance() and advance() for the new-style iterators. Like boost::TR1, the functions could just forward to implementations that are already updated.)
Patches (including docs and tests) welcomed. -- Dave Abrahams Boost Consulting www.boost-consulting.com
Sebastian Redl <sebastian.redl <at> getdesigned.at> writes:
Markus Werle wrote:
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.
std::distance doesn't understand the new iterator categories,
Ouch! The tutorial is definitely too short! So I can use std::random_access_iterator_tag instead? I simply want an iterator that works with current STL as random iterator. Class Demo uses a std::size_t as index type. How do I build my iterator with iterator_facade? Problem: If I use template <typename ValueT, typename SizeT, typename IndexOperatorT> class signal_iter : public boost::iterator_facade <signal_iter<ValueT, SizeT, IndexOperatorT>, ValueT, std::random_access_iterator_tag, ValueT> { [...] } iterator_facade implementation applies unary minus to unsigned type in its code: template <class Facade1, class Facade2> static typename Facade1::difference_type distance_from( Facade1 const& f1, Facade2 const& f2, mpl::true_) { return -f1.distance_to(f2); } How can I circumvent this? Markus
Markus Werle <numerical.simulation@web.de> writes:
Sebastian Redl <sebastian.redl <at> getdesigned.at> writes:
Markus Werle wrote:
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.
std::distance doesn't understand the new iterator categories,
Ouch! The tutorial is definitely too short!
Patches welcomed.
So I can use std::random_access_iterator_tag instead?
Not with your iterator definition; you'd be lying to the standard library. A standard random access iterator has a reference type of value_type&. Without that, your iterator is just an input iterator from the STL point-of-view.
I simply want an iterator that works with current STL as random iterator.
Then use a real reference type. Sorry, the STL iterator design took a limited worldview and you have to conform to it if you want to get all the expected optimizations.
Class Demo uses a std::size_t as index type. How do I build my iterator with iterator_facade?
Use a signed distance type; that's a requirement of STL (and new-style) iterators. -- Dave Abrahams Boost Consulting www.boost-consulting.com
David Abrahams wrote:
So I can use std::random_access_iterator_tag instead?
Not with your iterator definition; you'd be lying to the standard library. A standard random access iterator has a reference type of value_type&. Without that, your iterator is just an input iterator from the STL point-of-view.
Does that mean that I cannot create a standard conforming random access iterator for a class that behaves as a read-only proxy for values calculated on-the-fly when requested?
I simply want an iterator that works with current STL as random iterator.
Then use a real reference type. Sorry, the STL iterator design took a limited worldview and you have to conform to it if you want to get all the expected optimizations.
So the best way is to define distance(MyIterator, MyIterator); lower_bound... etc. in namespace std?
Class Demo uses a std::size_t as index type. How do I build my iterator with iterator_facade?
Use a signed distance type; that's a requirement of STL
I kind of fixed it by overloading operator- in order to avoid -distance_to. Now it "works". Is this dangerous?
(and new-style) iterators.
So using std::size_t as index argument type is a bad idea if I want to plug iterators? I mean: AFAIK it is not guaranteed that I have a signed type that can hold std::size_t. Correct me if I am wrong, please. Markus
participants (2)
-
David Abrahams -
Markus Werle -
Sebastian Redl