arrays - C++ Memoization understanding

Question

I was trying to understand how memoization works in C++, so I looked at an example of memoization used in Fib. sequence.

std::map<int, int> fibHash;

int memoized_fib (int n)
{
    std::map<int, int>::iterator fibIter = fibHash.find(n);
    if( fibIter != fibHash.end() ) return *fibIter;

    int fib_val;
    if( n <=1 )    fib_val = 1;
    else           fib_val = memoized_fib ( n-1 ) + memoized_fib ( n-2 );

    fibHash[ n ] = fib_val;
    return fib_val;
}

I was a little confused with how the fibHash[n] works. Does it just hold the individual values of each fib(#)? Also, the iterator traversess through the index to look for the correct value in the table and returns that? For example fib(6) = find fib(5) and fib(4), already stored and just add them?

Answer 1

What you are saying is essentially correct.

"Does it [fibHash] just hold the individual values of each fib(#)?"

Yes, exactly. The values are filled in as they are calculated (with fibHash[ n ] = fib_val;). Lower fib values are used to calculate the higher ones.

The fibHash map maps X to fib(X), plain and simple.

The advantage of doing it this way is that if you calculate fib(20) followed by fib(21) and fib(23), then perhaps fib(15), you only have to calculate the intermediate values once.

The cost for this speedup is the memory of storing the values in fibHash.