Cartesian product of multiple templates

Question

I have a few classes:

template <int,char>
class Foo{};
template <int,char>
class Bar{};

And I want to get all combinations with a few arguments, like this:

// {1, 2}, {'a', 'b'}
using CartesianProduct = mp_list<Foo<1,'a'>, Foo<1,'b'>,...,Bar<2,'b'>>;

I can change template parameters to types and use std::integral_constant, if it cannot be done with numeric constants.

I found a similar question, but it's far more difficult. Creating all template permutations with MPL. I assume, there is a better and easier solution for my case.

Answer 1

Finally, I figured it out by myself.

using namespace boost::mp11;

template <typename C1, typename C2>
struct Foo{};

template <typename C1, typename C2>
struct Bar{};

template <template <typename...> typename... F>
using mp_list_q = mp_list<mp_quote<F>...>;

using TypeList = mp_product<mp_invoke_q, 
    mp_list_q<Foo, Bar>, 
    mp_list_c<int, 1, 2>, 
    mp_list_c<char, 'a', 'b'>>;

Result:

boost::mp11::mp_list<
Foo<std::integral_constant<int, 1>, std::integral_constant<char, (char)97> >,
Foo<std::integral_constant<int, 1>, std::integral_constant<char, (char)98> >,
Foo<std::integral_constant<int, 2>, std::integral_constant<char, (char)97> >,
Foo<std::integral_constant<int, 2>, std::integral_constant<char, (char)98> >,
Bar<std::integral_constant<int, 1>, std::integral_constant<char, (char)97> >,
Bar<std::integral_constant<int, 1>, std::integral_constant<char, (char)98> >,
Bar<std::integral_constant<int, 2>, std::integral_constant<char, (char)97> >,
Bar<std::integral_constant<int, 2>, std::integral_constant<char, (char)98> > >

It uses std::integral_constant for arguments, but it's simple and short. Try it here

UPD: And I found how to use integers itselfs!

template <int, char>
struct Foo{};

template <int, char>
struct Bar{};

template <template <auto...> typename F>
struct mp_quote_c
{
    template <typename... C>
    using fn = F<C::value...>;
};

template <template <auto...> typename... F>
using mp_list_qc = mp_list<mp_quote_c<F>...>;

using TypeList = mp_product<mp_invoke_q,
    mp_list_qc<Foo, Bar>,
    mp_list_c<int, 1, 2>, 
    mp_list_c<char, 'a', 'b'>>;

Result:

boost::mp11::mp_list<
Foo<1, (char)97>, Foo<1, (char)98>, Foo<2, (char)97>, Foo<2, (char)98>,
Bar<1, (char)97>, Bar<1, (char)98>, Bar<2, (char)97>, Bar<2, (char)98> >

Try it here!

UPD2: Only clang can compile this code. It seems like there is a bug in msvc and gcc, because clang can build this code even with -pedantic-errors

UPD3: Now gcc also can compile it

Answer 2

There is an implementation called combine_view here: https://stackoverflow.com/a/27175631/225186 that I used in my library https://gitlab.com/correaa/boost-covariant

Maybe nowadays there is something better in the MP11 library.

This is my distilled version:

#include<boost/mpl/vector.hpp>
#include<boost/mpl/set.hpp>

#include<boost/mpl/fold.hpp>
#include<boost/mpl/zip_view.hpp>
#include <boost/mpl/at.hpp>
#include <boost/mpl/pop_front.hpp>

namespace boost{
namespace mpl{

template <class Seq, class ItrSeq>
class SequenceCombiner{

template < class _Seq = mpl::vector<int_<1> > >
struct StateSeq{
        typedef typename pop_front<_Seq>::type sequence;
        typedef typename mpl::at<_Seq, int_<0> >::type state;
        typedef _Seq type;
};

template < class _Seq, class _State >
struct set_state{
        typedef StateSeq< typename push_front<_Seq, _State>::type > type;
};

struct NextOp {

template<typename Out, typename In, typename Enable = typename Out::state>
class apply{
        using seq = typename Out::sequence;
        using new_state = typename Out::state;
        using in_seq = typename mpl::at<In,int_<0> >::type;
        using in_itr = typename mpl::at<In,int_<1> >::type;

