How to create the Cartesian product of a type list

Question

I'd like to create the cross product of a list of types using variadic templates.

Here's what I have so far:

#include <iostream>
#include <typeinfo>
#include <cxxabi.h>

template<typename...> struct type_list {};

template<typename T1, typename T2> struct type_pair {};

template<typename T, typename... Rest>
  struct row
{
  typedef type_list<type_pair<T,Rest>...> type;
};

template<typename... T>
  struct cross_product
{
  typedef type_list<typename row<T,T...>::type...> type;
};

int main()
{
  int s;
  typedef cross_product<int, float, short>::type result;
  std::cout << abi::__cxa_demangle(typeid(result).name(), 0, 0, &s) << std::endl;

  return 0;
}

This program outputs:

$ g++ -std=c++0x cross_product.cpp ; ./a.out 
type_list<type_list<type_pair<int, int>, type_pair<int, float>, type_pair<int, short> >, type_list<type_pair<float, int>, type_pair<float, float>, type_pair<float, short> >, type_list<type_pair<short, int>, type_pair<short, float>, type_pair<short, short> > >

But I'd like it to output:

type_list<type_pair<int,int>, type_pair<int,float>, type_pair<int,short>, type_pair<float,int>,...>

That is, without the nested type_lists.

Is there a direct way to do this without the row helper, or should the solution "unwrap" the nested type_lists somehow?

Answer 1

So far all solutions have drawbacks, unnecessary dependencies, unnecessary helpers and all are restricted to the Cartesian power of two. The following solution has no such drawbacks and supports:

1. Any cartesian power including 0.
2. Returning the empty set if any of the factors is an empty set.
3. The code is self contained and does not depend on any include files.
4. The inputs of the function can be of any template type.
5. The type of the output list can be specified via the first template parameter.

It was actually to harder to implement (but good as homework) then I thought. I am actually thinking about creating a little generator which allows me an extended template syntax which makes these things really easy.

Simplified the code works as follows: product converts an input list tuple<A...>,tuple<B...>,tuple<C...> into tuple<tuple<A>...>, tuple<B...>, tuple<C...>. This second list is then passed to product_helper which does the recursive Cartesian product computation.

template <typename... T> struct cat2;

template <template<typename...> class R, typename... As, typename... Bs>
struct cat2 <R<As...>, R<Bs...> > {
        using type = R <As..., Bs...>;
};

template <typename... Ts> struct product_helper;

template <template<typename...> class R, typename... Ts>
struct product_helper < R<Ts...> > { // stop condition
        using type = R< Ts...>;
};

template <template<typename...> class R, typename... Ts>
struct product_helper < R<R<> >, Ts... > { // catches first empty tuple
        using type = R<>;
};

template <template<typename...> class R, typename... Ts, typename... Rests>
struct product_helper < R<Ts...>, R<>, Rests... > { // catches any empty tuple except first
        using type = R<>;
};

template <template<typename...> class R, typename... X, typename H, typename... Rests>
struct product_helper < R<X...>, R<H>, Rests... > {
        using type1 = R <typename cat2<X,R<H> >::type...>;
        using type  = typename product_helper<type1, Rests...>::type;
};

template <template<typename...> class R, typename... X, template<typename...> class Head, typename T, typename... Ts, typename... Rests>
struct product_helper < R<X...>, Head<T, Ts...>, Rests... > {
        using type1 = R <typename cat2<X,R<T> >::type...>;
        using type2 = typename product_helper<R<X...> , R<Ts...> >::type;
        using type3 = typename cat2<type1,type2>::type;
        using type  = typename product_helper<type3, Rests...>::type;
};

template <template<typename...> class R, typename... Ts> struct product;

template <template<typename...> class R>
struct product < R > { // no input, R specifies the return type
    using type = R<>;
};

template <template<typename...> class R, template<typename...> class Head, typename... Ts, typename... Tail>
struct product <R, Head<Ts...>, Tail... > { // R is the return type, Head<A...> is the first input list
    using type = typename product_helper< R<R<Ts>...>, Tail... >::type;
};

Here is a compilable example of how the code can be used.