为什么这段代码打印垃圾？

Question

这是一种带有缓存的简单递归方法，因此不会一遍又一遍地重新计算数字。我确实看到它有效，但现在它坏了并且打印垃圾。我试过恢复到工作版本，但找不到任何可能破坏它的区别。

为什么它停止工作了？

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int Fibonacci_vector(int n) {
    static vector<int> cache(2, 1);
    cache.reserve(n);
    if (cache[n] == 0) {
        cache[n] = Fibonacci_vector(n-1) + Fibonacci_vector(n-2);
    }
    return cache[n];
}

int main() {
    cout << Fibonacci_vector(4);
}

更新 哎呀，我真是太蠢了，简直让人心疼。我已经将 if (n > cache.size()) { cache.resize(n); } 更改为 cache.reserve(n); 并且 当然 它破坏了一切！伙计们，为我的愚蠢感到抱歉。

Answer 1

您需要检查该元素是否存在。像这样更改代码：

int Fibonacci_vector(int n) {
    static vector<int> cache(2, 1);
    if (n >= cache.size()) {
        cache.push_back(Fibonacci_vector(n-1) + Fibonacci_vector(n-2));
    }
    return cache[n];
}

Answer 2

1. 有std::vector::reserve and there's also std::vector::resize. They do different things.

   ^{cache[n] 在这两种情况下仍然超出范围访问（在 std::vector::resize 的情况下是最后一个元素）}

2. 计算条件不应该尝试访问任何缓存数据（超出范围），它只需要比较if(n >= cache.size()).

3. 仅当满足上述条件时才需要调用cache.resize(n + 1)，因此将其放在if子句中。