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{}));

Spies

I've been doing some nasty stuff with parameters combinations... maybe this can be helpful: [click me] – Pharsalus

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

Puttee

Thank you. At a glance, this seems the solution, that is most readable to me. I'll have to experiment a bit with the real code to see what answer works best for me. – Spies

Could you translate this into a c++11 solution? – Spies

@MikeMB: C++11 version added. – Puttee

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.

Embargo

Does std::integral_constant actually have to have a integral type or are e.g. class enums also possible? – Spies

@Spies Mate, function pointers are even possible. They even are callable in C++14. – Embargo

Thank you. This seems like a good solution, but unless we need more tmp in our code, I'm a bit reluctant to add so many generic facilities just for my single usecase. – Spies

Answer 3

Taking the type-list cross product as a base

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

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

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

template<int, char > struct foo {};

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

We expand the char... pack with row

template<int I, char... Cs>
  struct row
{
  typedef type_list<foo<I,Cs>...> type;
};

template <typename... T> struct concat;

template <typename... S, typename... T>
struct concat<type_list<S...>, type_list<T...>>
{
    using type = type_list<S..., T...>;
};

We want an extra specialisation of concat to break out of the base case

template <typename... T>
struct concat<type_list<T...>, void>
{
    using type = type_list<T...>;
};

template<typename I, typename C>
struct cross_product;

Base case: no more ints

template<char... Cs>
struct cross_product<u_list<>, c_list<Cs...>>
{
    using type = void;
};

Recursive case: An int, followed by a pack of ints

template<int I, int... Is, char... Cs>
struct cross_product<u_list<I, Is...>, c_list<Cs...>>
{
    using type = typename concat<typename row<I,Cs...>::type, typename cross_product<u_list<Is...>, c_list<Cs...>>::type>::type;

};

int main()
{
  using int_vals = u_list<1, 5, 7>;
  using char_vals = c_list<-3, 3>;

  using result_t = cross_product<int_vals, char_vals>::type;
  using ref_t = type_list<
      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, "");
  return 0;
}

Live on Coliru!

Interstice

Answer 4

The following are my 2 cents...

If you want a generic solution, the bigger problem I see is that from int_vals and char_vals types isn't easy (in C++11; simpler in C++17) extract the types of the contained values (int and char).

So I suppose you have to pass they to magic<> together with foo and bar (if you don't want foo and bar hard-coded).

So the call to magic<> become (in my way)

using result_t
   = typename magic<int, char, foo, bar, int_vals, char_vals>::type; 

The following is a full working example with my solution.

#include <type_traits>

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

template <int, char>    struct foo {};
template <typename ...> struct bar {};

template <typename T1, typename T2, T1 t1, T2 ... T2s>
struct midProd
 { };

template <typename T1, typename T2, template <T1, T2> class, typename...>
struct magicHelper;

template <typename T1, typename T2,
          template <T1, T2> class ResIn,
          template <typename...> class ResOut,
          typename ... R>
struct magicHelper<T1, T2, ResIn, ResOut<R...>>
 { using type = ResOut<R...>; };

template <typename T1, typename T2,
          template <T1, T2> class ResIn,
          template <typename...> class ResOut,
          typename ... R, T1 ts1, T2 ... ts2, typename ... MpS>
struct magicHelper<T1, T2, ResIn, ResOut<R...>,
              midProd<T1, T2, ts1, ts2...>, MpS...>
 { using type = typename magicHelper<T1, T2, ResIn,
                   ResOut<R..., ResIn<ts1, ts2>...>, MpS...>::type; };


template <typename T1, typename T2,
          template <T1, T2> class,
          template <typename...> class,
          typename, typename>
struct magic;

template <typename T1, typename T2,
          template <T1, T2> class ResIn,
          template <typename...> class ResOut,
          template <T1...> class C1, template <T2...> class C2,
          T1 ... ts1, T2 ... ts2>
struct magic<T1, T2, ResIn, ResOut, C1<ts1...>, C2<ts2...>>
 { using type = typename magicHelper<T1, T2, ResIn, ResOut<>,
                   midProd<T1, T2, ts1, ts2...>...>::type ; };

int main ()
 {
   using int_vals  = u_list<1, 5, 7>;
   using char_vals = c_list<-3, 3>;

   using result_t
      = typename magic<int, char, foo, bar, int_vals, char_vals>::type;

   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, "");
 }

