0

I am a college Computer Science student and I have been trying to understand the stl::vector on a deeper level. I found out, vector are in fact dynamic arrays, meaning upon insertion/deletion, if needed, the array is resized.

A friend told me, when the array's reallocated, for example upon insertion, instead of creating a new array of size [original+1], it creates a new array of a size [2*original].

Wouldn't it be better to only add (or substract) one array field when you insert/delete something, instead of creating an array twice as large, leaving many indexes unused?

I thought the reason for this is, that perhaps creating an array twice as large, or reallocatin the array, only every once in a while rather than on every insertion/deletion has much better time complexcity, but for example, if I had an array of large objects, would it even then be still better to reallocate an array twice the size of original, or use size+1?

Thank you for responses.

Andy
  • 63
  • 1
  • 6
  • Yes, it's because then array insertion is amortized `O(1)`. If you reallocated and potentially copied the whole array each time, then array insertion would be `O(n)`. – The Paramagnetic Croissant Jan 06 '15 at 09:09
  • 1
    This post is very misleading. It's only specifically `std::vector` that reallocates in this way, not "any dynamically allocated array". In fact, `std::vector` is *not* a dynamically allocated array, and it separates memory from object construction, which makes this whole approach feasible in the first place. – Kerrek SB Jan 06 '15 at 09:09
  • @timrau Wow, thank you for the link, mate. I was trying all sorts of querries but couldn't ask the right question to see an answer. – Andy Jan 06 '15 at 09:12

1 Answers1

1

The reason is mathematics.

Containers with the reallocation strategy that you describe (or any exponential growth, for that matter, the factor is irrelevant) guarantee asymptotically averaged constant cost for inserting an element at the end, i.e. the cost of inserting n elements, all divided by n, converges to a constant value as n gets large. That's because allocations get increasingly rare as n grows.

If you always grew the array by one on each insertion, you would incur linear cost for each insertion.

Note that std::vector is not a "dynamically allocated array" in the sense of C++'s native array type new T[N]; and instead it separates memory allocation from object construction. What grows exponentially is std::vector's allocated memory. The number of constructed objects is always precisely the current size of the container.

Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084