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

C++ fastest way to clear or erase a vector

提问by user788171

I have a code where I routinely fill a vector with between 0 and 5000 elements. I know the maximum never exceeds 5000. Instead of initializing vector multiple times, I would like to do just once

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

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

However, to fill the vector again, I have to clear the vector first without altering its capacity. So usually I call myvector.clear();

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

This is a O(n) operation. Is there something simple I can do to increase the performance of this or is this about the best that it will get?

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

回答by Vaughn Cato

If your struct has a non-trivial destructor, then that needs to be called for all the elements of the vector regardless of how it is emptied. If your struct only has a trivial destructor, the compiler or the standard library implementation is allowed to optimize away the destruction process and give you a O(1) operation.

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

回答by David Rodríguez - dribeas

The cost of clear()depends greately on what the stored objects are, and in particular whether they have a trivial destructor. If the type does not have a trivial destructor, then the call must destroy all stored objects and it is in fact an O(n) operation, but you cannot really do anything better.

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

Now, if the stored elements have trivial destructors, then the implementation can optimize the cost away and clear()becomes a cheap O(1) operation (just resetting the size --endpointer).

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

Remember that to understand asymptotic complexity you need to know what it talks about. In the case of clear()it represents the number of destructors called, but if the cost (hidden) is 0, then the operation is a no-op.

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

回答by Jerry Coffin

Anything you do to remove the existing items from the vector needs to (potentially) invoke the destructor of each item being destroyed. Therefore, from the container's viewpoint, the best you can hope for is linear complexity.

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

That leaves only the question of what sort of items you store in the vector. If you store something like intthat the compiler can/will know ahead of time has no destructor to invoke, chances are at least pretty good that removal will end up with constant complexity.

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

I doubt, however, that changing the syntax (e.g., clear()vs. resize()vs. erase(begin(), end())) will make any significant difference at all. The syntax doesn't change that fact that (in the absence of threading) invoking N destructors is an O(N) operation.

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