An iterator is the STL's answer to a simple question: how to write code that walks through a std::vector, a std::list, a std::set, and a std::map the same way, without caring about the internal storage of each one. An iterator is a small object that behaves like a generalised pointer. Dereference it to get the current element, increment it to advance, and compare two iterators to know when the end is reached. This chapter covers the iterator concept, the begin() and end() family of accessors, how the range-based for loop uses them, const_iterator, iterator invalidation, and the insert and stream iterator adapters. The next chapter classifies iterators into categories and shows why those categories matter for algorithms.

A raw pointer into an array is the simplest possible iterator. Dereference it with *, advance it with ++, and compare two of them with == or !=. The STL takes that interface and lifts it to every container.

The pointer it walks the array. *it reads the current element, ++it moves to the next, and the loop stops when it reaches end, which sits one past the last valid element. That "one past the last" position is a sentinel: a valid iterator value that must not be dereferenced, but that can be compared against.

The STL generalises this pattern. Every standard container provides a begin() that returns an iterator to the first element and an end() that returns an iterator one past the last. The iterator type is specific to the container, but the four operations stay the same: *it, ++it, it == other, it != other. The loop body doesn't know whether it's walking a vector or a linked list.

The shape of the loop is identical to the raw-pointer version. The only difference is the type of it: a std::vector<int>::iterator instead of an int*. For a std::vector those are nearly interchangeable in behaviour, but for a std::list the iterator is structured differently internally. The loop above still works against std::list<int> with no changes to the body.

That uniformity is the entire point of iterators. They are the glue between containers and algorithms. A function that takes a begin and an end works against any container that supplies those, which is why std::sort, std::find, and friends can operate on most STL containers without caring how the elements are stored.

Every standard container provides a pair of member functions that return iterators delimiting its contents.

The important part of this table is end(). It does not point to a real element. It points to a position that sits one slot past the last valid element. This is called the half-open range [begin, end), and the STL uses it everywhere.

The cyan node is the position begin() returns. The orange nodes are the actual elements. The green node is end(), which marks "no more elements". Dereferencing end() is undefined behaviour. Comparing it == end() is how the boundary is detected.

There are three reasons the standard uses a half-open range instead of an inclusive [begin, last].

First, an empty container has begin() == end(). With a closed range, a special "no elements" flag would be needed because there's no valid "last" position to point to. The half-open range encodes "empty" naturally.

Second, the loop condition is it != end, not it <= end. That works even for iterators that don't support < (like std::list iterators), and it works without off-by-one errors.

Third, the length of the range is exactly end - begin (for iterators that support subtraction). With an inclusive range it would be end - begin + 1, and the + 1 is a constant source of bugs.

An empty vector demonstrating the convention:

begin() and end() compare equal because both point to the same imaginary "no elements" position. The half-open convention makes the empty case fall out of the same code path as the non-empty case.

The four operations every iterator supports are dereference, member access, increment, and comparison. These are the same operations a raw pointer supports.

*it gives a reference to the element, so (*it).name reads its name field. it->name is the same thing, shorter. ++it advances to the next element. == and != compare two iterators by position, not by the value they point to.

There's a small but real distinction between pre-increment ++it and post-increment it++. Pre-increment advances the iterator and returns it. Post-increment makes a copy of the iterator, advances the original, and returns the copy. For most STL iterators the copy is cheap, but pre-increment is still the default in C++ code because it avoids the copy.

Use ++it rather than it++ in loops. Pre-increment skips the temporary copy. The difference is negligible for most iterators but real for some custom iterator types, and the habit costs nothing.

The four core operations are universal. Not every iterator supports more than that. Some support backward stepping (--it), some support jumps (it + 5), some support comparison with < or subtraction between two iterators for a distance. The available extras depend on the iterator's category.

