The STL — Iterators & Algorithms

Course 2 · Ch 3

Templates, applied one level up — algorithms that don't know or care which container they're given

cpp2-2's containers gave C++ real, standard data structures. This chapter is what makes them interchangeable: one std::sort, working identically across every container that offers iterators.

What an Iterator Is

A generalized pointer-like object. begin() points at the first element; end() points one past the last — never the last element itself, the "half-open range" convention [begin, end). Dereferencing (*it) gives the element; ++it advances.

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

Iterating With Iterators

cpp1-2's own range-based for (auto x : container) is genuinely sugar for exactly this iterator pattern, generated automatically underneath.

Why Iterators Exist — Generic Algorithms Over Any Container

The real payoff: std::sort/std::find/and friends don't know or care whether they're operating on a vector, a list, or a raw array — they only need begin()/end() iterators satisfying certain requirements. This is cpp2-1's templates applied one level up, at the algorithm level rather than the container level — std::sort is itself a function template.

`std::sort`

std::sort(nums.begin(), nums.end());

Sorts a range in place. c3-2's own hand-built structures never included a general sorting algorithm at all — writing one in C means implementing the actual algorithm by hand, every time.

`std::find`

auto it = std::find(nums.begin(), nums.end(), 20);
if (it != nums.end()) {
    std::cout << "Found!" << std::endl;
}

A linear search returning an iterator to the found element, or end() if not found — the end()-as-sentinel pattern is idiomatic and used constantly across the STL.

Iterator Invalidation, Revisited

cpp2-2's own warn-box flagged reallocation invalidating iterators — with iterators now properly introduced, the fuller picture: erasing or inserting into a vector can invalidate iterators at or after the modification point too, not just growth-triggered reallocation.

Concept	C (c3-2)	C++ STL
Traversal	hand-written loop, container-specific	iterators — the same syntax across any container
Sorting	implement the algorithm by hand	std::sort — one call, any container
Searching	hand-written traversal loop	std::find — returns an iterator, end() as "not found"

Prefer a standard algorithm over hand-writing the equivalent loop

std::sort/std::find and the rest of the STL's algorithm library are genuinely less error-prone than a hand-written loop, and usually at least as fast — real implementations are heavily optimized.

Using an invalid or mismatched iterator is undefined behavior, uncaught by the compiler

Using an iterator from one container against a different container's begin()/end(), or one that's already been invalidated, compiles cleanly and is undefined behavior at runtime — the type system doesn't tie an iterator to "the container it's still safely valid for," the way Rust's borrow checker would.

Coding Challenges

Challenge 1

Create a std::vector with values in unsorted order, sort it with std::sort, and print the result using an explicit iterator-based loop (not a range-based for).

📄 View solution

Challenge 2

Use std::find to search a std::vector for a value that exists and a value that doesn't, printing "Found" or "Not found" for each using the end() sentinel check.

📄 View solution

Challenge 3

Explain why the range-based for loop (for (auto x : container)) is described as "sugar" over the explicit iterator loop, and rewrite one range-based for loop yourself as its equivalent explicit iterator-based form.

📄 View solution

Chapter 3 Quick Reference

begin()/end() — the half-open range [begin, end); end() points one past the last element
Range-based for is sugar over the exact same iterator pattern, generated automatically
Algorithms like std::sort/std::find work identically across any container offering iterators — templates, one level up
std::find returns end() as its "not found" sentinel — check it != container.end()
Erasing/inserting/reallocating can invalidate existing iterators — using one afterward is undefined behavior, uncaught by the compiler
Next chapter: smart pointers — unique_ptr and shared_ptr, a modern RAII alternative to raw malloc/free