c++ - 容器：向量类....慢

Question

谁能解释为什么在矢量容器中 push_back 操作通常较慢？我听到有人这么说，但找不到它有点慢的原因。

作为初学者，我想使用 vector 和 push_back 但我还有其他选择可以提高性能吗？请告诉我。谢谢，

Answer 1

向量将其对象存储在一个连续的数组中。它分配一定数量的空间（它的容量）来容纳对象；当对象的数量（其大小）即将超过容量时，它会分配更大的空间并复制（或移动）现有对象。

这可能需要一些时间。push_back为避免这种情况，并保证insert不需要重新分配，您可以reserve事先调用以分配足够大的块以满足您的需要。

Answer 2

当您将项目附加或插入到std::vector时，可能没有足够的空间来存储它。这会导致向量分配足够的存储空间来保存所有元素并将它们复制到新的内存块中。如果您按值而不是按指针存储对象，则将制作完整的副本。对于复杂类型，这可能会涉及并包括额外的分配和复制。在这种情况下，性能可能会受到矢量大小的影响。对于大型向量，性能损失将更加明显。

Answer 3

push_back操作并不总是较慢。它具有恒定的复杂性（摊销时间）。唯一较慢的情况是发生重新分配时。有用的事情之一std::vector是您始终可以将对象添加到向量中，而不管其大小。假设向量的容量为 10，向量中有 10 个对象，然后发生重新分配以使向量更大。通常，向量大小加倍并将对象复制到新向量中，这是一个较慢的操作。