Iterators

A range-for loop visits every element of a container but does not tell where the current one lies. Yet functions that erase elements need exactly that: the element's place in the container.

Picture checking a shopping list and running your finger down the lines. The finger shows which line you are on. You can move it one line down, and you can cross out the line under it.

std::map and std::set have no indices, so a place in the container is marked by such a "finger", an iterator. It is an object that points to an element of the container:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{10, 20, 30};
    for (auto it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << ' ';  // 10 20 30
    }
}

begin and end

v.begin() returns an iterator to the first element, and v.end() returns one to the place right after the last. There is no element at end(), and reading *v.end() is undefined behavior. That is why the loop runs while it != v.end(). In an empty container, begin() equals end(), and the loop body never runs.

An iterator resembles a pointer: *it gives the element, and ++it moves to the next one. The full name of its type is std::vector<int>::iterator, so the type is deduced with auto. Iterators of std::map and std::set work the same way. And a range-for loop is a short form of a loop with begin() and end().

Erasing by iterator

v.erase(it) removes the element it points to and shifts the following elements into its place. After that, it and every iterator after it become invalidated: using them is undefined behavior. In return, erase gives back an iterator to the element that followed the erased one.

This is where the finger on a paper list and an iterator part ways. After crossing out a line, you can move the finger down, but an invalidated iterator must not be moved: only erase itself gives a new one. So a loop that erases advances the iterator in its body, not in its header:

std::vector<int> v{1, 2, 4, 5, 6};
for (auto it = v.begin(); it != v.end();) {
    if (*it % 2 == 0) {
        it = v.erase(it);
    } else {
        ++it;
    }
}
for (int x : v) {
    std::cout << x << ' ';  // 1 5
}

The loop header has no step. Once an element is erased, the iterator it already points to the next one, and ++it runs only when nothing was erased. In a std::map or a std::set, erase(it) invalidates only the iterator to the erased element, and the erase loop looks the same.

Common mistake

A loop over a vector adds elements to the same vector:

std::vector<int> v{1, 2, 3};
for (int x : v) {
    v.push_back(x * 10);  // ✗
}

A range-for loop gets the begin() and end() iterators once, before the first iteration. push_back always invalidates end(), and on a reallocation it also invalidates every iterator, pointer and reference to the elements. So this loop is undefined behavior whatever the capacity. Store the size before the loop and walk the vector by index: an index stays correct even after a reallocation.

std::vector<int> v{1, 2, 3};
std::size_t n = v.size();
for (std::size_t i = 0; i < n; ++i) {
    v.push_back(v[i] * 10);
}
for (int x : v) {
    std::cout << x << ' ';  // 1 2 3 10 20 30
}

Key points

• An iterator points to an element of a container: *it gives the element, and ++it moves to the next one.
• end() points to the place after the last element, and *v.end() must not be read.
• erase(it) invalidates it and returns an iterator to the next element.
• push_back inside a range-for loop over the same vector is undefined behavior, so such a vector is walked by index.