Create cartesian product expansion of two variadic, non-type template parameter packs

Question

Lets say, I have

• two lists of non-type template parameteres (which might have a different type)
• a template foo that takes one value of each of those lists as a parameter

How can I create a variadic parameter pack of foos, parameterized with the cartesian product of the two list elements?

Here is what I mean:

template<int ...>
struct u_list {};

template<char ...>
struct c_list {};

template<int, char >
struct foo {};

template<class ...>
struct bar {};

using int_vals = u_list<1, 5, 7>;
using char_vals = c_list<-3, 3>;


using result_t = /* magic happens*/
using ref_t = bar<
    foo<1, -3>, foo<1, 3>,
    foo<5, -3>, foo<5, 3>,
    foo<7, -3>, foo<7, 3>
>;

static_assert(std::is_same<result_t, ref_t >::value, "");

I'm looking for a solution that works in c++11 and doesn't use any libraries except the c++11 standard library. I also have my handroled version of c++14's index_sequence / make_index_sequence and can provide the non-type parameter lists as arrays if that simplifies the code.

The closest I've found so far is this: How to create the Cartesian product of a type list?. So in principle (I haven't tested it) it should be possible to turn the non-type parameter packs into type parameter packs and then apply the solution in the linked post, but I was hoping that there is a simpler / shorter solution along the lines of this:

template<int... Ints, char ... Chars>
auto magic(u_list<Ints...>, c_list<Chars...>) 
{
    //Doesn't work, as it tries to expand the parameter packs in lock step
    return bar<foo<Ints,Chars>...>{};  
}

using result_t = decltype(magic(int_vals{}, char_vals{}));

Answer 1

You may do something like the following:

template <int... Is>
using u_list = std::integer_sequence<int, Is...>;

template <char... Cs>
using c_list = std::integer_sequence<char, Cs...>;

template<int, char> struct foo {};

template<class ...> struct bar {};

template <std::size_t I, typename T, template <typename, T...> class C, T ... Is>
constexpr T get(C<T, Is...> c)
{
    constexpr T values[] = {Is...};
    return values[I];
}


template <std::size_t I, typename T>
constexpr auto get_v = get<I>(T{});


template<int... Ints, char ... Chars, std::size_t ... Is>
auto cartesian_product(u_list<Ints...>, c_list<Chars...>, std::index_sequence<Is...>)
-> bar<foo<
        get_v<Is / sizeof...(Chars), u_list<Ints...> >,
        get_v<Is % sizeof...(Chars), c_list<Chars...> >
        >...
    >;

template<int... Ints, char ... Chars>
auto cartesian_product(u_list<Ints...> u, c_list<Chars...> c)
-> decltype(cartesian_product(u, c, std::make_index_sequence<sizeof...(Ints) * sizeof...(Chars)>()));




using int_vals = u_list<1, 5, 7>;
using char_vals = c_list<-3, 3>;

using result_t = decltype(cartesian_product(int_vals{}, char_vals{}));

Demo

Possible implementation of std part:

template <typename T, T ... Is> struct integer_sequence{};

template <std::size_t ... Is>
using index_sequence = integer_sequence<std::size_t, Is...>;

template <std::size_t N, std::size_t... Is>
struct make_index_sequence : make_index_sequence<N - 1, N - 1, Is...> {};

template <std::size_t... Is>
struct make_index_sequence<0u, Is...> : index_sequence<Is...> {};

And change in answer:

template <std::size_t I, typename T, template <typename, T...> class C, T ... Is>
constexpr T get(C<T, Is...> c)
{
    using array = T[];
    return array{Is...}[I];
}

template<int... Ints, char ... Chars, std::size_t ... Is>
auto cartesian_product(u_list<Ints...>, c_list<Chars...>, index_sequence<Is...>)
-> bar<foo<
        get<Is / sizeof...(Chars)>(u_list<Ints...>{}),
        get<Is % sizeof...(Chars)>(c_list<Chars...>{})
        >...
    >;

Demo C++11

Answer 2

Doing template metaprogramming in the domain of pure types is far easier in my opinion.

