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