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.

The code is as follows:

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

$ time ./a.out 
267914296

real    0m5.314s
user    0m5.220s
sys     0m0.020s

Now the memoized one (from the source above):

$ time ./a.out 
267914296

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