Vectors and the standard algorithms · C++ tutorial

A vector is an array that knows its size and grows as you add to it. It is the collection you will use most in C++.

Creating#

#include <vector>

vector<int> nums = {4, 8, 15};
vector<int> zeros(5);            // five 0s
vector<int> sevens(5, 7);        // five 7s
vector<string> names;            // empty

The type in angle brackets says what the vector holds.

Reading#

nums[0]          // 4
nums.back()      // 15
nums.size()      // 3
nums.empty()     // false
nums.at(5)       // throws an error: out of range

nums[i] does not check its range; reading past the end is undefined behaviour. at checks, at a small cost.

Adding and removing#

nums.push_back(16);              // add to the end: {4, 8, 15, 16}
nums.pop_back();                 // remove the last
nums.insert(nums.begin(), 1);    // add at the front: slow for big vectors
nums.erase(nums.begin() + 1);    // remove position 1
nums.clear();                    // remove everything

Adding and removing at the end is fast. At the front or middle, everything after has to shift. If you know roughly how many items are coming, nums.reserve(n) avoids repeated growing.

Looping#

for (int x : nums) cout << x << " ";
for (int i = 0; i < (int) nums.size(); i++) cout << i << ": " << nums[i] << "\n";

Two-dimensional vectors#

int rows = 3, cols = 4;
vector<vector<int>> grid(rows, vector<int>(cols, 0));
grid[1][2] = 7;

Each row is its own vector, so rows can even have different lengths, as in Pascal's triangle.

Sorting#

#include <algorithm>

sort(nums.begin(), nums.end());                     // ascending
sort(nums.begin(), nums.end(), greater<int>());     // descending

sort(words.begin(), words.end(), [](const string &a, const string &b) {
    return a.size() < b.size();                      // by length
});

The last form passes a lambda, a small unnamed function that says which of two items comes first. sort takes about n log n steps: under two million for a hundred thousand items.

begin() and end() are iterators, marking the start and one past the end. Most standard algorithms take a pair of them, meaning "this range".

Standard algorithms#

Before writing a loop, check whether one of these already does the job:

#include <numeric>

long long total = accumulate(nums.begin(), nums.end(), 0LL);
int largest = *max_element(nums.begin(), nums.end());
int smallest = *min_element(nums.begin(), nums.end());
int sevensCount = count(nums.begin(), nums.end(), 7);
reverse(nums.begin(), nums.end());
bool has = find(nums.begin(), nums.end(), 8) != nums.end();

Note 0LL in accumulate: the type of the starting value is the type of the total, so 0 would add up in int and overflow.

On a sorted vector, binary_search, lower_bound and upper_bound find things in about log n steps instead of n.

Removing duplicates#

A classic combination: sort, then unique moves the duplicates to the end, then erase removes them:

sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());

Key points#

vector<T> grows with push_back; size() gives its length.
[] is unchecked, at() is checked.
Build grids as vector<vector<int>> grid(r, vector<int>(c)).
sort(v.begin(), v.end()) sorts; a lambda changes the order.
accumulate needs 0LL to total large values safely.

That completes the C++ basics. Try the practice problems below, then the Learn track, where vectors, maps and sorting become real algorithms.