Boost logo

Boost :

Subject: Re: [boost] [mpl]iter_fold_if Forward Backward rationale?
From: Larry Evans (cppljevans_at_[hidden])
Date: 2009-06-03 14:59:54


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


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