3

I know that in std::vector, the size will grow every time it runs out of room. Yet I'm not noticing a pattern in how it grows. Can someone please explain to me the pattern and why it was chosen. 

#include <iostream>
using namespace std;

#include <iostream>
#include <vector>
int main()
{
    vector<int> myVector;
    for(int i =0 ; i < 100; ++i)
    {
        myVector.push_back(i);
        cout << myVector.capacity();
    cout << ", ";
    }
}

Result:

1, 2, 3, 4, 6, 6, 9, 9, 9, 13, 13, 13, 13, 19, 19, 19, 19, 19, 19, 28, 28, 28, 2
8, 28, 28, 28, 28, 28, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 6
3, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 6
3, 94, 94, 94, 94, 94, 94, 94, 94, 94, 94, 94, 94, 94, 94, 94, 94, 94, 94, 94, 9
4, 94, 94, 94, 94, 94, 94, 94, 94, 94, 94, 94, 141, 141, 141, 141, 141, 141
Caesar
  • 9,483
  • 8
  • 40
  • 66
  • It's highly compiler dependedent, but I read somewhere (forgot source though) it grows by factor 2X in some implementations – Mr.Anubis Sep 01 '12 at 16:06
  • This is not standardized, so it depends on the implementation. You can't rely on any patterns. – juanchopanza Sep 01 '12 at 16:07
  • You can normally rely on the fact that when capacity is increased, it'll be `new_capacity = old_capacity * some_factor;`. The main area of variation is in the value of `some_factor`. This is normally carried out with integer arithmetic, so for the smaller numbers, rounding tends to hide the underlying pattern. – Jerry Coffin Sep 01 '12 at 16:20
  • If you're using Microsoft's standard library then it increases by a factor of 1.5. Stephan T. Lavavej once said so in one of his online videos about the std. – s3rius Sep 01 '12 at 23:30

2 Answers2

4

It depends on the implementation, so don't expect the same pattern when you switch the operating system, the compiler, etc.

The most common growth patterns are 1.5 * previous_capacity and 2 * previous_capacity. In your example, it seems that it's the former.

See https://stackoverflow.com/a/1100426/784668 for a possible explanation for why that factor was chosen. The point is that it apparently allows reusing free memory blocks that were previously used for storing the array.

Community
  • 1
  • 1
  • Why was this pattern chosen? Why not for example do it in a Fibonacci sequence? – Caesar Sep 01 '12 at 16:07
  • 1
    A Fibonacci sequence would also end up with O(log N) allocations for N `push_back`s, but is unnecessarily complicated. Occam's razor. – aschepler Sep 01 '12 at 16:11
  • I remember reading that *in the absence of other memory allocations* a Fibonacci sequence is actually the best. Something to do with most efficient reuse of freed memory. – john Sep 01 '12 at 16:55
1

It is an implementation detail, you are not supposed co care about it. In your case it seems to be something like

i += i/2

but somewhat more complex.

yuri kilochek
  • 12,709
  • 2
  • 32
  • 59