Type Transformations #

Source code: 1uc/modern_numerics_cxx

Given a sequence of types, we’d like a corresponding sequence of transformed types. It’s like map or apply but instead of acting on values it should act on types.

We’ll demonstrate the idea for an array-of-struct (SoA) container. An SoA container rearranges the elements of an array of structs (AoS), e.g.

struct Int_Double {
  int i;
  double d;
};

std::vector<Int_Double> int_doubles;

such that i[i], i[i+1] are stored consecutively (same for d). The goal is to write a data-structure that generalizes,

struct SoA_Int_Double {
  std::vector<int> int_field;
  std::vector<double> double_field;
};

to support the following API:

auto soa = SoA<int, double>(n);
int i5 = soa.get<0>(5);
double d2 = soa.get<1>(2);

Problem: We Can’t Write it Out #

We can’t write one member per template parameter, because we don’t know how many we have. One solution would be to use recursion. However, we’d like to demonstrate how to manipulate types. Therefore, we’ll use existing data structures.

If only we could take T and convert it to std::vector<T> then we could maybe do:

std::tuple<std::vector<T1>, std::vector<T2>, ...>

to store the vectors.

Solution: Template Parameter Packs #

We need a template because we need it to work for different types, we also need a variadic template because we need it to work for arbitrary structs, some maybe have one member others five.

This is simply the syntax for a variadic template. The Args are referred to as a template parameter pack. We’ll be allowed to traverse and apply transformations on template parameter packs, i.e. on a sequence of types.

template <class... Args>
class SoA;

Next we show how the language allows us to apply “functions” to types. The “function” is std::vector<.> and we’d like to apply it to each of the template parameters. The magic is in the .... The jargon is “pack expansion”, see https://en.cppreference.com/w/cpp/language/parameter_pack

What’s happening is that the compiler takes std::vector<Args> and creates a pattern (or “function”) std::vector<.>, next for each T in Args... it’ll substitute the T for the . in the pattern, i.e. where Args use to be. Then it concatenates the expressions, separated by commas.

Example: Tuple of Vectors #

We use pack expansion to have a tuple of vectors:

template <class... Args>
class SoA {
  std::tuple<std::vector<Args>...> data;
};

Example: Constructor #

We need a constructor. It’ll suffice to have a ctor which creates default initialized vectors of the same size. We’re faced with the same problem, we’d like to write

  data{std::vector<int>(n), std::vector<double>(n)}

but more generically. Same solution: std::vector<.>(n) is the “function”/pattern we’d like to apply; and therefore this is the syntax to use:

  SoA(size_t n) : data{std::vector<Args>(n)...} {}

Completing the SoA #

Finally, let’s add an accessor. Since the user is kind enough to tell us the index of the element of the struct they want, we can simply forward that information to std::get:

  template <size_t tuple_index>
  auto& get(size_t vector_index) {
    return std::get<tuple_index>(data)[vector_index];
  }