The basics

Assume that one wants to store a list of student grades for a course (each grade is an int), so that some statistics can be computed. Most courses have dozens, some even over a hundred, students. Thus, defining one variable for each student, as shown below, is just not practical.

1
2
3
4
5
6
7
8
9
10
11
12
13
// Store the grades of 160 students
int grade0 = 20;
int grade1 = 65;
int grade2 = 73;
// ...
int grade159 = 88;

// Display the grades of all students
std::cout << grade0 << "\n";
std::cout << grade1 << "\n";
std::cout << grade2 << "\n";
// ... there must be a better way to code this!!
std::cout << grade159 << "\n";

This problem can be solved by using vectors. A vector represents a list of variables, each variable storing a value of the same type (e.g. int).

Vectors are part of the standard library of C++. Thus, to be able to use vectors in a C++ program, one needs to state that the vector library is used in the program. That’s the purpose of line $1$ of the code excerpt below.

1
2
3
4
#include <vector>

// Define a list V of 5 integers
std::vector<int> V = {1, 5, 4, 33, 0};  // define & initialize a vector

In line $4$, a vector named V is created to store a list of five integer values ($\{1, 5, 4, 33, 0\}$). Vector V consists of five variables of type int named and initialized as follows.

• Variable V[0] initialized with first value of the list, i.e. $1$.
• Variable V[1] initialized with second value of the list, i.e. $5$.
• Variable V[2] initialized with third value of the list, i.e. $4$.
• Variable V[3] initialized with fourth value of the list, i.e. $33$.
• Variable V[4] initialized with fith (and last) value of the list, i.e. $0$.

Vector V can be depicted as shown below.

Some important aspects about vectors to keep in mind.

• A vector keeps track of how many values it stores (size) and where is the first variable (V[0]) storing the first list’s value.
• std::ssize(V) gives the number of values stored in vector V (e.g. in the example above, $5$).
• All variables forming vector V, i.e. V[0], V[1], V[2], V[3], and V[4], are placed contiguously (i.e. one immediately after the another) in the computer’s memory. In this way, the vector only needs to know where its first variable is located in the memory.
• All variables of a vector store values of the same type (variables V[0], V[1], V[2], V[3], and V[4] are of type int).
• The variables forming vector V are subscripted (i.e. are numbered or have indices) starting from zero. Thus, the first variable V[0] has subscript (index) $0$, the second variable V[1] has subscript $1$, the third variable V[2] has subscript $2$ etc. The last variable of the vector has subscript std::ssize(V)-1. Note that programmers write subscripts between square brackets ‘[’ and ‘]’, though usually in math books subscripted variables are written as $V_0$, $V_1$, $V_2$, etc.

The program below defines a vector and displays the number of values it stores.

1
2
3
4
5
6
7
8
9
#include <iostream>
#include <vector>

int main() {
    std::vector<int> V = {1, 5, 4, 33, 0};

    // Display number of values stored in V
    std::cout << "V has " << std::ssize(V) << " elements.\n";
}

Of course, the values stored in a vector can be of some other type then int. Below, we show how to create a vector A storing a list of six elements of type double.

std::vector<double> A = {1.1, 5.5, 4.123, 33.8, 0.0, -1.2};

Defining and initializing vectors

Let us now see several examples of how vectors can be defined and initialized. These examples illustrate common ways of creating vectors used in programs.

First, it’s possible to create an empty vector (i.e. a vector that stores no elements, yet).

// Empty vector
std::vector<int> V1;

An empty vector can be depited as follows. Note that std::ssize(V1) is zero, since V1 does not store any values.

One may wonder what use one can have of an empty vector. But, as you will see in section Adding an element, it’s possible to add elements (variables storing values) to a vector during program execution. For instance, recall the problem of storing the grades students got for an exam to then compute some statistics (e.g. average grade). It’s not possible to know in advance how many students do an exam, it varies from course to course and from one exam occasion to another. Thus, an approach to the problem is that the program starts by creating an empty vector. When the program begins executing, it then requests each grade and adds it to the vector.

As seen in the previous section, it’s possible to supply a list of values when a vector is defined.

// Create a vector of six doubles and initialize it
std::vector<double> V2 = {1.1, 5.5, 4.123, 33.8, 0.0, -1.2};

It’s also possible to create a vector consisting of a number of copies of a given value. For instance, the statement below creates a vector with six copies of int $-1$.

// Create a vector of six integers and initialized all with -1
std::vector<int> V3(6, -1);

The next statements can be used to create a vector with six elements (of type int or double) and initialize them with zero.

// Create a vector of six integers, all initialized with 0
std::vector<int> V4(6);

// Create a vector of six doubles, all initialized with 0.0
std::vector<double> V5(6);

Subscripting

Recall that a vector represents a list of variables, all of the same type. One can fectch an element (or variable) of a vector by using a subscript (or index) between square brackets. For instance, V[3] is the fourth element of vector V (equivallent to $V_3$ in math). The first element of a vector has always subscript zero, i.e. V[0].

1
2
3
4
5
6
7
8
9
// Define a list V of 5 integers
std::vector<int> V = {1, 5, 4, 33, 0};  // define & initialize a vector

// Display the first element of V
std::cout << "First element: " << V[0] <<"\n";  // display 1
/ Display the third element of V
std::cout << "First element: " << V[2] <<"\n";  // display 4
// Display the last element of V
std::cout << "Last element: " << V[std::ssize(V)-1] <<"\n";  // display V[4], i.e. 0

As seen in the example code above, int constants such as0 or 2 can be used as subscripts.

Note that the last element of a vector V has index V[std::ssize(V)-1] because the index of the first element is always zero.

In addition, any int variable or expression evaluating to an int can be used as a subscript. For example, V[i] gives access to the the $i$th element stored in a vector, where i is an int variable (see the next program).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <vector>

int main() {
    // Define a list V of 5 integers
    std::vector<int> V = {1, 5, 4, 33, 0};
	 
    std::cout << "Enter an integer (0 to 4): ";
    int i;
    std::cin >> i;

    // Display the ith value of vector V
    std::cout << V[i] << "\n";
}

One could also modify the $(i+1)$th value in the vector to $-5$, by adding the following line of code to the program above. Note that i is an int variable and, consequently, the expression i+1 also returns an int value as result of its evaluation.

V[i+1] = -5;

One can even use more complex expressions as subscripts of a vector, as long the expressions evaluate to an int.

int k = 2;
V[2*i - k] = -5;

One can also easily write a loop that modifies each value stored in vector V to $-5$.

for(int i = 0; i < std::ssize(V); ++i) {
    V[i] = -5;
}

To access an element (variable) of a vector V, one must use an integer expression exp to subscript the vector, i.e. V[exp]. In other words, exp must be an integer constant (e.g. $0$) or an integer arithmetic expression.

Traversing a vector

It’s quite common that programs need to traverse a vector, i.e. access each variable (or value) of a vector and perform some operation with it. For instance, consider that one wants to display all values stored in a vector. A for-loop can be used for this purposed, as shown below.

1
2
3
4
5
std::vector<int> V = {1, 5, 4, 33, 0};
 
for(int i = 0; i < std::ssize(V); ++i) {
    std::cout << V[i] << "\n";
}

Note that the int variable i is used as subscript of vector V and i ranges from $0$ (the subscript of the first variable of V) to std::ssize(V)-1 (the subscript of the last variable of V). Thus, the test i < std::ssize(V) in line $3$ makes sure that the loop stops when the last element has been visited.

Another example is shown which multiplies by $2$ the value stored in each variable of vector V.

for(int i = 0; i < std::ssize(V); ++i) {
    V[i]*= 2;
}

In modern C++, one can also use range-based loops to traverse a vector. For instance, one can display all values stored in vector V by using a range-based loop.

for(int value : V) {
    std::cout << value << "\n";
}

The int variable value gets a copy of the value store in variable V[0] in the first iteration of the loop, then value gets a copy of value of V[1] in the second iteration of the loop, and so on, until the last element of the vector V[std::ssize(V)-1] is visited. Variable value has type int because the vector stores elements of type int.

The next example shows a range-based loop that counts the number of odd elements stored in vector V.

int count_odd = 0;        // define a variable to count odd values and initialize it to zero
for(int value : V) {
    if (value % 2 == 1) { // it it a odd value?
        ++count_odd;      // increment the counter of odd values
    }		
}
std::cout << "Number of odd elements: " << count_odd;

