//C++11
#include <functional>
#include <map>

template<typename... Args, typename T,
	typename R = std::result_of_t<std::decay_t<T>(Args...)>>
auto memoize(T&& f) -> std::function<R(Args...)>
{
	//use "move capture" in C++14
	auto const p = new std::map<std::tuple<Args...>, R>();
	return ([f, p](Args... args) -> R {
		auto&& t = std::make_tuple(args...);
		auto it = p->find(t);
		if ( it == p->end() ) { it = p->emplace(it, std::move(t), f(std::forward<Args>(args)...)); }
		return it->second;
	});
}

//---------------
// sample

#include <iostream>
using namespace std;

// Fibonacci
static auto fib = memoize<int>([](int n) {
	cout << "fib(" << n << ")" << endl;
	if ( n == 0 ) return 0;
	if ( n == 1 ) return 1;
	return fib(n - 1) + fib(n - 2);
});

// function with arity 3
static auto g = memoize<double, double, double>([](double x, double y, double z) {
	cout << "g" << endl;
	return x + y + z;
});

int main() {
	cout << fib(30) << endl;
	//invoke fib(n) only once for each n (= 30, 29, ..., 2, 1)

	for (int i = 0; i < 2; ++i) {
		cout << g(1.0, 2.0, 3.0) << endl;
	}
}