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

Subject: Re: [Boost-users] [Range] Strange!
From: Neil Groves (neil_at_[hidden])
Date: 2014-08-29 04:21:09

On 29 August 2014 04:04, Eric Niebler <eniebler_at_[hidden]> wrote:

> On 8/28/2014 3:49 PM, Neil Groves wrote:
> > 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
> 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