Iterator types are long. std::vector<std::string>::iterator is a mouthful; nested containers get worse. The auto keyword, available since C++11, lets the compiler deduce the type from the initialiser, and it's how iterator variables are typically declared.

The deduced type of it is std::map<std::string, int>::iterator. Spelling that out adds noise without adding information. auto keeps the loop readable.

The std::map output is sorted by key because std::map orders elements by key internally. That's a property of the container, not the iterator: the iterator walks the elements in whatever order the container stores them.

auto is also the only practical option for iterators whose type involves another deduced type, like the iterator into a vector of lambdas or a vector of iterators. Type inference handles those automatically; spelling them out by hand is tedious.

C++11 added the range-based for loop, the cleanest way to iterate. It's not a new mechanism, just shorthand for the begin()/end()/++ pattern.

What the compiler generates (in spirit, modulo a few details) is the explicit iterator loop:

The range-based loop calls begin() once, calls end() once, dereferences the iterator into the loop variable, and increments per iteration. Knowing this desugaring matters for two reasons.

First, the loop variable receives a copy of the element by default. Iterating a vector of large objects with for (Order o : orders) copies every order. Use for (const auto& o : orders) to take a const reference and avoid the copy. Use for (auto& o : orders) to modify the elements in place.

The first loop modifies stock counts through auto&. The second loop reads through const auto& and avoids copying the Product structs. Picking the right access mode for each loop keeps the cost predictable.

for (auto x : v) copies every element. For int or double that's free, but for std::string, std::vector, or any class with a non-trivial copy constructor, it adds an allocation per iteration. for (const auto& x : v) reads the elements without copying, the right default for non-trivial types.

Second, the range-based loop assumes begin() and end() work on whatever range it receives. Standard containers all qualify, raw arrays of known size qualify, and custom types qualify as long as they provide begin() and end() (member functions or free functions found via argument-dependent lookup).

For iteration without modification, use a const_iterator. It walks the container the same way but dereferences to a const reference, so the compiler reports an error on accidental writes.

There are three ways to land on a const_iterator.

First, call cbegin() and cend(), which always return const_iterator regardless of whether the container is const. This is the explicit way and the most clearly intentional.

Second, call begin() and end() on a const container. The non-const overloads aren't visible, so the const overloads take over and return const_iterator.

Inside printAll, stock is const std::vector<int>&, so stock.begin() is the const overload and the deduced auto type is std::vector<int>::const_iterator. Writing through it wouldn't compile.

Third, store the iterator in auto from a cbegin() call. That's the modern, succinct version of the first option.

Why use const_iterator when ordinary iterator works? Two reasons. It documents intent: a reader of the function knows the loop won't modify the elements. It catches bugs at compile time. A refactor that adds *it = ... inside a read-only loop makes the compiler stop the change instead of letting the bug slip into production.

For walking a container backwards, rbegin() returns an iterator pointing to the last element, and rend() returns one pointing to the position before the first element. The same ++ operator that advances forward on a regular iterator advances backward on a reverse iterator.

The output is the elements in reverse order. The reverse iterator does the bookkeeping internally: it stores a forward iterator one position ahead of where it conceptually points, so ++ on the reverse iterator becomes -- on the underlying forward iterator. None of that is visible from outside. The same *it/++it/it != end pattern works.

Reverse iterators exist mainly to plug into algorithms. Anywhere a function takes a begin and an end, passing rbegin() and rend() makes it process the range backwards.

The trickiest part of iterators is that they can become invalid. An iterator stores a position inside the container, and if the container reorganises its memory, that position no longer points to the expected element. Reading through an invalidated iterator is undefined behaviour and is one of the most common sources of bugs in STL code.

The rules differ by container.

std::vector

A std::vector stores its elements in a single contiguous block of heap memory. When an element is added and the block is already full, the vector allocates a new (larger) block, copies or moves the elements over, and frees the old block. Every iterator that pointed into the old block is now dangling.

