RFC on range design for D2

[Bill Baxter]

On Thu, Sep 11, 2008 at 8:17 AM, Steven Schveighoffer
<schveiguy at yahoo.com> wrote:
> "Sergey Gromov" wrote
>> 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.
>
> This is exactly the pattern I use.  I agree that your example would solve
> the problem, I hadn't thought of an empty range to be a cursor, that is
> clever!
>
> The only missing piece to your solution is that I must construct the range
> after the center range in order to access the value to see where I need to
> go.
>
> What I see as the biggest downside is the cumbersome and verbose code of
> moving the 'iterator' around, as every time I want to move forward, I
> construct a new range, and every time I want to move backwards I construct a
> new range (and construct a new 'center' afterwards).  So a 'move back one'
> looks like:
>
> auto before = all.before(center);
> if(!before.isEmpty)
>  center = before.pop.end;
>
> And to move forward it's:
> auto after = all.after(center);
> if(!after.isEmpty)
>  center = after.next.begin;
>
> To get the value there, I have to do:
> all.after(center).left // or whatever gets decided as the 'get first value
> of range' member
>
> or if opStar is used:
>
> *all.after(center);
>
> I much prefer:
>
> forward:
> if(center != list.end)
>    ++center;
>
> reverse:
> if(center != list.begin)
>   --center;
>
> get value:
> *center;
>
> Especially without all the extra overhead
>
> I see both methods as being just as open to mistakes, the first more-so, and
> more difficult to comprehend (at least for me).
>

Well put.  I was trying to come up with a comparison like this last
night.  But at 3am I was just too tired to pull it off.  Great example
of the kind of cognitive overload that comes from this kind of
scenario.

I really believe the point that ranges are good for std.algorithm is
fine.  But when people use iterators in code they are often used like
the above.  This whole shifting back and forth over a linked list was
seeming very familiar to me last night and I recalled this morning
that I had written some code to implement undo which worked in this
very way.  The linked list was the undo stack.  And undo() moved the
current iterator one direction, redo() moved it the other.

So far though we don't seem to be able to come up with a good example
other of where ranges are weak than traversing a list back and forth.
 Note that "move back and forth according to some user input" is not
clearly not an "algorithm" that would be in std.algorithm.  But it
does come up often enough in applications.  I don't think the fact
that it's not strictly an Algorithm-with-a-captial-A makes it any less
important.

But it is a little fishy that we can't come up with any other example
besides sliding a bead on a wire back and forth.

--bb