Exploring constexpr and templates for compile-time evaluation

Recently I needed to build a large lookup table that could be cached and reused in a larger program. I wanted to explore how we could fill-in a data structure made up of std::arrays of different sizes using constexpr.

Think of a structure that looks like a Christmas tree, e.g. Pascal's triangle. Each row size in the triangle corresponds to it's height in the triangle and the columns in the row are made up of the Binomial coefficients (nCk) of the row size.

For example, if row size is 4, we will have 4C1, 4C2,4C3 and 4C4 as the column values.

Since each row has different size, each row array is essentially a different type.

I am using a Tuple to collect these different types and pass the Tuple back to run-time context.

In summary, the goal is to generate a structure that looks like below at compile-time, N is known at compile-time.

std::tuple<std::array<int,1>,std::array<int,2>,std::array<int,3>,......std::array<int,N>>

Given an initial size of the Triangle, I use std::make_index_sequence to generate a compile-time sequence of integers upto the given size.

The index sequence is then passed to a function template that accepts a parameter pack and the integers can then be deduced.

The row generation function template accepts a size as non-type-template-parameter (NTTP) to initialize an array of required size.

As with anything in C++, we can do the same thing 5 different ways in decreasing order of readability, I present two versions of row generation function in the example.

One uses an old for loop to generate the Bionomial coefficients and the other uses c++20 variadic pack expansion (with comments) that replaces the loop.

The generated assembly shows that compiler has calculated the entire Triangle at compile-time and the main() does not have a call to gen_triangle() at runtime.

Compiler Explorer