How does the capacity of std::vector grow automatically? What is the rate?

by

The rate at which the capacity of a vector grows is implementation dependent. Implementations almost invariably choose exponential growth, in order to meet the amortized constant time requirement for the push_back operation. What amortized constant time means and how exponential growth achieves this is interesting.

Every time a vector’s capacity is grown the elements need to be copied. If you ‘amortize’ this cost out over the lifetime of the vector, it turns out that if you increase the capacity by an exponential factor you end up with an amortized constant cost.

This probably seems a bit odd, so let me explain to you how this works…

  • size: 1 capacity 1 – No elements have been copied, the cost per element for copies is 0.
  • size: 2 capacity 2 – When the vector’s capacity was increased to 2, the first element had to be copied. Average copies per element is 0.5
  • size: 3 capacity 4 – When the vector’s capacity was increased to 4, the first two elements had to be copied. Average copies per element is (2 + 1 + 0) / 3 = 1.
  • size: 4 capacity 4 – Average copies per element is (2 + 1 + 0 + 0) / 4 = 3 / 4 = 0.75.
  • size: 5 capacity 8 – Average copies per element is (3 + 2 + 1 + 1 + 0) / 5 = 7 / 5 = 1.4
  • …
  • size: 8 capacity 8 – Average copies per element is (3 + 2 + 1 + 1 + 0 + 0 + 0 + 0) / 8 = 7 / 8 = 0.875
  • size: 9 capacity 16 – Average copies per element is (4 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 0) / 9 = 15 / 9 = 1.67
  • …
  • size 16 capacity 16 – Average copies per element is 15 / 16 = 0.938
  • size 17 capacity 32 – Average copies per element is 31 / 17 = 1.82

As you can see, every time the capacity jumps, the number of copies goes up by the previous size of the array. But because the array has to double in size before the capacity jumps again, the number of copies per element always stays less than 2.

If you increased the capacity by 1.5 * N instead of by 2 * N, you would end up with a very similar effect, except the upper bound on the copies per element would be higher (I think it would be 3).

I suspect an implementation would choose 1.5 over 2 both to save a bit of space, but also because 1.5 is closer to the golden ratio. I have an intuition (that is currently not backed up by any hard data) that a growth rate in line with the golden ratio (because of its relationship to the fibonacci sequence) will prove to be the most efficient growth rate for real-world loads in terms of minimizing both extra space used and time.

More Related Contents:

  1. How does vector’s growth function work? [closed]
  2. How do I print out the contents of a vector?
  3. How do I print out the contents of a vector?
  4. Concatenating two std::vectors
  5. How to shuffle a std::vector?
  6. Correct way to work with vector of arrays
  7. How do I sort a vector of pairs based on the second element of the pair?
  8. Vector going out of bounds without giving error
  9. Nice way to append a vector to itself
  10. How to remove duplicates from unsorted std::vector while keeping the original ordering using algorithms?
  11. Vector of const objects giving compile error
  12. C++ valarray vs. vector
  13. Is std::vector copying the objects with a push_back?
  14. vector::at vs. vector::operator[]
  15. How do I sort the texture positions based on the texture indices given in a Wavefront (.obj) file?
  16. Performance issue for vector::size() in a loop in C++
  17. Vector of std::function with different signatures
  18. Unresolved externals in C++ when using vectors and find
  19. Reading and writing a std::vector into a file correctly
  20. vector push_back calling copy_constructor more than once?
  21. May std::vector make use of small buffer optimization?
  22. Why doesn’t vector::clear remove elements from a vector?
  23. How to compare two vectors for equality element by element in C++?
  24. Converting between C++ std::vector and C array without copying
  25. std::vector resize downward
  26. What is better: reserve vector capacity, preallocate to size or push back in loop?
  27. std::dynarray vs std::vector
  28. Is there a standard way of moving a range into a vector?
  29. How to cheaply assign C-style array to std::vector?
  30. Prevent class inheritance in C++

Leave a Comment