Writing Universal memoization function in C++11
c++, c++11, memoization
Solution
A compact one returning a lambda:
template <typename R, typename... Args>
std::function<R (Args...)> memo(R (*fn)(Args...)) {
std::map<std::tuple<Args...>, R> table;
return [fn, table](Args... args) mutable -> R {
auto argt = std::make_tuple(args...);
auto memoized = table.find(argt);
if(memoized == table.end()) {
auto result = fn(args...);
table[argt] = result;
return result;
} else {
return memoized->second;
}
};
}
In C++14, one can use generalized return type deduction to avoid the extra indirection imposed by returning `std::function`.
Making this fully general, permitting passing arbitrary function objects without wrapping them in `std::function` first is left as an exercise for the reader.
Problem
Looking for a way to implement a universal generic memoization function which will take a function and return the memoized version of the same? Looking for something like @memo (from Norving's site)decorator in python. ``` def memo(f): table = {} def fmemo(*args): if args not in table: table[args] = f(*args) return table[args] fmemo.memo = table return fmemo ``` Going more general, is there a way to express generic and reusable decorators in C++, possibly using the new features of C++11?