On 29 August 2014 04:04, Eric Niebler
On 28 August 2014 22:35, Krzysztof Czainski wrote: I see no conflated requirements. In Boost.Iterators (as opposed to the standard iterator categories), iterator *traversal* deals only with
On 8/28/2014 3:49 PM, Neil Groves wrote: traversal (++, --, +=, -=, etc) and says nothing about the return type of the dereference operation.
I perhaps used poor language. I believe that we are actually in complete agreement. The Boost.Iterator Traversal Concepts are perfect and do not have any problem. I was attempting to suggest that we could make improvements for code that uses this idiom. My concern was for interoperability with the standard algorithms (and therefore the Boost.Range algorithms). The conflation of return type and traversal in the standard definition for iterators is an issue we are clearly both aware of.
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 see where you are coming from, I might even agree, but the impact upon standard algorithms would be horrific. I don't find O(N) for std::distance of a counting iterator upon integers to be acceptable. Clearly I can make the Boost.Range boost::distance O(1) by altering the implementation to not forward to the standard implementation. This would be required for almost all of the standard algorithms, hence I'd have to rewrite them all. Even with this effort the result would be sub-optimal since there are many internal details within standard algorithm implementations to optimise for various standard containers e.g. __niter.
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. :-(
I agree that it is a bug. The defect is simple, but the best solution isn't. Your suggestion is valid, but it falls short of being an acceptable solution. I was hoping to find a cunning way to keep the counting_iterator random access while solving the lifetime issue. I've not spent enough effort to convince myself that this is not possible yet.
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.
Boost.Range uses the Boost.Iterator traversal idioms extensively. The Boost.Range Concepts are defined to avoid the reference type conflation with traversal for example. Sadly, this doesn't help when the result is fed into a Boost.Range algorithm that forwards to a standard algorithm. The state of play is that Boost.Range prefers the Boost.Iterator idioms but does not reimplement the standard parts and hence falls foul of the standard issues.
Making all of Boost.Range aware of the new-style iterators would be a piece of work, though.
I believe that most of Boost.Range (aside from the standard algorithms) does fully support the Boost.Iterator idioms. I'm completely willing to invest the time to modify any issue in Boost.Range related to this. At the moment I don't see a good solution for the standard algorithms. I am definitely open to suggestions. At the moment I am keen to at least reimplement boost::distance, but this does seem hopelessly incomplete.
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.
I'll wait for your response before raising the ticket.
Eric
Regards, Neil Groves