c++ - 说到序列， "vector[n].push_back()"总是 O(1) 吗？

Question

我用过 vector<int> v[N]很多。
这对我来说是一个非常强大的工具。

我想知道 v[n].push_back()平均花费 O(1)。
我知道当 vector 满了，它需要扩展成 double。
但是 vector 序列不是相互依附的吗？
如果是这样，我认为所有 vector 都需要向左移动，这意味着它的成本超过 O(n)。

总结一下，当涉及到 vector 序列时，就是v[n].push_back()总是 O(1)？
请给我一些帮助:D

Answer 1

它并不总是 O(1) 无论如何。参见 here (强调我的):

Complexity

Constant (amortized time, reallocation may happen).

If a reallocation happens, the reallocation is itself up to linear in the entire size.

所以即使只有一个 vector ，也不能保证它是常数。

But isn't the sequence of vector attached each other? If so, I think all vectors need to be shift which means it costs more than O(1).

这不会影响运行时。数组中的 vector 彼此独立并动态管理自己的存储(并且彼此分开)。数组中的实际 vector 对象始终具有相同的大小。当您修改数组中的对象时，它不会更改对象的大小并移动数组的其余部分。