Is it possible to create and initialize an array of values using template metaprogramming?
It's called Static Table Generation in metaprogramming.
#include <iostream>
const int ARRAY_SIZE = 5;
template <int N, int I=N-1>
class Table : public Table<N, I-1>
{
public:
static const int dummy;
};
template <int N>
class Table<N, 0>
{
public:
static const int dummy;
static int array[N];
};
template <int N, int I>
const int Table<N, I>::dummy = Table<N, 0>::array[I] = I*I + 0*Table<N, I-1>::dummy;
template <int N>
int Table<N, 0>::array[N];
template class Table<ARRAY_SIZE>;
int main(int, char**)
{
const int *compilerFilledArray = Table<ARRAY_SIZE>::array;
for (int i=0; i < ARRAY_SIZE; ++i)
std::cout<<compilerFilledArray[i]<<std::endl;
}
We use explicit template instantiation and a dummy variable to force the compiler to fill the array with index squares. The part after I*I is the trick needed to recursively assign each array elements.
Although you can't initialise an array in-place like that, you can do almost the same thing by creating a recursive struct
:
template <int I>
struct squared {
squared<I - 1> rest;
int x;
squared() : x((I - 1) * (I - 1)) {}
};
template <>
struct squared<1> {
int x;
squared() : x(0) {}
};
Then later in your code you can declare:
squared<5> s;
and the compiler will indeed create a struct
containing 5 int
s: 0, 1, 4, 9, 16.
A couple of notes:
- My interpretation of the C++ standard is that it stops short of guaranteeing that this
struct
will be laid out identically to an array. While it is a POD type, and POD types are guaranteed to be laid out "contiguously" in memory (1.8/5) with the first member at offset 0 (9.2/17) and later members at higher addresses (9.2/12), and arrays are also laid out "contiguously" (8.3.4/1), the standard doesn't say that arrays are layout-compatible with suchstruct
s. However, any sane compiler will lay these objects out identically. [EDIT: As ildjarn points out, the presence of a user-defined constructor actually makes this class non-aggregate and therefore non-POD. Again, any sane compiler will not allow this to affect its layout.] - C++ requires that even an empty
struct
be at least 1 byte long. If it did not, we could go with a slightly cleaner formulation in which the base case of the recursion wasI == 0
and we didn't subtract 1 fromI
for the calculations.
It would be nice if we could place this struct
inside a union
with an array of the appropriate size, to make it easy to access the members. Unfortunately, C++ bans you from including an object in a union
if that object has a non-trivial constructor. So the easiest way to get at the i
th element is with a good old-fashioned cast:
squared<5> s;
cout << "3 squared is " << reinterpret_cast<int*>(&s)[3] << endl;
If you wanted, you could write an overloaded operator[]()
function template to make this prettier.
It is possible in c++0x using variadic templates. Here is example how to create a table of binomial coefficients:
//typedefs used
typedef short int index_t;
typedef unsigned long long int int_t;
//standard recursive template for coefficient values, used as generator
template <index_t n, index_t k> struct coeff {static int_t const value = coeff<n-1, k-1>::value + coeff<n-1, k>::value;};
template <index_t n> struct coeff<n, 0> {static int_t const value = 1;};
template <index_t n> struct coeff<n, n> {static int_t const value = 1;};
//helper template, just converts its variadic arguments to array initializer list
template<int_t... values> struct int_ary {static int_t const value[sizeof...(values)];};
template<int_t... values> int_t const int_ary<values...>::value[] = {values...};
//decrement k, pile up variadic argument list using generator
template<index_t n, index_t k, int_t... values> struct rec: rec<n, k-1, coeff<n, k-1>::value, values...> {};
//when done (k == 0), derive from int_ary
template<index_t n, int_t... values> struct rec<n, 0, values...>: int_ary<values...> {};
//initialise recursion
template<index_t n> struct binomial: rec<n, n+1> {};
To access elements use syntax like binomial<N>::value[k], where N is compile time constant and k is index ranging from 0 to N inclusive.