Subject: Re: [boost] AlRangeExandrescu?
From: Andrei Alexandrescu (andrei_at_[hidden])
Date: 2009-07-27 09:20:24
David Abrahams wrote:
> on Fri Jul 24 2009, Andrei Alexandrescu <andrei-AT-metalanguage.com> wrote:
>
>>> Is popFront() mutable just for efficiency? Or is there something else
>>> I'm missing?
>> It's only efficiency. I was very attracted to popFront returning the
>> new range (100% functional interface!) but I gave up for efficiency
>> reasons. I didn't want iteration with ranges to be cool and iteration
>> with other means to be efficient.
>
> Could you describe the efficiency problem in more detail? I think it
> might be solvable.
Well a simple example is that a range in a contiguous array is a fat
pointer, e.g. (begin,end). To bump a range in-place you need to change
one pointer; returning a new range would have you copy two pointers. It
turns out that the difference is sensible for some loops.
In the general case, an unbounded amount of state would have to be
returned from r.next.
Now, here's what I think you might be thinking. The idiomatic use is r =
r.next(). Since there is reassignment, a possibility is to:
(a) have r.next() return a small proxy type Proxy that saves a reference
to the range
(b) have Range::operator=(Proxy) detect reassignment from itself and
only operate the minimum update.
(c) also define Range::Range(Proxy) for completeness.
After all has been said and done, the overhead is one word copied and
one more test. I hadn't thought of that.
Andrei