Re: MPL and apply_if trouble

Tarjei Knapstad writes:

On Mon, 2003-05-19 at 21:34, David Abrahams wrote:

...

Tarjei Knapstad writes:

...

I encountered the following problem today which I've reduced down to a simple example. Basically what I want to do is recurse through a typelist (mpl::vector) popping an element each time and end recursion by using apply_if with mpl::empty<List> as the condition. I've made a simple Reverse class template to illustrate the problem. (The Reverse class is of course intended to reverse the contents of a typelist....)

--------------------- begin code ---------------------

#include #include #include #include #include #include #include

using namespace boost::mpl;

template <typename List> struct Reverse { typedef typename front<List>::type FrontElem; typedef typename pop_front<List>::type Rest; typedef typename apply_if< empty<Rest>, vector<FrontElem>, typename push_back::type >::type Type; };

typedef vector List; typedef Reverse<List>::Type RevList;

<snip>

...

and it's easy to see that pop_front<List>::type is evaluated whether List is empty or not.

...is it?

Sure! What happens when you try to Reverse an empty sequence?

I thought apply_if<> only instantiated either the 'true' or 'false' statement depending on the condition.

Yes, but it doesn't inhibit evaluation *lexically*. Whenever you write ::type, you get a non-lazy evaluation. In fact, your apply_if is not delaying anything, since you greedily evaluate the 2nd argument, and the first argument is already the right type. You'd get the first argument correctly because vector::type == vector And for the same reasons, the 2nd argument to apply_if has the right type but is evaluated early. Even if you stripped the outer typename...::type and wrote: typedef typename apply_if< empty<Rest> , vector<FrontElem> , push_back< typename Reverse<Rest>::Type , FrontElem > >::type Type; you'd still be in trouble because Reverse is being evaluated greedily. The code above translates to something like (runtime): return ( // select a function object Rest.empty() ? boost::bind(identity, seq<type>(1, FrontElem)) : boost::bind(push_back, reverse(Rest), FrontElem) ) (); // now invoke it If you really want to do it that way, break the thing you want to delay out into a separate metafunction: template struct append_reversed : push_back { }; ... typedef typename apply_if< empty<Rest> , vector<FrontElem> , append_reversed >::type Type; or, apply a lambda expression explicitly: typedef typename apply_if< empty<Rest> , vector<FrontElem> , apply< lambda, FrontElem> > , Rest > >::type Type;

...

Some things to note:

1. If your algorithm is doing repeated pop_fronts, you probably want a list: since each successive list is a sublist of the previous one, the new list doesn't cost any instantiations

2. Barring that, use an iterator_range to avoid instantiating a new vector at each iteration

Thanks, will keep in mind. In fact it looks like I can more or less adopt my STL mindset to the MPL which I guess is half the point :) (barring the pop_back stuff ;) )

Oh, and please, do yourself a favor and follow the MPL metafunction protocol! That means your result is called "::type", not "::Type".

...

3. The easy way to do this is

mpl::fold< List , mpl::push_front<> , typename mpl::clear<List>::type>::type >

I believe.

Thanks a lot, this works great! (except that the push_front and clear arguments need to be switched around)

Thanks once again for your help Dave,

Sure thing. -- Dave Abrahams Boost Consulting www.boost-consulting.com