c++ - C++ 清除或擦除矢量的最快方法

Question

我有一个代码，我经常用 0 到 5000 个元素填充一个向量。我知道最大值永远不会超过 5000。我不想多次初始化向量，我只想做一次

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

但是，要再次填充向量，我必须先清除向量而不改变其容量。所以通常我调用 myvector.clear();

这是一个 O(n) 操作。我可以做一些简单的事情来提高它的性能，还是它会得到最好的？

Answer 1

如果您的结构有一个重要的析构函数，那么无论它是如何清空的，都需要为向量的所有元素调用它。如果您的结构只有一个简单的析构函数，则允许编译器或标准库实现优化销毁过程并为您提供 O(1) 操作。

Answer 2

的成本在clear()很大程度上取决于存储的对象是什么，尤其是它们是否具有微不足道的析构函数。如果该类型没有简单的析构函数，那么调用必须销毁所有存储的对象，这实际上是一个 O(n) 操作，但你真的不能做得更好。

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

请记住，要理解渐近复杂性，您需要知道它在谈论什么。在它的情况下clear()它表示调用的析构函数的数量，但如果成本（隐藏）为0，则该操作是空操作。

Answer 3

您从向量中删除现有项目的任何操作都需要（可能）调用每个被销毁项目的析构函数。因此，从容器的角度来看，您所能期望的最好的就是线性复杂性。

剩下的问题是你在向量中存储了什么样的项目。如果您存储类似int编译器可以/将提前知道没有要调用的析构函数的东西，那么至少很有可能删除最终会带来恒定的复杂性。

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