On 05/29/09 16:02, Steven Watanabe wrote:
David Abrahams wrote:
on Tue May 19 2009, Larry Evans <cppljevans-AT-suddenlink.net> wrote:
Alas. AFAICT, there are no tests or uses for the Backward Predicate in MPL.
However, there may be a use in the future.
That's really no excuse ;-)
I think this is probably a case of premature generalization.
Anything that can be done with the backward predicate can be done by passing an appropriate boolean flag along with the result. Unlike the forward predicate, there are no big-O gains from having the algorithm know about it.
Why not? It seems there should be. After all, if the backward predicate is satisfied by the last element in the sequence, wouldn't that avoid going back up the recursion stack? Let's see, for a sequence, Seq, where size<Seq>::value == n, then you'd take linear time going down (with forward predicate == always<true_>) and then linear time going up *unless* the backward predicate was satisfied early. So, wouldn't the complexity for something like reverse_find be n (going down)+n/2(on the average,going up)? -Larry