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

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);
}

更新 Jeez,我是如此愚蠢,只是伤害.我已经改变了if (n > cache.size()) { cache.resize(n); }对cache.reserve(n);和当然它打破了一切!伙计们,对不起我的愚蠢.

Answer 1

1. 还有std::vector::reserve,也有std::vector::resize.他们做不同的事情.

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

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

3. cache.resize(n + 1)只有在满足上述条件时才需要调用,所以将它放在if-clause中.