Re: [Boost-users] MPL intersection of type sequences and compile-time performance

From: Andrej van der Zee (mavdzee_at_[hidden])
Date: 2007-06-10 23:41:22

Hi,

Than you for the quick reply :) Now I reimplemented
intersect by converting the type sequences to mpl::set
and do a mpl::has_key instead of mpl::contains:

template <typename seq1, typename seq2>
struct intersect
{
  typedef typename copy<seq2
     , inserter< set<>, insert< _1, _2 > >
     >::type set_seq2;

  typedef typename copy_if<seq1
     , has_key <set_seq2, _1> 
     , back_inserter < vector<> >
     >::type type;
};

Now I would like to optimize this and only convert to
a set if the type sequence does not support
mpl::has_key. How should I do this?

I looked at the mpl::sequence_tag<seq2> but I am not
sure how to use this. Nor if this is the right way to
do this. Could you please help?

Thanks,
Andrej
 

--- David Abrahams <dave_at_[hidden]> wrote:

> 
> on Sun Jun 10 2007, Andrej van der Zee
> <mavdzee-AT-yahoo.co.uk> wrote:
> 
> > Hi,
> >
> > Sorry if this already has been posted, but I have
> a
> > problem with compile-time performance when trying
> to
> > get the intersection of two type sequences. For
> > example, when I do something like this:
> >
> > template<typename list1, typename list2>
> > struct intersect
> > {
> >   typedef typename boost::mpl::remove_if<list1,
> >     mpl::not_< mpl::contains<list2, mpl::_1>
> >    >::type type;
> > };
> >
> > typedef mpl::vector<a,b,...,z> l1;
> > typedef mpl::vector<c,e,t,u,v> l2;
> >
> > typename intersect<list1,list2>::type
> my_intersection;
> >
> > Then for large type sequences compile-time becomes
> > unacceptable (O(M*N)). 
> 
> I'm surprised it's even that good, since most
> compilers have such poor
> performance for multiple instantiations of the same
> template.  That's
> the cost you'd expect for a direct runtime
> translation of your
> algorithm.
> 
> > Is there a better way to do this?
> 
> I'd use an associative sequence like mpl::set.
> 
> -- 
> Dave Abrahams
> Boost Consulting
> http://www.boost-consulting.com
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
>
http://lists.boost.org/mailman/listinfo.cgi/boost-users
> 

      ___________________________________________________________ 
Yahoo! Mail is the world's favourite email. Don't settle for less, sign up for
your free account today http://uk.rd.yahoo.com/evt=44106/*http://uk.docs.yahoo.com/mail/winter07.html