Recursive patterns do not work as expected with static variables

Question

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; } 

exits

 0 0 1 2 1 1 

in VC ++. (According to user M M., it compiles, as expected, in gcc). When the compiler hits the marked line with n=5 , it does not compile the same line again for n=4 , but simply processes Fibo<4>::x , as if it were declared using

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

Why? Why it works, 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 )?

Answer 1

The standard is very clear:

14.7.1 Implicit instance creation [temp.inst]

9 Implicit creation of a class template does not cause static data members of this class to be implicitly created.

All calls to main() on your Fibo<n>::x for n > 1 are explicit instances that through Fibonnaci recursion will implicitly create instances of Fibo<n-1> and Fibo<n-2> , but not their members x . This means that at these points, static x members will be evaluated by default, with a default of 0 . For n=1 and n=0 compiler will see explicit initialization values ​​of 1. Thus, you get the following calculation

 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 x member or through a function (possibly constexpr in C ++ 11), as @ Jarod42 shows.

Answer 2

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

You can 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; } }; 

Dependencies are respected.

[change]

In the case where the value can be changed (according to your comment), you can use a similar technique, but returning the link:

 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; } };