On 8/29/2014 1:21 AM, Neil Groves wrote:
On 29 August 2014 04:04, Eric Niebler wrote:
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.
Are people passing counting_iterators to std::distance? Yes, it's a problem, but taking too long to get the right answer doesn't seem as bad as the random garbage the current behavior is giving.
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.
Yes. IMO, Boost.Algorithm should have versions of ALL the standard library algorithm, rewritten to work with the new-style iterator categories. And yes, it's a lot of work, but not as much as you might think. I should know, I'm just about finished my own complete reimplementation of the algorithms for my range work.
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.
Not a big problem in practice, IMO.
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.
You prefer undefined behavior to a perf bug? Undefined behavior is exploitable. It's a security issue.
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.
Great! Then only the algorithms need to be reimplemented. ;-) And actually, only those that require anything more than input iterators. That should cut the work load in half, or better.