RFC on range design for D2

Bill Baxter wbaxter at gmail.com
Wed Sep 10 19:01:58 PDT 2008


On Thu, Sep 11, 2008 at 10:35 AM, Steven Schveighoffer
<schveiguy at yahoo.com> wrote:
> "Bill Baxter" wrote
>> On Thu, Sep 11, 2008 at 9:32 AM, Bill Baxter <wbaxter at gmail.com> wrote:
>>> On Thu, Sep 11, 2008 at 8:17 AM, Steven Schveighoffer
>>>> 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);
>>>
>>> Why is all that necessary?  Can't you just do a  *center?
>>
>> Oh, I get it.  It's empty.  Duh.
>>
>> Ok, so you can have third cursor function in the std lib:
>>
>> T cursorValue(R,T)(R all, R center)
>> {
>>   return all.after(center).left;
>> }
>> ... plus the
>> cursorAdvance and cursorRetreat.
>
> That is all fine and dandy in the world of "I don't care how well my
> iterators perform or how much code bloat is added because of them," but I
> usually work in a different world ;)

Ok, but I have yet to hear an actual use case that demands blazing
fast iteration both forwards and backwards.  In your shuffling video
there's no way moving the iterator back and forth is going to be the
bottleneck.  In my undo/redo stack example it is also far from being
on the critical path.    I think it goes back to the fact that going
back and forth randomly isn't a property of many algorithms.  In all
the examples I can think of it's more a property of how humans
interact with data.  And humans are slow compared to how long it takes
to update a few extra values.

Certainly one-way iteration needs to be as fast as possible, for all
kinds of algorithms.  But does bidirection iteration really need to be
super-fast?

> But if I were forced not to use an iterator model (which isn't the case,
> iterators should be very possible without compiler help), I would actually
> implement this as a wrapper struct:
>
> struct Cursor(containerType)
> {
>   private Range!(containerType) _cur;
>   private containerType owner;
>
>   Cursor  moveLeft() {...}
>   Cursor moveRight() {...}
>   bool hasLeft() {...}
>   etc.
> }

That would work for me too.  Just put it in the standard lib so I
don't have to scratch my head wondering why such a basic thing is so
hard to do!  Of course once you do that, you have to wonder why this
one's interface isn't branded a range concept but the others are.  (I
know I know... it's not Stepanov "basic"), but if it's there and
people want to use it, I see no value in refusing to recognize it on
purist grounds.

> Thus one can implement iterators on top of ranges, but I'd argue that ranges
> are much easier to implement on top of iterators.

Ranges are safer and easier to work with in most cases so it's worth
it, or so the argument goes.  You don't buy it?
I think things like infinite generators make more sense as a range
because it's difficult to express succinctly as two iterators.  Or
perhaps you don't mean to imply that every range would have a begin()
and an end() iterator you could access?

> In any case, I think there are benefits to having a range type that is not
> necessarily defined as two iterators.

But how to do it without a large increase in the number of fundamental
concepts you have to keep track of -- that's the issue.

--bb


More information about the Digitalmars-d-announce mailing list