为什么在这个实现中 push_back 保留了 2 * capacity + 1 而不是 2 * capacity？

Question

我期待在实施vector上https://www.cs.odu.edu/~zeil/cs361/sum18/Public/vectorImpl/index.html。

在 1.3.1 下，它显示：

if( theSize == theCapacity ) ?
    reserve( 2 * theCapacity + 1 ); ?

我想知道，为什么它是保留2 * theCapacity + 1而不是2 * theCapacity？

在 中std::vector，当向量的大小等于容量时，它只是将容量加倍，并且您正在尝试执行追加操作。我不太明白+1这里的目的。

Answer 1

C++ 标准没有指定std::vector需要如何增加大小。加倍是一种常见的实现¹，可能是因为懒惰而不是其他任何东西。该+1是有太多的目的是避免的零能力的问题，如果它可以发生vector::reserve被称为具有零的说法，如果您的实现构建一个零容量，或std::vector默认。

¹我个人认为使用斐波那契数列增加容量可能更自然，尽管我从未遇到过std::vector这样做的实现。