Geek Answers Handbook

Static variable in template function is not unique to template instance

I am trying to learn about memoization using C ++ along with boost and the C ++ 11 specification. However, I ran into a problem that I am having problems wrapping my head around. I follow the tutorial here: remembering in C and the tutorial says that you can generalize by remembering recursive functions using templates and lambda functions. The tutorial also lists the functions of the recursive factorial and fibonacci for use with the template. However, the manual uses only the fibonacci function.

I wrote a test program to see how it all works, and to do the same memoized fibonacci AND factorial function in the same mode. The fact is that the memoization template uses a static map to store cached values, and it seems that the map is not unique to each instance of memoized functions. Is this expected? What to do to make the map unique for each instance of the template? Before I started using the features of C ++ 11, I tried to create a template class that adopted a boost function to encapsulate this process. Will a static map be unique in the template class?

The main logic for creating noticed functions

// Template function to create memoized versions of recursive lambda functions
template<typename inType, typename outType>
std::function<outType(inType) > memoize(std::function<outType(inType) > foo) {
   return [foo](inType n) {
      static std::map<inType, outType> memo;

      outType ret;
      if (memo.count(n) > 0) {
         cout << "Cache Hit" << endl;
         ret = memo[n];
         return ret;
      }
      ret = foo(n);
      memo[n] = ret;
      return ret;
   };
}

// Recursive lambda fibonacci function
std::function<int(int) > fibonacci_r = [](int n) {
   if (n <= 1) {
      return n;
   } else {
      return fibonacci_r(n - 1) + fibonacci_r(n - 2);
   }
};

// Recursive lambda factorial function
std::function<int(int) > factorial_r = [](int n) {
   if (n == 0) {
      return 1;
   } else {
      return n * factorial_r(n - 1);
   }
};

Logic for testing memorable functions

int position = 7;
cout << "Fibonacci:" << endl;
cout << "Non Memo Fibonacci" << endl;
cout << position << "-> " << fibonacci_r(position) << endl;
cout << "Memo Fibonacci" << endl;
fibonacci_r = memoize(fibonacci_r);
cout << position << " -> " << fibonacci_r(position) << endl;

cout << endl;

cout << "Non Memo Factorial" << endl;
cout << position << " -> " << factorial_r(position) << endl;
cout << "Memo Factorial" << endl;
factorial_r = memoize(factorial_r);
cout << position << " -> " << factorial_r(position) << endl;

Exit

Fibonacci:
Non Memo Fibonacci
7-> 13
Memo Fibonacci
Cache Hit
Cache Hit
Cache Hit
Cache Hit
Cache Hit
7 -> 13

Non Memo Factorial
7 -> 5040
Memo Factorial
Cache Hit
7 -> 13

, Memo . , , 1 . 7! 13, 13 - 7 memoacci memo.

+4
1

... , memoized . ?

, , , instance wrt to static , . std::function<outType(inType)> . , , map.

:

template<typename inType, typename outType>
std::function<outType(inType) > memoize(std::function<outType(inType) > foo) {
   static int i = 0;
   ++i;
   return [foo](inType n) {
      static std::map<int, std::map<inType, outType>> memo;
      auto& m = memo[i];
      outType ret;
      if (m.count(n) > 0) {
         cout << "Cache Hit" << endl;
         ret = m[n];
         return ret;
      }
      ret = foo(n);
      m[n] = ret;
      return ret;
   };
}

, map. :

auto f1 = memoize(factorial_r);
auto f2 = memoize(factorial_r);

f1 f2 map. , , .

+2

More articles:


All Articles