How does c std vector work

Question

How do the addition and removal of pieces "rescale" the data?

How is the vector's size determined (and, I presume, tracked)?

Any further resources for learning about vectors would be greatly appreciated.

Answer 1

In terms of sizing, a std::vector has two values of interest: size and capacity (accessible via.size() and.capacity()).

.size() returns the number of items in the vector, whereas.capacity() returns the number of elements that may be added to the vector before memory is re-allocated.

When you.push back() an element, the size increases by one until you reach the capacity. 

When the maximum capacity is reached, most (all?) implementations re-allocate memory, thereby doubling the capacity.

You can reserve a capacity by using the.reserve command (). 

As an 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.