Boost logo

Boost :

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


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