C++ Iterators

An iterator is an object that lets you walk through the elements of a container — like std::vector, std::list, or std::map — one at a time, without needing to know how that container stores its data internally. Iterators are the glue that connects containers to algorithms in the C++ Standard Template Library (STL): instead of writing a separate loop for every container type, algorithms like std::sort or std::find just work with iterators, and any container that supplies the right kind of iterator can use them. Understanding iterators well is the key to using the STL confidently and avoiding subtle, hard-to-debug bugs.

Overview / How Iterators Work

Think of an iterator as a generalized pointer. A raw pointer to an array element can be incremented (++p) to move to the next element and dereferenced (*p) to access the value it points to. An iterator supports the same two core operations — increment and dereference — but it can be implemented in whatever way makes sense for the container it belongs to. For std::vector, the iterator really can be (and often is) a raw pointer, because vector elements sit in one contiguous block of memory. For std::list, which stores elements as separate heap-allocated nodes linked by pointers, the iterator is a small wrapper class whose operator++ follows the node’s “next” pointer instead of moving through contiguous memory. For std::map and std::set, which are usually implemented as red-black trees, the iterator’s operator++ walks to the in-order successor node in the tree.

This is the essence of the STL’s design: algorithms are written once, in terms of iterators, and containers each provide iterators that behave correctly for their internal layout. The algorithm never needs to know whether it is traversing an array, a linked list, or a tree — it just calls ++it and *it and trusts the container to do the right thing.

Every standard container exposes begin(), which returns an iterator to the first element, and end(), which returns an iterator to one position past the last element. The range [begin(), end()) is a half-open range — it includes begin() but excludes end(). This is why loops compare with != rather than trying to dereference end(): end() does not point to a real element, it is a sentinel marking “one past the last item,” and dereferencing it is undefined behavior.

Iterator Categories

Not all iterators support the same operations. The C++ standard defines a hierarchy of iterator categories, from the most limited to the most capable. Each category is a superset of the one before it (a random access iterator can do everything a forward iterator can, and more).

Category Capabilities Typical containers
Input Read-only, single pass, ++it, *it std::istream_iterator
Output Write-only, single pass, *it = value std::ostream_iterator, std::back_inserter
Forward Read/write, multi-pass, ++it std::forward_list, std::unordered_map
Bidirectional Forward plus --it std::list, std::map, std::set
Random Access Bidirectional plus it + n, it[n], it1 - it2, relational operators std::vector, std::deque, std::array, C-style arrays

This matters practically: an algorithm like std::sort requires a random access iterator, so you cannot call std::sort directly on a std::list (it has its own list::sort() member function instead). Trying to do arithmetic like it + 2 on a bidirectional iterator (such as a list iterator) will not compile at all — the type simply has no operator+.

Syntax

The general forms you will see when working with iterators:

ContainerType<T>::iterator it = container.begin();
ContainerType<T>::const_iterator cit = container.cbegin();
auto it2 = container.begin();       // preferred in modern C++

for (auto it = container.begin(); it != container.end(); ++it) {
    // use *it
}

for (auto& element : container) {
    // range-based for loop, uses iterators internally
}
  • begin() / end() — mutable iterators over the whole container (half-open range).
  • cbegin() / cend() — const_iterator versions; the elements cannot be modified through them.
  • rbegin() / rend() — reverse iterators; incrementing them moves backward through the container.
  • crbegin() / crend() — const reverse iterators.
  • *it — dereference, gives you the element (or, for maps, a std::pair<const Key, Value>).
  • it->member — shorthand for (*it).member, commonly used with map iterators as it->first / it->second.
  • std::advance(it, n), std::next(it, n), std::prev(it, n), std::distance(first, last) — from <iterator>, these work correctly on any iterator category, even ones without +/-.

Examples

Example 1: Basic iteration over a vector

#include <iostream>
#include <vector>

