Iterators and Algorithms

An iterator is a generalized pointer: something you can dereference to get an element, and advance to move to the next one, without the code using it needing to know whether it's walking a std::vector, a std::list, or a std::map. This one abstraction is what lets a single std::sort work on any container that supports the right kind of iteration, instead of every container needing its own sort function.

What an iterator actually is

v.begin() and v.end() are the same idea [start, end) half-open ranges use everywhere in C++: begin() points at the first element, end() points one past the last one, and it's never dereferenced, it only exists as a stopping point to compare against.

Iterator categories, briefly

Not every container's iterator supports the same operations. std::vector's iterator supports random access (jump to any position in O(1), like it + 5). A std::forward_list's iterator can only move forward one step at a time. The standard groups these into categories, input, forward, bidirectional, random-access, and templates on <algorithm> are written in terms of the weakest category they actually need. std::sort requires random access (you can't efficiently sort something you can only walk forward through one element at a time), so it doesn't work on std::list, std::list has its own .sort() member function instead for exactly this reason.

Range-based for, under the hood

The for (int x : v) syntax you've been using is sugar. The compiler rewrites it, roughly, into exactly the iterator loop from the first example: call v.begin() once, v.end() once, and loop comparing and advancing. Any type that provides begin()/end() (as members or as free functions found via argument-dependent lookup) works with range-based for automatically, which is how it works uniformly across every standard container and your own types too, if you write begin()/end() for them.

<algorithm> basics

The standard library's algorithms operate on iterator ranges, not containers directly, that's precisely what lets one std::sort implementation work on a std::vector<int>, a std::vector<std::string>, or a raw array, as long as you hand it a valid [begin, end) pair with the right iterator category.

std::find returning an iterator, not a boolean, is a recurring pattern worth internalizing: it returns end() on failure (an iterator you can compare against, but never dereference), and a valid iterator on success that you can immediately dereference or use in further algorithm calls, no separate "did I find it" flag needed.

A note on C++20 ranges

C++20 added the ranges library, which lets you write std::ranges::sort(v) directly on a container instead of std::sort(v.begin(), v.end()), and compose operations with pipe syntax like v | std::views::filter(pred) | std::views::transform(fn). It's a real improvement in readability and composability, and worth reaching for once you're comfortable with the iterator-pair model above, since ranges are built as a layer on top of exactly that model, not a replacement for understanding it. This course covers ranges properly in its modern-C++ chapter; the goal here is just to know it exists and why it looks different from the classic two-iterator calls.

struct IntBox {
    int data[3];
    // Add begin()/end() here so "for (int x : box)" works
};