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.)
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).
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, 16, 25.
A couple of notes:
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.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.
It is possible with 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.
This method is from Static Table Generation.
And I feel obligated to quote Bryan O'Sullivan:
Metaprogramming is the language feature that helps you write code that you won't be able to understand once the cocaine wears off.