12

i wrote a little piece of code to determine, how memory allocating in a vector is done. 

#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 using 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 like that? Is it only depending on the compiler or is it addicted to other factors?

Does it really make sense to keep on with doubling the capacity, even for large numbers of elements?

m47h
  • 1,611
  • 2
  • 18
  • 26
  • It's allowed to increase however they want it to as long as it fits the standard's requirements for the vector and it's efficiency. – chris Jul 19 '12 at 12:28
  • I think the capacity extension is dependent on the implementation of the compiler. I doubt the standard says anything about this. – nhahtdh Jul 19 '12 at 12:30
  • Stretching vector size like capacity = capacity * 1.5; produces, mathematically speaking, weird results using MSVS compiler. 1→2: 1 * 1.5 = 1.5 that is rounded up to 2 - that's FINE 3→4: 3 * 1,5 = 4.5 but the new allocation is 4, not 5 how you would assume according to rounding 0.5s up in math. Do someone know, what's happening here? – Stepo Dec 30 '16 at 18:02
  • They must be using half-even rounding mode https://en.wikipedia.org/wiki/Rounding#Round_half_to_even – lav Dec 11 '18 at 11:34

3 Answers3

8

How the vector is growing is implementation defined. So different strategies can be used resulting in different capacity after inserting the same count of elements

If you need to rely on how many items are allocated you should use reserve and/or resize methods of vector

Andrew
  • 24,218
  • 13
  • 61
  • 90
4

As you can see, VS is adding extra space with smaller chunks, while G++ i doing it by the powers of 2. This is just implementations of the same basic idea: the more elements you add, the more space will be allocated next time (because it is more likely that you will add additional data).

Imagine you've added 1 element to the vector, and I've added 1000. It's more likely that will add another 1000 and it is less likely that you will. This is the reasoning for such a strategy of allocating space.

The exact numbers sure depends on something, but that's the reasoning of the compiler makers, since they can implement it in any way they want.

SingerOfTheFall
  • 29,228
  • 8
  • 68
  • 105
3

The standard only defines a vector's behaviour. What really happens internally depends on the implementation. Doubling the capacity results in an amortized O(n) cost for pushing/popping n elements, which is required for a vector, I guess. Look here for more details.

Ben
  • 4,486
  • 6
  • 33
  • 48
  • 1
    the requirement of O(n) is an important aspect, i did not think about before – m47h Jul 19 '12 at 12:45
  • Wrong. _"any factor greater than 1 ensures O(1) amortized append complexity towards infinity"_ – https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md – Tamás Zahola Feb 09 '16 at 15:18
  • Adding/removing one element is done in (amortized) O(1), true. Adding/removing n elements - as stated in my answer - is done in linear time (meaning: it takes twice as long to insert the double amount of elements). But I admit that my answer was a bit confusing. When I just re-read my answer, I wondered myself, what I was thinking ;) – Ben Feb 10 '16 at 10:59