[iterator] Silent-but-deadly bug in iterator_facade category
Hi folks, I've stumbled across a nasty problem with iterator_facade in which code which appears correct and compiles fine can cause runtime problems. Consider an iterator_facade which just wraps a random access iterator and applies a transformation to it: char transform(int i) { return 'a'; } struct my_iterator : public boost::iterator_facade<my_iterator, char, // value_type std::random_access_iterator_tag, // *** char> // reference { my_iterator(const std::vector<int>::iterator& it) : _it(it) {} char dereference() const { return transform(*_it); } bool equal(const my_iterator& other) const { return _it == other._it; } void increment() { ++_it; } void decrement() { --_it; } void advance(int n) { std::advance(_it, n); } int distance_to(const my_iterator& other) const { return other._it - _it; } private: std::vector<int>::iterator _it; }; Now if I have an STL-style function which is overloaded on the iterator category, clearly the random-access version will be selected. template <typename TIterator> void funcImpl(TIterator it, std::input_iterator_tag) { std::cerr << "Running func treating 'it' as input iterator\n"; } template <typename TIterator> void funcImpl(TIterator it, std::random_access_iterator_tag) { std::cerr << "Running func treating 'it' as random access iterator\n"; } template <typename TIterator> void func(TIterator it) { funcImpl(it, typename std::iterator_traits<TIterator>::iterator_category()); } In the line marked ***, the docs suggest I should use boost::random_access_traversal_tag instead of std::random_access_iterator_tag - but when I do, the program no longer selects the random access version of 'func', choosing the forward-only version instead! The iterator_category of my_iterator ends up as: boost::detail::iterator_category_with_traversal<std::input_iterator_tag, boost::random_access_traversal_tag> The reason I called this a 'deadly' bug is that std::advance is suddenly a deathtrap: std::advance(it, -1); This is fine and legal for random access iterators, but if the forward-only version gets called instead, the behavior is undefined (on my system, it loops endlessly). The compiler doesn't complain either way - the problem surfaces only at runtime. Does the problem lie with iterator_category_with_traversal? It looks like it's intended in this case to be convertible to either std::input_iterator_tag or std::random_access_iterator_tag, but clearly something is wrong with the latter conversion. Any ideas? Thanks, -Gabe
Does the problem lie with iterator_category_with_traversal? It looks like it's intended in this case to be convertible to either std::input_iterator_tag or std::random_access_iterator_tag, but clearly something is wrong with the latter conversion. Any ideas?
The problem lies in the fact that your iterator when it calls `dereference()`, returns something that is not a reference(ie char). For it to be a `std::random_access_iterator_tag` it must a reference. That is, `iterator_traits<X>::reference` must be an actual reference. So therefore your iterator is given the `std::input_iterator_tag`, since it is the only iterator category that doesn't require `dereference()` to return a reference. So then when you call:
std::advance(it, -1);
With an input iterator, it will, depending on the implementation and the build type, either fail with a runtime assertion, or go into an infinite loop. Thanks, Paul
Hi Paul, Thanks for your reply.
For it to be a `std::random_access_iterator_tag` it must a reference. That is, `iterator_traits<X>::reference` must be an actual reference.
Can you point me at a reference (pun not intended) for this requirement? The sites I've looked at don't mention this [1-3]. Is it a requirement for, say, bidirectional iterators too? Your message makes it sound like this is specific to random access iterators. If the iterator's reference must be a real reference type, then why does iterator_facade not check this at compile time? And in any case, isn't this a flaw? my_iterator can be advanced etc. in constant time - why should the STL be forced to use a possibly-suboptimal overload of some algorithm on account of the reference type? Confused, -Gabe [1] http://www.cplusplus.com/reference/iterator/RandomAccessIterator/ [2] http://en.cppreference.com/w/cpp/concept/RandomAccessIterator [3] http://www.sgi.com/tech/stl/RandomAccessIterator.html
[Gabriel Redner]
Can you point me at a reference (pun not intended) for this requirement? The sites I've looked at don't mention this [1-3]. Is it a requirement for, say, bidirectional iterators too? [1] http://www.cplusplus.com/reference/iterator/RandomAccessIterator/ [2] http://en.cppreference.com/w/cpp/concept/RandomAccessIterator [3] http://www.sgi.com/tech/stl/RandomAccessIterator.html
Only Standards - and Working Papers that will become Standards when they grow up - are authoritative. The latest Working Paper is N3485, http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3485.pdf 24.2.7 [random.access.iterators]/1: "A class or pointer type X satisfies the requirements of a random access iterator if, in addition to satisfying the requirements for bidirectional iterators, [...]" 24.2.6 [bidirectional.iterators]/1: "A class or pointer type X satisfies the requirements of a bidirectional iterator if, in addition to satisfying the requirements for forward iterators, [...]" 24.2.5 [forward.iterators]/1: "A class or pointer type X satisfies the requirements of a forward iterator if [...] - if X is a mutable iterator, reference is a reference to T; if X is a const iterator, reference is a reference to const T, [...]" Stephan T. Lavavej Visual C++ Libraries Developer
And in any case, isn't this a flaw? my_iterator can be advanced etc. in constant time - why should the STL be forced to use a possibly-suboptimal overload of some algorithm on account of the reference type?
This exactly the problem that Boost.Iterator is trying to address. It separates access and traversal. So, whereas the random access iterator category requires an lvalue access with random access traversal, in Boost.Iterator you can specify them separately. Unfortunately, the proposal to accept this into C++ was never accepted. There was talk of relaxing the requirements for C++11, but that never happened. And I dont think theres any talk of it for C++14 that I know of. Thanks, Paul
For it to be a `std::random_access_iterator_tag` it must a reference. That is, `iterator_traits<X>::reference` must be an actual reference.
Can you point me at a reference (pun not intended) for this requirement? The sites I've looked at don't mention this [1-3]. Is it a requirement for, say, bidirectional iterators too? Your message makes it sound like this is specific to random access iterators.
It is a requirement for forward iterators and higher. The authoritative source for the requirement is the C++ standard. In the 2003 standard, section 24.1.3 has a table listing requirements for forward iterators. One of them is that if 'a' if a forward iterator, '*a' is a valid expression and has type 'T&', where T is the iterator's value type. In the 2011 standard, it's even more clear: section 24.2.5 states that one of the requirements for X to be a forward iterator is that "if 'X' is a mutable iterator, 'reference' is a reference to 'T'; if 'X' is a const iterator, 'reference' is a reference to 'const T'". Regarding the sites you linked to, the completeness and accuracy of their information is to be taken with a grain of salt, but I do see [1] list as a requirement for forward, bidirectional, and random access iterators that they "can be deferenced as an lvalue", which effectively requires that 'reference' be a reference type.
And in any case, isn't this a flaw? my_iterator can be advanced etc. in constant time - why should the STL be forced to use a possibly-suboptimal overload of some algorithm on account of the reference type?
Yes, it's a flaw. The STL unnecessarily conflates iterator traversal and iterator value access in its iterator categories. This is why Boost has developed, and uses, its own iterator concepts. See [2]. You can take advantage of Boost's iterator concepts by modifying 'func' from your original post to dispatch on boost::iterator_traversal<TITerator>::type() instead of std::iterator_traits<TIterator>::iterator_category(), since traversal is the relevant aspect in that case.
If the iterator's reference must be a real reference type, then why does iterator_facade not check this at compile time?
It "must" be a real reference type only from the point of view of the STL's broken iterator concepts. Boost.Iterator is perfectly happy to let you write an iterator whose traversal is random-access but whose 'reference' is not a reference type, which will then be considered an 'input iterator' by the STL. Hope that helps. Regards, Nate [1] http://www.cplusplus.com/reference/iterator/ForwardIterator/ http://www.cplusplus.com/reference/iterator/BidirectionalIterator/ http://www.cplusplus.com/reference/iterator/RandomAccessIterator/ [2] http://www.boost.org/doc/libs/1_53_0/libs/iterator/doc/new-iter-concepts.htm...
On Tue, 7 May 2013, Nathan Ridge wrote:
Yes, it's a flaw. The STL unnecessarily conflates iterator traversal and iterator value access in its iterator categories. This is why Boost has developed, and uses, its own iterator concepts. See [2].
And those concepts are "incompatible" with algorithms written for the standard concepts, so we are left with 2 choices: - don't use the STL directly, use the boost implementations instead - don't use boost iterators (well, a few classes are usable, but not transform_iterator for instance) In my experience, the easiest way to handle this painful reference requirement is to ignore it and pretend that the standard categories are only about traversal. I've never had anything break because of this. -- Marc Glisse
In my experience, the easiest way to handle this painful reference requirement is to ignore it and pretend that the standard categories are only about traversal. I've never had anything break because of this.
Is the OP's problem not an example of pretending that the standard iterator categories are only about traversal and having something break as a result? Regards, Nate
On Tue, 7 May 2013, Nathan Ridge wrote:
In my experience, the easiest way to handle this painful reference requirement is to ignore it and pretend that the standard categories are only about traversal. I've never had anything break because of this.
Is the OP's problem not an example of pretending that the standard iterator categories are only about traversal and having something break as a result?
As far as I can tell, the OP's problem only appeared when he started using boost traversal iterator categories, and things were working fine when he had random_access_iterator_tag (violating the reference requirement). Did I misunderstand his post? -- Marc Glisse
In my experience, the easiest way to handle this painful reference requirement is to ignore it and pretend that the standard categories are only about traversal. I've never had anything break because of this.
Is the OP's problem not an example of pretending that the standard iterator categories are only about traversal and having something break as a result?
As far as I can tell, the OP's problem only appeared when he started using boost traversal iterator categories, and things were working fine when he had random_access_iterator_tag (violating the reference requirement).
Well, you didn't say anything about using standard iterator categories in lieu of Boost ones when using Boost classes like iterator_facade. If you're saying that doing that together with ignoring the reference requirement has kept you out of trouble, I take your word for it :) Regards, Nate
Hi folks, Stephan T. Lavavej:
if X is a mutable iterator, reference is a reference to T; if X is a const iterator, reference is a reference to const T,
If I'm reading this right, then an iterator whose 'reference' is not a reference is not an std iterator at all. If so, then my question (not necessarily to you, but to everyone) becomes: why does the Iterator library tag such an iterator with std::input_iterator_tag? Isn't this strictly wrong? Nathan Ridge:
You can take advantage of Boost's iterator concepts by modifying 'func' from your original post to dispatch on boost::iterator_traversal<TITerator>::type() instead of std::iterator_traits<TIterator>::iterator_category(), since traversal is the relevant aspect in that case.
In my experience, the easiest way to handle this painful reference requirement is to ignore it and pretend that the standard categories are only about traversal. I've never had anything break because of this.
'func' exists just to illustrate the issue that these iterators interact badly with the STL. I realize that I could dispatch on the boost traversal concepts, but my concern was interoperability with STL algorithms. Marc Glisse: + Nathan Ridge:
Is the OP's problem not an example of pretending that the standard iterator categories are only about traversal and having something break as a result?
I would say that my problem was misunderstanding what iterator_facade is trying to do. It's not clearly explained how the CategoryOrTraversal argument is translated into the interator_category, and in what cases the result is different from what one would intuitively expect. The docs state over and over again how one of the goals of the library is easy interoperability of boost iterators with STL algorithms, but the gotchas seem to be hidden or not mentioned at all. Thanks everyone for the information. -Gabe
On Tue, May 7, 2013 at 7:58 AM, Gabriel Redner <gredner@gmail.com> wrote:
Hi folks,
Stephan T. Lavavej:
if X is a mutable iterator, reference is a reference to T; if X is a const iterator, reference is a reference to const T,
If I'm reading this right, then an iterator whose 'reference' is not a reference is not an std iterator at all.
If so, then my question (not necessarily to you, but to everyone) becomes: why does the Iterator library tag such an iterator with std::input_iterator_tag? Isn't this strictly wrong?
You snipped the relevant context: The above applies to ForwardIterators, not to InputIterators or OutputIterators. [...] - Jeff
You snipped the relevant context: The above applies to ForwardIterators, not to InputIterators or OutputIterators.
Ah ok, I see. I don't see why it should be that way, but I see that it is. The more I learn about iterators, the less I understand :-\ Thanks, -Gabe
On Tue, May 7, 2013 at 8:26 AM, Gabriel Redner <gredner@gmail.com> wrote:
You snipped the relevant context: The above applies to ForwardIterators, not to InputIterators or OutputIterators.
Ah ok, I see. I don't see why it should be that way, but I see that it is.
Welcome to the club :/ - Jeff
on Tue May 07 2013, Gabriel Redner <gredner-AT-gmail.com> wrote:
Hi folks,
Stephan T. Lavavej:
if X is a mutable iterator, reference is a reference to T; if X is a const iterator, reference is a reference to const T,
If I'm reading this right, then an iterator whose 'reference' is not a reference is not an std iterator at all.
It might be an input iterator or an output iterator, but it's not a forward iterator.
If so, then my question (not necessarily to you, but to everyone) becomes: why does the Iterator library tag such an iterator with std::input_iterator_tag? Isn't this strictly wrong?
No, it's strictly correct. -- Dave Abrahams
participants (7)
-
Dave Abrahams -
Gabriel Redner -
Jeffrey Lee Hellrung, Jr. -
Marc Glisse -
Nathan Ridge -
paul Fultz -
Stephan T. Lavavej