On 06/05/09 11:05, Larry Evans wrote:
On 06/05/09 10:00, David Abrahams wrote:
on Wed Jun 03 2009, Larry Evans <cppljevans-AT-suddenlink.net> wrote:
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?
How can you possibly "avoid going back up the recursion stack?"
By making the stack explicit and using 2 while loops. The first while loop goes down the recursion stack, while storing the values in an mpl::list, the 2nd while then goes up the stack but terminates when the BackPred is reached. Shouldn't that work? It does work for the tests shown in the code.
[snip]
That's like asking the recursive metafunction invocations not to "return." I suppose we could cause a compiler error, but I doubt that's what you had in mind!
Actually, the 2 BOOST_PP_REPEAT invocations in iter_fold_if_impl do essentially the same as 2 while loops mentioned above. The 1st BOOST_PP_REPEAT invocation creates the "explicit" stack and the 2nd BOOST_PP_REPEAT goes down this explicit stack (or up the "implicit" recursion stack), while invoking BackwardOp. Well, that's not entirely true. The explicit stack is created by recursive calls of iter_fold_if_impl *and* the 1st BOOST_PP_REPEAT call. If the I-th recursive call of iter_fold_if_impl is denoted by: iter_fold_if_impl@[I] and the typedef target (e.g. forward_step4) produced by the J-th call of the 1st BOOST_PP_REPEAT is denoted by: forward_step#[J] then the explicit stack can be denoted by: iter_fold_if_impl@[0]::forward_step#[0] iter_fold_if_impl@[0]::forward_step#[1] iter_fold_if_impl@[0]::forward_step#[2] . . . iter_fold_if_impl@[0]::forward_step#[M] iter_fold_if_impl@[1]::forward_step#[0] iter_fold_if_impl@[1]::forward_step#[1] iter_fold_if_impl@[1]::forward_step#[2] . . . iter_fold_if_impl@[1]::forward_step#[M] ... iter_fold_if_impl@[N]::forward_step#[0] iter_fold_if_impl@[N]::forward_step#[1] iter_fold_if_impl@[N]::forward_step#[2] . . . iter_fold_if_impl@[N]::forward_step#[M+1] where: horizontal indentation is a visual que (in addition to the @[.] notation ) to the recursion depth. M+1 == BOOST_MPL_LIMIT_UNROLLING. N is the number of recursive calls to iter_fold_if_impl. As mentioned, the 2nd BOOST_PP_REPEAT goes up the recursion stack. Instead of creating forward_stepJ typedefs, it creates backward_stepJ typedefs. These will be denoted: backward_step#[J]<Iterator,State> where: Iterator and State are some previous typedef targets. The reason for the <,> suffix is to indicate the dependency on previous typedefs. The actual dependency is, roughly, on the stack's forwardstep's iterator and the immediately previous backstep's state. Thus, going up the recursion stack results in typedefs denoted by: iter_fold_if_impl@[N]::backward_step#[M] < iter_fold_if_impl@[N]::forward_step#[M]::iterator , iter_fold_if_impl@[N]::forward_step#[M]::state > . . . iter_fold_if_impl@[N]::backward_step#[2] < iter_fold_if_impl@[N]::forward_step#[2]::iterator , iter_fold_if_impl@[N]::backward_step#[3]::state > iter_fold_if_impl@[N]::backward_step#[1] < iter_fold_if_impl@[N]::forward_step#[1]::iterator , iter_fold_if_impl@[N]::backward_step#[2]::state > iter_fold_if_impl@[N]::backward_step#[0] < iter_fold_if_impl@[N]::forward_step#[0]::iterator , iter_fold_if_impl@[N]::backward_step#[1]::state > ... iter_fold_if_impl@[1]::backward_step#[M] < iter_fold_if_impl@[1]::forward_step#[M]::iterator , iter_fold_if_impl@[2]::backward_step#[0]::state > . . . iter_fold_if_impl@[1]::backward_step#[2] < iter_fold_if_impl@[1]::forward_step#[2]::iterator , iter_fold_if_impl@[1]::backward_step#[3]::state > iter_fold_if_impl@[1]::backward_step#[1] < iter_fold_if_impl@[1]::forward_step#[1]::iterator , iter_fold_if_impl@[1]::backward_step#[2]::state > iter_fold_if_impl@[1]::backward_step#[0] < iter_fold_if_impl@[1]::forward_step#[0]::iterator , iter_fold_if_impl@[1]::backward_step#[1]::state > iter_fold_if_impl@[0]::backward_step#[M] < iter_fold_if_impl@[0]::forward_step#[M]::iterator , iter_fold_if_impl@[1]::backward_step#[0]::state > . . . iter_fold_if_impl@[0]::backward_step#[2] < iter_fold_if_impl@[0]::forward_step#[2]::iterator , iter_fold_if_impl@[0]::backward_step#[3]::state > iter_fold_if_impl@[0]::backward_step#[1] < iter_fold_if_impl@[0]::forward_step#[1]::iterator , iter_fold_if_impl@[0]::backward_step#[2]::state > iter_fold_if_impl@[0]::backward_step#[0] < iter_fold_if_impl@[0]::forward_step#[0]::iterator , iter_fold_if_impl@[0]::backward_step#[1]::state > One bad consequence of using BOOST_PP_REPEAT this way is that the iterator argument to the topmost backward_step: iter_fold_if_impl@[N]::backward_step#[M] < iter_fold_if_impl@[N]::forward_step#[M]::iterator , iter_fold_if_impl@[N]::forward_step#[M]::state > may be the the end iterator, mpl::end<Sequence>::type, where Sequence is the 1st argument to iter_fold_if. The solution proposed here: https://svn.boost.org/trac/boost/attachment/ticket/3044/iter_fold_if.patch is to simply replace the BackwardPred with a test on whether the iterator is the end iterator. Of course this lessens the ease of use because now the user, if he desires something like reverse_find, will have to modify BackwardOp to incorporate some sort of BackwardPred and to do nothing if this BackwardPred is false. This solution was proposed here: http://article.gmane.org/gmane.comp.lib.boost.devel/189764 A second bad consequence of using BOOST_PP_REPEAT is that no "short-circuiting" (i.e. BackwardPred returns false part-way up the recursion stack) is possible. This is because each backward_step#[J]'s depends on either backward_step#[J+1] in the current recursive call or the backward_step#[0] in the previous recursive call to iter_fold_if_impl. Thus all the bacward_step#[J]'s instantiated even if they're no-ops. In contrast, the 2 while loop solution, implemented using the while_recur template here: https://svn.boost.org/trac/boost/attachment/ticket/3044/while_recur.cpp suffers neither of these bad consequences because the explicit recursion stack is implemented with a mpl::list. While creating the explicit stack, the end iterator is not pushed onto the explicit stack because template metaprogramming (in contrast to preprocessor metaprogramming) can detect the end iterator. Going up the recursion stack can be short-circuited because, again, template metaprogramming can detect when an element in the explicit stack fails the BackwardPred and can exit the while_recur loop early. The only advantage that the 2 BOOST_PP_REPEAT loop solution has over the 2 while_recur solution is that it may create fewer template instantions, especially when BackwardPred is always<true_>. That's because with such a BacwardPred, no short-ciruiting is possible and the mpl::list used to implement the explicit stack has some instantiation overhead. However, that's only a guess. To really tell, some tests with Steven's template profiler are needed. -regards, Larry