明智地进行向量内存分配

假设我必须迭代一个可能非常大的数字向量，并将偶数和奇数元素复制到新的单独向量中。 （源向量可以具有任意比例的偶数与奇数；它可以是全偶数、全奇数或介于两者之间。）

为了简单起见，push_back经常用于此类事情：

for (std::size_t Index; Index < Source.size(); Index++)
{
    if (Source[Index] % 2) Odds.push_back(Source[Index]);
    else Evens.push_back(Source[Index]);
}

但是，我担心如果将其用作排序算法（其中性能至关重要）的实现的一部分，这将是低效且有害的。例如，快速排序涉及分离元素，就像这样。

你可以使用reserve()预先分配内存，因此只需要一次分配，但随后您必须对整个源向量进行两次迭代 - 一次是为了计算需要排序的元素数量，另一次是为了实际复制。

当然，您可以分配与源向量大小相同的空间，因为两个新向量都不需要容纳比这更多的空间，但这似乎有点浪费。

我缺少更好的方法吗？是push_back()通常被信任为程序员管理此类事情，或者它会成为敏感算法的负担吗？

我将回答我认为您真正想问的问题，即“应该push_back()在重型算法的内部循环中应该避免吗？”而不是其他人似乎在你的帖子中读到的内容，即“如果我在对大向量进行不相关的排序之前调用push_back，这有什么关系吗？”另外，我要去根据我的经验来回答，而不是花时间寻找引文和同行评审的文章。

您的示例基本上做了两件事，这些事情加起来就等于总 CPU 成本：它读取输入向量中的元素并对其进行操作，然后必须将这些元素插入到输出向量中。您担心插入元素的成本，因为：

1. 当向量为附加元素预先保留足够的空间时，push_back() 是恒定时间（实际上是瞬时的），但当您用完保留空间时，会很慢。
2. 分配内存的成本很高（malloc()只是很慢 https://stackoverflow.com/questions/470683/memory-allocation-deallocation-bottleneck，即使学究假装new是不同的东西）
3. 重新分配后将向量的数据从一个区域复制到另一个区域也很慢 https://stackoverflow.com/questions/4008128/one-large-malloc-versus-multiple-smaller-reallocs：当push_back()发现它没有足够的空间时，它必须分配一个更大的向量，然后复制所有元素 http://www.tantalon.com/pete/files/gdc04_common_cpp_mistakes_in_games.ppt。 （理论上，对于大小为许多操作系统页面的向量，STL 的神奇实现可以使用 VMM 在虚拟地址空间中移动它们，而无需复制 — 实际上我从未见过一个可以 http://www.gamedev.net/topic/505481-do-stl-containers-always-move-memory/.)
4. 过度分配输出向量会导致问题：它会导致碎片，使未来的分配速度变慢；它会燃烧数据缓存，使一切变慢；如果持续存在，它会占用稀缺的可用内存，导致 PC 上的磁盘分页和嵌入式平台上的崩溃。
5. 分配不足的输出向量会导致问题，因为重新分配向量是一个 O(n) 操作，因此重新分配它m次数为O(m×n)。如果 STL 的默认分配器使用指数重新分配（每次重新分配时使向量的保留大小变为之前大小的两倍），则线性算法的复杂度为 O(n + n log m)。

因此，您的直觉是正确的：尽可能为向量预先保留空间，不是因为 push_back 很慢，而是因为它可以触发重新分配is慢的。另外，如果你看看shrink_to_fit，您会看到它还会进行副本重新分配，暂时使内存成本加倍并导致进一步的碎片。

这里的问题是，您并不总是确切地知道输出向量需要多少空间；通常的反应是使用启发式或者自定义分配器。默认情况下为每个输出向量保留 n/2+k 的输入大小，其中 k 是一些安全裕度。这样你就会usually只要您的输入合理平衡，就有足够的空间用于输出，并且在极少数情况不平衡的情况下，push_back 可以重新分配。如果您发现 push_back 的指数行为浪费了太多内存（导致您在实际上只需要 n+2 时保留 2n 个元素），您可以给它一个自定义分配器，将向量大小扩展为更小的线性块 - 但当然在向量确实不平衡并且最终需要进行大量调整大小的情况下，这会慢得多。

如果不提前遍历输入元素，就无法始终保留正确的空间量；但如果你知道平衡点是什么usually看起来，您可以使用启发式方法对其进行很好的猜测，以便在多次迭代中获得统计性能增益。