为什么在push_back()后Vector的size()和capacity()不同

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

标准要求std::vector<T>::push_back()具有摊销的O(1)复杂性.这意味着扩展必须是几何的,即每次填充时存储量加倍.

简单的例子:顺序push_back32 int秒进入a std::vector<int>.您将存储所有这些,并且如果每次耗尽时将容量加倍,也会复制31份.为什么31？在存储第二个元素之前,复制第一个元素; 在存储第3个之前,你复制元素1-2,在存储第5个之前,你复制1-4,等等.所以你复制1 + 2 + 4 + 8 + 16 = 31次,有32个商店.

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

由于这种扩展策略,您将拥有size() < capacity()大部分时间.查找shrink_to_fit并reserve学习如何以更细粒度的方式控制向量的容量.

注意:对于几何增长率,任何大于1的因子都可以,并且有一些研究声称1.5由于内存浪费较少而提供更好的性能(因为在某些时候重新分配的内存可以覆盖旧内存).

Answer 2

它是为了提高效率,因此每次添加元素时都不必扩展底层数据结构.即,不具有呼叫delete/ new每次.

Answer 3

所述的std ::矢量::容量不是其实际尺寸(这是由返回size()),但实际的内部分配的大小的大小.

换句话说,它是在需要另一次重新分配之前可以达到的大小.

每次执行a时它不会增加1 push_back,以便不在每个插入的元素上调用新的重新分配(这是一个沉重的调用).它保留更多,因为它不知道你之后是否会做其他事情push_back,在这种情况下,它不必更改4个下一个元素的分配内存大小.

在这里,4个下一个元素是1之间的折衷,它将最大限度地优化内存分配,但很快就会有另一个重新分配的风险,并且数量巨大,这将允许您push_back快速制作许多但可能保留大量内存.

注意:如果您想自己指定容量(例如,如果您知道向量最大大小),则可以使用保留成员函数来执行此操作.