Re: [Boost-users] [mpl] Implementing eraseVal

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2007-03-29 03:28:00

Scott Meyers ha escrito:

> Since set seems to be broken, I find myself wanting to implement this
> metafunction.  It need work only for vectors:
>
> // erase all occurrences of T in Seq
> template<typename Seq, typename T> struct eraseVal;
>
> After several hours and tens or hundreds of thousands of lines of error messages
> from three compilers, I am unable to get it working.
>
> My attempt to do it the "right" way looks like this, and I must warn you in
> advance that it's not pretty, unless you like an approach that calls find three
> times with the same arguments:
>
> template<typename Seq, typename T>
> struct eraseVal
>    : mpl::eval_if<
>        boost::is_same<typename mpl::find<Seq, T>::type,
>                       typename mpl::end<Seq>::type>,
>        typename mpl::identity<Seq>::type,
>        eraseVal<typename mpl::erase<Seq,
>                   typename mpl::find<Seq,T>::type,
>                   typename mpl::next<typename mpl::find<Seq,T>::type>::type
>                   >::type,
>                 T>
>      >
> {};
>
> My more procedural attempt looks better (to me), but it still doesn't compile:
>
> template<typename Seq, typename T>
> struct eraseVal {
>    typedef typename mpl::find<Seq,T>::type iter;
>    typedef typename mpl::eval_if<
>      boost::is_same<iter,
>                     typename mpl::end<Seq>::type>,
>      typename mpl::identity<Seq>::type,
>      typename eraseVal<typename mpl::erase<Seq,
>                                            iter,
>                                            mpl::next<iter>::type
>                                           >::type,
>                        T>::type
>      > type;
> };
>
> God I miss iteration.  And I really wish emacs would match angle brackets in C++
> mode, sigh.
>
> Can somebody please help me out?

Hello Scott, I see several problems with your procedural approach: the first one
is the ::type added to mpl::identity<Seq> and eraseVal<...> in the expression

    typedef typename mpl::eval_if<
      boost::is_same<...>,
      typename mpl::identity<Seq>::type,
      typename eraseVal<...>::type
    > type;

Since eval_if is designed precisely to defer invocation of its argument
metafunctions the correct  mode of use is

    typedef typename mpl::eval_if<
      boost::is_same<...>,
      typename mpl::identity<Seq>,
      typename eraseVal<...>
    > type;

so that infinite recursion on eraseVal is avoided. But even after dropping those
::type's you still get errors like this:

[...]/boost/mpl/next_prior.hpp: In instantiation of `boost::mpl::next<mpl_::void_>':

[...]
[...]/boost/mpl/next_prior.hpp:31: no type named `next' in `struct mpl_::void_'

The problem now is that, although the eraseVal<...> expression is only invoked
(i.e. its nested ::type calculated) when strictly necessary --this is what eval_if
is
used for--, its first argument is computed *always*, regardless of what branch
of the eval_if<...> expr is finally selected:

  typename eraseVal<
    typename mpl::erase<Seq,iter,mpl::next<iter>::type>,
    T>

See the mpl::erase<...> thing? When no more T's are left in the sequence,
iter points to the end of Seq, and mpl::next<iter>::type is an *invalid*
expression (Incidentally, a ::type is missing for mpl::erase<...>, but this is not
the
root of the problem here.)

So, what we need if to add a layer of indirection so as to not invoke the
arguments to the recursive call to eraseVal except when strictly necessary,
like for instance as follows:

  template<typename Seq,typename T>
  struct eraseVal
  {
     template<typename Iter>
     struct eraseValRecurse:
       eraseVal<typename mpl::erase<Seq,Iter>::type,T>
     {};

     typedef typename mpl::find<Seq,T>::type iter;

     typedef typename mpl::eval_if<
       boost::is_same<iter,typename mpl::end<Seq>::type>,
       mpl::identity<Seq>,
       eraseValRecurse<iter>
     >::type type;
  };

This works, but it is quite inefficient, as mpl::find, which computes
in linear time, is called for every element of Seq. The same thing
can be done in one pass through the sequence as follows:

template<typename Seq,typename T>
struct eraseVal2:mpl::copy_if<Seq,mpl::not_<boost::is_same<mpl::_,T> > >
{};

Please find attached a compilable snippet showing both algorithms
at work.

HTH,

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo