在vector :: push_back内存中发生了什么？

问题描述

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

IIRC内存对象以顺序方式分配，因此我的问题是 vector :: push_back 是否只是立即分配更多内存向量，如果是，如果在那个位置没有足够的可用内存，会发生什么？或者可能在结束中添加指针以使向量跳到它继续的位置？还是只是通过将其复制到另一个具有足够空间并且旧副本被丢弃的位置来重新分配？

解决方案

如果有足够的空间已经分配，​​对象是从参数就地复制构造的。当没有足够的内存时，向量将按照某种几何级数递增它的内部数据缓冲区（每次新的大小将 k * old_size 与 k> 1 ），然后将原始缓冲器中存在的所有对象移动到新缓冲器。在操作完成后，旧缓冲区将被释放到系统。

在上一句中， move 移动构造函数 / 移动赋值，可以移动或 b
$ b

增长一个因子 k> 1 确保 push_back 的摊销成本为常数。实际的常数从一个实现到另一个（Dinkumware使用1.5，gcc使用2）。摊销的成本意味着，即使每个常常一个 push_back 将是非常昂贵的（ O（N） ），那些情况很少发生，使得整个插入集合上的所有操作的成本在插入数量上是线性的，因此每个插入平均了恒定成本） / p>

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 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?

解决方案

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) 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.

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.

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内存中发生了什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！