Re: [boost] AlRangeExandrescu?

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