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

It's one of these:

http://en.wikipedia.org/wiki/Dynamic_array

Answer 2

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

http://en.wikipedia.org/wiki/Vector_%28C%2B%2B%29

Answer 3

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

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.