Recently I’ve read an article Efficient Memoization using Partial Function Application. Author explains function memoization using partial application. When I was reading the article, I thought “Hmmm, can I come up with a more general solution?” And as suggested in comments, one can use variadic templates to achieve it. So here is my version.

First let’s do it in a more object-oriented way: we define a template class `Memoizator`

with 2 parameters: a return value type and a list of argument’s types. Also we incapsulate a lookup map and will use C++11’s std::tuple to represent an arguments set.

Good, but what about computing n-th Fibonacci number using memoization? It’s not possible with a current version of `Memoizator`

since it uses a separate map for each instance even if function is the same. It looks inefficient to store a separate lookup map for each instance of the same function. We’ll fix it by creating a static storage for maps accessed by a function address:

Now let’s compare the memoized version against the regular one. If we compute the 42th fibonacci number using simple recursive version (with exponential time complexity), we’d get

Now the memoized one (from the source above):$ time ./a.out267914296 real 0m5.314s user 0m5.220s sys 0m0.020s

$ time ./a.out267914296 real 0m0.005s user 0m0.004s sys 0m0.004s

Moreover, our memoization reduced time complexity from exponential to linear.

**UPD**: you can take a look at another implementation here: General-purpose Automatic Memoization for Recursive Functions in C++11