The range-based loop above could easily be replaced by a for-loop (and this is often the case). However, whenever possible, we prefer range-based loops to other types of loops because they are less verbose, consequently easier to read, and less error prone (see Pitfalls section).

Adding an element

In C++, vectors support a function named push_back that adds a new element (variable) to the end of the vector. In this way, one can use this function to make a vector to grow one element at a time. For instance, consider an empty vector A of numbers (doubles).

// Empty vector
std::vector<double> A;

The vector can be depicted as follows. Note that std::ssize(A) evaluates to $0$, since the vector has no elements, yet.

We now add the first number $1.2$ to vector A.

A.push_back(1.2);

The vector looks then like this. Note that the vector’s size becomes $1$.

Let us add one more number, $5$, to vector A.

A.push_back(5);

Note that push_back always adds elements to the end of the vector and increments the vector’s size.

Finally, we add two more values to A.

A.push_back(4.6);
A.push_back(-1);

Next, we give two practical examples that use vectors and the push_back operation.

Example $1$: Consider that one wants to create a vector storing a list of $1000$ integers, with values $0$, $1$, $2$, $\cdots$, $999$. Creating directly a vector with $1000$ elements and initializing it as we did previously, in section Defining and initializing vectors would not be feasible because we would need to type $1000$ values for initializing the vector. Instead, one can start with an empty vector and then use a loop to add one element at a time, as shown below.

1
2
3
4
5
6
std::vector<int> V;  // empty vector

// Add integers 0 to 999 to V
for (int i = 0; i != 1000; ++i) {
     V.push_back(i);
}

Example $2$: Assume that you are asked to create a C++ program that performs the following steps, by the indicated order.

• To read a list of grades.
• To display the average grade.
• To display all grades, five per line. The grades above the average should also be marked.

The user provides the grades as a list of integers (validation not needed) terminated by a non-integer (e.g. “STOP”). An example of the program execution is shown below.

As you probably guess, a vector is used to store the grades. It’s not know in advance how many grades the user will provide nor the grade values. Thus, the program starts by creating an empty vector, named grades (line $21$). It then requests the user to enter the grades (line $23$). A while-loop is used to read one grade at a time and the body of the loop adds each new grade read to the end of vector grades (lines $26$ to $29$). Note that push_back is used to add each grade to the vector. When the program attempts to read a non integer value like word “STOP”, while-loop stops executing because it’s not possible to store value “STOP” in an int variable (grade_).

Before proceeding, the program tests if any elements have been added to the vector. Imagine that the user just types “STOP” as input. In this case, the while-loop (lines $27$ to $29$) would not execute at all and vector grades would remain empty. The if-statement in line $31$ tests if the vector is empty and if not then the average is computed (lines $34$ to $50$) followed by displaying the grades (lines $52$ to $71$), as requested. Note that testing whether vector grades is empty is also important to avoid a division by zero in line $46$ which would lead to a nasty run-time error, see also Run-time errors. Just try it! Most likely, you’ll get that “Average = -nan”, where “nan” means “not a number”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <iomanip>
#include <vector>

/*
* Test data:
55 78 90 45 100 90 95 70 78 68
55 78 90 40 100 90 95 70 80 68
60 78 90 50 100 90 95 70 80 68
55 78 90 77 30  90 95 70 80 68
55 78 90 77 68  85 95 55 80 68
99 78 65 77 68  85 95 55 80 68
99 78 65 77 68  85 95 55 80 100
99 33 65 67 68  85 65 55 53 100
90 33 65 67 60  85 65 55 53 92
10 23 65 67 16  70 65 50 53 92
STOP
*/

