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

From: David Abrahams (dave_at_[hidden])
Date: 2007-06-10 14:45:18

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