Re: [boost] AlRangeExandrescu?

Subject: Re: [boost] AlRangeExandrescu?
From: Thorsten Ottosen (thorsten.ottosen_at_[hidden])
Date: 2009-07-24 08:35:29

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)

?

-Thorsten