Iterators

Iterators are the glue between containers and algorithms; misusing an invalidated iterator is one of the most common C++ bugs.

An iterator is a generalised pointer into a container: *it gives the element, ++it advances. Every container has begin(), pointing at the first element, and end(), pointing one past the last. Ranges are half-open, [begin, end), so an empty container has begin() == end() and loops use it != end().

Range-for is built on these: for (auto x : v) is shorthand for a loop from begin() to end(). Other variations are cbegin() for read-only iteration and rbegin()/rend() for reverse order.

Iterators come in categories that determine which algorithms they work with:

Input/forward: only ++ (e.g. std::forward_list, stream iterators).
Bidirectional: ++ and -- (std::list, std::map, std::set).
Random access: also it + n, it[n], it2 - it1 (std::deque).
Contiguous: random access with elements adjacent in memory (std::vector, std::array, std::string).

That's why std::sort works on a vector but not on a list (which has its own sort() member).

The critical rule is invalidation. Operations that change a container's structure can invalidate iterators, pointers and references into it. For std::vector, any reallocation invalidates everything, and erase invalidates everything from the erased point on. Node-based containers (list, map, set) only invalidate iterators to erased elements. Using an invalid iterator is undefined behaviour.

To erase while iterating, use the iterator that erase returns. Better still, C++20's std::erase(v, value) and std::erase_if(v, pred) remove matching elements in one call.

Example

#include <iostream>
#include <list>
#include <vector>

int main() {
    std::vector<int> v{3, 1, 4, 1, 5, 9};
    for (auto it = v.begin(); it != v.end(); ++it)   // [begin, end): end is one past the last
        *it *= 10;

    for (auto it = v.rbegin(); it != v.rend(); ++it) std::cout << *it << ' ';
    std::cout << '\n';                               // 90 50 10 40 10 30

    auto third = v.begin() + 2;                      // random access: jump by n
    std::cout << *third << ' ' << (v.end() - v.begin()) << '\n';   // 40 6

    std::list<int> l{1, 2, 3};
    auto li = l.begin();
    ++li;                                            // bidirectional: no li + 2
    l.insert(li, 99);                                // list iterators stay valid: 1 99 2 3

    for (auto it = v.begin(); it != v.end();)        // erase while iterating:
        it = (*it == 10) ? v.erase(it) : it + 1;     // continue from what erase returns
    std::erase(v, 90);                               // C++20 one-liner
    for (int x : v) std::cout << x << ' ';           // 30 40 50
    std::cout << '\n';
}

Remember

Ranges are half-open: [begin(), end()); end() is never dereferenced
Iterator category decides which algorithms apply (e.g. std::sort needs random access)
Structural changes can invalidate iterators; continue from the one erase returns

Watch out for

Calling v.erase(it) inside a for loop and then doing ++it on the invalidated iterator.

Check yourself

Which container's iterators allow `it + 5`?
You hold an iterator to the 2nd element of a vector and then erase the 1st element. What about your iterator?

Official docs: en.cppreference.com/w/cpp/iterator

Example

Remember

Watch out for

Check yourself

Builds on

Unlocks