c++ - 聪明地处理 vector 内存分配

Question

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

为简单起见，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() 预先分配内存，因此只需要一次分配，但随后您必须遍历整个源 vector 两次 - 一次计算需要多少元素进行整理，并再次进行实际复制。

当然，您可以分配与源 vector 大小相同的空间量，因为两个新 vector 都不需要容纳超过该大小的空间，但这似乎有些浪费。

有没有我缺少的更好的方法？ push_back() 通常可以信任为程序员管理此类事情，还是会成为敏感算法的负担？

Answer 1

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

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

1. push_back() 是常数时间(瞬时的，真的)当一个 vector 有足够的预留空间用于附加元素时，但当你用完预留空间时速度很慢。
2. 分配内存是昂贵的(malloc() is just slow，即使学究们假装 new 是不同的)
3. 在重新分配后将 vector 的数据从一个区域复制到另一个区域 is also slow : 当 push_back() 发现它没有足够的空间时，it has to go and allocate a bigger vector, then copy all the elements . (理论上，对于大小为许多操作系统页面的 vector ，STL 的神奇实现可以使用 VMM 在虚拟地址空间中移动它们而不进行复制——实际上是 I've never seen one that could。)
4. 过度分配输出 vector 会导致问题:它会导致碎片化，使 future 的分配速度变慢；它会消耗数据缓存，使一切变慢；如果持续存在，它会占用稀缺的可用内存，导致 PC 上的磁盘分页和嵌入式平台上的崩溃。
5. 分配不足的输出 vector 会导致问题，因为重新分配 vector 是一个 O(n) 操作，因此重新分配 m 次是 O(m×n)。如果 STL 的默认分配器使用指数重新分配(每次重新分配时使 vector 的预留大小是其先前大小的两倍)，这会使您的线性算法 O(n + n log m)。

因此，您的直觉是正确的:始终尽可能为您的 vector 预留空间，不是因为 push_back 很慢，而是因为它会触发一个很慢的重新分配。此外，如果您查看 shr​​ink_to_fit 的实现，您会发现它还会进行复制重新分配，暂时使内存成本翻倍并导致进一步碎片化。

这里的问题是您并不总是确切知道输出 vector 需要多少空间；通常的 react 是使用启发式分配器，也可能使用自定义分配器。默认情况下，为每个输出 vector 保留 n/2+k 的输入大小，其中 k 是一些安全边际。这样一来，您通常就会有足够的空间用于输出，只要您的输入合理平衡，并且 push_back 可以在极少数情况下重新分配。如果你发现 push_back 的指数行为浪费了太多内存(导致你保留 2n 个元素，而实际上你只需要 n+2 )，你可以给它一个自定义分配器，以更小的线性 block 扩展 vector 大小——当然如果 vector 真的不平衡并且你最终会做很多调整大小，那会慢得多。

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