Skip to content

Instantly share code, notes, and snippets.

@artsobolev
Last active February 15, 2020 16:53
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save artsobolev/5271223 to your computer and use it in GitHub Desktop.
Save artsobolev/5271223 to your computer and use it in GitHub Desktop.
#include <iostream>
#include "Memoizator.hpp"
int f(int n) {
if (n == 0) return 0;
if (n <= 2) return 1;
auto mf = memoize(f);
return mf(n-1) + mf(n-2);
}
int main() {
std::cout << f(42) << std::endl;
return 0;
}
#ifndef MEMOIZATOR
#define MEMOIZATOR
#include <tuple>
#include <map>
template<class R, class... Args>
class Memoizator {
typedef std::tuple<Args...> tuple;
typedef std::map<tuple, R> map;
public:
typedef R (*function)(Args...);
Memoizator(function f) : f(f) {}
R operator()(const Args& ...args) {
map &m = maps[f];
auto it = m.find(std::forward_as_tuple(args...));
if (it != m.end()) {
return it->second;
}
R value = f(args...);
m[std::make_tuple(args...)] = value;
return value;
}
private:
function f;
static std::map<function, map> maps;
};
template<class R, class... Args>
std::map<typename Memoizator<R, Args...>::function, typename Memoizator<R, Args...>::map>
Memoizator<R, Args...>::maps = std::map<function, map>();
template<class R, class... Args>
Memoizator<R, Args...> memoize(R (*f)(Args...)) {
return Memoizator<R, Args...>(f);
}
#endif // MEMOIZATOR
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment