Iterator in C++

In one sentence: Iterator lets you visit every element of a collection without the caller ever learning how the collection stores them.

Real-world analogy

At the museum entrance they hand you an audio guide. It has one button that matters: next. Press it and you're taken to the following exhibit, then the next, in an order the museum has already decided, until there's nothing left to see.

What you're never shown is how the museum actually holds its collection. Wing numbers, crate labels in the storeroom, the curator's catalogue database — the guide knows enough to walk you through them; you don't need to know any of it. The curators can renumber every room over the winter and your visit is unchanged: press next, see the next thing.

And you're not the only visitor. Someone who started twenty minutes earlier is on exhibit 12 while you're on exhibit 3, each holding their own guide, neither one disturbing the other or the collection. The guide holds a position — the museum holds the art.

Mapping the analogy to the pattern:

The audio guide → the ConcreteIterator, whose entire state is "which exhibit am I on."
The next button → Next() / operator++, alongside "play the current one" (CurrentItem() / operator*) and "have we run out" (IsDone() / != end()).
The museum's internal arrangement — storerooms, catalogue numbers, wing layout → the ConcreteAggregate's representation, which the visitor never sees and which can change freely.
Two visitors carrying two guides → several traversals pending at once, each iterator carrying its own position.
The desk that hands you a guide on the way in → CreateIterator() — in C++, begin(). The aggregate is the only one who knows which iterator is right for it, which makes this a factory method.

Another angle: conveyor-belt sushi. You take the next plate as it reaches your seat and never see the kitchen; the diner further down the belt is at a different point in the same rotation.

The problem

Your Playlist stores songs in a hand-rolled linked list. Someone wants to print all of them:

You'd have to expose the nodes. Handing out Node* leaks your internals into every caller, and now you can never switch to a std::vector without breaking all of them.
Every traversal is rewritten by hand. Each caller writes the same while (node) { ...; node = node->next; } loop, and each one can get the ending condition wrong.

The solution

Move the "where am I, and what's next?" logic into a small iterator object:

