FibMain.cpp

#include <iostream>
#include <functional>
#include <cstdio>
#include <ctime>

#include "Memoize.h"

using namespace std;

int main()
{
	function<int(int)> fib;
	
	function<int(int)> f = [&](int x)
	{ 
		if (x==0) 
			return 0;
		else if (x==1)
			return 1;
		else
			return fib(x-1) + fib(x-2); 
	};
	
	//Normal Fib
	fib = f;
	
	auto start = clock();
	cout << "Start Fib 37" << endl;
	cout << fib(37) << endl;
	cout << "End" << endl;
	cout << "time: " << ( clock() - start ) / (double) CLOCKS_PER_SEC << endl;
	
	//Memoized Fib
	fib = Memoize::Memoize(f);
	
	start = clock();
	cout << "Start Fib 37" << endl;
	cout << fib(37) << endl;
	cout << "End" << endl;
	cout << "time: " << ( clock() - start ) / (double) CLOCKS_PER_SEC << endl;
	return 0;
}

Memoize.h

#ifndef MEMOIZE_H
#define MEMOIZE_H

#include <functional>
#include <map>
#include <tuple>

namespace Memoize {
	
	using namespace std;
	
	template< class R, class... Args >
	using mt = map< tuple< Args... >, R >;
	
	template< class R, class... Args >
	function< R( Args... ) > Memoize( function< R( Args... ) > &originalFunction )
	{
		return [ & ]( Args... args ) mutable { 
			static mt< R, Args... > memoizeMap = mt< R, Args... >();
			
			auto index = tuple< Args... >( args... );
			
			auto it = memoizeMap.find( index );
			if ( it != memoizeMap.end() ) {
				return it->second;
			} else {
				auto res = originalFunction( args... );
				memoizeMap[ index ] = res;
				return res;
			} 
		};
	}		
}

#endif /* MEMOIZE_H */