为什么模板参数 deduction/substitution 在这里失败了？

Question

我正在尝试编写一个简单的模板，我可以将其用于带有单个参数的函数的记忆：

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

但我收到错误消息：

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

note: candidate is:

note: template OUT memoization(IN)

note: template argument deduction/substitution failed:

为什么编译失败？

实际上，当我指定所有模板参数时，我根本不明白为什么模板参数 deduction/substitution 会出现。

我正在使用 gcc 4.7.2 版（未启用 C++11）

PS: 模板中的错误比我最初意识到的要多得多，但我保持原样...

Answer 1

你的函数模板有三个类型参数：

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

您将 test 传递给 F。 test 不是类型，而是值。另外，由于同样的原因，函数模板中的表达式 F(in) 也是错误的。

总的来说，这种方法有很大的缺陷，因为它看起来与实际情况相去甚远。也就是说，它是被记忆的函数，而不是一个值。在编译时要求函数值也是非常有限的。

更好的方法是将记忆化视为装饰器。即：

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

这样：

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

我将 Memoized<T> 的实施留作练习。

Answer 2

Why does template argument deduction/substitution fail here?

~~因为有 3 个模板参数和只有一个实际参数，所以其中两个是不可推导的（这是一个词吗？）。~~

b。存在语法错误。模板参数 F 是一种类型，而不是可调用对象。

如果这必须在 c++11 之前的环境中工作，boost 的 result_of 可以提供帮助：

#include <map>         
#include <boost/utility/result_of.hpp>

//
// now that template arguments are all used when collecting function
// arguments, the types F and IN can be deduced.
//    
template <typename F,typename IN> 
typename boost::result_of<F(IN)>::type memoization(F f, IN in)
{
  typedef typename boost::result_of<F(IN)>::type OUT;
    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, i*0.5);
    }
}

Answer 3

答案已经得到了令人满意的答案，但是我很好奇我是否可以让它与 C++11 之前的版本一起工作。实际上可以将函数指针作为模板参数传递，只需在模板参数上指定它而不是让它期望类型参数：

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

输出：

not found
1
1
1

not found
1
1
1

仍然不确定这是否是一个好方法，但它似乎有效。

为什么模板参数 deduction/substitution 在这里失败了？

Why does template argument deduction/substitution fail here?

c++

templates

memoization