        using new_seq = typename mpl::push_back<seq, in_itr>::type;
public:
        typedef typename set_state<new_seq, int_<0> >::type type;
};

template<typename Out, typename In>
class apply<Out,In,mpl::int_<1> >{
        typedef typename Out::sequence seq;
        typedef typename Out::state state;
        typedef typename mpl::at<In,int_<0> >::type in_seq;
        typedef typename mpl::at<In,int_<1> >::type in_itr;

        typedef typename mpl::begin<in_seq>::type Itr_begin;
        typedef typename mpl::next<in_itr>::type  Itr_next;
        typedef typename mpl::end<in_seq>::type   Itr_end;

typedef typename mpl::if_<
        boost::is_same<Itr_next,Itr_end>,
        typename mpl::push_back<seq,Itr_begin>::type,
        typename mpl::push_back<seq,Itr_next>::type
>::type new_seq;

typedef typename mpl::if_<boost::is_same<Itr_next,Itr_end>,
        mpl::int_<1>,
        mpl::int_<0>
>::type new_state;

public:
        typedef typename set_state<new_seq, new_state>::type type;

};
};

typedef typename mpl::fold<
        typename mpl::zip_view<mpl::vector<Seq, ItrSeq> >::type,
        StateSeq<>,
        NextOp
>::type StateResult;

public:

typedef typename mpl::if_<
        boost::is_same<typename StateResult::state, int_<1> >,
        typename mpl::transform<Seq, mpl::end<_1> >::type,
        typename StateResult::sequence
>::type next;

};

template<typename Seq, typename Itrs>
struct combine_iterator{
        typedef mpl::forward_iterator_tag category;
        typedef Seq  seq;
        typedef typename transform<Itrs, deref<_1> >::type type;
};

template <class Seq, class Pos>
struct next<typename mpl::combine_iterator<Seq, Pos>>{
    typedef typename mpl::SequenceCombiner<Seq,Pos>::next next_Pos;
    typedef boost::mpl::combine_iterator<Seq, next_Pos> type;
};

template<class Seq>
class combine_view{
        using Pos_begin = typename mpl::transform<Seq, mpl::begin<_1> >::type;
        using Pos_end   = typename mpl::transform<Seq, mpl::end<_1>   >::type;
public:
        using begin = combine_iterator<Seq, Pos_begin>;
        using end   = combine_iterator<Seq, Pos_end>;
        using type  = combine_view;
};

} // mpl
} // boost

Example use:

using boost::mpl::combine_view;
using product = combine_view<
    boost::mpl::list<
        boost::mpl::list<double, int, std::string>, 
        boost::mpl::list<double, int>,
        boost::mpl::list<std::string, char>
    >
>::type;               

static_assert( boost::mpl::size<product>::value == 12 );

Answer 3

For fun I gave it a try to make a manual implementation of this work with variadic templates, std::integer_sequence and std::tuple_cat and was actually surprised to get it to work quite easily: Based on simple arrays of arbitrary length

constexpr std::array<int,2>  t1 = {1, 2};
constexpr std::array<char,3> t2 = {'a', 'b', 'c'};

and given the variadic template classes (e.g. Foo and Bar) it generates all possible permutations itself and merges them to an std::tuple (or boost::mpl::list) data type for which a convenient alias can be defined:

using SomeAlias = typename AllClassesAllPermutations<t1.size(), t2.size(), t1, t2, Foo, Bar>::type;

• Not being familiar with Boost::MPL I tried to stay away from it: My first version is actually based on std::tuple

  Try std::tuple version here!

• If you want to have a boost::mpl::list instead of an std::tuple this can be easily done with another variadic template conversion function

  Try boost::mpl::list version here!

The next section will go into more detail on how this can be achieved!

---

