为什么std :: vector不保留“ double”？它的容量，而调整大小呢？ [英] Why does std::vector reserve not "double" its capacity, while resize does?

问题描述

我刚刚发现 std :: vector< T> :: resize 即使将大小调整为当前大小以上的一个元素，也会倍增其容量：

I just found out that std::vector<T>::resize "doubles" its capacity even when resizing to one element above the current size:

std::vector<int> v(50);
v.resize(51);
std::cout << v.capacity() << std::endl;

该程序使用GCC和Clang输出100，使用Visual C ++输出75。但是，当我从调整大小切换到保留时：

This program outputs 100 with GCC and Clang, and 75 with Visual C++. However, when I switch from resize to reserve:

std::vector<int> v(50);
v.reserve(51);
std::cout << v.capacity() << std::endl;

所有三个编译器的输出均为51。

The output is 51 with all three compilers.

我想知道为什么实现对于调整大小和保留使用不同的扩展策略。似乎不一致，我希望在这里有同样的行为。

I wonder why implementations use a different expansion strategy for resize and reserve. It seems inconsistent, and I would expect the same behavior here.

我只是为我的动机添加了一个链接问题，其中报告了对性能的影响： 为什么做很多保留时C ++ STL向量的速度慢1000倍吗？

I am just adding a link to a motivation for my question, where the impact on performance is reported: Why are C++ STL vectors 1000x slower when doing many reserves?

在C中添加引号++ 11标准，明确了储备的要求； §23.3.6.3（2）：

Adding a quote from C++11 Standard to clarify requirements for reserve; §23.3.6.3(2):

在 reserve（）之后，<$如果发生重新分配，则c $ c> capacity（）与 reserve 的参数更大或等于 ...

After reserve(), capacity() is greater or equal to the argument of reserve if reallocation happens...

---

一些其他想法：来自C ++ 11标准：

---

Some additional thoughts: From C++11 Standard:

复杂度：复杂度是线性的，即插入的元素数加上到向量末端的距离。

Complexity: The complexity is linear in the number of elements inserted plus the distance to the end of the vector.

实际上，这意味着在末尾插入单个元素的恒定（摊销）复杂性。但是，这仅适用于 vector修饰符，例如 push_back 或 insert （第23.3节.6.5）。

Which, effectively, implies constant (amortized) complexity for inserting a single element at the end. However, this applies only for vector modifiers, such as push_back or insert (§23.3.6.5).

调整大小不在修饰符中。 §23.3.6.3 vector 容量部分中列出了它。而且，调整大小没有复杂性要求。

resize is not listed among modifiers. It's listed in §23.3.6.3 vector capacity section. And, there are no complexity requirements for resize.

但是，在 vector 概述部分（第23.3.6.1节），内容如下：

However, in the vector overview section (§23.3.6.1), there is written:

it（ vector ）支持（摊销）最后的固定时间插入和擦除操作

it (vector) supports (amortized) constant time insert and erase operations at the end

问题是，是否将 resize（size（）+ 1）视为插入末尾 。

The question is whether resize(size()+1) is considered to be "insertion at the end".

推荐答案

据我所知，调整大小和保留必须具有所证明的行为。但是，尽管都可以分配确切的金额，并且都可以乘以先前的分配（就标准而言），但是两者都允许这种行为。

As far as I can tell, neither resize nor reserve is required to have the demonstrated behaviour. Both are however allowed such behaviour although both could either allocate the exact amount, and both could multiply the previous allocation as far as the standard is concerned.

每种分配策略都有其各自的分配策略。优点。分配精确数量的优点是，当预先知道最大分配量时，它没有内存开销。乘积的优点是当与最终插入操作混合时，它保持不变的摊销属性。

Each allocation strategies have their advantages. The advantage of allocating exact amount is that it has no memory overhead when the maximum allocation is known beforehand. The advantage of multiplying is that it maintains the constant amortized property when mixed with end-insertion operations.

经测试的实现选择的方法的优点在于，它允许两种策略调整大小时。要使用一种策略，可以保留然后调整大小。要使用另一个，只需调整大小即可。当然，必须意识到这种未指定的行为才能利用这一点。选择或选择这些实现背后的原因可能是原因，也可能不是原因。

The approach chosen by the tested implementations has the advantage that it allows both strategies when resizing. To use one strategy, one can reserve and then resize. To use the other, just resize. Of course, one has to be aware of the unspecified behaviour to take advantage of this. This advantage may or might not be the reasoning behind the choice of these implementations.

一个人可能认为它是标准中指定的矢量API失败，表示预期的重新分配行为是不可能的（以标准保证的方式）。

One might consider it a failure of the vector API, as specified in the standard, that expressing the intended reallocation behaviour is not possible (in a way that is guaranteed by the standard).

这篇关于为什么std :: vector不保留“ double”？它的容量，而调整大小呢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！