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

Question

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

c++vectorallocation

9

我刚开始学习向量，对于size()和capacity()感到有些困惑。我对它们的了解很少。但是为什么在这个程序中两者都不同呢？即使array(10)为10个元素腾出空间并初始化为0。

添加array.push_back(5)之前

所以array.size();是10，这是可以的。

所以array.capacity();是10，这是可以的。

添加array.push_back(5)之后

所以array.size();是11，这是可以的（已经添加了10个0，然后push_back再添加一个元素5）。

所以array.capacity();是15，为什么呢？（难道它为一个int保留了5个块吗？）。

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

- Asif Mushtaq

4

请注意，您不应该将“array”用作变量名，特别是当类型不是数组时。我知道这只是示例代码，但仍然可能是个好主意。 :) - erip

除非您需要std::endl的额外功能，否则请不要使用它。 '\n' 开始新行。 - Pete Becker

3

@PeteBecker，确实如此，但在这种情况下，由于输出是诊断性的，我们往往希望有隐式的flush，就像endl一样，否则消息可能不会及时出现或顺序错误。（至少这是我的经验） - underscore_d

@underscore_d - 可能是，但这并不适用于此处的代码。 - Pete Becker

@erip 感谢指出。只是确认一下，因为数组是内置的STL？ - Asif Mushtaq

显示剩余2条评论

6个回答

10

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

- Ed Heal

为了避免在扩展时多次复制所有元素，我猜测。 - MikeCAT

那么我们无法确定任何向量的确切容量（capacity()）？ - Asif Mushtaq

1

@UnKnown 是的，我们可以：capacity() 返回在进行新的重新分配之前可以容纳的元素数量。 - TemplateRex

7

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

换句话说，它是在需要重新分配之前可以达到的大小。

它不会每次执行push_back时都增加1，以免在插入每个元素时调用新的重新分配（这是一个重要的调用）。它会保留更多的空间，因为它不知道您是否会在此后立即进行其他push_back操作，在这种情况下，它不必为接下来的4个元素更改分配的内存大小。

在这里，4个元素是一种折衷方式，既可以最大程度地优化内存分配，又可以避免很快再次重新分配，但也不会为许多无用的元素保留大量内存。

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

- Aracthor

我已经使用了reserve();但是我很困惑为什么容量会跳到15，即使我只添加/ push_back一个整数？ - Asif Mushtaq

@UnKnown：虽然你没有为11个元素预留空间。 - Kerrek SB

@UnKnown 因为它分配多个元素，以便不必为接下来的几个元素重新分配并限制realloc次数。它调整大小得越多，就会越大，以便约束“reserve”内部调用。 - Aracthor

1

@UnKnown 如果你知道你的向量的内存管理方式（这可能取决于系统、编译器等），你就可以预测它。但这几乎总是在分配内存大小和重新分配次数之间做出权衡。（分别表示已使用的RAM和已使用的CPU） - Aracthor

如果仅增加容量1，那么每次push_back()都必须增加容量，这是一项非常耗费的操作。将容量更改为15，下面的四个push_back()调用则便宜得多。 - gnasher729

显示剩余2条评论

3

使用

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

您实际上已经用零填满了所有十个空间。添加另一个元素将会导致容量扩展，从而提高效率。在您的情况下，调用reserve函数是无用的，因为您已经实例化了相同数量的元素。

检查此链接this和this。

- MagoNick

2

我认为以下问题可以更详细地说明向量的容量。关于向量增长的问题我将引用上述问题中的答案。 capacity 的增长策略需要满足摊销常数时间要求，以满足 push_back 操作的要求。因此，当空间不足时，该策略通常设计为指数增长。简而言之，向量的 size 表示现在的元素数量，而 capacity 则表示它在未来用于 push_back 的能力。

- Jcppython

1

Size() 返回向量中的值的数量。

Capacity() 返回分配的存储容量的大小，即它现在可以容纳多少个值。

- Shafi

1

调用push_back()后为什么容量会改变？ - Asif Mushtaq

为了容纳该向量中即将到来的元素。 - Shafi

那么我们无法确定确切的capacity()容量吗？ - Asif Mushtaq

@UnKnown capacity() 是确切的容量。它会在必要时增长，但增长的“步骤”比大小大。您无法预测未来的容量，但您始终可以确定当前的容量。 - molbdnilo

由于数据结构在运行时分配内存。 - Shafi

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- TemplateRex · Accepted Answer

这个标准规定std::vector<T>::push_back()的摊销复杂度为O(1)。这意味着扩展必须是几何级数，例如每次填满后将存储量加倍。

举个例子：将32个整数依次push_back到std::vector<int>中。您会将它们全部存储一次，并且做31次副本，如果每次运行时都将容量加倍。为什么是31？在存储第二个元素之前，您需要复制第一个元素；在存储第三个元素之前，您需要复制元素1-2，在存储第五个之前，您需要复制1-4等。因此，您需要复制1 + 2 + 4 + 8 + 16 = 31次，共存储32个元素。

进行正式分析表明，对于N个元素，您获得O(N)次存储和复制操作。这意味着每个push_back的摊销复杂度为O(1)(通常只是存储而不是复制，有时是存储和一系列的复制)。

由于这种扩展策略，大多数时间您都会有size() < capacity()。了解如何更精细地控制向量容量的方法请查看shrink_to_fit和reserve。

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