RFC on range design for D2

[Andrei Alexandrescu]

Sergey Gromov wrote:
> Steven Schveighoffer <schveiguy at yahoo.com> wrote:
>> "Andrei Alexandrescu" wrote
>>> Steven Schveighoffer wrote:
>>>> "Andrei Alexandrescu" wrote
>>>>> 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.
>>> No, this is incorrect. I don't "have to" at all. I could define the
>>> behavior of range as you mention, or I could render them undefined.
>>> Iterators invalidate anyway at the drop of a hat, so they're none the
>>> wiser. You can't transform a lack of an advantage into a disadvantage.
>> A range or iterator that becomes undefined when adding an element to a 
>> linked list or removing an element from a linked list (provided you don't 
>> remove the element in question) makes it useless for this type of purpose. 
>> What I want is a cursor that saves the position of an element, not the end 
>> and beginning.
>>
>> Here is what I'm assuming a range consists of, and granted this is an 
>> assumption since I didn't look at any of your implementation, and a list 
>> object which uses ranges doesn't even exist AFAIK.  Assume that integers 
>> below are individual elements
>>
>> all: 0 1 2 3 4 5 6 7 8 9 E
>> reverse range: 0 1 2 3 4
>> forward range: 5 6 7 8 9 E
>>
>> Now I remove an element from the front:
>>
>> all: 1 2 3 4 5 6 7 8 9 E
>> reverse range: ? 1 2 3 4
>> forward range: 5 6 7 8 9 E
>>
>> I've now lost my reverse iterator because it's no longer valid, but I can 
>> reconstruct it by diffing the forward iterator and list.all.
>>
>> If I add to the end I got a similar situation, I can reconstruct my forward 
>> iterator by diffing list.all and the reverse iterator.
> 
> You don't mention here which iterator usage pattern you are trying to 
> model with ranges.  I can think of at least two.
> 
> 1.  You use a single bidirectional 'center' iterator, center == 5.  As 
> one would naturally do with iterators.  Note then that whenever you use 
> your center for, say, backward iteration, you reconstruct the actual 
> range by calling list.begin.  You do it on each iteration.  No wonder it 
> stays valid even if you remove the first element in the meantime: you're 
> constructing your range from scratch anyway.  If you want to model this 
> pattern with ranges---no problem, keep an empty 'center' range, center 
> == (5,5), and reconstruct backward iteration range,
> 
> reverse = all.before(center);
> 
> whenever you need to iterate, then
> 
> center = reverse.end;
> 
> This 'center' range, being slightly less efficient, stays valid and 
> becomes invalid in exactly the same conditions as your classical 
> iterator.
> 
> 2.  You use 3 iterators, one for the list start, one for the center, and 
> one for the end.  In this case the 'start' iterator becomes invalid 
> after removing the first element exactly like 'reverse' range becomes 
> invalid in your example, with exactly the same consequences.

I'm acquiring the nagging feeling that Sergey understands ranges better 
than I do. I could understand how to address Steven's point only after 
reading the post above. Thanks, Sergey.

Andrei