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.


It's one of these:


+5  A: 

There is a really nice wikipedia article about the stl vector class


Nikolaus Gradwohl
It's generally considered good form, when posting a link, to give an extract in your answer, especially when the link provides much more information than the specific question. It allows the reader to decide whether or not clicking and prevents the information provided from becoming meaningless if ever the page referenced were to move/disappear. It's a very good link nonetheless.
Matthieu M.

The required things are written in the C++ standard documents. Questions like calculation of the size of the vector are implementation specific.

Peter G.

I wrote a vector in C++ a year or so ago. It is an array with a set size (ex. 16 chars) which is expanded by that amount when needed. That is to say, if the default size is 16 chars and you need to store Hi my name is Bobby, then it will double the size of the array to 32 chars then store the char array there.

Caleb Thompson
+10  A: 

In terms of sizing, there are two values of interest for an 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.

+1  A: 

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.

Zan Lynx
+1, Not only doubling the memory is a common pattern, but it is "required"(\*) to fulfill the *amortized constant time insertion and deletion at the end*. (\*) doubling is not required, but exponential growth is.
David Rodríguez - dribeas

Every time you resize a vector, God kills a kitten. – Noah Roberts

@Noah Roberts yes, but using reserve() method on the vector should decrease the amout of resizes of vector in memory.