Iterators and algorithms

Introduction

Loops that search, count and sort are written again and again, and each is a chance to make a small mistake. The standard library provides well-tested versions that say exactly what they are doing. A line that reads sort(...) needs no explanation.

How it works

An iterator is like a pointer into a container. *it reads the element, and ++it moves on. v.begin() points at the first element, and v.end() points just past the last, which is why it must never be read. Together they describe a range.

Algorithms come from <algorithm> and take such a range:

Passing a function. Without brackets, a function's name is a value, so it can be handed to an algorithm. A function that returns true or false is called a predicate:

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

bool is_negative(int x) {
    return x < 0;
}

int main() {
    vector<int> v = {4, -2, 7, -9};
    auto it = find(v.begin(), v.end(), 7);
    if (it != v.end()) {
        cout << "found at " << it - v.begin() << endl;
    }
    cout << count_if(v.begin(), v.end(), is_negative) << endl;
    cout << *find_if(v.begin(), v.end(), is_negative) << endl;
    return 0;
}

Removing repeats. unique needs sorted data, and it only moves the unique items to the front. The usual form erases the leftovers: v.erase(unique(v.begin(), v.end()), v.end());.

Syntax

sort(v.begin(), v.end());
auto it = find(v.begin(), v.end(), x);
if (it != v.end()) { ... }
int n = count_if(v.begin(), v.end(), is_even);

Example

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

bool larger_first(int a, int b) {
    return a > b;
}

int main() {
    vector<int> v = {5, 1, 4};
    sort(v.begin(), v.end());
    cout << v[0] << " " << v[2] << endl;
    sort(v.begin(), v.end(), larger_first);
    cout << v[0] << " " << v[2] << endl;
    cout << *max_element(v.begin(), v.end()) << endl;
    return 0;
}

Line by line

1. sort with two iterators puts the numbers in increasing order.
2. v[0] and v[2] are now the smallest and the largest.
3. The second sort is given a compare function, which makes it sort from largest to smallest.
4. max_element returns an iterator, and * reads the value.

Expected result

1 5
5 1
5

In the real world

The standard algorithms are heavily optimised and thoroughly tested, so using them means faster and safer code. Experienced C++ programmers tend to reach for an algorithm first, and write a loop only if nothing fits.

Common mistakes

• Reading *v.end(), which is past the last element.
• Not checking find against end().
• Using binary_search on unsorted data.
• Forgetting that unique needs sorted data, and the erase afterwards.

Best practices

• Check for a standard algorithm before you write a loop.
• Compare a compare function strictly: use < or >, never <=.
• Include <algorithm>, and do not rely on another header to bring it in.

Summary

Iterators point into containers, and begin and end describe a range. Algorithms take a range and do common jobs reliably. Functions can be passed to them to customise their behaviour.

Mark lesson complete