int main() {
    std::vector<int> scores = {85, 92, 78, 90, 88};

    std::cout << "Scores: ";
    for (std::vector<int>::iterator it = scores.begin(); it != scores.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    int sum = 0;
    for (auto it = scores.begin(); it != scores.end(); ++it) {
        sum += *it;
    }
    std::cout << "Sum: " << sum << std::endl;

    return 0;
}

Output:

Scores: 85 92 78 90 88 
Sum: 433

The first loop uses the explicit iterator type to print every score; the second uses auto to accumulate a sum. Both loops rely on the same pattern: start at begin(), stop when you reach end(), and dereference with *it to read the value.

Example 2: Bidirectional iteration, std::advance and std::distance

#include <iostream>
#include <list>
#include <string>
#include <iterator>

int main() {
    std::list<std::string> tasks = {"Design", "Code", "Test", "Deploy"};

    auto it = tasks.begin();
    std::advance(it, 2);
    std::cout << "Third task: " << *it << std::endl;

    std::cout << "Distance from begin: " << std::distance(tasks.begin(), it) << std::endl;

    std::cout << "Tasks in reverse: ";
    for (auto rit = tasks.rbegin(); rit != tasks.rend(); ++rit) {
        std::cout << *rit << " ";
    }
    std::cout << std::endl;

    return 0;
}

Output:

Third task: Test
Distance from begin: 2
Tasks in reverse: Deploy Test Code Design

std::list iterators are bidirectional, not random access, so there is no it + 2. Instead, std::advance moves the iterator forward by repeatedly calling operator++ internally — it works for any iterator category. rbegin()/rend() give a reverse iterator, so incrementing it walks the list from the back to the front.

Example 3: Map iterators, const_iterator, and erasing safely

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> inventory = {
        {"apples", 50},
        {"bananas", 0},
        {"cherries", 20},
        {"dates", 0}
    };

    std::cout << "Inventory:" << std::endl;
    for (std::map<std::string, int>::const_iterator it = inventory.begin(); it != inventory.end(); ++it) {
        std::cout << "  " << it->first << ": " << it->second << std::endl;
    }

    for (auto it = inventory.begin(); it != inventory.end(); ) {
        if (it->second == 0) {
            it = inventory.erase(it);
        } else {
            ++it;
        }
    }

    std::cout << "After removing out-of-stock items:" << std::endl;
    for (const auto& pair : inventory) {
        std::cout << "  " << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

Output:

Inventory:
  apples: 50
  bananas: 0
  cherries: 20
  dates: 0
After removing out-of-stock items:
  apples: 50
  cherries: 20

A std::map keeps its keys sorted, so iterating from begin() to end() visits entries in key order. Dereferencing a map iterator gives a pair, accessed with it->first / it->second. The removal loop shows the correct erase pattern: erase(it) invalidates it, so you must capture its return value (an iterator to the next valid element) rather than incrementing the now-dangling iterator yourself.

Under the Hood

What actually happens when you write for (auto it = v.begin(); it != v.end(); ++it) depends entirely on the container:

  • std::vector / std::array — the iterator is typically a raw pointer (or a thin wrapper around one). ++it just adds sizeof(T) to the address; *it is a direct memory read.
  • std::list — the iterator wraps a pointer to a node struct containing the value plus prev/next pointers. ++it follows node->next; the elements themselves may be scattered anywhere on the heap.
  • std::map / std::set — the iterator wraps a pointer to a tree node. ++it computes the in-order successor: if the node has a right child, go right then all the way left; otherwise walk up through parent pointers until you move up-and-to-the-right.
  • std::unordered_map / std::unordered_set — the iterator tracks a bucket index and a position within that bucket’s chain; ++it advances within the chain, then moves to the next non-empty bucket.

Because the underlying storage differs so much, so does iterator invalidation — the rules for when an iterator stops being safe to use:

  • For std::vector, inserting or erasing can trigger a reallocation (if capacity is exceeded), which invalidates every iterator, pointer, and reference into the vector. Even without reallocation, erasing invalidates the erased iterator and everything after it.
  • For std::list, std::map, and std::set, inserting never invalidates existing iterators, and erasing only invalidates the iterator to the erased element — all others remain valid.

Common Mistakes

Mistake 1: Using arithmetic on a non-random-access iterator

List iterators are only bidirectional — they have no operator+, so this fails to compile:

std::list<int> nums = {1, 2, 3, 4, 5};
std::list<int>::iterator it = nums.begin();
std::cout << *(it + 2) << std::endl; // compile error: no operator+ for list::iterator

Fix it by using std::next, which works for any iterator category by internally calling ++ the requested number of times:

std::list<int> nums = {1, 2, 3, 4, 5};
auto it = nums.begin();
std::cout << *std::next(it, 2) << std::endl; // 3

Mistake 2: Incrementing an iterator after erase() invalidates it

A very common bug is erasing from a vector inside a loop without reassigning the iterator that erase() returns:

std::vector<int> nums = {1, 2, 3, 4, 5, 6};
for (auto it = nums.begin(); it != nums.end(); ++it) {
    if (*it % 2 == 0) {
        nums.erase(it); // invalidates it; the following ++it is undefined behavior
    }
}

This compiles, but erase(it) invalidates it, and the loop’s own ++it then operates on a dangling iterator — the program’s behavior is undefined and results (or crashes) are unpredictable. The fix is to capture erase()‘s return value, which is a valid iterator to the element that followed the one just removed:

std::vector<int> nums = {1, 2, 3, 4, 5, 6};
for (auto it = nums.begin(); it != nums.end(); ) {
    if (*it % 2 == 0) {
        it = nums.erase(it);
    } else {
        ++it;
    }
}
for (int n : nums) std::cout << n << " ";

Output:

1 3 5

Best Practices

  • Prefer auto over spelling out the full iterator type — it is shorter and immune to type-name changes.
  • Use cbegin()/cend() (or a const reference to the container) whenever you are only reading, to make your intent explicit and let the compiler catch accidental modification.
  • Use a range-based for loop when you don’t need the iterator itself (no erasing, no position tracking) — it is clearer and just as fast.
  • When erasing from a container while iterating, always reassign the iterator from erase()‘s return value; never increment an iterator you just erased.
  • Know your container’s invalidation guarantees before storing an iterator across a mutation — vector iterators are the most fragile (any insert/erase can invalidate them), list/map/set iterators are the most robust.
  • Use std::next/std::prev/std::advance/std::distance instead of raw +/- arithmetic when the iterator category is not guaranteed to be random access.
  • Never dereference or increment an end() iterator — it is a sentinel, not a real element.

Practice Exercises

  • Exercise 1: Given std::vector<int> nums = {4, 7, -2, 9, -5, 1};, use an iterator-based loop (not indexing) to find and print the first negative number, or “None found” if there isn’t one.
  • Exercise 2: Given std::list<std::string> names = {"Ana", "Ben", "Cara", "Drew", "Eve", "Finn"};, use an iterator and std::advance to print every other name starting from the first (Ana, Cara, Eve).
  • Exercise 3: Given std::map<std::string, double> prices with several product/price pairs, write a loop using const_iterator that prints only the products priced above $10, formatted as “product: $price”.

Summary

  • An iterator generalizes a pointer, providing a uniform ++/* interface so STL algorithms can work with any container.
  • begin() returns the first element; end() is a sentinel one-past-the-last — the valid range is half-open, [begin, end).
  • Iterator categories (input, output, forward, bidirectional, random access) determine which operations are legal; vectors support full arithmetic, lists and maps do not.
  • Internally, vector iterators are often raw pointers, list iterators follow linked nodes, and map/set iterators traverse a tree via in-order successor logic.
  • Iterator invalidation rules differ per container — vectors are the riskiest since reallocation invalidates everything; always reassign iterators after insert/erase on a vector.
  • std::advance, std::next, std::prev, and std::distance work safely across all iterator categories.