The iterator holds the position — a node pointer, an index, whatever the container really uses.
It exposes a tiny interface: read the current element, advance, compare against the end. (GoF's version of that interface is First(), Next(), IsDone(), CurrentItem().)
The container hands out a begin() and an end(), and nothing else. GoF names this operation CreateIterator() and points out it is itself a factory method — the aggregate is the only one who knows which iterator class is right for it.

In C++ this pattern isn't a suggestion, it's the language contract. A range-based for loop is literally rewritten by the compiler into calls to begin(), !=, *, and ++. Provide those, and your class works with for (auto x : c) and with the standard algorithms — for free.

Note: GoF's two big implementation questions are worth knowing by name. Who drives the loop? If the client asks for each element, that's an external iterator (what C++ has, and what std::find needs); if you hand the iterator a function and it applies that to every element, that's an internal iterator (std::for_each, or a forEach method). External ones are more flexible — comparing two collections element by element is easy externally and nearly impossible internally. Who owns the traversal algorithm? Usually the iterator, but the aggregate can own it and let the iterator hold nothing but a position; GoF calls that stripped-down variant a cursor.

Structure

Four participants split into two parallel hierarchies, joined by the factory method:

Iterator — defines the interface for accessing and traversing elements. In C++ this is not a base class but a concept: operator*, operator++, operator!=.
ConcreteIterator — implements that interface and keeps track of the current position in the traversal. Here: Playlist::Iterator, whose entire state is one Node*.
Aggregate — defines the interface for creating an iterator.
ConcreteAggregate — returns an instance of the right ConcreteIterator. Here: Playlist, whose begin() and end() are the factory methods.

C++ example

A linked-list playlist whose nodes are completely private, yet which works in a range-based for loop and with std::find.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <memory>
#include <string>

class Playlist {
    struct Node {                       // private: nobody outside can even name this
        std::string song;
        std::unique_ptr<Node> next;
    };

public:
    void add(std::string song) {
        auto node = std::make_unique<Node>();
        node->song = std::move(song);
        Node* raw = node.get();
        if (tail_) tail_->next = std::move(node);
        else       head_ = std::move(node);
        tail_ = raw;
    }

    // The only view outsiders ever get of our nodes.
    class Iterator {
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type        = std::string;
        using difference_type   = std::ptrdiff_t;
        using pointer           = const std::string*;
        using reference         = const std::string&;

        explicit Iterator(Node* n) : node_(n) {}
        reference operator*() const { return node_->song; }
        Iterator& operator++() { node_ = node_->next.get(); return *this; }
        bool operator==(const Iterator& o) const { return node_ == o.node_; }
        bool operator!=(const Iterator& o) const { return !(*this == o); }
    private:
        Node* node_;
    };

    Iterator begin() const { return Iterator(head_.get()); }
    Iterator end()   const { return Iterator(nullptr); }

private:
    std::unique_ptr<Node> head_;
    Node* tail_ = nullptr;
};

int main() {
    Playlist playlist;
    playlist.add("Blue in Green");
    playlist.add("So What");
    playlist.add("Flamenco Sketches");

    int track = 1;
    for (const std::string& song : playlist)      // the compiler calls begin()/end()
        std::cout << track++ << ". " << song << "\n";

    auto it = std::find(playlist.begin(), playlist.end(), std::string("So What"));
    std::cout << "Found 'So What'? " << std::boolalpha << (it != playlist.end()) << "\n";
}

Output

1. Blue in Green
2. So What
3. Flamenco Sketches
Found 'So What'? true

main() never mentions Node or next — the container could switch to an array tomorrow and both the loop and std::find would keep working unchanged.

When should you use it?

GoF's applicability is three lines long. Use Iterator:

To reach an aggregate's contents without exposing how it stores them — tree, graph, linked list, paged file. In C++ this also buys you range-based for and the whole <algorithm> header, which is reason enough on its own.
To support multiple traversals of the same aggregate — in-order and pre-order, forward and reverse, filtered and unfiltered, as separate iterator types.
To give one uniform interface for traversing different aggregate structures — what GoF calls polymorphic iteration, where the same client code walks a list and a skip list without knowing which it has.

Pros and cons

Pros (GoF's consequences)

Traversal becomes variable — swapping the iterator changes the walk order without touching the collection, and a new traversal is a new iterator subclass.
It simplifies the aggregate's interface — once the iterator carries the traversal operations, the collection doesn't need its own set of them.
More than one traversal can be pending at once — each iterator carries its own position, so two loops can walk the same collection independently.

Cons

Writing a fully correct iterator (const versions, the right traits, comparison rules) is more fiddly than it looks.
Polymorphic iterators have a real cost, and GoF says so plainly: making the iterator interface virtual forces the object onto the heap via a factory method, and then the client has to remember to delete it — easy to leak on an early return, and guaranteed to leak if an exception unwinds past it. This is exactly why the C++ standard library went the other way: STL iterators are cheap value types you allocate on the stack and copy freely, at the price of being resolved at compile time rather than through a base class.
Iterators can be invalidated by modifying the container mid-loop — a classic source of crashes. GoF calls an iterator that survives insertions and removals a robust iterator; making one usually means registering the iterator with its aggregate so the aggregate can fix it up when the contents change.

Tip: Before writing an iterator class, check whether your data already lives in a std::vector or std::map. If it does, just forward: auto begin() { return items_.begin(); }. You get a correct, fully featured iterator for two lines of code.

How to remember it

Memory hook: "A bookmark, not the book." The iterator's whole job is to remember where you are; the collection keeps the pages. Contrast with Visitor: the iterator decides what order you reach the elements, the visitor decides what you do when you get there.

Composite — GoF notes iterators are often applied to recursive structures like composites. Beware: an external iterator over a tree has to store a whole path, which is why an internal or cursor-based iterator is sometimes the easier answer.
Factory Method — begin() is exactly that: polymorphic iterators rely on a factory method to instantiate the right iterator subclass.
Memento — GoF's third link, and the one people miss: an iterator can hold a memento capturing the state of an iteration. A cursor is really a small memento of "where am I."
Visitor — the other half of the job: iterator decides what order you visit, visitor decides what you do at each element.