Counting Iterator return-type causes lifetime issues

[Neil Groves]

The counting_iterator upon integers has a dereference member function which is a reference to an integral value held in the iterator. Since an iterator may be destroyed, the reference can be invalid.

An example where this occurs was provided by a user of Boost.Range. The application used counting_range with reversed and transformed adaptors. The result was garbage since the reversed dereference member function does *boost::prior(this->base()); Hence it returns a reference to a temporary iterator that results from the "prior" function.

[Neil Groves]

As requested by Eric I have included his thoughts on one of the possible solutions:

On 8/28/2014 3:49 PM, Neil Groves wrote:

On 28 August 2014 22:35, Krzysztof Czainski wrote:

I think the problem is counting_iterator returns a reference to an int it owns. Iterators shouldn't do that.

This is exactly what is causing the issue.

Right.

Iterators should either:

• return a reference to something they don't own, or
• return by value.

Your logic for return type makes a lot of sense. Unfortunately there are conflated requirements upon the return type of dereference operations for the various iterator traversals. See http://www.boost.org/doc/libs/1_56_0/libs/multi_array/doc/iterator_categories.html.

I see no conflated requirements. In Boost.Iterators (as opposed to the standard iterator categories), iterator *traversal* deals only with traversal (++, --, +=, -=, etc) and says nothing about the return type of the dereference operation.

Krzysztof is right, though. The dereference operation should return an rvalue. That would make the counting_iterator a Readable iterator in the new-style categories. "Readable" is orthogonal to the iterator traversal.

So IMO, counting_iterator should be a Readable Iterator and a Random Access Traversal Iterator. When this is mapped to one of the standard iterator categories, it becomes std::input_iterator_tag (because of the requirements on Forward Iterators in the standard).

I imagine that this is why the counting_iterator is implemented to return a true reference.

No, I think this is a bug, plain and simple. Fixing it is likely to cause trouble though. :-(

This leaves us with rather a thorny problem, a counting_iterator can't have the dereference operator return by value and model the Bidirectional Iterator Concept. Therefore if counting_iterator were to return by value we wouldn't be allowed to reverse (if we constrained ourselves to the Standard iterator traversal categories). It might be that there is room for improvement while working with the Boost traversal tags rather than the iterator traversal tags.

If Boost.Range were made aware of the Boost new-style iterator categories -- which make traversal and access independent -- the reversed view could still work with counting_iterator. The resulting view's iterators would also be Random Access Traversal and Readable.

Making all of Boost.Range aware of the new-style iterators would be a piece of work, though.

Thanks for pointing this out, I hadn't spotted this issue with the counting_iterator. After giving this some more thought I shall raise a ticket for Boost.Iterator.

Indeed. Please include this discussion in the bug report.

Eric

[Neil Groves]

My personal view is that we should ensure we have considered alternative solutions since simply making the counting_iterator compliant will:

1. Break existing code without obvious solutions for clients of counting_iterator
2. Severely degrade performance of many STL algorithms due to degredation to the input iterator category.

I think it is worth considering adopting the same solution as has been chosen in Boost.Iterator detail/int_iterator. This returns by value and claims to be a std random_access_iterator. This does potentially practically go wrong if an algorithm uses auto&. I think returning by const value_type would ensure that the lifetime extension works. I believe this only leaves theoretical cases where this would go wrong by classes squirelling away a reference. I don't think this is of practical significance since there are very few assumptions one can make about the lifetime of the reference without knowing about the underlying container/sequence.

It is probably worth looking at the experience users have had with int_iterator.

[Kohei Takahashi <flast@…>]

Is this dup of #2640 ?