Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Recursive templates don't work as expected with static variables

The code

#include <iostream>
using namespace std;

template<int n> struct Fibo { static int x; };
template<> int Fibo<0>::x = 1;
template<> int Fibo<1>::x = 1;
template<int n> int Fibo<n>::x = Fibo<n-1>::x + Fibo<n-2>::x; //marked line

int main() {
    cout << Fibo<5>::x << endl;
    cout << Fibo<4>::x << endl;
    cout << Fibo<3>::x << endl;
    cout << Fibo<2>::x << endl;
    cout << Fibo<1>::x << endl;
    cout << Fibo<0>::x << endl;

    return 0;
}

outputs

0
0
1
2
1
1

in VC++. (According to user M M. it compiles as expected in gcc). When the compiler gets to the marked line with n=5 it doesn't compile that same line again for n=4, but just treats Fibo<4>::x as if it were declared with

template<> int Fibo<4>::x; // x defaults to 0

Why is that? Why does it work as expected when using

template<int n> struct Fibo { enum { x = Fibo<n-1>::x + Fibo<n-2>::x }; };
template<> struct Fibo<0> { enum { x = 1 }; };
template<> struct Fibo<1> { enum { x = 1 }; };

instead, but not with a static variable? And how do you fix the first code (without enum)?

like image 227
string QNA Avatar asked Oct 13 '13 12:10

string QNA


2 Answers

The Standard is very clear on this:

14.7.1 Implicit instantiation [temp.inst]

9 The implicit instantiation of a class template does not cause any static data members of that class to be implicitly instantiated.

All the calls in main() to your Fibo<n>::x for n > 1, are explicit instantiations, that through the Fibonnaci recursion will implicitly instantiate Fibo<n-1> and Fibo<n-2> but not their members x. This means that at those points, the static members x will be evaluated to their default initialization of 0. For n=1 and n=0, the compiler will see the explicit initialization values of 1. So effectively, you get the following computation

Fibo<5>::x --> Fibo<4>::x + Fibo<3>::x --> 0 + 0 = 0
Fibo<4>::x --> Fibo<3>::x + Fibo<2>::x --> 0 + 0 = 0
Fibo<3>::x --> Fibo<2>::x + Fibo<1>::x --> 0 + 1 = 1
Fibo<2>::x --> Fibo<1>::x + Fibo<0>::x --> 1 + 1 = 2
Fibo<1>::x --> 1
Fibo<0>::x --> 1

You need to instantiate the static member x before evaluating the Fibonacci recursion. You can do this through a static const int or enum member x, or through a function (possibly constexpr in C++11) as shown by @Jarod42.

like image 67
TemplateRex Avatar answered Sep 23 '22 12:09

TemplateRex


I'm not sure if the initialization order of the static variables of template<int n> int Fibo<n>::x = Fibo<n-1>::x + Fibo<n-2>::x; is specified...

You may write this:

template <int N> struct Fibo { int operator()() const { static int x = Fibo<N - 1>()() + Fibo<N - 2>()(); return x; } };

template <> struct Fibo<1> { int operator()() const { static int x = 1; return x; } };
template <> struct Fibo<0> { int operator()() const { static int x = 1; return x; } };

The dependencies are respected.

[Edit]

In a case where the value may be modified (according to your comment), you may use similar technique but returning reference:

template <int N> struct Fibo {
private:
    int& operator()() { static int x = Fibo<N - 1>()() + Fibo<N - 2>()(); return x; }

public:
    int operator()() const { return const_cast<Fibo&>(*this)(); }
    // This change Fibo<0> and Fibo<1> and then update value up to Fibo<N>.
    int operator(int fibo0, int fibo1) {
        int n_1 = Fibo<N - 1>()(fibo1, fibo2);
        (*this)() = n_1 + Fibo<N - 2>()();
    }
};

template <> struct Fibo<1> {
private:
    int& operator()() { static int x = 1; return x; }
public:
    int operator()() const { return const_cast<Fibo&>(*this)(); }
    void operator(int fibo0, int fibo1) { Fibo<0>()(fibo0); (*this)() = fibo1; }
};

template <> struct Fibo<0> {
private:
    int& operator()() { static int x = 1; return x; }
public:
    int operator()() const { return const_cast<Fibo&>(*this)(); }
    void operator(int fibo0) { (*this)() = fibo0; }
};
like image 27
Jarod42 Avatar answered Sep 21 '22 12:09

Jarod42