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)操作。我能做些简单的事情来提高它的性能吗?或者这是最好的?
3 个解决方案
#1
38
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.
如果您的结构体有一个非平凡的析构函数，那么需要为向量的所有元素调用它，而不管它是如何清空的。如果您的struct只有一个简单的析构函数，则允许编译器或标准库实现来优化销毁过程，并给您一个O(1)操作。
#2
23
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 --end pointer).
现在，如果存储的元素具有普通的析构函数，那么实现就可以对成本进行优化，clear()成为一种廉价的O(1)操作(只需重置大小——结束指针)。
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，则操作为无操作。
#3
10
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 int that 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)操作的事实。
#1
38
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.
如果您的结构体有一个非平凡的析构函数，那么需要为向量的所有元素调用它，而不管它是如何清空的。如果您的struct只有一个简单的析构函数，则允许编译器或标准库实现来优化销毁过程，并给您一个O(1)操作。
#2
23
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 --end pointer).
现在，如果存储的元素具有普通的析构函数，那么实现就可以对成本进行优化，clear()成为一种廉价的O(1)操作(只需重置大小——结束指针)。
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，则操作为无操作。
#3
10
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 int that 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)操作的事实。