Using Iterators — Use iterators to traverse containers (begin/end)

Before the Standard Template Library existed, C and early C++ programmers traversed arrays with raw pointer arithmetic and hand-rolled loops for every custom data structure—linked lists, trees, hash tables—each requiring its own traversal logic. This tight coupling between algorithms and data structures meant that sorting code written for an array could not be reused on a linked list without a complete rewrite. The combinatorial explosion of M algorithms × N containers demanded M × N implementations, a maintenance nightmare that grew worse with every new container or algorithm added to a codebase.

The fundamental question that iterators answer is deceptively simple: how can we write a single algorithm that works across any container, without knowing the container's internal layout? The answer lies in providing a uniform interface—the iterator—that generalizes the notion of a pointer to work with vectors, lists, maps, sets, and even I/O streams. By defining the half-open range [begin, end), the STL collapses M × N complexity into M + N: M algorithms and N containers, connected through a shared iterator concept.

An iterator is a generalized pointer: an object that refers to an element within a container and supports operations such as dereferencing (to access the element), incrementing (to advance to the next element), and comparison (to detect when traversal is complete). Every standard container provides at least two member functions— begin() and end()—that return iterators defining the half-open range [first, one-past-last). This half-open convention is not arbitrary; it elegantly handles empty ranges (where begin equals end), avoids off-by-one errors, and enables natural loop termination conditions.

The critical insight encoded in this diagram is the half-open range convention. By designating end() as a past-the-end sentinel rather than the last valid element, the number of elements in any range [first, last) is simply last − first. An empty container satisfies begin() == end() without any special-case logic. This design eliminates the ambiguity that plagued earlier "inclusive range" approaches, where an empty range required a separate flag or invalid index. Moreover, the pattern generalizes: whether the underlying container is a contiguous array, a doubly-linked list, or a balanced tree, the loop for (auto it = c.begin(); it != c.end(); ++it) remains syntactically and semantically identical.

Iterators in C++ are realized through operator overloading. Each container defines a nested class (or type alias) named iterator that overloads the operators operator*, operator++, operator!=, and (for random-access iterators) operator[] and operator+. Because these operators share the same syntax as raw pointer operations, generic algorithms written with iterators compile identically whether the underlying type is a simple pointer into an array or a complex object wrapping a tree node.

Key Member Functions & Free Functions

Since C++11, the free-standing functions std::begin() and std::end() provide a uniform entry point that dispatches to c.begin() for STL containers and to pointer arithmetic for raw C arrays. This allows template functions to accept both int arr[5] and std::vector<int> with identical syntax, further strengthening the iterator abstraction.

Not all iterators are created equal. The STL defines a hierarchy of iterator categories that specify which operations an iterator supports. Each category is a refinement of the previous one, adding more capabilities. Understanding these categories is essential because STL algorithms impose minimum iterator requirements: std::sort demands random-access iterators, while std::find needs only input iterators.

Let us walk through a complete, realistic example that demonstrates iterator-based traversal, element mutation, and interoperation with an STL algorithm. We will work with a std::vector<int> containing student exam scores and compute the sum, find the maximum, and then normalize each score to a percentage.

C++ programmers often face a stylistic and functional choice among three traversal strategies. Understanding the trade-offs helps you select the right tool for each situation and write code that is both idiomatic and efficient.

While the begin()/end() iterator pair remains foundational, the C++20 standard introduced Ranges (the <ranges> header) as a higher-level abstraction that builds upon iterators. A range is any object that provides begin() and end(), exactly as we have discussed, but ranges allow composable view pipelines using the pipe operator |. Mastering classical iterators is prerequisite to understanding ranges.

C++20 also formalized iterator requirements using concepts such as std::input_iterator, std::forward_iterator, std::bidirectional_iterator, and std::random_access_iterator. These concepts replace the informal "iterator traits" documentation with compile-time constraints, producing clear error messages when a programmer supplies an iterator of insufficient category. The trajectory is clear: iterators are not going away—they are being strengthened and wrapped in higher-level abstractions that make them safer and more composable.