Vector memory allocation strategy

Question

I wrote a small piece of code to determine how memory allocation is performed in a vector.

#include <iostream> #include <vector> using namespace std; int main () { vector<unsigned int> myvector; unsigned int capacity = myvector.capacity(); for(unsigned int i = 0; i < 100000; ++i) { myvector.push_back(i); if(capacity != myvector.capacity()) { capacity = myvector.capacity(); cout << myvector.capacity() << endl; } } return 0; } 

I compiled this with Visual Studio 2008 and g ++ 4.5.2 on Ubuntu and got these results:

Visual Studio:

1 2 3 4 6 9 13 19 28 42 63 94 141 211 316 474 711 1066 1599 2398 3597 5395 8092 12138 18207 27310 40965 61447 92170 138255

 capacity = capacity * 1.5; 

g ++:

1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072

 capacity = capacity * 2; 

As you can see, these are two very different results. Why is this so? Does it depend only on the compiler or depends on other factors?

Does it really make sense to continue to double capacity even for a large number of elements?

Answer 1

As vector grows, implementation is determined. Thus, different strategies can be used, which leads to different capacities after inserting the same number of elements.

If you need to rely on how many positions are allocated, you should use the reserve and / or resize vector methods

Answer 2

As you can see, VS adds extra space with smaller fragments, while g ++ does it in powers of 2. This is just an implementation of the same basic idea: the more elements you add, the more space will be allocated next time (because more it’s likely that you will add additional data).

Imagine you added 1 element to a vector, and I added 1000. Most likely, it will add another 1000, and it will be less likely that you will do it. These are arguments in favor of such a space allocation strategy.

The exact numbers will probably depend on something, but this is the reason for the compiler manufacturers, because they can implement it in whatever way they want.

Answer 3

The standard defines only vectorial behavior. What really happens inside depends on the implementation. Doubling the capacity leads to the amortized cost of O (n) for push / popping n elements, which is required for the vector, I think. Check here for more details.