How does std::vector reallocates every time an item is inserted using a loop?

Question

I've read that std::vector reallocation works like this:

How expensive is reallocation? It involves four steps:

1. Allocate enough memory for the desired new capacity;
2. Copy the elements from the old memory to the new;
3. Destroy the elements in the old memory; and
4. Deallocate the old memory.

So that it may be a good practice to use .reserve() somewhat like this:

std::vector<int> vec;
int unnkownNumberOfElementsToAdd = 30; //it's 30 now, but suppose you don't know

vec.reserve(unnkownNumberOfElementsToAdd);
for(int i=0; i<unnkownNumberOfElementsToAdd; i++ )
{
    vec.push_back(i);
}

So that it doesn't reallocate the entire vector everytime an item is inserted. But the funny thing is, if you DON'T .reserve() and you print vec.sizeand vec.capacity everytime i is inserted, this is the output:

size | capacity
1 1
2 2
3 3
4 4
5 6
6 6
7 9
8 9
9 9
10 13
11 13
12 13
13 13
14 19
15 19
16 19
17 19
18 19
19 19
20 28
21 28
22 28
23 28
24 28
25 28
26 28
27 28
28 28
29 42
30 42

I don't know if the capacity increase is compiler dependent (I'm using old VS2003). In case it's not, how does this reallocation works?

Answer 1

std::vector does not reallocate every time an element is added. It reallocates when it runs out of capacity. And when it reallocates, it doesn't allocate space for just 1 more element. It typically allocates by some factor of the the current capacity. I believe VS uses a factor of 1.5, and some others use 2. It has to do this in order to ensure that push_back has amortized O(1) complexity, which is a requirement of the standard.

If you know for certain exactly how many elements you are going to add to the vector over its lifetime, it is still a good idea to reserve though, imo. Some might consider that premature optimization. But it is such a simple thing to do, I consider not doing it to be premature pessimization.

Answer 2

reserve() is somehow outdated by now, as vector reallocation strategies are well-tailored for majority of usage.

However, they come with drawback. For instance, when I was dealing with 32-bit systems, I had an extremely large data structure (large because it holded a lot of elements) in memory, and one the members of it's elements was a vector. Vectors were incredibly short - many of them empty, some having one or two elements. Yet the implementation pre-allocated 32 elements, and caused my program to run out of memory (simply because I had insane number of those vectors). Replacing vector with list degraded my random access, but allowed the program to run.