Vectors

Introduction

An array in C has a fixed size, and it forgets how long it is. std::vector fixes both problems: it grows when you add to it, it knows its size, and it frees its own memory. In modern C++, it should be your first choice for a list.

How it works

Range-based for visits each element: for (int x : v). Use for (int& x : v) to change them, and const auto& for large elements.

Bad indexes. v[10] on a smaller vector is not checked, and its behaviour is undefined. v.at(10) throws an exception instead.

Sorting uses the <algorithm> header: sort(v.begin(), v.end());.

Tables are vectors of vectors:

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<vector<int>> grid(2, vector<int>(3, 0));
    grid[1][2] = 7;
    for (const vector<int>& row : grid) {
        for (int x : row) {
            cout << x << " ";
        }
        cout << endl;
    }
    return 0;
}

Inserting and erasing in the middle must move every later element, so they are slow on long vectors. Adding and removing at the end is fast.

Syntax

vector<int> v = {3, 1, 2};
v.push_back(5);
sort(v.begin(), v.end());
for (int x : v) {
    cout << x << " ";
}

Example

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> marks = {72, 85, 64};
    marks.push_back(90);
    cout << marks.size() << " " << marks[0] << " " << marks.back() << endl;
    marks.pop_back();
    int sum = 0;
    for (int m : marks) {
        sum += m;
    }
    cout << sum << endl;
    return 0;
}

Line by line

1. marks starts with three elements.
2. push_back adds a fourth, and the vector grows by itself.
3. size, [0] and back read from it.
4. pop_back removes the last element, 90.
5. The loop adds up the three that remain.

Expected result

4 72 90
221

In the real world

vector is the most used container in C++. Because its elements sit next to each other in memory, it is often faster in practice than cleverer structures.

Common mistakes

• Using v[i] past the end, which is undefined behaviour.
• Reading v.back() of an empty vector.
• Comparing an int with v.size() when the int can be negative, because size is unsigned.
• Changing a vector while looping over it with a range-based for.

Best practices

• Use vector instead of arrays by default.
• Pass vectors by const& when only reading them.
• Use a range-based for unless you need the index.

Summary

vector is a list that grows by itself and knows its size. push_back adds, range-based for visits, sort orders, and a vector of vectors makes a table.

Mark lesson complete