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@boost-consulting.com> 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@lists.boost.org

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.htm...

Andrej van der Zee <mavdzee@yahoo.co.uk> writes:

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?

Ideally, we should have a metafunction that would allow you to query whether the sequence (or any other library entity) supports a particular concept (Associative Sequence in your case). In absence of that, something like the following should work: template< typename Sequence, typename Dummy = boost::mpl::false_ > struct is_Associative_Sequence : boost::mpl::false_ { }; template< typename S > struct is_Associative_Sequence< S , typename boost::mpl::has_key_impl< typename boost::mpl::sequence_tag<S>::type >::template apply<S,S>::type > : boost::mpl::true_ { }; int main(int argc, char *argv[]) { BOOST_MPL_ASSERT_NOT(( is_Associative_Sequence< boost::mpl::vector0<> > )); BOOST_MPL_ASSERT(( is_Associative_Sequence< boost::mpl::map0<> > )); } HTH, -- Aleksey Gurtovoy MetaCommunications Engineering