Re: [Boost-Users] Re: MPL and apply_if trouble

From: Tarjei Knapstad (tarjeik_at_[hidden])
Date: 2003-05-20 06:38:07

On Mon, 2003-05-19 at 21:34, David Abrahams wrote:
> Tarjei Knapstad <tarjeik_at_[hidden]> 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;
> >
> > --------------------- end code -----------------------
> >
> > When attempting to create the RevList type however, gcc spits the
> > following at me:
> >
> > reverse.cpp: In instantiation of
> > `boost::mpl::pop_front<boost::mpl::vector0<boost::mpl::void_> >':
> > reverse.cpp:15:   instantiated from
> > `Reverse<boost::mpl::vector0<boost::mpl::void_> >'
> > reverse.cpp:21:   instantiated from `Reverse<boost::mpl::vector1<long
> > int> >'
> > reverse.cpp:21:   instantiated from `Reverse<boost::mpl::vector2<int,
> > long int> >'
> > reverse.cpp:21:   instantiated from `Reverse<List>'
> > reverse.cpp:25:   instantiated from here
> 
> > reverse.cpp:15: base class `
> >    boost::mpl::pop_front_traits<boost::mpl::aux::vector_tag<0> 
> >    >::algorithm<boost::mpl::vector0<boost::mpl::void_> >' has incomplete
> > type
> 
> That line above means that you tried to pop the front element off an
> empty vector, 
Yes, I noticed that but...

>and it's easy to see that pop_front<List>::type is
> evaluated whether List is empty or not.
>
...is it? I thought apply_if<> only instantiated either the 'true' or
'false' statement depending on the condition. When the recursion gets
down to where the Rest type is a list with only one element, this is
what I thought should happen:

1. 'FrontElem' becomes the one reamining type in the list.

2. 'Rest' becomes an empty list after pop_front<> has been applied to   
List which has one element.

3. The condition empty<Rest> in the apply_if evaluates to true, thus
Type is now vector<FrontElem> instead of instantiating another Reverse
class with the empty list which would of course wreak havoc. Types are
then recursively pushed onto this vector.

At least that was the thought behind all this, i.e. because of the
apply_if, Reverse should never be instantiated with an empty list.

> 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 ;) )

>      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,
--
Tarjei