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

Question

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 metaprogramming, just wondering if it's possible to do this with an array.)

Hussy

You might be better off with preprocessor metaprogramming. I don't think C++ has enough workarounds. – Canonicals

Or, my personal favorite for compile-time structured data construction, use a macro assembler! – Canonicals

From IBM 'The art of Metaprogramming' the author gives perl script to to generate his table. Perhaps not what you are looking for, but someone might appreciate it. – Aurora

Answer 1

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.

Hett

squared<> is not a POD type in C++03 since it has a user-declared constructor (§8.5.1/1). Does your rationale still hold in light of this? – Gap

@ildjarn: Good point. I think that means the guarantees I mention are lost, but as I'm already relying on non-standard "sane compiler" behaviour for layout compatibility, this doesn't introduce much additional weakness into the solution. I don't think it will cause difficulties in practice. – Hett

why not write code as: template <int I> struct squared { squared<I - 1> rest; int x; squared() : x((I) * (I )) {} }; template <> struct squared<0> { int x; squared() : x(0) {} }; – Sybaris

why a recursive struct not a recursive class? – Sybaris

@MuhammadAnnaqeeb: You could do it that way, but the indexing I've chosen makes squared<42> have the same size and semantics as int some_array[42]. Regarding class vs. struct: struct is equivalent in every way to class, except that the default access is public: instead of private:. If you only want to have public: members, it saves typing to write struct XYZ { instead of class XYZ { public:. – Hett

just what i was looking for, but can anyone tell how this affects compilation times? I would think it is quite exhausting for very large I, isn't it? Just want to know whether or not it is a good idea for me to implement this in a project with reeaally large arrays. – Garbers

@Julian: I suspect it's terrible for compilation times, and I wouldn't be surprised if there are other gotchas -- for example, code that loops over all elements might not be optimised as well as code that loops over normal arrays. I would avoid using it in practice. – Hett

Answer 2

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.

Unseal

Note that you'll need to add an explicit definition for Table<N, 0>::dummy – Vapor

As of Nov. 2015 the wikipedia entry is missing. There is a relevant talk however : en.wikipedia.org/wiki/… – Undercast

Answer 3

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.

Raceme

At first it wasn't clear to me if this was a recursive struct like the other answers or not. You might want to mention the int_t const int_ary<values...>::value[] = {values...}; line specifically. – Quechua

Answer 4

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.

Leucotomy

Answer 5

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.

Logjam

Answer 6

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.

Ghat

I want a lookup table similar to what you have, but I think I'd be better off just generating the array in a .h file using a scripting language. Thanks, though, this is interesting. – Hussy

Answer 7

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).

Illuse

You're actually creating the array first, but this is probably the only way it can be done... – Hussy

This is not initialization. Also, you don't need to explicitly specify the array-size if you'd prevent the decay into pointers by using references (template<size_t n> void fill(int (&arr)[n]) ...). – Logjam

Yes, I noticed after I posted this and played a little more with the code that it isn't compile-time at all. After trying my hands at this I see templates alone just can't do the trick of manipulating an array. It's not as easy as computing a value. – Illuse

Although this isn't quite initialisation, if you declared arr[] without an initialiser it will be just as efficient -- which is as efficient as compile-time initialisation could be, if it existed. (Currently you're setting every element to 0 first, which is a waste of time.) – Hett