RFC on range design for D2

[Andrei Alexandrescu]

Steven Schveighoffer wrote:
> "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.

Of course it does. You just remember the leftmost point in time you need 
to remember. Then you use range primitives to get to where you want. 
Maybe a better abstraction for all that is a sliding window though.

> 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.

You don't need a meta range, though it's a good idea to have it as a 
convenience structure. All you need is store the two ranges and do range 
operations on them.

Notice that "a range can't grow" is different from "a range can't be 
assigned from a larger range". In particular, a range operation can 
return a range larger than both input ranges. But not larger than their 
union :o).

> 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.

If we agree it's better without iterators if not needed, we'd need a 
strong case to add them. Right now I have a strong case against 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.

Which functions?


Andrei