For this purpose I wrote a class that - based on a few template arguments such as the said combinations of the int and char parameters as well as the corresponding template template class - creates an std::tuple containing all permutations of the int and char arrays of this single template template class. This is done by creating two permutation vectors holding the pairwise permutations. E.g. two input arrays t1_in = {1, 2} and t2_in = {'a', 'b', 'c'}; are expanded to t1 = {1, 1, 1, 2, 2, 2} and t2 = {'a', 'b', 'c', 'a', 'b', 'c'} with the function duplicateArray and then an std::integer_sequence is created so the two can be fused into a template T<t1[I], t2[I]> that in combination with the std::integer_sequence gives you all permutations for a single class:

template <std::size_t I1, std::size_t I2, std::array<int,I1> const& t1_in, std::array<char,I2> const& t2_in, template <int, char> class T>
class SingleClassAllPermutations {
  private:    
    template <std::size_t K, std::size_t I, typename TA, std::size_t J>
    static constexpr auto duplicateArray(std::array<TA, J> const& arr_in) {
      std::array<TA, I*J*K> arr_out {0};
      std::size_t l {0};
      for (std::size_t i = 0; i < I; ++i) {
        for (std::size_t j = 0; j < J; ++j) {
          for (std::size_t k = 0; k < K; ++k) {
            arr_out[l] = arr_in[j];
            ++l;
          }
        }
      }
      return arr_out;
    }

    static constexpr std::size_t N = I1*I2;
    static constexpr std::array<int,N>  t1 = duplicateArray<I2,1>(t1_in);
    static constexpr std::array<char,N> t2 = duplicateArray<1,I1>(t2_in);
    static constexpr auto index_seq = std::make_index_sequence<N>{};

    template <std::size_t... I>
    static constexpr auto getTuple(std::index_sequence<I...>) {
      return std::make_tuple(T<t1[I], t2[I]>() ...);
    }

  public:
    static constexpr auto tup = getTuple(index_seq);
};

Then I created a variadic template which may take several different template template classes (as long as their template arguments are int and char respectively) as additional input arguments and then merges the internal tuple tup of the individual permutations with std::tuple_cat to create the tuple containing all possible permutations of the int and char arrays as well as the different variadic template template classes:

template <std::size_t I1, std::size_t I2, std::array<int,I1> const& t1, std::array<char,I2> const& t2, template <int,char> class... Ts>
class AllClassesAllPermutations {
  public:
    static constexpr auto getTuple() {
      return std::tuple_cat(SingleClassAllPermutations<I1,I2,t1,t2,Ts>::tup ...);
    }

    using type = decltype(getTuple());
};

Now one can then define global constexpr arrays inside namespaces and a convenient alias such as

namespace some_namespace {
  constexpr std::array<int,2>  t1 = {1, 2};
  constexpr std::array<char,3> t2 = {'a', 'b', 'c'};
  using SomeInstantiation = typename AllClassesAllPermutations<t1.size(), t2.size(), t1, t2, Foo, Bar>::type;
}

This way one can re-use the templates above to generate different data types.

The templates then expand it to all possible permutations, in the case above to

std::tuple<Foo<1,'a'>, Foo<1,'b'>, Foo<1,'c'>, Foo<2,'a'>, Foo<2,'b'>, Foo<2,'c'>,
           Bar<1,'a'>, Bar<1,'b'>, Bar<1,'c'>, Bar<2,'a'>, Bar<2,'b'>, Bar<2,'c'>>

Finally if you want to have an boost::mpl::list instead you can introduce a conversion function such as

template <class... Ts>
static constexpr auto tupleToMplList(std::tuple<Ts...>) {
  return boost::mpl::list<Ts...>{};
}

that you again use to decltype instead of the std::tuple which results in a data type

boost::mpl::list<Foo<1,'a'>, Foo<1,'b'>, Foo<1,'c'>, Foo<2,'a'>, Foo<2,'b'>, Foo<2,'c'>,
                 Bar<1,'a'>, Bar<1,'b'>, Bar<1,'c'>, Bar<2,'a'>, Bar<2,'b'>, Bar<2,'c'>>

Try it here