RFC on range design for D2

[Sergey Gromov]

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.