# Memoization via template

This is kind of follow up of this question on stack overflow...

I wrote the following to utilize memoization for functions that take a single parameter and return a value:

#include <iostream>
#include <map>
using namespace std;

template <class T, class R, R (*Func)(T)>
R memoized(T in) {
static std::map<T,R> memo;
typename std::map<T,R>::iterator found = memo.find(in);
if (found != memo.end()) { return found->second; }
std::cout << "not found" << std::endl; // only for demo
R res = Func(in);
memo[in] = res;
return res;
}

double test(double x){return x*x;}
double test2(double x){return x;}

int main() {
std::cout << memoized<double,double,test>(1) << std::endl;
std::cout << memoized<double,double,test>(1) << std::endl;
std::cout << memoized<double,double,test>(1) << std::endl;
std::cout << std::endl;
std::cout << memoized<double,double,test2>(1) << std::endl;
std::cout << memoized<double,double,test2>(1) << std::endl;
std::cout << memoized<double,double,test2>(1) << std::endl;

return 0;
}


output:

not found
1
1
1

1
1
1


It is a rather strong restriction that it works only for functions taking a single parameter, but thats ok for now. Is there anything else wrong with this approach?

PS: on purpose this is using only pre C++11

I would change memoized to work with a functor type and use a traits approach to deduce the return type and the argument type.

template <typename Functor>
typename Functor::R memoized(typename Functor::T in) {
using T = typename Functor::T;
using R = typename Functor::R;

static std::map<T,R> memo;
typename std::map<T,R>::iterator found = memo.find(in);
if (found != memo.end()) { return found->second; }
std::cout << "not found" << std::endl; // only for demo
R res = Functor()(in);
memo[in] = res;
return res;
}

struct Test1
{
using T = double;
using R = double;
R operator()(T x) { return x*x; }
};

struct Test2
{
using T = double;
using R = double;
R operator()(T x) { return x; }
};


My rationale for using a functor is that it simplifies user code.

int main() {
std::cout << memoized<Test1>(1) << std::endl;
std::cout << memoized<Test1>(1) << std::endl;
std::cout << memoized<Test1>(1) << std::endl;
std::cout << std::endl;
std::cout << memoized<Test2>(1) << std::endl;
std::cout << memoized<Test2>(1) << std::endl;
std::cout << memoized<Test2>(1) << std::endl;

return 0;
}

• hm.. the functions I want to use it for are partly legacy code. I think its a trade off whether it is worth wrapping them in a functor. However, I couldnt find out how to reduce the number of tempalte arguments on my own. Maybe some tempalte specialisation may help to accept both... – formerlyknownas_463035818 Sep 20 '16 at 20:12
• @tobi303. I think wrapping legacy code with a function is worth it. It obviates the need to repeat the type of T and R every time you call the function. – R Sahu Sep 20 '16 at 20:15
• I was wondering if this also works across compilation units, ie if I can be sure that there will always be a single template instantiation for each function – formerlyknownas_463035818 Sep 20 '16 at 20:20
• @tobi303, are you worried about size of DLLs/EXEs? – R Sahu Sep 20 '16 at 20:22
• no, I am worried about getting two instantiations with seperate static maps when it actually should be the same – formerlyknownas_463035818 Sep 20 '16 at 20:24