RFC on range design for D2

Steven Schveighoffer schveiguy at yahoo.com
Wed Sep 10 11:44:37 PDT 2008


"Andrei Alexandrescu" wrote
> 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.

Not sure.  I'd have to see how messy the 'use range primitives' looks :)

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

Perhaps not, I haven't used the ranges as you have implemented them, nor 
have I used them from boost.  I agree with the general idea that ranges are 
safer and simpler to use when a range is needed.  It makes perfect sense to 
pass a single range type rather than 2 iterators, and this is the majority 
of usages for iterators anyways.  I 100% agree that ranges are the way to go 
instead of passing begin() and end() all the time to algorithm templates.

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

Yes, so every time you add an element you have to update your forward range 
from the 'all' range so it includes the new element at the end.  Every time 
you remove an element, you have to update your reverse range from the 'all' 
range so it excludes the element at the beginning.  Failure to do this 
results in invalid ranges, which seems to me like a lot more work than 
simply not doing anything  (in the case of an iterator).  The pitfalls of 
using ranges for dynamically changing containers might outweigh the 
advantages that they provide in certain cases.

>> 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 don't need to worry about whether you have them or not, I can always 
implement them on my own ;)  Really, range/iterator support doesn't require 
direct support from the compiler (except for builtin arrays), and any 
improvements made to the compiler to support ranges (such as reference 
returns, etc) can be applied to iterators as well.

I think ranges are an excellent representation when a range of elements is 
needed.  I think a cursor or iterator is an excellent representation when an 
individual position is needed.

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

Functions which take or return a single position.  Such as 'erase the 
element at this position' or 'find the position of element x'.

-Steve 




More information about the Digitalmars-d-announce mailing list