#include <iostream>
#include <iomanip>
#include <map>

// memoizer.  
//  usage: m(f, a)
//  returns f(a), memoizing the result.  f should invoke 'm(f, x)' to recurse.
template <
    class Result, 
    class Arg,
    class ResultStore = std::map<Arg, Result>
>
class memoizer1{
public:
    template <class F>
    const Result& operator()(F f, const Arg& a){
        typename ResultStore::const_iterator it = memo_.find(a);
        if(it == memo_.end()) {
            it = memo_.insert(make_pair(a, f(a))).first;
        }
        return it->second;
    }
private:
    ResultStore memo_;
};

// driver function, forward declaration
int fib(int);

namespace {
    int total_ops = 0;

    // implementation
    int fib_(int n){
        ++total_ops;
        if(n == 0 || n == 1) 
            return 1;
        else
            // recurse into driver, not implementation, to ensure 
            // intermediate results are memoized.
            return fib(n-1) + fib(n-2);
    }
}

// driver function
int fib(int n)
{
    static memoizer1<int,int> memo;
    return memo(fib_, n);
}

using namespace std;

int main(){
    total_ops = 0;
    cout << "fib(8) == " << fib(8) << endl;
    cout << "cost was " << total_ops << endl;
    total_ops = 0;
    cout << "fib(9) == " << fib(9) << endl;
    cout << "cost was " << total_ops << endl;
}

fib(8) == 34
cost was 9
fib(9) == 55
cost was 1