Reallocation intervals of <vector> library (c++)

Question

I'm trying to understand how to dynamically allocate more space in a dynamic array in the most efficient way.

So I tried to understand how the reallocations are made in the std::vector library. According to this:

"Libraries can implement different strategies for growth to balance between memory usage and reallocations, but in any case, reallocations should only happen at logarithmically growing intervals of size so that the insertion of individual elements at the end of the vector can be provided with amortized constant time complexity"

What does "logarithmically growing intervals of size" mean? Assume I now have an array with capacity n and there is no vacancy at all. What would be the next reallocation?

Also, how exactly does the amortized complexity become constant? I'd really appreciate an explanation about how it is more efficient than reallocation's by constant, i.e, say now we have an array of length n with no vacancy, the reallocation would be an array of n+constant, say n+15.

Answer 1

The sentence is wrong. It is supposed to say

at exponentially growing intervals

or practically speaking usually a geometric series is used to achieve this, since it only requires multiplying the capacity by a constant at each reallocation.

With the geometric series allocation points are at sizes a^k with positive integers k and constant factor a>1, the sum is asymptotic to a^(k_max+1)/(a-1) and given that k_max must be so that a^k_max = n, we have then a total complexity of at most n*a/(a-1), averaging to constant amortized.