Is it possible to create and initialize an array of values using template metaprogramming?

I want to be able to create an array of calculated values (let's say for simplicity's sake that I want each value to be the square of it's index) at compile time using template metaprogramming. Is this possible? How does each location in the array get initialized?

(Yes, there are easier ways to do this without resorting to template meta开发者_开发知识库programming, just wondering if it's possible to do this with an array.)

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.

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 ints: 0, 1, 4, 9, 16.

A couple of notes:

1. 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 such structs. 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.]
2. 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 was I == 0 and we didn't subtract 1 from I 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 ith 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.

I really like j_random_hackers answer - its beautiful and short. With C++11, one can extend this to

template <int I>
struct squared {
  squared<I - 1> rest;
  static const int x = I * I ;
  constexpr int operator[](int const &i) const { return (i == I ?  x : rest[i]); }
  constexpr int size() const { return I; }
};

template <>
struct squared<0> {
  static const int x = 0;
  constexpr int operator[](int const &i) const { return x; }
  constexpr int size() const { return 1; }
};

This code is usable both at run time

  squared<10> s;

  for(int i =0; i < s.size() ; ++i) {
    std::cout << "s[" << i << "]" << " = " << s[i] << std::endl;
  }

as well as compile time

struct Foo {
  static const squared<10> SquareIt;
  enum { 
    X = 3,
    Y = SquareIt[ X ]
  };
};

int main() {
  std::cout << "Foo::Y = " << Foo::Y << std::endl;
}

and provides a nice and readable syntax.

You can have that for fixed-size arrays:

int a[] = { foo<0>::value, foo<1>::value, ... };

Arbitrarily sized arrays however can't be done without preprocessor meta-programming - Boost.Preprocessor can help here.

Another thing you might want to look into are compile-time sequences of integral constants, e.g. using Boost.MPL:

template<int n>
struct squares {
    typedef typename squares<n-1>::type seq;
    typedef typename boost::mpl::integral_c<int, n*n>::type val;    
    typedef typename boost::mpl::push_back<seq, val>::type type;
};

template<>
struct squares<1> {
    typedef boost::mpl::vector_c<int, 1>::type type;
};

// ...
typedef squares<3>::type sqr;
std::cout << boost::mpl::at_c<sqr, 0>::type::value << std::endl; // 1
std::cout << boost::mpl::at_c<sqr, 1>::type::value << std::endl; // 4
std::cout << boost::mpl::at_c<sqr, 2>::type::value << std::endl; // 9

(Note that this could probably be done more elegantly using MPLs algorithms)

If you're more curious about the compile-time subject the books "Modern C++ Design" (TMP basics) and "C++ Template Metaprogramming" (mainly MPL explained in depth) are worth looking into.

It may be more sensible to use specializations than an actual array. It gets messy though... I did this for a string hashing algorithm I did with template metaprogramming. Part of the algorithm used a large lookup table, which ended up looking like:

template <> struct CrcTab<0x00> { enum { value = 0x00000000 }; };
template <> struct CrcTab<0x01> { enum { value = 0x77073096 }; };
template <> struct CrcTab<0x02> { enum { value = 0xee0e612c }; };

And was accessed like this:

CrcTab<index>::value

The advantage of this is that you can use the results in the metaprogram, where you wouldn't be able to access the array.

For the value of the argument's square you don't even need to specialize. Warning: compiler not handy...

template <uint32_t N> struct Square { enum { value = N*N }; };

Actually this highlights the disadvantage of this approach, you can't index with a variable... only a constant.

I'm not sure whether you want to see it done or find a library that will just do it for you. I assume the former.

template<int N>
struct SqArr {
    static inline void fill(int arr[]) {
        arr[N-1] = (N-1)*(N-1);
        SqArr<N-1>::fill(arr);
    }
};

template<>
struct SqArr<0> {
    static inline void fill(int arr[]) { }
};

Now let's try to use this beast:

#include <iostream>
#include <algorithm>
#include <iterator>

using namespace std;

int main(int argc, char* argv[])
{
    int arr[10];
    SqArr<10>::fill(arr);
    cout << endl;
    copy(arr, arr+10, ostream_iterator<int>(cout, "\t"));
    cout << endl;
    return 0;
}

Note (confession): This isn't compile-time computation. To motivate that you can try to change the fourth line from SqArr<N-1>::fill(arr); to SqArr<N>::fill(arr); so the recursion is infinite, and you will see this compiles fine (when the compiler should in fact recurse indefinitely, or complain about the infinite recursion).