[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
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
(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
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
Markus Werle
Sebastian Redl
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 (3)
-
David Abrahams -
Markus Werle -
Sebastian Redl