C++ memoization实现Fibonacci函数：map与vector执行时间差异问询

Great question—this is a super common gotcha when implementing memoization with different C++ containers. Let’s break down exactly why your vector version timed out while the map one sailed through:

1. The Most Likely Culprit: Linear Lookups in the Vector #

If your vector implementation stored pairs like (n, fib(n)) and you scanned the entire vector every time to check if a value was already cached, that’s a massive performance drain. For each lookup, you’d iterate through every previously computed entry—this is O(k) time where k is the number of cached values. As n grows, this linear search gets exponentially slower with every recursive call, which is exactly why you hit time limits.

Compare that to std::map (a balanced binary search tree) or std::unordered_map (a hash table): both give you O(log k) or average O(1) lookup times respectively. For large n, this difference in lookup speed is the main reason your map version passed.

2. Dynamic Resizing Overhead #

If you used the vector’s index to directly map to n (e.g., vector[i] = fib(i)), but resized the vector on the fly as you computed larger values, you might have run into repeated reallocation costs. Every time a vector needs more space, it allocates a new larger memory block, copies all existing elements over, and frees the old block. For very large n, this can happen dozens of times, adding up to significant overhead.

Maps don’t have this problem—each element lives in its own separate node, so inserting new values never triggers bulk copies of existing data.

3. How to Fix the Vector Version #

You can make your vector-based memoization faster than the map version by using the index-to-n mapping correctly:

• Preallocate the vector to the maximum n you expect (if you know it upfront) with a sentinel value (like -1) to mark uncomputed entries.
• When calculating fib(k), check if vector[k] != -1. If so, return it immediately. If not, compute the value and store it directly in vector[k].

This gives you O(1) lookups and avoids linear searches or repeated resizing. Here’s a quick example snippet:

#include <vector>
using namespace std;

long long fib(int n, vector<long long>& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib(n-1, memo) + fib(n-2, memo);
    return memo[n];
}

// Usage:
vector<long long> memo(n_max + 1, -1);
long long result = fib(target_n, memo);

This vector approach will outperform a map because of its contiguous memory layout (better cache locality), making value access faster than jumping between scattered map nodes.

内容的提问来源于stack exchange，提问作者samsung gather