为什么Vector的size()和capacity()在push_back()之后不一样

Question

我刚开始学习向量，对 size() 和 capacity() 有点困惑我对他们两个都知之甚少。但是为什么在这个程序中两者是不同的呢？甚至 array(10) 也在为 10 个元素腾出空间并用 0 进行初始化。

添加前array.push_back(5)

所以 array.size(); 是 10 就可以了。

所以 array.capacity(); 是 10 就可以了。

添加后array.push_back(5)

所以 array.size(); 是 11 没问题 (already 10 time 0 is added and then push_back add one more element 5 )。

所以 array.capacity(); 是 15 为什么？ ( is it reserving 5 blocks for one int? ).

#include <iostream>
#include <vector>
int main(){
    std::vector<int> array(10); // make room for 10 elements and initialize with 0
    array.reserve(10);    // make room for 10 elements
    array.push_back(5);
    std::cout << array.size() << std::endl;
    std::cout << array.capacity() << std::endl;
    return 0;
}

Answer 1

为了效率，每次添加元素时，它都不必扩展底层数据结构。即不必每次都调用 delete/new。

Answer 2

std::vector::capacity不是它的实际大小（由size()返回），而是实际内部分配的大小。

换句话说，它是在需要另一个 re-allocation 之前可以达到的大小。

它不会在您每次执行 push_back 时增加 1，以便不对每个插入的元素调用新的重新分配（这是一个繁重的调用）。它保留了更多，因为它不知道你是否会在之后做一些其他的 push_back，在这种情况下，它不必为接下来的 4 个元素更改分配的内存大小。

这里，接下来的 4 个元素是 1 之间的折衷，这将最大限度地优化内存分配，但很快就会冒着再次重新分配的风险，以及一个巨大的数字，这将允许您快速制作许多 push_back 但也许白白预留大量内存

注意：如果您想自己指定一个容量（例如，如果您知道向量的最大大小），您可以使用 reserve 成员函数来完成。

Answer 3

Size() returns 向量中有多少个值。

而capacity() returns分配的存储容量的大小表示它现在可以容纳多少个值。

Answer 4

标准要求 std::vector<T>::push_back() 分摊 O(1) 复杂性。这意味着扩展必须是几何级数的，比如每次填充时将存储量加倍。

简单的例子：按顺序push_back 32 int秒变成一个std::vector<int>。你将把它们全部存储一次，如果你每次用完容量翻倍，也可以做 31 个副本。为什么是 31？在存储第二个元素之前，复制第一个元素；在存储第 3 个之前，你复制元素 1-2，在存储第 5 个之前，你复制 1-4，等等。所以你复制 1 + 2 + 4 + 8 + 16 = 31 次，有 32 个存储。

进行正式分析表明您获得了 O(N) 个存储和 N 个元素的副本。这意味着每个 push_back 分摊 O(1) 复杂度 （通常只有一个没有副本的商店，有时是一个商店和一系列副本）。

由于这种扩展策略，您大部分时间都会有 size() < capacity()。查找 shrink_to_fit 和 reserve 以了解如何以更 fine-grained 的方式控制向量的容量。

注意：几何增长率，任何大于1的因素都可以，并且有一些研究声称1.5提供更好的性能，因为内存浪费更少（因为在某些时候重新分配的内存可以覆盖旧内存）。

Answer 5

正在使用

std::vector<int> array(10); // make room for 10 elements and initialize with 0

你居然用零填满了十个空格。添加广告附加元素将导致容量扩展，这要归功于效率。在你的情况下，调用函数 reserve 是没有用的，因为你已经实例化了相同数量的元素。

检查 this and this link

Answer 6

我认为以下问题可以为您提供有关矢量容量的更多详细信息。

About Vectors growth

我会参考上面问题的答案

capacity 的增长策略需要满足 push_back 操作的摊销常数时间要求。然后，该策略被设计为在缺少 space 时通常具有指数增长。简而言之，vector的size表示现在元素的个数，而captacity表示它在未来push_back中使用的能力。

为什么Vector的size()和capacity()在push_back()之后不一样

Why Vector's size() and capacity() is different after push_back()

c++

allocation

vector