Vectors capacity question

[Ryan Wilson]

Well I've been learning about vectors in this C++ book and then came across the memory reallocation and deallocation process for them but I don't really get how these capacity numbers add up.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{

	cout << "Creating a 10 element vector to hold scores.\n";
	vector<int> scores(10, 0); // Initialize all 10 elements to 0
	cout << "\nVector size is :" << scores.size() << endl;
	cout << "Vector capacity is :" << scores.capacity() << endl;

	cout << "\nAdding a score.\n";
	scores.push_back(0); // memory is reallocated to accommodate growth
	cout << "\nVector size is :" << scores.size() << endl;
	cout << "Vector capacity is :" << scores.capacity() << endl;

	scores.push_back(0); // memory is reallocated to accommodate growth
	scores.push_back(0); // memory is reallocated to accommodate growth
	scores.push_back(0); // memory is reallocated to accommodate growth
	scores.push_back(0); // memory is reallocated to accommodate growth
	scores.push_back(0); // memory is reallocated to accommodate growth

	cout << "\nVector size is :" << scores.size() << endl;
	cout << "Vector capacity is :" << scores.capacity() << endl;

	scores.push_back(0); // memory is reallocated to accommodate growth
	scores.push_back(0); // memory is reallocated to accommodate growth
	scores.push_back(0); // memory is reallocated to accommodate growth
	scores.push_back(0); // memory is reallocated to accommodate growth
	scores.push_back(0); // memory is reallocated to accommodate growth
	scores.push_back(0); // memory is reallocated to accommodate growth
	scores.push_back(0); // memory is reallocated to accommodate growth

	cout << "\nVector size is :" << scores.size() << endl;
	cout << "Vector capacity is :" << scores.capacity() << endl;

	scores.push_back(0); // memory is reallocated to accommodate growth
	scores.push_back(0); // memory is reallocated to accommodate growth
	scores.push_back(0); // memory is reallocated to accommodate growth
	scores.push_back(0); // memory is reallocated to accommodate growth
	scores.push_back(0); // memory is reallocated to accommodate growth
	scores.push_back(0); // memory is reallocated to accommodate growth
	scores.push_back(0); // memory is reallocated to accommodate growth
	scores.push_back(0); // memory is reallocated to accommodate growth
	scores.push_back(0); // memory is reallocated to accommodate growth
	scores.push_back(0); // memory is reallocated to accommodate growth
	scores.push_back(0); // memory is reallocated to accommodate growth

	cout << "\nVector size is :" << scores.size() << endl;
	cout << "Vector capacity is :" << scores.capacity() << endl;

	return 0;
}

Am I explaining this right?

The first time I added another element to the stack of vector it has to reallocate memory for it because it extends the length of the vectors element size and then the capacity jumped from 10 to 15. Then after I pushed 5 more elements into the vector the capacity jumped from 15 to 22 which I was thinking it would just go up to 20. I know that I can avoid this by using reserve() but I just want to know the whole thing about this. Please tell me if I'm explaining with push, stack correctly as well etc, Thanks.

[Athar]

Usually vectors just double their capacity when it runs out, but the standard library that comes with VC++ is a bit more conservative and increases the capacity by 50% every time. That's where your numbers come from.

[Stewbond]

You are explaining it well.

It's good to know that Memory doesn't always fill up in order. When you define a label, it is given an address in memory where we know it will fit. A double takes up 8 bytes, so we look for space in the memory that has 8 consecutive bytes free.

With vectors we still want to store everything in one place. If we have a vector<int> with three elements, then we need to store the vector in a place where there are at least 3*4 = 12 bytes free. There could be more free. If there is more free then we can see that with .capacity().

When we reach the capacity, the next push_back() will reallocate the vector to a location where there is a larger chunk of free memory. How big will this chunk be? AT LEAST big enough to take the new vector, maybe bigger. How much bigger? This is not constant, and guessing would not be reliable. Once it has been allocated, you can tell how much bigger by using .capacity().

EDIT: I didn't realize it was by 50% each time. I learned something! Thanks Athar

[Ryan Wilson]

Thanks for the explanation Athar, and Stewbond!

[Ryan Wilson]

From reading this book though it says in little game programs that I'm going to be making in the near future for education purposes won't really need reserve() sense they will be a smaller program than production games, and I shouldn't obsess over the concept because they really wont benefit from it.

[JLBorges]

The requirement for a vector is that we must be able to add or remove elements from the end of the sequence (push_back/pop_back) in constant amortized time.

Let us say the current size() == capacity() == N
To add a new element, the capacity must be increased, say by M to N+M.

The question now is: what should be the value of M?

When the capacity is increased from N to N+M, freash memory has to be allocated
and the N elements in the vector must be moved/copied. The time taken for this is clearly O(N).

The time taken to pusk_back another element, all that is needed is that the element is copied/moved into the buffer; this clearly takes constant time or O(1).

Once we have added another M elements, we are back to square one; current size() == capacity().

The total time to push_back M elements == O(N) + ( M * O(1) )

The amortized time to add M elements == ( O(N) / M ) + ( ( M * O(1) ) / M ) ) and this must be a constant or O(1).

Therefore, M must be proportional to N.



> won't really need reserve() ...
> ... shouldn't obsess over the concept because they really wont benefit from it.

Yes. Most real life measurements indicate that in the typical case, reserve() does not yield any significant improvement in performance.

[Athar]

Yes. Most real life measurements indicate that in the typical case, reserve() does not yield any significant improvement in performance.

It should be apparent that reserve() only makes sense is when you have a large number of objects and and you already know how many in advance. This can significantly improve performance (how much exactly depends on the stored type) and more importantly, it massively reduces peak memory usage.

Example with pushing back 150 million 4-byte elements:
Without reserve(): 1.5 GB peak memory usage, 1.0 GB stay allocated
With reserve(): ~572 MB peak memory usage, ~572 MB stay allocated

[JLBorges]

> it massively reduces peak memory usage.

Yes. During the buffer resize, both buffers must remain allocated for the duration of the copy/move.