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.
>> 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
> 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
> as opposed to
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk