Shout out to D at cppcon, when talkign about ranges.

[H. S. Teoh via Digitalmars-d]

On Thu, Oct 08, 2015 at 02:46:05PM +0000, John Colvin via Digitalmars-d wrote:
> On Thursday, 8 October 2015 at 14:36:03 UTC, Kagamin wrote:
> >On Thursday, 8 October 2015 at 13:10:24 UTC, John Colvin wrote:
> >>What you're effectively describing is a trio of iterators wrapped to
> >>give an interface of two linked ranges. popFront grows the first one
> >>and shrinks the second. I'd be interested to see how to construct
> >>that, given a generic range as input.
> >
> >The C++ example doesn't work with generic iterators, it needs a
> >specific ability to iterate in both directions, hence a bidirectional
> >range.
> 
> Of course.
> 
> >The way ranges are used for iteration, they can be seen as adapters
> >for iterators providing various consistent interfaces depending on
> >their capabilities. In this example we need a bidirectional range
> >that can go back and forth, one way to do it is to provide undo
> >mechanism like undoPopFront and frontUndoEmpty to allow the range
> >grow back, thus remaining a range that is a list of items and not an
> >iterator.
> 
> I much prefer this second version:
> 
> >Another way is to provide a reverse range of previously popped items
> >- this can be seen as iterator or not, more like a range with history
> >rather than an undoable input range, so maybe the getter should be
> >`history`.
> 
> my question is: How, in practice, does one take a bidirectional range
> and make one of these new things? I foresee some difficulty, but
> perhaps I'm just not being imaginative enough.

Bidirectional ranges do have a fundamental lack in their definition, in
that the bidirectionality is weaker than the C++ form of
bidirectionality.

For example, suppose you're given some bidirectional range r, with
swappable elements. Clearly, reverse(r) is easily implementable (just
swap .front and .back, then popFront() and popBack() until the range is
empty).

However, suppose you want to reverse the last n elements of r. How would
you do it? Conceptually speaking, if the range is bidirectional, then
its last segment of n elements ought to be bidirectional too, right?
However, there is currently no (easy) way to get a bidirectional
subrange out of r, using the current range primitives.

One brute force way to do it, is to iterate a .save'd copy of r (since
bidirectionality implies forward range) from the front, until there are
only n elements left, then perform the reverse() operation. However,
this is horribly inefficient if n is relatively small w.r.t. the total
number of elements in r. It gets worse if r does not have .length, so
you may have to iterate over *two* .save'd copies of r so that you know
the subrange you end up with has exactly n elements (since you can't
tell how many elements are in the subrange until you reach the end).

Ideally, though, we'd like to be able to iterate from the end of r, so
that we only incur the cost of calling .popBack n times. However, no
amount of trickery with the current bidirectional range API is going to
get you this subrange by iterating from the back. The problem is that
once you call .popBack n times, there's no way to turn .back into the
new .front of the subrange. You can't unpop .back once you've called
popBack(), so you can't implement .front on the subrange.  Whereas with
iterators, you *could* just do iter-- n times, then use iter with the
original .end() to form the n element subrange.

So D's bidirectional ranges are inherently weaker than a pair of C++
bidirectional iterators, because D's bidirectional ranges are, under the
hood, a pair of *uni-directional* iterators in opposite directions. Once
you advance either iterator, you can't go back anymore without resorting
to ugly inefficient hacks (e.g., allocate a stack of .save'd positions),
whereas in C++ both ends are bidirectional, and can go forward/back at
anytime.

If we were to add an .unpop primitive to bidirectional ranges, though,
then we could solve this problem. However, I'm not sure how this fits in
with the overall concept of ranges.


T

-- 
Век живи - век учись. А дураком помрёшь.