Obviously, if you prefer hard-code some types (u_list, c_list, foo, and bar), the solution become a lot simpler

#include <type_traits>

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

template <int, char>    struct foo {};
template <typename ...> struct bar {};

template <int, char...> struct midProd {};

template <typename...>
struct magicH;

template <typename ... R>
struct magicH<bar<R...>>
 { using type = bar<R...>; };

template <typename ... R, int i, char ... cs, typename ... MpS>
struct magicH<bar<R...>, midProd<i, cs...>, MpS...>
 { using type = typename magicH<bar<R..., foo<i, cs>...>, MpS...>::type; };


template <typename, typename>
struct magic;

template <int ... is, char ... cs>
struct magic<u_list<is...>, c_list<cs...>>
 { using type = typename magicH<bar<>, midProd<is, cs...>...>::type; };

int main ()
 {
   using int_vals  = u_list<1, 5, 7>;
   using char_vals = c_list<-3, 3>;

   using result_t = typename magic<int_vals, char_vals>::type;

   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, "");
 }

Smithy

Answer 5

The same as others in C++17:

// Type your code here, or load an example.
#include <type_traits>

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>;

template<class... Args> struct type_list{
    template<class> struct make_concat;
    template<class ...Xs>
    struct make_concat<type_list<Xs...>>{
        using type = type_list<Args...,Xs...>;
    };
    template<class T>
    using concat = typename make_concat<T>::type;
    template<template<class...>class TT>
    using applied_to = TT<Args...>;
};

template<
         template<auto,auto> class C
        ,class X,class Y,class Yit=Y>
struct cart_prod;
template<template<auto,auto> class C,
         template<auto...> class Xt,
         template<auto...> class Yt,
         class Yit,
         auto Xi,auto...Xis,auto Yi,auto...Yis>
struct cart_prod<C,Xt<Xi,Xis...>,Yt<Yi,Yis...>,Yit>{
    using type = typename type_list<class C<Xi,Yi>>
       ::template concat<typename cart_prod<C,Xt<Xi,Xis...>,Yt<Yis...>,Yit>::type>;
};
template<template<auto,auto> class C,
         template<auto...> class Xt,
         template<auto...> class Yt,
         class Yit,
         auto Xi,auto...Xis,auto Yi>
struct cart_prod<C,Xt<Xi,Xis...>,Yt<Yi>,Yit>{
    using type = typename type_list<class C<Xi,Yi>>
       ::template concat<typename cart_prod<C,Xt<Xis...>,Yit,Yit>::type>;
};
template<template<auto,auto> class C,
         template<auto...> class Xt,
         template<auto...> class Yt,
         class Yit,
         auto Xi,auto Yi>
struct cart_prod<C,Xt<Xi>,Yt<Yi>,Yit>{
    using type = type_list<class C<Xi,Yi>>;
};


using result_t = cart_prod<foo,int_vals,char_vals>::type::applied_to<bar>;
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, "");

Nicolella

Answer 6

yet another (but shorter) solution might be

template<typename Ret,typename R>
auto magic( bar<u_list<>, R>, Ret result, R ) { return result; }

template<int I, int... Ints, typename... Foos, typename R>
auto magic( bar<u_list<I,Ints...>, c_list<>>, bar<Foos...>, R rollback ) { return magic(
    bar<u_list<Ints...>,R>{}, bar<Foos...>{}, rollback );}

template<int I, int... Ints, char J, char ... Chars, typename... Foos, typename R >
auto magic( bar<u_list<I,Ints...>, c_list<J,Chars...>>, bar<Foos...>, R rollback ) { return magic(
    bar<u_list<I,Ints...>, c_list<Chars...>>{},
    bar<Foos...,foo<I,J>>{},
    rollback );}

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

Antimonic