Is there a better way to fill array with precalculated values by templates (for using in runtime)?

Question

So, assume I have a template structure-function fib<i>::value. I want to get nth fibonacci number in runtime. For this i create array fibs[] = { fib<0>::value, ... , fib<maxN>::value }. Unfortunatelly, for some functions maxN can be very large and I can't fill it with hands only. So I writed some preprocessor directives to make task easier.

#define fib(x) (fib<(x)>::value)
#define fibLine_level_0(x) fib(5*(x) + 0), fib(5*(x) + 1), fib(5*(x) + 2), fib(5*(x) + 3), fib(5*(x) + 4)
#define fibLine_level_1(x) fibLine_level_0(2*(x) + 0), fibLine_level_0(2*(x) + 1)
#define fibLine_level_2(x) fibLine_level_1(2*(x) + 0), fibLine_level_1(2*(x) + 1)
#define fibLine_level_3(x) fibLine_level_2(2*(x) + 0), fibLine_level_2(2*(x) + 1)

#define cAarrSize(x) (sizeof(x) / sizeof(x[0]))

And I use it so:

int fibs[] = { fibLine_level_3(0) };

for (int i = 0; i < cAarrSize(fibs); i++)
    cout << "fib(" << i << ") = " << fibs[i] << endl;

The code that you may need:

template<int i>
struct fibPair{
    static const int fst = fibPair<i-1>::snd;
    static const int snd = fibPair<i-1>::fst + fibPair<i-1>::snd;
};

template<>
struct fibPair<0> {
    static const int fst = 0;
    static const int snd = 1;
};

template<int i>
struct fib {
    static const int value = fibPair<i>::fst;
};

But this code is really ugly. What to do to make it more beautiful?

Constraints: this code must be used in sport programming. That means - no third-party libraries and sometimes no C++11 (but it can be)

Answer 1

Fib structure can be rewritten as follows:

template <size_t i>
struct fib
{
    static const size_t value = fib<i - 1>::value + fib<i - 2>::value;
};

template <>
struct fib<0>
{
    static const size_t value = 0;
};

template <>
struct fib<1>
{
    static const size_t value = 1;
};

Compile-time array of the Fibonacci numbers can be calculated using C++11.

Edit 1 (changed the type of fib values).

Edit 2:

Compile-time generation of Fibonacci numbers array (based on this answer).

template<unsigned... args> struct ArrayHolder
{
    static const unsigned data[sizeof...(args)];
};

template<unsigned... args>
const unsigned ArrayHolder<args...>::data[sizeof...(args)] = { args... };

template<size_t N, template<size_t> class F, unsigned... args>
struct generate_array_impl
{
    typedef typename generate_array_impl<N-1, F, F<N>::value, args...>::result result;
};

template<template<size_t> class F, unsigned... args>
struct generate_array_impl<0, F, args...>
{
    typedef ArrayHolder<F<0>::value, args...> result;
};

template<size_t N, template<size_t> class F>
struct generate_array
{
    typedef typename generate_array_impl<N-1, F>::result result;
};

int main()
{
    const size_t count = 10;
    typedef generate_array<count, fib>::result fibs;

    for(size_t i = 0; i < count; ++i)
        std::cout << fibs::data[i] << std::endl;
}

All you need is to provide generate_array with the generation «function» (our fib struct).

Answer 2

Thanks to @nameless, for giving link to question, where I found answer by @MichaelAnderson for simple c++ (without new features). I used it and expanded for my own needs.

So, concept is simple, but a bit strange. We must produce recursive templated structure, where the first field is this same temlated structure with other argument.

template<size_t N>
struct FibList {
    FibList<N-1> previous;
    size_t value;
    FibList<N>() : value(fib<N>::value) {}
};

Let's try expand it a bit (just to see, what compiler will produce):

template<size_t N>
struct FibList {
    FibList<N-3> previous;
    size_t value_N_minus_2;
    size_t value_N_minus_1;
    size_t value_N;
};

So we can think that FibList is array and just cast it (that is weak point of my solution - I can't prove this now)

static const size_t maxN = 2000;
FibList<maxN> fibList;
size_t *fibArray = &fibList.value - maxN;

Or in another way:

size_t *fibArray = reinterpret_cast<size_t*>(&fibList);

Important: size of array is maxN+1, but standart methodic to get array size (sizeof(array) / sizeof(array[0]) will fail. Be pretty accurate with that.

Now we must stop recursion:

// start point
template<>
struct FibList<0> {
    size_t value;
    FibList<0>() : value(0) {}
};

// start point
template<>
struct FibList<1> {
    FibList<0> previous;
    size_t value;
    FibList<1>() : value(1) {}
};

Note, that swapping places of FibList<1> and FibList<0> will produce stack overflow in compiler.

And we must solve another problem - template recursion have limited depth (depends on compiler and/or options). But, fortunately, compiler have only depth limit, not memory limit for templates (well, yeah, memory limit is more bigger than depth limit). So we have obvious ugly solution - call fib<N> in series with step equal to depth limit - and we will never catch template depth limit about fib<N>. But we can't just write fib<500>::value not in runtime. So we got solution - write macro that will specialize FibList<N> using fib<N>::value:

#define SetOptimizePointForFib(N) template<>\
struct FibList<N> {\
    FibList<(N)-1> previous;\
    size_t value;\
    FibList<N>() : value(fib<N>::value) {}\
};

And we must write something like this:

SetOptimizePointForFib(500);
SetOptimizePointForFib(1000);
SetOptimizePointForFib(1500);
SetOptimizePointForFib(2300);

So we got really compile time precalc and filling static arrays of awesome lengths.