RFC on range design for D2

[Steven Schveighoffer]

"Andrei Alexandrescu" wrote
> Bill Baxter wrote:
>> But upon further reflection I think it may be that it's just not what
>> I would call a bidirectional range.  By that I mean it's not good at
>> solving the problems that a bidirectional iterator in C++ is good for.
>
> It's good. I proved that constructively for std.algorithm, which of course 
> doesn't stand. But I've also proved it theoretically informally to myself. 
> Please imagine an algorithm that bidir iterators do and bidir ranges 
> don't.

Any iterative algorithm where the search might go up or down might be a 
candidate.  Although I think you have a hard time showing one that needs 
strictly bidirectional iterators and not random access iterators.  Perhaps a 
stream represented as a linked list?  Imagine a video stream coming in, 
where the player buffers 10 seconds of data for decoding, and keeps 10 
seconds of data buffered behind the current spot.  If the user pauses the 
video, then wants to play backwards for 5 seconds, what kind of structure 
would you use to represent the 'current point in time'?  A bidir range 
doesn't cut it, because it can only move one direction at a time.  You would 
need 2 bidir ranges, but since you can't 'grow' the ranges, you can't add 
stuff as it is consumed from the forward range to the backwards range, or am 
I wrong about that?  So how do you continually update your backwards 
iterator?  I suppose you could simply 'generate' the backwards iterator when 
needed by diff'ing with the all range, but it seems unnecessarily 
cumbersome.  In fact, you'd need to regenerate both ranges as data is 
removed from the front and added to the back (because the ends are 
continually changing).  Perhaps a meta-range which has 2 bidir ranges in it 
can be provided.  It would be simple enough to implement using existing 
ranges, but might have unnecessary performance issues.

My belief is that ranges should be the form of input to algorithms, but 
iterators should be provided for using containers as general data 
structures.  Similar to how strings are represented by arrays/slices, but 
iterators (pointers) exist if you need them.

I'll probably move forward with this model in dcollections, I really like 
the range idea, and in general the view on how ranges are akin to slices. 
But I also like having access to iterators for other functions.

-Steve