int main() {
    std::vector<int> grades;  // empty vector

    std::cout << "Enter student's grades:\n";

    // Read list of grades and store them in vector grades
    int grade_;
    while (std::cin >> grade_) {   // Read one more grade
        grades.push_back(grade_);  // Add _grade to vector grades
    }

    if (grades.empty() == false) {  // has the user provided any grades?
        std::cout << "\n";

        // Calculate average grade
        //=========================================

        // 1. calculate the sum of all grades
        double sum = 0.0;

        // range-based loop
        for (int g : grades) {
            sum += g;
        }

        // 2. make the average
        double average = sum / std::ssize(grades);
        //=========================================

        // Display average grade
        std::cout << "Average = " << average << "\n\n";

        // Display all grades, 5 values per line
        // Mark the grades above the average
        constexpr int ncols = 5;
        std::cout << "The list of grades: \n";

        int counter = 0;  // to count number of grades displayed

        for (int g : grades) {  // loop through each grade g in vector grades
            std::cout << std::setw(8) << g;

            if (g > average) {     // is grade g above average?
                std::cout << "^";  // mark the grade
            } else {
                std::cout << " ";
            }
            ++counter;
            if (counter % ncols == 0) {  // is counter a multiple of ncols?
                std::cout << "\n";       // change line
            }
        }
        std::cout << "\n";
    } else {
        std::cout << "No grades provided!!\n";
    }
}

We have seen, in this section, that V.push_back(e) adds an element e to the end of vector V. However, in some practical applications, one may need to add new elements somewhere in the middle of the vector, like in the beginning of the vector or after the third element. Though it’s possible to insert an element anywhere in a vector, vectors are made to only support efficiently adding elements to the end of the vector. The reason is that the elements of a vector, V[0], V[1], V[2], etc, are placed consecutively in the computer’s memory. You can imagine a box with slots, as the one below. One can easily store one more item by placing it in the free slot after the last one occupied, if one exists (this is the equivalent of push_back). But, what if you want to place the new item in the second slot which is occupied by another item? How can this problem be solved? Can you come up with a strategy and translate it to code?

Removing an element

It’s also possible to remove the last element of a vector V by simply writting V.pop_back(). For instance, consider the following vector with four elements.

std::vector<double> A = {1.2, 5.0, 4.6, -1.0}

Then, the following statement removes the last element (i.e. $-1.0$) from the vector and updates the vector’s size.

A.pop_back(); // remove last element of the vector

Then, the vector can be depicted as follows.

If one needs to delete all elements of the vector then A.clear(); can be used. In this case, std::ssize(A) becomes zero, since the vector becomes empty.

Though it’s possible to remove an element which is placed anywhere in a vector, vectors are made to only support efficiently removing elements from the end of the vector. In section Remove an item from a vector, we discuss two possible algorithms to remove items placed anywhere in a vector.

Copying and comparing

It is also possible to create a vector that is a copy of another existing vector. Consider the code below.

1
2
3
4
5
6
7
8
 std::vector<int> V1;  // empty vector

// Add integers 0 to 999 to V1
for (int i = 0; i != 1000; ++i) {
     V1.push_back(i);
}

std::vector<int> V2(V1);  // Create a vector V2 as a copy of vector V1

Line $8$ of the piece of code above defines a vector V2 as a copy of vector V1. Thus, std::ssize(V2) is equal to std::ssize(V1) (i.e. $1000$) and V2[0] stores $0$, V2[1] stores $1$, V2[2] stores $2$, $\cdots$, V2[999] stores $999$ ( similar to vector V1, V1[0] stores $0$, V1[1] stores $1$, V2[2] stores $2$, $\cdots$, V1[999] stores $999$).

Assigning a vector to another vector, as shown in line $3$ below, is also allowed. In this case, all elements of vector V1 (on the left side of the assignment =) are discarded and they are replaced by a copy of the elements in V3 (on the right side of =). Note that the assignment between vectors (like V1 = V3;) is only possible if both vectors store elements of the same type (e.g. int).

1
2
3
std::vector<double> V3 = {-1, -2, -3};

V1 = V3; // replace the elements in V1 with a copy of the elements in V3

Vectors can also be compared using V1 == V2 or V1 != V2. Two vectors V1 and V2 are equal (i.e. V1 == V2 evaluates to true), if the vectors have the same number of elements and each element of V1 is equal to the corresponding element in V2 (i.e. V1[0] == V2[0], V1[1] == V2[1], V1[2] == V2[2], etc). Otherwise, the vectors are different (i.e. V1 != V2 evaluates to true).

std::vector<int> A1 = {1, 5, 4, -1};

std::vector<int> A2;
int value;
while (std::cin >> value) {
       A2.push_back(value);
}

if (A1 == A2) {
    std::cout << "User entered the list [1, 5, 4, -1]";
}