Vectors

A variable holds one value. A program that works with thirty temperatures, or with every number somebody types, would need thirty variables, or a number of variables nobody knows in advance.

A vector holds many values of one type under one name. Module 8 treated a string as a row of characters with numbered positions. A vector is the same idea for any type of value.

Many values under one name

This program keeps five days of rainfall, in millimetres, in one vector.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> rainfall = {12, 0, 7, 31, 4};
    std::cout << "Days measured: " << rainfall.size() << "\n";
}

Days measured: 5

The declaration has four parts.

Each value in a vector is an element. rainfall has five elements. They keep the order in which they were written: 12 is the first and 4 is the last.

rainfall.size() is the number of elements, as s.size() is the number of characters of a string. It counts the elements. It does not add them up.

std::vector comes from the header <vector>, so the program names that header in an #include line.

The element type is part of the vector's type, and every element has it. A std::vector<int> holds ints and nothing else. This program does not compile, because "seven" is text.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> rainfall = {12, 0, "seven"};
    std::cout << rainfall.size() << "\n";
}

Any type you know can stand between the angle brackets. std::vector<double> is a row of numbers with a fraction, and std::vector<std::string> is a row of strings. Most of this lesson uses std::vector<int>; a later section looks at a vector of strings.

Three ways to start a vector

A list in braces is one way to give a vector its first elements. There are two more.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> listed = {3, 5};
    std::vector<int> repeated(3, 5);
    std::vector<int> zeros(4);
    std::vector<int> nothing_yet;

    std::cout << listed.size() << "\n";
    std::cout << repeated.size() << "\n";
    std::cout << zeros.size() << "\n";
    std::cout << nothing_yet.size() << "\n";
}

2
3
4
0

Braces and parentheses mean different things here, and both compile. {3, 5} is a list of two elements. (3, 5) is an instruction: make three elements, each with the value 5. Read the brackets before you read the numbers.

A vector declared with nothing after its name is empty: its size is 0. That is a proper starting value. Module 2 warned that an int given no value holds whatever was in memory. A vector is different: with no value given, it is always an empty vector, never an unknown one.

The element at a position

Each element has a position, counted from 0, exactly like the characters of a string. v[i] is the element at position i.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> heights = {150, 162, 171, 158};

    std::cout << heights[0] << "\n";
    std::cout << heights[heights.size() - 1] << "\n";

    heights[1] = 165;
    heights[2] += 1;

    int n = heights.size();
    for (int i = 0; i < n; ++i) {
        std::cout << i << ": " << heights[i] << "\n";
    }
}

150
158
0: 150
1: 165
2: 172
3: 158

At the start the vector looks like this.

Three things to notice.

• The first element is heights[0]. The size is 4, and the last element is at position 3, which is heights.size() - 1. There is no element at position 4.
• heights[1] is a variable like any other int. It can be printed, assigned to and updated. heights[1] = 165; replaces one element and leaves the others alone.
• The loop visits every position: i starts at 0 and the loop runs while i < n, so i takes the values 0, 1, 2 and 3.

The loop stores the size in an int first, as every loop over a string did in module 8. size() gives a std::size_t, which is unsigned, and storing it in an int once means that every comparison and subtraction in the loop is between two ints.

The expression between the square brackets can be any int expression: a number, a variable, or a calculation such as n - 1 - i.

A vector that grows

The size of a vector is not fixed. push_back adds one element at the end.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> laps;
    std::cout << laps.empty() << "\n";

    laps.push_back(74);
    laps.push_back(71);
    laps.push_back(69);
    std::cout << laps.size() << " " << laps.back() << "\n";

    laps.pop_back();
    std::cout << laps.size() << " " << laps.back() << "\n";
    std::cout << laps.empty() << "\n";
}

1
3 69
2 71
0

laps starts empty, so laps.empty() is true and prints as 1. After three calls of push_back it holds 74, 71, 69, in that order: each new element goes after the ones already there. pop_back then removes the 69, and 71 is the last element again.

back() and pop_back() need a last element to work on. On an empty vector C++ does not say what they do. When a vector may be empty, test empty() first.

Growing is what makes a vector fit input of unknown length. This program reads temperatures until the input ends, and only then prints them.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> readings;
    int value = 0;
    while (std::cin >> value) {
        readings.push_back(value);
    }

    int n = readings.size();
    for (int i = 0; i < n; ++i) {
        std::cout << "Reading " << i + 1 << " of " << n << ": " << readings[i] << "\n";
    }
}

18 21 19

Reading 1 of 3: 18
Reading 2 of 3: 21
Reading 3 of 3: 19

