Re: [boost] AlRangeExandrescu?

Subject: Re: [boost] AlRangeExandrescu?
From: Andrei Alexandrescu (andrei_at_[hidden])
Date: 2009-07-24 20:04:52

Thorsten Ottosen wrote:
> Andrei Alexandrescu skrev:
> 
>> 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).
> 
> Right. I think more general adjustments might also be useful in some cases.
> 
>> 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.
> 
> Right.
> 
>> 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.
> 
> I don't see why that is a problem; it seems like an inherent limitation
> of input iterators, not of the algorithm.
> 
>> 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.
> 
> Seems useful. But how does this work if you want to have the range
> 
>   [_b,_f)
> 
> as opposed to
> 
>   [_b,_f+1)
> 
> ?

That sounds like a function before() (or an overload of find() with 
enough syntactic frosting to be distinguished from other find() 
functions) that works for forward ranges. (It can't work on input 
ranges.) I think I'll add before() to D's standard library.

Andrei