Eu escrevi um pequeno pedaço de código para determinar como a alocação de memória em um vetor é feita.

#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;
}

Eu compilei isto usando o Visual Studio 2008 e g ++ 4.5.2 no Ubuntu e obtive estes resultados:

Estúdio visual:

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;

Como você pode ver, estes são dois resultados muito diferentes. Por que isso é assim? Só depende do compilador ou é viciado em outros fatores?

Será que realmente faz sentido continuar dobrando a capacidade, mesmo para um grande número de elementos?