Dan*_*ica 25 c++ resize vector capacity
我刚刚发现,std::vector<T>::resize即使调整大小超过当前大小的一个元素,它的容量"加倍":
std::vector<int> v(50);
v.resize(51);
std::cout << v.capacity() << std::endl;
该程序使用GCC和Clang输出100,使用Visual C++输出75.但是,当我切换resize到reserve:
std::vector<int> v(50);
v.reserve(51);
std::cout << v.capacity() << std::endl;
所有三个编译器的输出为51.
我不知道为什么实现使用了不同的扩张策略resize和reserve.它似乎不一致,我希望在这里有相同的行为.
我只是添加了一个关于我的问题动机的链接,其中报告了对性能的影响:为什么C++ STL向量在做多个预留时会慢1000倍？
添加C++ 11标准中的引用以阐明要求reserve; §23.3.6.3(2):
之后
reserve(),capacity()为大于或等于给的参数reserve,如果重新分配发生...
一些额外的想法:来自C++ 11标准:
复杂性:插入元素的数量加上到向量末尾的距离是复杂的.
实际上,这意味着在最后插入单个元素的常数(摊销)复杂性.但是,这仅适用于矢量修饰符,例如push_back或insert(§23.3.6.5).
resize未在修饰符中列出.它列在§23.3.6.3 vector容量部分中.并且,没有复杂性要求resize.
但是,在vector概述部分(§23.3.6.1)中,写有:
it(
vector)支持(分期)常量时间插入和擦除操作
问题是是否resize(size()+1)被认为是"插入到最后".
eer*_*ika 17
据我所知,既不是resize也不reserve需要具有证明的行为.然而,两者都允许这样的行为,尽管两者都可以分配确切的数量,并且就标准而言,两者都可以乘以先前的分配.
每种分配策略都有其优点.分配精确数量的优点是,当事先知道最大分配时,它没有内存开销.乘法的优点是,当与末端插入操作混合时,它保持恒定的摊销属性.
测试实现选择的方法具有以下优点:在调整大小时它允许两种策略.要使用一种策略,可以预留然后调整大小.要使用另一个,只需调整大小.当然,人们必须意识到利用这一点的未指明行为.这种优势可能是也可能不是这些实现选择背后的原因.
有人可能认为它是标准中规定的向量API的失败,表达了预期的重新分配行为是不可能的(以标准保证的方式).
如果您的resize容量超过了容量,那么您已经"证明"您不想保留恰当的容量.另一方面,如果您使用reserve明确要求正确的容量.如果reserve使用相同的策略,resize将无法保留适当的金额.
从这个意义上来说,resize没有reserve是懒惰的,或者你不知道确切的预留金额.reserve如果你知道你需要什么容量,你打电话.这是两种不同的情景.
PS:正如StoryTeller指出的那样,reserve也不需要保留按照标准要求的确切金额.尽管如此,我认为我的主要论点仍然存在:( resize没有reserve)并且reserve适用于不同的场景,你要么暗示要保留多少,要么不关心实际容量,只想让容器大小适合你要的是什么
你为什么期望它们表现一样？reserve用于预分配稍后将使用的空间,期望用户对容器的预期最终大小有一个合适的处理.resize只是一个正常的分配,因此它遵循几何增加容器分配空间的正常,速度有效的方法.
容器通过乘法步骤增加,以减少所需的分配数量,从而保持速度并减少内存碎片.加倍是最常见的,但是一些实现使用1.5的步骤(例如,MSVC),其为每个容器内的较低浪费空间交换增加的分配.
但是,如果用户已经告诉图书馆他们认为容器会有多大 - 通过引起reserve- 没有必要分配多余空间,他们可以信任用户用正确的号码调用它.这是reserve不寻常的行为,而不是resize.
resize需要遵循指数重新分配策略来实现其复杂性保证(插入的元素数量的线性).这可以通过考虑resize(size() + 1)需要具有摊销的常数复杂性来看出,因此必须遵循指数增长,因为push_back(摊销的常数复杂性)必须呈指数增长.
的实现reserve被允许跟随它喜欢的任何分配策略,因为其唯一的复杂性要求是它的元素的数量成线性关系存在.但是,如果一个实现是例如四舍五入到下一个2的幂,那么在用户确切知道需要多少内存的情况下,这将是空间效率低(并且令人惊讶),并且如果用户来到,则可能使移植复杂化.依靠这种行为.如果分配器以该粒度运行,则在没有空间效率低的情况下,例如通过将分配四舍五入到字大小,可以更好地执行标准中的宽容度.