Static Variable in Template Function Doesn't Seem Unique to Template Instance

Question

I'm trying to learn about memoization using C++ along with boost, and the C++11 spec. However I've run into a problem that I'm having trouble wrapping my head around. I'm following a tutorial here: Memoization in C and the tutorial says that you can generalize the memoization of recursive functions using a templates and lambda functions. The tutorial also lists recursive factorial and fibonacci functions to use with the template. However, the guide only uses the fibonacci function.

I wrote a test program to see how this all worked and make both a memoized fibonacci AND factorial function in the same run. Thing is, the memoization template uses a static map to store cached values and it seems like the map isn't unique to each instance of the memoized functions. Is this expected? What should I do to make the map unique to each template instance? Before I started using C++11 features, I had tried to create a template class that accepted a boost function to encapsulate this process. Would the static map be unique in a template class instead?

Main Logic for Creating Memoized 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 Memoized 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;

Output

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

At the tail end of the output you can see that the Memo factorial has a cache hit. However, I don't think it should have only 1 cache hit. Either way, 7! isn't 13 and 13 is the cache value for 7 under the fibonacci memo lambda.

Answer 1

When you write

...it seems like the map isn't unique to each instance of the memoized functions. Is this expected?

you seem to forget that the instance wrt to static variables is based on the types, not on the value of the parameters. The type std::function<outType(inType)> is the same in both cases. Obviously, when there is only one instance you also have only one static map.

---

A partial solution could be this:

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

But note that now each call will generate its own independent map. If you do:

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

then f1 and f2 will not share the same map. This also means that if you do this very often, you might end up using a lot of memory.