# 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.

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.

In line $3$, 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 (elements) it stores and where is the first variable (V[0]) storing the first list’s value.
• V.size() gives the number of values stored in vector V.
• 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 V.size()-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.

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 doubles.

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 V1.size() 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].

As seen in the example code above, int constants such as0 or 4 can be used as subscripts. 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).

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 < V.size(); ++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.

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 V.size()-1 (the subscript of the last variable of V). Thus, the test i < V.size() in line $3$ makes sure that the loop stops when the last element has been visited.

Another example is shown which duplicates the value stored in each variable of vector V.

for(int i = 0; i < V.size(); ++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[V.size()-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;
for(int value : V) {
if (value % 2 == 1) {
++count_odd;
}
}
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).

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 A.size() 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 add one element at a time, as shown below.

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

• To display the average grade.
• To display all grades, five per line. The grades above the average should 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”.

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, A.size() 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.

Line $8$ of the piece of code above defines a vector V2 as a copy of vector V1. Thus, V2.size() is equal to V1.size() (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).

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 = 0;

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

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