Combination of types using boost::mpl

Question

I have a list of types, from which I want to construct the list of all combinations with two elements. For example:

namespace mpl = boost::mpl;
typedef mpl::vector<int, long> typelist;
// mpl magic...
// the wanted list is equivalent to:
typedef mpl::vector<pair<int, int>, pair<int, long>,
                    pair<long, int>, pair<long, long> > combinations;

Here, pair<T1,T2> could be std::pair<T1,T2>, or mpl::vector<T1,T2>. How to do this? I would also be interested in removing the duplicates when we consider that pair<T1, T2> == pair<T2, T1>.
Thanks.

Answer 1

The list of combinations of a single type int with the list of types mpl::vector<int, long> can be computed by invoking mpl::fold:

typedef fold<
    mpl::vector<int, long>, vector<>, 
    push_back<mpl::_1, std::pair<int, mpl::_2> > 
>::type list_of_pairs;

Now, if we wrap that into a separate meta-function and invoke it for all types of the initial typelist we get:

typedef mpl::vector<int, long> typelist;

template <typename T, typename Result>
struct list_of_pairs
  : mpl::fold<typelist, Result, 
        mpl::push_back<mpl::_1, std::pair<T, mpl::_2> > > 
{};

typedef mpl::fold<
    typelist, mpl::vector<>, mpl::lambda<list_of_pairs<mpl::_2, mpl::_1> >
>::type result_type;

BOOST_MPL_ASSERT(
    mpl::equal<result_type, 
        mpl::vector4<
            std::pair<int, int>, std::pair<int,long>,
            std::pair<long,int>, std::pair<long,long> 
        > >::value);

---

EDIT: answering second question:

Making the result containing only unique elements (in the sense you mentioned) is a bit more involved. First you need to define a meta function comparing two elements and returning mpl::true_/mpl::false_:

template <typename P1, typename P2>
struct pairs_are_equal
  : mpl::or_<
        mpl::and_<
            is_same<typename P1::first_type, typename P2::first_type>,
            is_same<typename P1::second_type, typename P2::second_type> >,
        mpl::and_<
            is_same<typename P1::first_type, typename P2::second_type>, 
            is_same<typename P1::second_type, typename P2::first_type> > >
{};

Then we need to define a meta-function which tries to find a given element in a given list:

template <typename List, typename T>
struct list_doesnt_have_element
  : is_same<
        typename mpl::find_if<List, pairs_are_equal<mpl::_1, T> >::type, 
        typename mpl::end<List>::type>
{};

Now, this can be utilized to build a new list, making sure no duplicates are inserted:

typedef mpl::fold<
    result_type, mpl::vector<>,
    mpl::if_<
        mpl::lambda<list_doesnt_have_element<mpl::_1, mpl::_2> >, 
        mpl::push_back<mpl::_1, mpl::_2>, mpl::_1>

>::type unique_result_type;

All this is from the top of my head, so it may need some tweaking here or there. But the idea should be correct.

---

EDIT: minor corrections as outlined by @rafak

Answer 2

I've been doing some metaprogramming myself lately, have you looked into boost::mpl::set? That will eliminate duplicates. As for combinations, that sounds to me like mapping, what about boost::mpl::map? Beware that there are library limits that are imposed on the limits of types the sequences can take, though this can be adjusted with a macro, you're still at the mercy of your compiler's upper limit, depending on the number of types you need to handle.

Answer 3

Excellent question. There are many interesting ways to solve this. Here is one.

All the unqualified names are in the mpl namespace, except for _1 and _2 which are in mpl::placeholders and boost::is_same, which is found in the type_traits library. The first template is a helper class to generate a list of all pairs consisting of a single element and each element of the given sequence. The second template aggregates all the results together to form the final sequence. Note that the results are not in a vector. You can do that easily with mpl::copy.

template <class Elem, class Seq>
struct single_combo {
    typedef typename transform<Seq
            ,lambda< std::pair<Elem, _1> >
        >::type type;
};

template <class Seq>
struct combo {
    typedef typename unique<Seq, is_same<_1,_2> >::type U;
    typedef typename fold<
        typename transform<U
            ,lambda< single_combo<_1, U> >
            >::type
        ,empty_sequence
        ,lambda< joint_view<_1,_2> >
    >::type type;
};

typedef typename combo<typelist>::type combinations;

---

Side note: If you're reading this and want a challenge, try answering this question yourself. It's a great plunge into MPL.