The output of the second print depends on whether the vector reallocated. If it did, it points to freed memory. If it didn't, it still works. Either way, the code is broken because it depends on knowledge the vector doesn't guarantee.

For std::vector, the invalidation rules are:

Repeatedly calling push_back on a std::vector triggers occasional reallocations, each one O(n). Iterators captured before the reallocation become dangling. Call reserve(expected_size) first to remove the reallocations and keep iterators valid for the life of the loop.

std::deque

A std::deque stores elements in chunks rather than a single block. Inserting or removing at either end is O(1) and does not invalidate iterators to elements that didn't move. Inserting or removing in the middle invalidates all iterators, because the deque has to shift chunks around to maintain its layout.

std::list and std::forward_list

Linked lists hold each element in its own node. Adding or removing nodes elsewhere in the list doesn't touch the existing nodes, so iterators pointing to those nodes stay valid. The only iterator that becomes invalid is the one pointing to a node that was just erased.

it still points to the same node it always did. The new elements went into newly-allocated nodes that don't disturb the existing chain.

std::set, std::map (and their multi-* variants)

These are typically implemented as balanced binary search trees. Insertions and deletions rearrange tree pointers but don't move existing nodes in memory, so iterators to nodes that weren't erased stay valid. The iterator to an erased element is the only one invalidated.

std::unordered_set, std::unordered_map

Hash tables have a wrinkle. As elements are inserted, the load factor (elements per bucket) grows. When it crosses a threshold, the table rehashes: it allocates a new bucket array, recomputes hashes, and redistributes elements. Iterators into the old buckets are invalidated. Iterators don't move within their bucket, but the bucket itself may have moved.

The summary table:

Most algorithms in <algorithm> write to an output range that already has room for the results. std::copy(first, last, dest) writes through dest by assignment, which means *dest = value; ++dest. If dest is a plain vector iterator, the vector must already have enough size for the writes.

Insert iterators wrap a container and turn assignment into a container operation. *it = value becomes container.push_back(value), push_front(value), or insert(pos, value) depending on which insert iterator was used. The container grows as the algorithm writes to it.

std::back_inserter(dest) returns a small iterator object that, on assignment, calls dest.push_back(...). The std::copy algorithm doesn't know or care that the destination is a back-inserter; it just performs *it = value; ++it in a loop, and the wrapper turns those operations into the right container calls. dest started empty and ended up holding all five values.

There are three insert iterators in <iterator>:

front_inserter reverses order, because each new element is pushed in front of the previous one.

1 was pushed to the front, then 2 was pushed in front of 1, and so on, leaving the deque with elements in reverse order. back_inserter would have preserved the order.

std::inserter(c, pos) is the general one. It inserts at the position given by pos and updates pos as it goes, so successive inserts happen in order.

std::set doesn't have push_back, so back_inserter wouldn't work. inserter calls dest.insert(pos, value), which is what std::set provides, and the set sorts as it goes.

The other useful pair of adapters treats input and output streams as iterator ranges. std::istream_iterator<T> reads T values one at a time from a stream; std::ostream_iterator<T> writes T values to a stream one at a time. They're useful for plugging algorithms into I/O without writing custom loops.

std::istream_iterator<int>(input) is the beginning of the range: it reads one int from input on each dereference and increment. std::istream_iterator<int>() (no argument) is the end-of-stream sentinel: comparing the live iterator to a default-constructed one detects when the stream has run out of data.

std::ostream_iterator<int>(std::cout, " ") builds an iterator that, on assignment, writes its argument to std::cout followed by a space. std::copy walks the vector and assigns each element through it, producing the printed output.

The stream-iterator approach is most useful for reading or writing a range of values without writing the loop. For one-off std::cin reads it's overkill; for piping data through algorithms it's clean.

istream_iterator performs one stream extraction per increment. That's not free, but it's the same cost the equivalent loop would pay. The wrapper is a convenience, not a performance win.