在 vector::push_back 内存的背后会发生什么？

Question

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

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

Answer 1

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

在上一句中，move 没有在技术move-constructor/ move-assignment 意义上使用，它们可以移动 em> 或复制 或任何等效操作。

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

Answer 2

当向量空间不足时，它将使用其分配器来保留更多空间。

由分配器决定如何实现。

然而，向量决定了要保留多少空间：该标准保证向量容量应以几何方式增长至少 1.5¹ 倍（参见注释），从而防止由于重复的“小”分配而导致糟糕的性能。

关于元素的物理移动/复制：

• 如果支持移动分配和构造，符合 c++11 的实现将移动元素，
• 我知道的大多数实现（尤其是 g++）将仅使用 std::copy 进行 POD类型； POD 类型的算法专门化确保它编译成（本质上）memcpy 操作。这反过来会被编译成系统上最快的任何 CPU 指令（例如 SSE2 指令）

¹ 我尝试从 n3242 标准草案文档中找到该指令的参考引用，但我无法在这次

Answer 3

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

在内部，您可以将其视为定义为三个指针（或类似指针的行为）：

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.

当您向后推时。

1. 如果最终值小于容量：
   • 新元素被复制到final指向的位置
   • final 递增到下一个位置。
2. 如果最终与容量相同，则向量已满
   • 必须分配新内存。
   • 编译器随后将分配 X*(capacity - start)*sizeof(t) 字节。
   • 其中 X 通常是 1.5 到 2 之间的值。
   • 然后，它将所有值从旧内存缓冲区复制到新内存缓冲区。
   • 新值将添加到缓冲区中。
   • 传输开始/最终/容量指针。
   • 释放旧缓冲区

Answer 4

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

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

Answer 5

如果您知道数组的最终大小是多少，请首先尝试 vector::reserve 内存。请注意，reserve 与vector::resize 不同。使用 reserve 时，数组的 vector::size() 不会更改

Answer 6

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

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

Answer 7

std::vector 过度分配 - 它通常会自动分配比所需更多的内存。 size不受此影响，但您可以通过capacity进行控制。

如果额外容量不够，std::vector 将复制所有内容。

std::vector 分配的内存是原始的，没有按需调用构造函数，使用放置 new。

所以，push_back 的作用是：

• 如果容量不足以容纳新元素，它将
  • 分配一个新块
  • 复制所有现有元素（通常使用复制构造函数）
• 将大小增加一个
• 将新元素复制到新位置