The first line of output says of 3. The program could not have printed that while it was still reading: it did not yet know how many values there would be. With the values kept in a vector, the program can finish reading first and then go through them as often as it likes.

One past the end

A vector with three elements has the positions 0, 1 and 2. Position 3 is one past the end. It is the position a loop reaches when its test says <= where it should say <.

int n = v.size();
for (int i = 0; i <= n; ++i) {      // wrong: the last turn uses i == n
    std::cout << v[i] << "\n";
}

What does v[3] give in a vector of three? C++ makes no promise. The square brackets do not check the position. The program may print a number left over in memory, it may stop, or it may seem to work today and fail on another computer. There is no error message to rely on. Positions below 0 are outside the vector in the same way.

A string is slightly different here. Module 8 showed that a string keeps the null character at position size(), so reading s[s.size()] gives that character. A vector, unlike a string, has nothing at position size().

This is worse than a program that stops, because a wrong number can travel a long way before anybody notices it. So the rule is strict: a position used with [] must be at least 0 and less than size(). It is the programmer who makes sure of that. No program in this course uses [] outside a vector, not even to show what happens, because nobody can say what would happen.

A vector has a second way to reach an element, which does check. v.at(i) gives the same element as v[i] when position i exists. When it does not, the program stops at that line.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {5, 6, 7};
    std::cout << v.at(2) << "\n";
    std::cout << v.at(3) << "\n";
    std::cout << "not reached\n";
}

This program prints 7, and then stops at the line with v.at(3). The last line never runs. Like a failed assert in module 7, this is a run-time error that points at the place where things went wrong.

Use [] inside a loop whose test you have checked: with i from 0 while i < n, every position is an element. Use at() when a position comes from input or from a calculation you are less sure of, and while you hunt a bug.

Before you run a loop over a vector, check the two ends by hand. What is i on the first turn? What is i on the last turn, and is that position less than the size?

Each element in turn

Many loops over a vector need each element and do not care about its position. C++ has a second form of for for them.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> rainfall = {12, 0, 7, 31, 4};
    int total = 0;
    for (int amount : rainfall) {
        total += amount;
    }
    std::cout << "Total: " << total << "\n";
}

Total: 54

Read for (int amount : rainfall) as "for each int in rainfall, call it amount". The body runs once for each element, from the first to the last. On the first turn amount is 12, on the second 0, and so on. This form is called a range-based for loop.

There is no position, no test and no update to write, so there is nothing to get wrong by one. A loop of this form cannot go past the end.

The variable before the colon is a new variable on every turn, and it holds a copy of the element. Changing it does not change the vector.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> prices = {4, 9, 6};

    for (int p : prices) {
        p = p * 2;
        std::cout << "copy: " << p << "\n";
    }
    for (int p : prices) {
        std::cout << "element: " << p << "\n";
    }

    int n = prices.size();
    for (int i = 0; i < n; ++i) {
        prices[i] = prices[i] * 2;
    }
    std::cout << "first element now: " << prices[0] << "\n";
}

copy: 8
copy: 18
copy: 12
element: 4
element: 9
element: 6
first element now: 8

The first loop doubled three copies and printed them. The second loop shows that the elements are still 4, 9 and 6. The third loop assigns to prices[i], which is the element itself, and that does change the vector.

The elements can go straight into a picture. Each turn of this loop draws one disc with the next radius, and moves right for the one after.

#include "scimigo.h"
#include <vector>
using namespace scimigo;

int main() {
    canvas(600, 200);
    std::vector<int> sizes = {10, 25, 40, 25, 10};
    int x = 80;
    for (int radius : sizes) {
        circle(x, 100, radius, "teal");
        x += 110;
    }
}

Letting the compiler name the type

Every value in a program has a type, and the compiler always knows it. When a variable is declared with a starting value, you may write auto where the type goes, and the compiler writes the type of that value for you.

#include <iostream>
#include <vector>

int main() {
    std::vector<double> lengths = {2.5, 4.0};

    auto count = 3;
    auto half = 7 / 2;
    auto exact = 7 / 2.0;
    auto first = lengths[0];

    std::cout << count << " " << half << " " << exact << " " << first << "\n";

    for (auto length : lengths) {
        std::cout << length * 2 << "\n";
    }
}

3 3 3.5 2.5
5
8

auto is not a type that can hold anything. The type is fixed at the declaration, from the value on the right, by the rules you already know. half is an int because 7 / 2 is an int division; auto does not rescue the fraction. Afterwards half is an int for good.

