How does c++ std::vector work?

Question

How does adding and removing elements "rescale" the data? How is the size of the vector calculated (I believe it is kept track of)? Any other additional resources to learn about vectors would be appreciated.

Answer 1

In terms of sizing, there are two values of interest for a std::vector: size, and capacity (accessed via .size() and .capacity()).

.size() is the number of elements that are contained in the vector, whereas .capacity() is the number of elements that can be added to the vector, before memory will be re-allocated.

If you .push_back() an element, size will increase by one, up until you hit the capacity. Once the capacity is reached, most (all?) implementations, re-allocate memory, doubling the capacity.

You can reserve a capacity using .reserve(). For example:

std::vector<int> A; A.reserve(1);        // A: size:0, capacity:1  {[],x} A.push_back(0);      // A: size:1, capacity:1  {[0]} A.push_back(1);      // A: size:2, capacity:2  {[0,1]} A.push_back(2);      // A: size:3, capacity:4  {[0,1,2],x} A.push_back(3);      // A: size:4, capacity:4  {[0,1,2,3]} A.push_back(4);      // A: size:5, capacity:8  {[0,1,2,3,4],x,x,x} 

Reallocations of memory would occur at lines 4, 5, and 7.

Answer 2

The vector usually has three pointers. If the vector has never been used they are all 0, or NULL.

• One to the first element of the vector. (this is the begin() iterator)
• One to last element of the vector + 1. (this is the end() iterator)
• And one more to the last allocated but unused element + 1. (this minus begin() is the capacity)

When an element is inserted, the vector allocates some storage and sets its pointers. It might allocate 1 element, or it might allocate 4 elements. Or 50.

Then it inserts the element and increments the last element pointer.

When you insert more elements than are allocated the vector has to get more memory. It goes out and gets some. If the memory location changes then it has to copy all the elements into the new space and free the old space.

A common choice for resizing is to double the allocation every time it needs more memory.