It takes some work to move from the land of non-type template parameters to the land of types and back again, but it means you are using generic metaprogramming utilities instead of ones specific to your problem.

---

So I'll reduce your problem to a cartesian product on a list of types.

Here is my type pack:

template<class...Ts>struct types {
  using type=types; // makes inheriting from it useful
  static constexpr std::size_t size = sizeof...(Ts);
};

First we write fmap. Fmap takes a function and a list, and returns a list of each element of the list with the function applied.

template<template<class...>class Z, class List>
struct fmap {};
template<template<class...>class Z, class List>
using fmap_t = typename fmap<Z,List>::type;
template<template<class...>class Z, class...Ts>
struct fmap<Z, types<Ts...>>:
  types<Z<Ts>...>
{};

and fapply. fapply takes a function and a list as well, but applies the function to the entire set of list elements.

template<template<class...>class Z, class List>
struct fapply {};
template<template<class...>class Z, class List>
using fapply_t=typename fapply<Z,List>::type;
template<template<class...>class Z, class...Ts>
struct fapply<Z, types<Ts...>> {
  using type=Z<Ts...>;
};

As it happens, partial application of fapply is very useful:

template<template<class...>class Z>
struct applier {
    template<class List>
    using apply = fapply_t<Z,List>;
};

We'll want to be able to concatinate lists:

template<class...>
struct cat:types<> {};
template<class...As, class...Bs, class...Cs>
struct cat<types<As...>, types<Bs...>, Cs...>:
    cat<types<As..., Bs...>, Cs...>
{};
template<class...As>
struct cat<types<As...>>:types<As...>{};
template<class...Ts>using cat_t=typename cat<Ts...>::type;

Then, here is cart_product_t:

template<class A, class B>
struct cart_product {};
template<class A, class B>
using cart_product_t = typename cart_product<A,B>::type;
template<class A, class... Bs>
struct cart_product<types<A>, types<Bs...>>:
  types< types<A, Bs>... >
{};
// reduce cart_product to cart_product on a one element list on the lhs:
template<class...As, class... Bs>
struct cart_product<types<As...>, types<Bs...>>:
  fapply_t<
    cat_t,
    fmap_t<
      applier<cart_product_t>::template apply,
      types<
        types< types<As>, types<Bs...> >...
      >
    >
  >
{};

Types specific to your problem:

template<int...>struct u_list {};
template<char...>struct c_list {};
template<int, char>struct foo {};
template<class...>struct bar{};

A tool that lift lists of values to types:

template<class> struct lift {};
template<int...is> struct lift<u_list<is...>>:
  types< std::integral_constant<int, is>... >
{};
template<char...is> struct lift<c_list<is...>>:
  types< std::integral_constant<char, is>... >
{};
template<class T>using lift_t=typename lift<T>::type;

lower_to_foo takes a pair of types, and converts them to a foo:

template<class I, class C>
using lower_to_foo = foo<I::value, C::value>;

now we put them together:

using int_vals = u_list<1, 5, 7>;
using char_vals = c_list<-3, 3>;

using product = cart_product_t< lift_t<int_vals>, lift_t<char_vals> >;
static_assert( product::size == 6, "should be 6" );
using result_t = fapply_t< bar, fmap_t< applier<lower_to_foo>::template apply, product > >;

using ref_t = bar<
  foo<1, -3>, foo<1, 3>,
  foo<5, -3>, foo<5, 3>,
  foo<7, -3>, foo<7, 3>
>;
ref_t test = result_t{}; // gives better error messages than static_assert
static_assert(std::is_same<result_t, ref_t >::value, "");

and bob is your uncle.

cat, fmap and fapply are both relatively standard functions in functional programming. applier just lets you write your template mapping functions taking elements instead of lists (it is a partially applied fapply).

Live example.

---

Now, remember how I said template metaprogramming was easier with types?

Notice all those template template parameters? It gets easier if they are types.

template<template<class...>class Z>
struct ztemplate {
  template<class...Ts>using apply=Z<Ts...>;
};

and you can go all the way down to hana-style constexpr metaprogramming with type tags and operator() on ztemplate and other fun.