0

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

Blaze
  • 16,736
  • 2
  • 25
  • 44
marks jun
  • 25
  • 4
  • Isn't this explicitly documented already? Research first please. – user202729 Dec 03 '19 at 10:44
  • I know for "vector v", the "v.push_back(a)" takes O(1) on average. I'm wondering when it comes to "vector v[n]" it cost O(1) on average or not. – marks jun Dec 03 '19 at 10:48
  • Check this one: https://stackoverflow.com/questions/3064559/how-is-vector-implemented-in-c – Pedro Isaaco Dec 03 '19 at 10:49
  • @marksjun Calling `push_back` on some vector in an array of vectors does not affect the other vectors in any way. – Max Langhof Dec 03 '19 at 10:51
  • Array access (as in `v[n]`) is `O(1)`. Complexity of `std::vector`s `push_back()` is amortised constant time. That doesn't mean that it is always `O(1)`. It means that, using `push_back()` to insert `m` elements is `O(m)`. Which means the times may vary between calls of `push_back()` but that they average out in the long run. – Peter Dec 03 '19 at 11:39

2 Answers2

4

It's not always O(1) anyway. See here (emphasis mine):

Complexity

Constant (amortized time, reallocation may happen).

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

So even with just one vector, it's not guaranteed to be constant.

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).

This doesn't affect the runtime. The vectors in the array are independent of each other and manage their own storage dynamically (and separate from each other). The actual vector object in the array is always of the same size. When you modify an object in an array, it doesn't change the size of the object and move the rest of the array.

Blaze
  • 16,736
  • 2
  • 25
  • 44
  • it still is guaranteed to be amortized constant, though I have to admit I dont fully understand "amortized" either, only that amortized does not tell you complexity of a single call, but rather averaged over many calls – 463035818_is_not_an_ai Dec 03 '19 at 10:48
  • 2
    Yes, it's constant on average. This is because the storage goes up exponentially every time it's reallocated, and if you add up the total runtime and divide it by the amount of calls, the result is constant. But if we look at one single call in a vacuum, it's not guaranteed to be constant. So if we have, say, a time critical call where we have to be sure that it's done in constant time, we would have to be sure that no reallocation happens. – Blaze Dec 03 '19 at 10:51
  • @MaxLanghof Yes, I covered that in the second part of the answer where I explained that modiying an element of an array does generally not affect the rest of the array. – Blaze Dec 03 '19 at 10:52
  • 2
    @Blaze Reading would've helped, my bad. – Max Langhof Dec 03 '19 at 10:52
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.

463035818_is_not_an_ai
  • 109,796
  • 11
  • 89
  • 185
  • @marksjun actually i didnt write anything that wasnt already present in the other answer, I just thought sometimes it helps to have more than one view on the same – 463035818_is_not_an_ai Dec 03 '19 at 10:59