什么时候std :: vector重新分配它的内存数组？

Question

我找不到任何可以给出明确答案的东西.我只是好奇,如果std :: vector只在绝对必须时重新分配它的内部数组,或者它会在预期中提前重新分配(可以这么说).

例如:

std::vector<int> myVector;
for (int i = 0; i < 1000; ++i) myVector.push_back(i);

cout << myVector.size() << '\n'      // Gives 1000 as expected
     << myVector.capacity() << endl; // Gives 1024 which makes sense

如果我继续添加元素,是否有可能我添加的下24个项目中的一个会改变容量,或者只有在我放入第25个项目后它才会重新分配？

注意:

我在Linux下使用gcc 4.4.3进行了测试,但似乎重新分配是"按需"完成的,但我很好奇我是不是很幸运,或者有什么东西说明这是预期的行为.

Answer 1

从C++标准23.2.4.2开始:

size_type capacity() const;

返回:向量可以容纳的元素总数,无需重新分配.

也来自标准

注意:重新分配使引用序列中元素的所有引用,指针和迭代器无效.它保证了不会重新分配发生在通话后发生的保留(),直到时间的插入会使矢量比()在最近的调用中指定要保留的尺寸更大的尺寸在插入过程.

所以是的,你可以肯定.

编辑:正如@Bo Persson所说,有一个问题.如果我们从不打电话,标准没有说什么reserve().但是在实践中它运行良好,因为如果你调用reserve,没有实现会记住.我相信这是错误.正如@Martin在C++ 0x草案中的回答中提到的那样,它得到了纠正.

Answer 2

从标准:n3092:草案C++ 0x

23.3.6.2载体容量[载体容量]

void reserve(size_type n);
2效果:一种指令,通知向量计划的大小更改,以便它可以相应地管理存储分配.在reserve()之后,如果重新分配,capacity()大于或等于reserve的参数; 并且等于capacity()的先前值.当且仅当当前容量小于reserve()的参数时,才会发生重新分配.如果除了非CopyConstructible类型的移动构造函数之外抛出异常,则没有效果.

23.3.6.4向量修饰符[vector.modifiers]
备注:如果新大小大于旧容量,则会导致重新分配.如果没有重新分配,插入点之前的所有迭代器和引用仍然有效.如果除了复制构造函数之外抛出异常,移动构造函数,赋值运算符或T的移动赋值运算符,或者通过任何InputIterator操作都没有效果.如果非CopyConstructible T的移动构造函数抛出异常,则不指定效果.

Answer 3

如果你看一下cplusplus.com上的 push_back文档,它说:

这有效地将向量大小增加1,如果向量大小等于调用之前的向量容量,则导致内部分配存储的重新分配.重新分配使以前获得的所有迭代器,引用和指针无效.

所以我非常怀疑在此之前尺寸会发生变化,但你可以随时测试它.至少在我的平台上,尺寸如上所述变化:

size vs capacity
1020 vs 1024
1021 vs 1024
1022 vs 1024
1023 vs 1024
1024 vs 1024
1025 vs 2048