Since the type comes from the starting value, there must be one. This does not compile.

#include <iostream>

int main() {
    auto total;
    total = 5;
    std::cout << total << "\n";
}

Two cases need care.

The first is size(). In auto n = v.size(); the compiler writes std::size_t, the unsigned type that size() gives and that module 8 warned about. It has no negative values, so n - 1 is not -1 when n is 0.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> none;
    auto n = none.size();
    int m = none.size();
    std::cout << (n - 1 < 0) << "\n";
    std::cout << (m - 1 < 0) << "\n";
}

0
1

With auto, n - 1 < 0 is false, although the vector is empty. With int, it is true, as expected. For a size you will subtract from or compare with an int, write int.

The second is text in quotes. auto word = "kite"; does not make a std::string. Text written in quotes has an older type of its own, which module 18 explains. When you want a string, write std::string.

Use auto where the type is plain from the same line, as in a range-based for over a vector you can see. Write the type out where reading it helps.

A vector of strings

The elements of a vector can be strings. Everything so far works the same way.

#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> tools = {"hammer", "saw", "chisel"};
    tools.push_back("file");

    std::cout << tools.size() << "\n";
    std::cout << tools[1] << "\n";
    std::cout << tools[1].size() << "\n";
    std::cout << tools[2][0] << "\n";

    for (std::string tool : tools) {
        std::cout << tool << " has " << tool.size() << " letters\n";
    }
}

4
saw
3
c
hammer has 6 letters
saw has 3 letters
chisel has 6 letters
file has 4 letters

Two sizes are in play, and they answer different questions.

• tools.size() is the number of elements in the vector: 4 strings.
• tools[1].size() is the number of characters in one element: "saw" has 3.

tools[1] is a std::string, so anything a string can do, it can do: .size(), +, ==, and a second pair of square brackets. tools[2][0] is read from the left: tools[2] is the string "chisel", and [0] is its first character, the char 'c'.

A vector of strings is the natural place for words or lines that are read from input. For words, std::cin >> word in the test of a while loop works as it did for numbers in module 5. For whole lines, std::getline can stand in the test in the same way: while (std::getline(std::cin, line)) is true each time a line was read, and false when the input has run out.

#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> items;
    std::string line;
    while (std::getline(std::cin, line)) {
        items.push_back(line);
    }

    std::cout << items.size() << " things to buy\n";
    for (std::string item : items) {
        std::cout << "- " << item << "\n";
    }
}

brown rice
two lemons
tea

3 things to buy
- brown rice
- two lemons
- tea

Each element is one whole line, spaces included.

A function that returns a vector

A vector is a value, so a function can build one and give it back. The return type is the vector's type.

#include <iostream>
#include <vector>

std::vector<int> countdown(int from) {
    std::vector<int> result;
    for (int i = from; i >= 1; --i) {
        result.push_back(i);
    }
    return result;
}

int main() {
    std::vector<int> steps = countdown(4);
    std::cout << steps.size() << " steps\n";
    for (int step : steps) {
        std::cout << step << "\n";
    }
    std::cout << countdown(0).size() << "\n";
}

4 steps
4
3
2
1
0

The pattern has three parts: declare an empty vector, add to it, return it. result is a local variable of countdown and is gone when the call ends, but its value has been handed to the caller, exactly as with an int. main stores it in steps.

For countdown(0) the loop does not run at all, and the function returns an empty vector. An empty vector is a perfectly good answer.

The function builds the vector and main prints it. As in module 6, a function that is asked to return something should not print it.

A vector can also be a parameter. The rule from module 6 holds without any change: the function gets a copy. All the elements are copied into the parameter when the call starts, and whatever the function does to its copy, the caller's vector stays as it was.

#include <iostream>
#include <vector>

std::vector<int> with_bonus(std::vector<int> marks, int bonus) {
    int n = marks.size();
    for (int i = 0; i < n; ++i) {
        marks[i] += bonus;
    }
    return marks;
}

int main() {
    std::vector<int> marks = {52, 67, 48};
    std::vector<int> raised = with_bonus(marks, 5);

    std::cout << marks[0] << " " << marks[1] << " " << marks[2] << "\n";
    std::cout << raised[0] << " " << raised[1] << " " << raised[2] << "\n";
}

52 67 48
57 72 53

with_bonus changes every element of its parameter marks, and returns it. The marks of main is a different vector, and still holds 52, 67 and 48. The changed elements reach main only through the returned value, which main stores in raised.

Copying a vector copies every element, which takes time when the vector is long. Module 10 shows how a function can work on the caller's vector without a copy.