tobi303 tobi303 - 2 months ago 31
C++ Question

Why does template argument deduction/substitution fail here?

I am trying to write a simple template that I can use for memoization with functions taking a single argument:

#include <map>

template <typename F,typename OUT,typename IN>
OUT memoization(IN in){
static std::map<IN,OUT> memo;
static typename std::map<IN,OUT>::iterator found = memo.find(in);
if (found != memo.end()) { return found->second; }
OUT res = F(in);
memo(in) = res;
return res;
}

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

int main(){
for (int i=0;i<5;i++){
memoization<test,double,double>(i*0.5);
}
}


But i get the error:


error: no matching function for call to 'memoization(double)'

note: candidate is:

note: template OUT memoization(IN)

note: template argument deduction/substitution failed:


Why does this fail to compile?

Actually I dont understand why template argument deduction/substitution is taking place at all when I specify all the template parameters.

I am using gcc version 4.7.2 (no C++11 enabled)

Answer

Your function template takes three type arguments:

template <typename F,typename OUT,typename IN> 
OUT memoization(IN in) { ... }

You're passing in test for F. test isn't a type, it's a value. Also, the expression F(in) in your function template is wrong for the same reason.


This approach in general is pretty flawed as it seems pretty backwards from what actually is going on. Namely, it's the function that's being memoized, not a value. Also requiring the function value at compile time is pretty limiting.

A better approach is to treat memoization as a decorator. That is:

template <class F>
Memoized<F> memoize(F f) {
    return {f};
}

such that:

auto memo_test = memoize(test);
memo_test(0); // performs computation
memo_test(0); // doesn't perform computation
memo_test(0); // ditto

I leave the implementation of Memoized<T> as an exercise.

Comments