Iterators — The Glue of the STL

Iterator Categories

Every iterator belongs to one of five categories, ordered weakest → strongest:

C++20 added contiguous iterators (vector, array, string, span) — random-access plus the guarantee that elements are physically adjacent.

The category determines which algorithms can use the iterator. std::sort requires random-access. std::find only needs input. The compiler picks the most efficient implementation based on category.

begin(), end() — and Their cv-qualified Friends

v.begin();   v.end();           // iterator (mutable)
v.cbegin();  v.cend();          // const_iterator (read-only)
v.rbegin();  v.rend();          // reverse_iterator
v.crbegin(); v.crend();         // const reverse_iterator

The non-member free functions std::begin(v), std::end(v) work on raw arrays too:

int arr[5] = {1, 2, 3, 4, 5};
sort(begin(arr), end(arr));

Reverse Iteration

for (auto it = v.rbegin(); it != v.rend(); ++it)
    cout << *it << ' ';
// Or simpler:
for (auto x : v | std::views::reverse) cout << x << ' ';   // C++20

distance, advance, next, prev

size_t idx = distance(v.begin(), it);   // O(1) for random-access, O(n) otherwise
auto m = next(v.begin(), v.size() / 2); // doesn't mutate begin()
advance(it, 3);                          // mutates it
auto p = prev(v.end(), 1);              // last element

> Why use these? They work for *every* iterator category. it + n only compiles for random-access iterators (so it would break on list or map).

Output Iterators — Inserters

The classic algorithms write through an output iterator. To grow a container, wrap it with an inserter from :

vector<int> dst;
copy(src.begin(), src.end(), back_inserter(dst));      // push_back
                                                        
list<int> lst;
copy(src.begin(), src.end(), front_inserter(lst));      // push_front
set<int> s;
copy(src.begin(), src.end(), inserter(s, s.end()));     // generic insert

back_inserter(dst) returns a back_insert_iterator whose assignment calls dst.push_back.

Stream Iterators

Treat input/output streams as ranges:

#include <iterator>
// Read all whitespace-separated ints from cin into a vector
vector<int> v{istream_iterator<int>(cin),
              istream_iterator<int>()};
// Write a vector to cout, separated by spaces
copy(v.begin(), v.end(),
     ostream_iterator<int>(cout, " "));

Combine with algorithms for some surprisingly readable I/O:

// Print all even numbers from input
copy_if(istream_iterator<int>(cin),
        istream_iterator<int>(),
        ostream_iterator<int>(cout, "\n"),
        [](int x){ return x % 2 == 0; });

Iterator Invalidation — The Silent Killer

Many container operations invalidate existing iterators (and references and pointers). Common cases:

Bug: Erasing While Iterating

// ❌ Undefined behaviour — ++it on an invalidated iterator
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it < 0) v.erase(it);
}
// ✅ erase returns the next valid iterator
for (auto it = v.begin(); it != v.end(); ) {
    if (*it < 0) it = v.erase(it);
    else         ++it;
}
// ✅✅ even better — erase-remove idiom
v.erase(remove_if(v.begin(), v.end(),
        [](int x){ return x < 0; }), v.end());

Custom Iterators (Brief)

Sometimes you want your own type to be range-iterable:

class Range {
    int lo, hi;
public:
    Range(int l, int h) : lo(l), hi(h) {}
    struct Iterator {
        int v;
        int operator*() const { return v; }
        Iterator& operator++() { ++v; return *this; }
        bool operator!=(const Iterator& o) const { return v != o.v; }
    };
    Iterator begin() const { return {lo}; }
    Iterator end()   const { return {hi}; }
};
for (int x : Range(1, 6)) cout << x;     // 12345

In modern code, prefer std::views::iota(1, 6) — that's exactly what it does.

Range-Based For — Sugar Over begin/end

for (auto& x : v) { /* ... */ }
// Compiles roughly to:
{
    auto __end = v.end();
    for (auto __it = v.begin(); __it != __end; ++__it) {
        auto& x = *__it;
        /* ... */
    }
}

Works on anything with begin() / end() — your custom types, arrays, ranges, etc.

Cheat-Sheet

You now understand the contract every algorithm depends on. Next: modern C++ features that make all of this even nicer.