2012.05.03 - variadic template homework

finally i got some spare time and finish watching recordings from Going Native 2012. during one of the Andrei Alexandrescu's presentations on variadic templates viewers were given a homework to be done: implementing cartesian product of the given template arguments, to exercise variadics a little.

since the task is originally underspecified, let us stick to the number values, instead of (usual) types (for the sake of outputting) and assume the simple notion of generating result by directly printing each pair on the screen, instead of “saving” it as a type for later expansion (saves extra code to print-out the result in test/toy app). of course all of the computations are done in the compile time (except of printing itself ;)).

so first let us define the interface, that will be used:

template<int...Ts>
void expand(void)
{
  Cart<Ts...>::template go<Ts...>();
}

it takes sequence of numbers as the argument and prints them out using Cart template class and its go() template method. they both take expanded arguments (i.e. values) lists. this enables us to iterate over the twice-expanded arguments.

having this done, we implement the most generic class, that will be used to stop compile-time iteration:

template<int...Ts>
struct Cart
{
  template<int...Us>
  static void go() { }
};

now comes the fun part – iteration over the list. first we'll define previous template's specialization, that splits arguments into head (H) and tail of “T” elements (Ts – “s” is for plural):

template<int H1, int...Ts>
struct Cart<H1, Ts...>
{
};

now go() template (static) method is being implemented. what it does is to call helper sub-class (also variadic template), that will creates elements for all arguments, paired with the current one. class is called X, in short. next step is to call instance of own class, but with different arguments – implementation moves to the next class-template argument:

template<int H1, int...Ts>
struct Cart<H1, Ts...>
{
  template<int...Us>
  static void go()
  {
    X<Us...>::go();
    Cart<Ts...>::template go<Us...>();
  }
};

note that last line – Cart<Ts…>::template go<Us…>(). we move to the next argument with Ts BUT keep the original, full list Us for go(), so that next argument can be paired up with the full list of elements again!

now it's time for X to appear – this is simple metaprogram, that prints first argument of the class it is part of and then another arguments, given as its arguments. so the full Cart's class specialization looks like this:

template<int H1, int...Ts>
struct Cart<H1, Ts...>
{
  template<int...Us>
  static void go()
  {
    X<Us...>::go();
    Cart<Ts...>::template go<Us...>();
  }
 
  template<int...Us>
  struct X
  {
    static void go() { }
  };
  template<int H2, int...Us>
  struct X<H2, Us...>
  {
    static void go()
    {
      cout<<H1<<":"<<H2<<endl;
      X<Us...>::go();
    }
  };
};

example output for:

expand<1,2,66>();

gives (i.e. prints):

1:1
1:2
1:66
2:1
2:2
2:66
66:1
66:2
66:66

clean, short and simple! :) here is the full source of the cartesian product implementation.