Tarjei Knapstad <tarjeik@chemcon.no> writes:
On Mon, 2003-05-19 at 21:34, David Abrahams wrote:
Tarjei Knapstad <tarjeik@chemcon.no> 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 <boost/mpl/front.hpp> #include <boost/mpl/push_back.hpp> #include <boost/mpl/pop_front.hpp> #include <boost/mpl/apply_if.hpp> #include <boost/mpl/empty.hpp> #include <boost/mpl/size.hpp> #include <boost/mpl/vector.hpp>
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<typename Reverse<Rest>::Type, FrontElem>::type >::type Type; };
typedef vector<int,int,long> 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<T1, T2, ... TN>::type == vector<T1, T2, ... TN> 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 <class Seq, class E> struct append_reversed : push_back<typename Reverse<Seq>::type, E> { }; ... typedef typename apply_if< empty<Rest> , vector<FrontElem> , append_reversed<Rest,FrontElem> >::type Type; or, apply a lambda expression explicitly: typedef typename apply_if< empty<Rest> , vector<FrontElem> , apply< lambda<push_back<Reverse<_1>, 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