16.10 — std::vector resizing and capacity

In the previous lessons in this chapter, we introduced containers, arrays, and std::vector. We also discussed topics such as how to access array elements, get the length of an array, and how to traverse an array. While we used std::vector in our examples, the concepts that we have discussed are generally applicable to all of the array types.

In the remaining lessons in this chapter, we’re going to focus on the one thing that makes std::vector significantly different than most of the other array types: the ability to resize itself after it has been instantiated.

Fixed-size arrays vs dynamic arrays

Most array types have a significant limitation: the length of the array must be known at the point of instantiation, and then cannot be changed. Such arrays are called fixed-size arrays or fixed-length arrays. Both std::array and C-style arrays are fixed-size array types. We’ll discuss these further next chapter.

On the other hand, std::vector is a dynamic array. A dynamic array (also called a resizable array) is an array whose size can be changed after instantiation. This ability to be resized is what makes std::vector special.

Resizing a std::vector at runtime

A std::vector can be resized after instantiation by calling the resize() member function with the new desired length:

#include <iostream>
#include <vector>

int main()
{
    std::vector v{ 0, 1, 2 }; // create vector with 3 elements
    std::cout << "The length is: " << v.size() << '\n';

    v.resize(5);              // resize to 5 elements
    std::cout << "The length is: " << v.size() << '\n';

    for (auto i : v)
        std::cout << i << ' ';

    std::cout << '\n';

    return 0;
}

This prints:

The length is: 3
The length is: 5
0 1 2 0 0

There are two things to note here. First, when we resized the vector, the existing element values were preserved! Second, the new elements are value-initialized (which performs default-initialization for class types, and zero-initialization for other types). Thus the two new elements of type int were zero-initialized to value 0.

Vectors may also be resized to be smaller:

#include <iostream>
#include <vector>

void printLength(const std::vector<int>& v)
{
	std::cout << "The length is: "	<< v.size() << '\n';
}

int main()
{
    std::vector v{ 0, 1, 2, 3, 4 }; // length is initially 5
    printLength(v);

    v.resize(3);                    // resize to 3 elements
    printLength(v);

    for (int i : v)
        std::cout << i << ' ';

    std::cout << '\n';

    return 0;
}

This prints:

The length is: 5
The length is: 3
0 1 2

The length vs capacity of a std::vector

Consider a row of 12 houses. We’d say that the count of houses (or the length of the row of houses) is 12. If we wanted to know which of those houses were currently being occupied… we’d have to determine that in some other way (e.g. ring the doorbell and see if anybody answered). When we only have a length, we only know how many things exist.

Now consider a carton of eggs that currently has 5 eggs in it. We’d say that the count of eggs is 5. But in this context, there’s another dimension we care about: how many eggs the carton could hold if it were full. We’d say that the capacity of the carton of eggs is 12. The carton has room for 12 eggs, and only 5 are being used -- therefore, we could add 7 more eggs without overflowing the carton. When we have both a length and a capacity, we can differentiate how many things currently exist from how many things there is space for.

Up to this point, we’ve only talked about the length of a std::vector. But std::vector also has a capacity. In the context of a std::vector, capacity is how many elements the std::vector has allocated storage for, and length is how many elements are currently being used.

A std::vector with a capacity of 5 has allocated space for 5 elements. If the vector contains 2 elements in active use, the length (size) of the vector is 2. The 3 remaining elements have memory allocated for them, but they are not considered to be in active use. They can be used later without overflowing the vector.

Getting the capacity of a std::vector

We can ask a std::vector for its capacity via the capacity() member function.

For example:

#include <iostream>
#include <vector>

void printCapLen(const std::vector<int>& v)
{
	std::cout << "Capacity: " << v.capacity() << " Length:"	<< v.size() << '\n';
}

int main()
{
    std::vector v{ 0, 1, 2 }; // length is initially 3

    printCapLen(v);

    for (auto i : v)
        std::cout << i << ' ';
    std::cout << '\n';

    v.resize(5); // resize to 5 elements

    printCapLen(v);

    for (auto i : v)
        std::cout << i << ' ';
    std::cout << '\n';

    return 0;
}

On the author’s machine, this prints the following:

Capacity: 3  Length: 3
0 1 2
Capacity: 5  Length: 5
0 1 2 0 0

First, we’ve initialized the vector with 3 elements. This causes the vector to allocate storage for 3 elements (capacity is 3), and all 3 elements are considered to be in active use (length = 3).

We then call resize(5), meaning we now want a vector with a length of 5. Since the vector only has storage for 3 elements, but it needs 5, the vector needs to get more storage to hold the additional elements.

After the call to resize() has completed, we can see that the vector now has space for 5 elements (capacity is 5), and that all 5 elements are now considered to be in use (length is 5).

Most of the time you won’t need to use the capacity() function, but we’ll use it a lot in the following examples so we can see what’s happening to the storage of the vector.

Reallocation of storage, and why it is expensive

When a std::vector changes the amount of storage it is managing, this process is called reallocation. Informally, the reallocation process goes something like this: