C++最快清空或删除向量的方法

Question

我有一段代码，我会经常用它来填充一个长度在0到5000之间的向量。我知道向量的最大长度不超过5000。为了避免多次初始化向量，我想只初始化一次。

vector<struct> myvector;
myvector.reserve(5000);

然而，要重新填充向量，我必须首先清除向量而不改变其容量。所以通常我会调用myvector.clear();

这是一个O(n)的操作。是否有简单的方法可以提高性能，还是这已经是最好的了？

- user788171

---

将现有元素分配给其它变量是一个合理的解决方案吗？ - Joseph Mansfield

我忘了提到，这个结构体没有析构函数。 - user788171

因此，将大小调整为当前大小，并覆盖现有元素。（如果您不知道有多少元素，请在最后调整大小） - Mats Petersson

我猜你最好的选择是封装vector，并提供这些自定义的resize和size功能，以模拟大小的变化。换句话说，你的自定义resize只会改变新成员的size而不会销毁任何元素。当然，你应该考虑如何使它与其余的vector保持一致，以便这个包装对客户端无缝，但这不是什么大问题。 - Alexander Shukaev

如果这是一个真正的问题，我会在评论中给你最好的答案：运行分析器 :) - NoSenseEtAl

Answer 1

如果您的结构体具有非平凡析构函数，则需要为向量中的所有元素调用该函数，无论它是如何清空的。如果您的结构体只有平凡析构函数，则编译器或标准库实现可以优化销毁过程并提供O(1)操作。

- Vaughn Cato

---

编译器可能会对代码进行优化和实现可以执行成本优化是有区别的（正如@DavidRodríguez-dribeas在他的回答中所说）。我认为后者更加合理！ - Nawaz

@Nawaz：我想这是真的。我的意图是类似于“大多数编译器执行此优化，所以很有可能您正在使用其中之一的编译器”，但我可以理解它可能被解释为“有时编译器会优化，有时编译器不会优化，但通常情况下会优化”。 - Vaughn Cato

我认为您没有理解我的评论。语句“实现可以优化成本…”是一个超集，因为它还包括了“编译器很可能进行优化”的想法，除了“优化过的”库代码的可能性。这意味着，即使编译器本身不进行优化，库也可以被编写成在value_type具有平凡析构函数时发出O(1)代码（这也是@DavidRodríguez-dribeas所指的，请参见他的评论）。 - Nawaz

Answer 2

对于clear()的成本取决于存储对象的类型，特别是它们是否有一个平凡的析构函数。如果类型没有平凡的析构函数，则调用必须销毁所有存储的对象，并且实际上是O(n)操作，但您无法做得更好。

现在，如果存储的元素具有平凡的析构函数，则实现可以优化成本并使clear()变为廉价的O(1)操作（只需重置大小--end指针）。

请记住，要理解渐近复杂度，您需要知道它所讨论的内容。对于clear()的情况，它代表被调用的析构函数数量，但如果成本（隐藏）为0，则操作是一个no-op。

- David Rodríguez - dribeas

---

你能解释一下什么是“平凡析构函数”吗？我不熟悉这个术语。 - user788171

在这个语境中，我认为“trivial destructor”和“no destructor”是相同的意思。 - Mats Petersson

你可能需要阅读什么是聚合体和POD，它们为什么特殊？以了解这些“琐碎”东西的含义（向下滚动一点以达到“琐碎”部分）。 - syam

@MatsPetersson：嗯……稍微有点复杂，但这就是意图。基本上，该类型不能有用户提供的析构函数（就像你说的），它不能有任何虚函数或基类，并且所有成员和基类也必须具有平凡的析构函数（即没有成员将具有虚函数/基类或用户提供的析构函数）。 - David Rodríguez - dribeas

@JamesKanze：是的，这是可能的，我甚至希望它是普遍的（虽然我没有测试过，但在1995年的《C++对象模型》中提到过这个优化，所以我希望它是常见的）。但是我正在考虑一些库在库级别上做的事情（即使没有优化）：通过特性检测类型是否具有平凡析构函数，并使用不调用构造函数的实现（即首先没有要优化的内容）。 - David Rodríguez - dribeas

Answer 3

任何你对向量中现有项进行删除的操作都需要（潜在地）调用每个被销毁项的析构函数。因此，从容器的角度来看，你所能期望的最好情况是线性复杂度。

这就只剩下一个问题：你存储在向量中的是什么类型的项。如果像 int 这样的东西，编译器可以/会提前知道没有析构函数可调用，那么移除的复杂度很可能是常数级别的。

但我怀疑，改变语法（例如，clear() vs. resize() vs. erase(begin(), end())）不会有任何重大差异。语法并不改变在没有线程的情况下调用 N 个析构函数是 O(N) 操作这一事实。

- Jerry Coffin