Re: [Boost-users] [Range] Strange!

Subject: Re: [Boost-users] [Range] Strange!
From: Eric Niebler (eniebler_at_[hidden])
Date: 2014-08-29 12:16:55

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.