Boost logo

Boost :

Subject: Re: [boost] AlRangeExandrescu?
From: Andrei Alexandrescu (andrei_at_[hidden])
Date: 2009-07-23 11:38:41


Thorsten Ottosen wrote:
> David Abrahams skrev:
>> Hi Neil,
>>
>> I'm sure someone already spoke to you about this, but just in case:
>> Andrei Alexandrescu gave a very interesting presentation at BoostCon
>> that was based on a "ranges only" approach that should eliminate
>> issues like this one:
>>
>> 2: return type specification for find() etc
>> ===========================================
>> There where no major objection to the mechanism, but some found
>> the syntax ugly. I believe the suggested syntax (e.g.)
>>
>> boost::find[_f,_e]( range, x )
>>
>> boost::find[_f+1,_e]( range, x )
>>
>>
>> He says he's implemented a superset of the STL algorithms with it so
>> we know the expressive power is fairly complete.
>
> If I remember correctly, he claims that his return of find() is the
> "correct" one. I think that is plain wrong, as the syntax above shows
> that there are many useful return ranges, perhaps with an obvious
default.

(Thanks Dave for pointing out this thread to me.)

I can think of four useful subranges you might want to look at when
searching linearly: the range before the found element (including it or
not) and the one after the found element (including it or not).

If find() is to work on most ranges, it needs to return the range
starting with the found element. Then it's easy to derive the range
after the found element by simply popping one element off the range.

There remains the case when the range preceding the found element is
needed. Requiring find to be able to do that reduces the generality of
find(), so the principled approach is to confine that task to a
different function. Without having looked at RangeEx, I infer from the
code above that for example find[_b, _f] would only work on forward
iterators and better, whereas find[_f, _e] would also work on input
iterators.

During my talk at Boost this same issue was brought again, so after
thinking some more about it I found what I think is the principled
solution: define a different function that returns the range before the
found element. That function is called until().

Surprisingly, until() also works on input ranges! It works because it
finds the element lazily - it returns a range that tests for termination
condition in its .empty() test. So until() returns a range that iterates
the original passed-in range until the sought element is found, at which
time until() reports termination.

So one design is to define find[_b, _f] that works with forward ranges
and find[_f, _e] that works with input ranges. With the design proposed
above we have until that works with input ranges and find that works
with input ranges. That is a net expressiveness win, and the cost is the
necessity of defining a new type of range (the one returned by until).

Again, I haven't looked at find[] and RangeEx so please apologize if I
mis-inferred how it works.

Andrei


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk