在vector::push_back memory wise的背后发生了什么？

Question

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

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

Answer 1

当vector耗尽空间时，它会被重新分配，所有元素都会被复制到新的数组中。然后销毁旧的数组。

为了避免过多的分配并将平均push_back()时间保持在O(1)，重新分配要求大小至少增加一个恒定因子。(1.5和2是常见的)

Answer 2

向量保证所有元素在内存中是连续的。

在内部，您可以将其定义为三个指针(或类似于指针的行为)：

start:     Points at the beginning of the allocated block.
final:     Points one past the last element in the vector.
           If the vector is empty then start == final 
capacity:  Points one past the end of allocated memory.
           If final == capacity there is no room left.

当你反击的时候。

如果final小于location.：

1. 将新元素复制到final所指向的位置
2. final将递增到下一个location.

​

1. 如果allocated.
2. The与容量相同，则矢量已满，则必须将新内存装满。编译器将分配X*(capacity - start)*sizeof(t)字节。
3. ，其中X通常是一个介于1.5和2之间的值。
4. 然后将所有值从旧内存缓冲区复制到新内存缓冲区。<代码>H222<代码>H123新值将添加到启动/最终/容量缓冲区中

​

Answer 3

调用vector::push_back时，会将结束指针与容量指针进行比较。如果有足够的空间容纳新对象，则调用placement new在可用空间中构造对象，并递增结束指针。

如果没有足够的空间，vector调用它的分配器为至少现有元素和新元素分配足够的连续空间(不同的实现可能会以不同的乘数增加分配的内存)。然后将所有现有元素加上新元素复制到新分配的空间。