在 vector::push_back 内存明智的引擎盖下会发生什么? [英] What happens under the hood of vector::push_back memory wise?

问题描述

我的问题是关于 vector::push_back 的效果，我知道它在矢量的末尾添加了一个元素，但在引擎盖下会发生什么?

My question is regarding the effect of vector::push_back, I know it adds an element in the end of the vector but what happens underneath the hood?

IIRC 内存对象是按顺序分配的，所以我的问题是 vector::push_back 是否只是在向量之后立即分配更多内存，如果是这样，如果没有足够的空闲内存会发生什么在那个位置?或者也许在结束"中添加了一个指针以使向量跳"到它继续的位置?或者它只是通过将其复制到另一个有足够空间的位置而重新分配，旧副本被丢弃?或者别的什么?

IIRC memory objects are allocated in a sequential manner, so my question is whether vector::push_back simply allocates more memory immediately after the vector, and if so what happens if there is not enough free memory in that location? Or perhaps a pointer is added in the "end" to cause the vector to "hop" to the location it continues? Or is it simply reallocated through copying it to another location that has enough space and the old copy gets discarded? Or maybe something else?

推荐答案

如果已经分配了足够的空间，则对象将根据原位参数复制构造.当没有足够的内存时，向量将按照某种几何级数增长它的内部数据缓冲区(每次新大小将是 k*old_size 和 k > 1^[1]) 并且原始缓冲区中存在的所有对象将移动到新缓冲区.操作完成后，旧缓冲区将被释放到系统中.

If there is enough space already allocated, the object is copy constructed from the argument in place. When there is not enough memory, the vector will grow it's internal databuffer following some kind of geometric progression (each time the new size will be k*old_size with k > 1^[1]) and all objects present in the original buffer will then be moved to the new buffer. After the operation completes the old buffer will be released to the system.

在前面的句子中move不是在技术move-constructor/move-assignment意义上使用的，它们可以是移动或复制或任何等效操作.

In the previous sentence move is not used in the technical move-constructor/ move-assignment sense, they could be moved or copied or any equivalent operation.

^[1] 按因子 k > 增长1 确保 push_back 的摊销成本是恒定的.实际常量因一种实现而异(Dinkumware 使用 1.5，gcc 使用 2).摊销成本意味着即使每隔一段时间 push_back 会非常昂贵(O(N) 当时的向量大小)，这些情况也很少发生足以使整个插入集的所有操作的成本与插入次数成线性关系，因此每次插入平均一个恒定成本)

^[1] Growing by a factor k > 1 ensures that the amortized cost of push_back is constant. The actual constant varies from one implementation to another (Dinkumware uses 1.5, gcc uses 2). The amortized cost means that even if every so often one push_back will be highly expensive (O(N) on the size of the vector at the time), those cases happen rarely enough that the cost of all operations over the whole set of insertions is linear in the number of insertions, and thus each insertion averages a constant cost)

这篇关于在 vector::push_back 内存明智的引擎盖下会发生什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！