logo标签列表

vector::push_back在内存方面的底层运作是什么？

c++vectorpush-back
16

我的问题与vector::push_back的影响有关，我知道它会在向量的末尾添加一个元素，但底层发生了什么？

如果我没记错的话，内存对象是按顺序分配的，那么我的问题是，vector::push_back是否只是在向量后立即分配更多的内存，如果没有足够的空闲内存该怎么办？或者说会在“末尾”添加一个指针来使得向量“跳转”到其继续的位置吗？还是通过将其复制到另一个具有足够空间的位置来重新分配，旧副本被丢弃？抑或存在其他情况？

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

在上一句话中，move并不是以技术上的move-构造函数/move-赋值的意义使用，它们可以被移动、复制或进行任何等效操作。

[1]以k > 1的因子增长确保push_back的平摊成本是常数级别的。实际常数从一个实现到另一个实现不同（Dinkumware使用1.5，gcc使用2）。平摊成本意味着即使每隔一段时间就会有一个push_back非常昂贵（在时间点的向量大小上是O(N)），这些情况发生得很少，以至于整个插入操作集合的成本与插入次数呈线性关系，因此每个插入平均一个恒定的成本。

1
@ddriver：那是一根绳子。经过一番讨论，STL实现者们已经同意std::vector保证连续的内存。而绳子根据其段数可能没有O(1)索引访问。 - peterchen
5
Deque通常实现为在数据块之间使用指针的方式。 - Martin York
4
@Vlad：那将使参考无效。您可以使用参考，但必须注意容器的失效规则。 - Björn Pollex
谢谢Loki - 但是从我所读的来看，Deque不具备大小感知能力，所以我仍然需要实现额外的安全功能。谢谢！ - dtech
2
对象并非在原地构造，而是在原地复制，并且复制操作可以被编译器省略。这是非常不同的。C++11中的vector::emplace是在原地构造的。 - xanatos
显示剩余5条评论
4
当向量空间不足时，它将使用其分配器来保留更多的空间。然而，如何实现这一点取决于分配器。但是，向量决定要保留多少空间：标准保证向量容量至少按1.5倍的几何级数增长，从而防止由于重复的“小”分配而导致的可怕性能问题。关于元素的物理移动/复制：C++11符合实现将移动元素（如果支持移动赋值和构造），我所知道的大多数实现（特别是g++）只会对POD类型使用std::copy；POD类型的算法专业化确保这编译成（基本上）一个memcpy操作。这反过来在您的系统上编译为最快的CPU指令（例如SSE2指令）。
3
该标准仅通过复杂性要求间接保证增长是几何级数而非等差级数。它没有设置乘数的最小要求；一个增长因子为1.1的实现也可以符合标准。 - James Kanze
@JamesKanze: 啊，这就解释了我为什么找不到它。当我发现push_back的复杂性要求时，我有点想知道（让我想起了https://dev59.com/uGsz5IYBdhLWcg3w8Mmr#7554172） - sehe
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.

当您执行push_back操作时。

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

vector当空间耗尽时，会重新分配一块新的数组，并将所有元素复制到新数组中，旧数组随之销毁。

为了避免过多的内存分配并保持平均 push_back() 时间为 O(1)，每次重新分配前需要将容量至少增加一个固定因子（通常为 1.5 或 2）。

1
@James Kanze：感谢您的回复。我会相应地进行编辑。 - Mysticial
嗯，我正在查看相同的规格。无论如何，“它被重新分配”至少掩盖了分配器的概念。我感到不对的地方是它无条件地说“然后销毁旧数组”。如果分配器使用类似于realloc()的东西来实现其目标，那么这似乎是极其低效的事情。在有人更详细地解释之前，我会撤回我的-1。 - sehe
@sehe：realloc() 的观点很好。我也不确定这个的状态。 - Mysticial
@SteveJessop 总是有“好像”规则。标准确实要求默认分配器使用operator new来获取内存，这意味着用户定义的operator new可以看到它，但明确指出“不确定何时或多少次调用此函数[operator new]”。这听起来足够灵活，可以允许这种优化。 - James Kanze
经过所有这些，我认为可以相对有把握地说，“旧数组已被销毁”，这给出了您应该在一般情况下期望vector的行为方式的正确概念，如果有特定的实现可以进行优化，使得新数组实际上位于旧数组的相同位置，那很好，但不能依赖它。 - Steve Jessop
显示剩余4条评论
0
当您调用vector::push_back时，将比较end指针和capacity指针。如果有足够的空间来存储新对象，则会调用placement new在可用空间中构造对象，并增加end指针。
如果没有足够的空间，则vector会调用其allocator来分配足够的连续空间，以至少包含现有元素和新元素（不同的实现可能通过不同的乘数增加已分配的内存）。然后将所有现有元素和新元素复制到新分配的空间中。
0

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

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

由std::vector分配的内存是原始的，在需要时不调用构造函数，而是使用放置的new。

所以，push_back做了以下事情：

  • 如果容量不足新元素，则会：
    • 分配一个新块
    • 复制所有现有元素（通常使用复制构造函数）
  • 增加大小一次
  • 将新元素复制到新位置
0
如果您对数组的最终大小有一些想法，请尝试首先使用vector::reserve预留内存。请注意，reserve与vector::resize不同。使用reserve时，数组的vector::size()不会改变。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接