当涉及到一个序列时，"vector[n].push_back()" 总是 O(1) 吗？
When it comes to a sequence, is "vector[n].push_back()" is always O(1)?
我用了很多vector<int> v[N]。
这对我来说是一个非常强大的工具。
我不知道 v[n].push_back() 平均花费 O(1)。
我知道当vector满了，它需要扩展成double。
但是向量序列不是相互依附的吗？
如果是这样，我认为所有向量都需要向左移动，这意味着它的成本超过 O(n)。
综上所述，当涉及到向量序列时，v[n].push_back() 总是 O(1) 吗？
请给我一些帮助:D
反正也不总是 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.
所以即使只有一个向量，也不能保证它是常数。
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).
这不会影响运行时间。数组中的向量彼此独立并动态管理自己的存储（并且彼此分开）。数组中的实际矢量对象始终具有相同的大小。当您修改数组中的对象时，它不会更改对象的大小并移动数组的其余部分。
If so, I think all vectors need to shift to the left which means it costs more than O(n).
不，事实并非如此。
std::vectors 为数组动态分配内存以将元素放入其中，并且仅存储指向该数组的指针（连同大小和容量）。 sizeof(std::vector<T>) 是编译时常量。当您向向量添加元素时，c 数组中 std::vector 占用的内存量不会改变。
因此，push_back 的复杂性不受将向量放在数组中的影响。
我用了很多vector<int> v[N]。
这对我来说是一个非常强大的工具。
我不知道 v[n].push_back() 平均花费 O(1)。
我知道当vector满了，它需要扩展成double。
但是向量序列不是相互依附的吗？
如果是这样，我认为所有向量都需要向左移动，这意味着它的成本超过 O(n)。
综上所述，当涉及到向量序列时，v[n].push_back() 总是 O(1) 吗？
请给我一些帮助:D
反正也不总是 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.
所以即使只有一个向量，也不能保证它是常数。
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).
这不会影响运行时间。数组中的向量彼此独立并动态管理自己的存储（并且彼此分开）。数组中的实际矢量对象始终具有相同的大小。当您修改数组中的对象时，它不会更改对象的大小并移动数组的其余部分。
If so, I think all vectors need to shift to the left which means it costs more than O(n).
不，事实并非如此。
std::vectors 为数组动态分配内存以将元素放入其中，并且仅存储指向该数组的指针（连同大小和容量）。 sizeof(std::vector<T>) 是编译时常量。当您向向量添加元素时，c 数组中 std::vector 占用的内存量不会改变。
因此，push_back 的复杂性不受将向量放在数组中的影响。