std::vector memory

I have been using vectors for leet coding all the time. However, I still think that vector is worth talking about and its memory management in C++. Let us talk about the vector template class in C++ and its memory behind it.

Basics

The vector class in C++ is like a resizable array, a template class in a standard template library. Consider the following Student class.

Let’s say now we want to create an array using vector and name it classRoomSeat. We want to assign only 5 seats to the classroom so let us declare a vector with a size of 5, with initializing some initial data to each block of vector as a Student class.

In this case, I would like to illustrate the situation of push_back() method with a fill vector constructor. Consider the following main function.

And when we try to call the printStudentInfor method for the first element in the vector, this is what the result shows.

Student empty has an age 0 with height 0 
Student empty has an age 0 with height 0  
classRoomSeat has a size of 7

The reason is that the vector has a size of 5 when we construct it and we push 2 more elements to the end of the vector so the total size is actually 7.

If we pre-sized the vector, avoid setting an element using index notation. Although it won’t throw an exception the behavior is undefined. On the other hand, do not use push_back() method if we pre-sized the vector.

2 ways of vector iteration

One way is to use an iterator object to overload the * operator and access the iterator like a pointer by dereferencing it. The alternative way is just a simple old school index base for loop iteration.

We can add a const keyword to iterator to tell the compiler that we are not going to change to the content of the vector.

Student empty has an age 0 with height 0 
Student empty has an age 0 with height 0 
Student empty has an age 0 with height 0 
Student empty has an age 0 with height 0 
Student empty has an age 0 with height 0 
Student Kevin has an age 18 with height 180.2 
Student Mary has an age 18 with height 158.9

Memory in vector

A vector manages an array internally.

If we add more elements to the vector that the internal array can currently hold, the vector class will create another array that is bigger and copies all the elements from the old array to the new array. The vector has a method called capacity, which is the size of the internal array that the current vector is using. Consider the following code and result to see how the internal array changes.

Initial vector size = 20
Initial internal array size = 20
i = 0, vector size = 21, internal array size = 40
i = 20, vector size = 41, internal array size = 80
i = 60, vector size = 81, internal array size = 160
i = 140, vector size = 161, internal array size = 320
i = 300, vector size = 321, internal array size = 640
i = 620, vector size = 641, internal array size = 1280
i = 1260, vector size = 1281, internal array size = 2560
i = 2540, vector size = 2561, internal array size = 5120
i = 5100, vector size = 5121, internal array size = 10240

What does the result prove? The internal array uses new to create a new array exponentially by doubling the size of the old array whenever the size exceeds the old array size. Hence, push_back is O(1) time in the majority of the case but when the size exceeds what the internal array can hold, the push_back is in O(n) time as it has to create a new array with double the size of the old array and copy all elements in the old array to the new array.

Some vector methods to mention

.clear() method

We can clean up the vector by using .clear() method where all contents in the vector will be removed. But let us see what is going inside the internal array. Consider the following code from above.

Initial vector size = 20
Initial internal array size = 20
i = 0, vector size = 21, internal array size = 40
i = 20, vector size = 41, internal array size = 80
i = 60, vector size = 81, internal array size = 160
i = 140, vector size = 161, internal array size = 320
i = 300, vector size = 321, internal array size = 640
i = 620, vector size = 641, internal array size = 1280
i = 1260, vector size = 1281, internal array size = 2560
i = 2540, vector size = 2561, internal array size = 5120
i = 5100, vector size = 5121, internal array size = 10240
vector size = 0
internal array size = 10240

We can see that the vector size is 0 now but we are not able to remove the size of the internal array created after using push_back() method.

.resize() method

There is another method that I also want to mentioned and it is the .resize() method. It resizes the vector but has no effect on the internal array size. Consider the code below and the result from above (I will not repeat the code above again here).

2
vector size = 100
internal array size = 10240

.reserve() method

But how about the internal array? What if we want to modify the current internal array size? Consider the code below to see how .reserve() help us to deal with it. This method also creates a new internal array and copy all the elements from the old array to the new array.

internal array size before reserve = 10240
2
vector size = 10020
internal array size = 20000

Conclusion

All in all, I have explained how the vector template class in the standard template library manages an array using the new keyword behind, as well as some methods that worth digging deep to see how the memory works behind. Nowadays many high-level languages provide many convenient features for programmers. As a good software engineer, we should always know deeply about how the language works and its nature.