When it comes to a sequence, is "vector[n].push_back()" is always O(1)?

Question

I've used vector<int> v[N] a lot.
It's a very powerful tool for me.

I wonder v[n].push_back() costs O(1) on average.
I know when the vector is full, it needs to expand into double.
But isn't the sequence of vectors attached to each other?
If so, I think all vectors need to shift to the left which means it costs more than O(n).

To sum up, when it comes to sequence of vector, is v[n].push_back() always O(1)?
Please give me some help :D

Answer 1

If so, I think all vectors need to shift to the left which means it costs more than O(n).

No thats not the case.

std::vectors dynamically allocate memory for an array to place the elements inside and merely store a pointer to that array (together with size and capacity). sizeof(std::vector<T>) is a compile-time constant. The amount of memory occupied by a std::vector inside a c-array does not change when you add elements to the vectors.

Hence, complexity of push_back is not effected by placing the vector in an array.