聪明地处理向量内存分配

Question

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

为了简便起见，通常使用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]);
}

然而，我担心如果它被用作类似于排序算法实现的一部分，那么这将是低效的，并且会有害。例如，QuickSort 就像这样分离元素。

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

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

我是否遗漏了更好的方法？程序员通常信任 push_back() 来管理这种情况吗？或者对于敏感算法来说，它可能会变得繁琐吗？

- Maxpm

---

哇，我刚发布问题几秒钟就被踩了。这是什么原因？ - Maxpm

@Maxpm 一些 StackOverflow 的读者出于一般原则而讨厌高性能的代码。 - Crashworks

@Maxpm：我不知道任何需要分配内存的std::sort()的实现，它确实是原地排序。 - Benjamin Lindley

又一个踩？我真希望人们能够解释一下为什么。 - Maxpm

大家好：非常抱歉让你们感到困惑，我刚刚意识到问题有些不清楚。分离源向量元素是程序员正在编写的算法的一部分，这个算法需要尽可能高效。我已经修改了问题以澄清这一点。 - Maxpm

Answer 1

我将回答我认为你真正想问的问题，即“在重算法的内部循环中是否应避免使用push_back()”，而不是其他人似乎从你的帖子中读出来的“如果我在对大向量进行无关排序之前调用push_back()会有什么影响？”此外，我将根据我的经验回答，而不是花时间追寻引文和同行评审文章。

你的示例基本上做了两件事，这两件事加起来就是总CPU成本：它正在读取和操作输入向量中的元素，然后必须将元素插入输出向量中。你担心插入元素的成本，因为：

1. 当vector预留了足够的空间以容纳额外的元素时，push_back()是常数时间（实际上是瞬间完成的），但是当您用完预留的空间时，它会变慢。
2. 分配内存是昂贵的（即使挑剔者假装new是不同的，malloc()非常慢）。
3. 在重新分配后将向量的数据从一个区域复制到另一个区域也很慢：当push_back()发现没有足够的空间时，它必须去分配一个更大的向量，然后复制所有元素。（理论上，对于许多OS页面大小的向量，STL的魔法实现可以使用VMM在虚拟地址空间中移动它们而无需复制 - 实际上我从未见过能够做到这点的实现。）
4. 过度分配输出向量会导致问题：它会导致碎片化，使未来的分配变慢；它会烧掉数据缓存，使一切都变慢；如果持续存在，它会占用稀缺的自由内存，导致PC上的磁盘分页和嵌入式平台上的崩溃。
5. 向量的欠分配输出会导致问题，因为重新分配向量是O(n)操作，因此重新分配m次是O(m×n)。如果STL的默认分配器使用指数重新分配（每次realloc使向量的reserve大小加倍），那么您的线性算法就变成了O(n + n log m)。

因此，您的直觉是正确的：尽可能为向量预留空间，不是因为push_back很慢，而是因为它可能会触发一个真正缓慢的重新分配。另外，如果您查看shrink_to_fit的实现，您会看到它也执行了一个复制重新分配，临时加倍了您的内存成本并引起进一步的碎片化。

您在这里的问题是，您并不总是确切地知道输出向量需要多少空间；通常的做法是使用启发式和自定义分配器。默认情况下，为每个输出向量保留输入大小的n/2+k，其中k是一些安全裕量。这样，只要您的输入相当平衡，您通常就会有足够的输出空间，如果不行，push_back可以重新分配。如果您发现push_back的指数行为浪费了太多内存(导致您预留了2n个元素，而实际上只需要n+2)，那么您可以给它一个自定义分配器，将向量大小扩展为较小的线性块——但是当向量真正不平衡并且您不得不进行许多大小调整时，这当然会更加缓慢。

在不提前遍历输入元素的情况下，无法始终保留完全正确的空间量；但如果您知道平衡点通常是什么样子，您可以使用启发式方法来猜测它，以获得统计性能的提升。

- Crashworks

---

+1 对于 shrink_to_fit 做了一次拷贝。刚刚查看了微软的实现，确实如此... - Gabriel

Answer 2

如何使用自定义谓词对原始向量进行排序，使所有偶数排在所有奇数之前？

bool EvenBeforeOdd(int a, int b)
{
  if ((a - b)  % 2 == 0) return a < b;

  return a % 2 == 0;
}

std::sort(v.begin(), v.end(), EvenBeforeOdd);

然后你只需要找到最大的偶数，可以使用 upper_bound 来查找非常大的偶数，或者类似的方法。一旦找到了，就可以非常便宜地复制这些范围。

更新：正如 @Blastfurnace 的评论所说，使用 std::partition 要比使用 sort 更有效率，因为我们实际上并不需要每个分区内的元素有序：

bool isEven(int a) { return 0 == a % 2; }
std::vector<int>::const_iterator it =  std::partition(v.begin(), v.end(), isEven);

std::vector<int> evens, odds;
evens.reserve(std::distance(v.begin(), it);
odds.reserve(std::distance(it, v.end());

std::copy(v.begin(), it, std::back_inserter(evens));
std::copy(it, v.end(), std::back_inserter(odds));

- Kerrek SB

---

如果他只是将元素复制到两个目标向量中，那么使用std::partition_copy更简单，而且可能更快。 - Blastfurnace

@Blastfurnace：是的，非常好！partition_copy在C++0x中是新的吗？但是即使是partition也比我的想法好得多。我会加上的！ - Kerrek SB

Answer 3

当然，你可以分配与源向量大小相同的空间，因为两个新向量都不需要超过它，但这似乎有些浪费。然后跟上一个shrink_to_fit的调用。

然而，我担心这会影响效率并损害排序算法之类的东西。... push_back()通常被信任来管理程序员这种类型的事情，还是对于敏感算法来说可能变得繁琐？

是的，push_back是可靠的。尽管老实说我不明白你的担忧是什么。假设如果你正在对向量使用算法，那么你已经把元素放入了向量中。你所说的什么样的算法会关心元素是如何到达向量中的，无论是通过push_back还是其他方式？

- Benjamin Lindley

---

要明确一点，程序员是编写算法的人。他不会调用 std::sort 或任何其他函数——向量分割是他正在编写的算法的一部分，而且该算法需要尽可能高效。 - Maxpm

@Maxpm：那么，除非你所谈论的是绝对巨大的数据集，否则我建议您直接使用全尺寸的储备空间，然后再根据您在帖子中展示的算法进行操作，最后再使用shrink_to_fit方法。这里，我将"绝对巨大"的定义放宽到您系统内存的约10%左右。 - Benjamin Lindley

Answer 4

如果您的对象是动态创建的，那么向量实际上只存储指针。这使得向量在内部重新分配时更加高效。如果同一对象存在于多个位置，则这也可以节省内存。

std::vector<YourObject*> Evens;

注意：不要从函数的上下文中推送指针，因为这会导致该帧之外的数据损坏。相反，对象需要动态分配。

这可能不能解决您的问题，但也许有用。

- Lea Hayes

---

这几乎从来不是一个好主意。这样做的动机通常是严重低估库编写者的智力水平的结果。在这种情况下，这绝对没有任何帮助，因为我们正在谈论整数。 - Benjamin Lindley

Answer 5

如果您的子向量恰好是一半（奇数/偶数），那么只需为每个子向量分配原始向量的50％即可。这将避免浪费和shrink_to_fit。

- Lea Hayes