Not every iterator can do everything. A std::vector iterator can jump 100 positions forward in O(1). A std::list iterator only steps one position at a time. A std::istream_iterator can be incremented once per element and never reread. The STL formalises these differences into iterator categories, and almost every algorithm in the standard library is documented in terms of the minimum category its input iterators must satisfy. This chapter walks through the six categories, what each one supports, which containers provide which, why algorithms care, and how the old tag-based system was modernised by C++20 concepts.

Iterators are classified into a refinement hierarchy. Each category supports everything the previous one supports, plus a few extra operations.

The hierarchy has two roots, input and output, because reading and writing through an iterator are independent capabilities. Forward iterators merge the two: they support reading, writing (when not const), and re-traversal. Bidirectional iterators add --. Random access iterators add jumps and ordering. Contiguous iterators, added in C++20, are random access iterators with the extra guarantee that the elements live in a single contiguous block of memory.

The short version of what each one supports:

"Multi-pass" means the iterator can be copied, one of the copies can walk, and the other one can walk independently and get the same elements. Input and output iterators are single-pass: after advancing, the position behind is gone.

The categories aren't trivia. Every algorithm in <algorithm> advertises the category it requires. std::sort needs random access. std::find needs only input. std::reverse needs bidirectional. The wrong container with an algorithm won't compile, by design.

An input iterator reads each element exactly once and then advances. Backing up isn't possible, re-traversal isn't possible, and copies of the iterator share the same position in the underlying stream. The standard example is std::istream_iterator: each increment consumes one value from the stream, and the value can't be pushed back.

The reads happen as the loop runs. Dereferencing it a second time before incrementing might return the same value, the next one, or garbage; the standard only guarantees that one read per increment is well-defined.

Input iterators are the weakest read iterator, so they have the broadest reach. Any algorithm that needs only a single forward pass over the input (like std::find, std::count, std::accumulate) is documented to require only input iterators, which means it works against streams, against any sequence container, and against custom iterators.

An output iterator is the write-only counterpart. Assignment through it (*it = value) works, and increment works, and that's all. Reading from it isn't allowed, comparing two of them meaningfully isn't allowed, and backing up isn't allowed.

Insert iterators (back_inserter, front_inserter, inserter) are output iterators. So is std::ostream_iterator.

std::copy performs *out = value; ++out for each input element, and the ostream_iterator turns the assignment into a write to std::cout. The algorithm doesn't know or care that the destination is a stream.

A forward iterator combines input and output: reading works, writing works (assuming the underlying type is mutable), and crucially, a copy can be made and the copy is independent. Walking the copy doesn't disturb the original. Two passes over the same range produce the same results.

std::forward_list is the canonical container whose iterators are forward but not bidirectional. The list is singly-linked, so each node has a "next" pointer but no "previous" pointer. Walking forward through the chain works, going back doesn't, which is the contract of a forward iterator.

The copy and the original walk independently. That's the multi-pass property that input iterators don't have.

The std::unordered_set and std::unordered_map containers also expose forward iterators. They're hash tables, so the storage is bucketed and walking is one-directional within each bucket. Iteration and re-iteration work, but --it doesn't and jumps don't.

A bidirectional iterator adds -- to the forward iterator's contract. Stepping backward as well as forward works. That's enough for algorithms like std::reverse and std::next_permutation that need to walk a range in both directions.

std::list, std::set, std::map, std::multiset, and std::multimap all expose bidirectional iterators. They're either doubly-linked lists or balanced binary search trees, both of which let you move to the previous node without searching from the start.

The loop starts at the last element (one step back from end()) and decrements until it reaches begin(). With a forward iterator the same loop wouldn't compile, because --it isn't defined.

What a bidirectional iterator still can't do is jump. Going from position 0 to position 7 requires seven ++ calls. Each step is O(1), but the trip is O(n) in the distance traveled.

std::advance(it, 7) on a bidirectional iterator runs ++ seven times, so it's O(n). The same call on a random access iterator is a single pointer arithmetic operation, O(1). When std::distance shows up in a hot loop, the iterator category determines constant or linear time.

A random access iterator adds three powers on top of bidirectional. Jumping by an arbitrary offset (it + n and it - n), subtracting two iterators for a signed distance (it2 - it1), and ordering two iterators with <, >, <=, >=. All of these are O(1).

std::vector, std::deque, and std::array expose random access iterators. Vector and array store their elements contiguously, deque stores them in chunks but maintains O(1) random access through an indirection table.

The jumps, the subtraction, and the ordering comparison all compile because the iterator is random access. The same code against a std::list iterator would fail to compile, which is the language doing its job: the contract for a list iterator doesn't include any of these operations.

C++20 added a sixth category at the top of the hierarchy: contiguous iterators. A contiguous iterator is a random access iterator with the extra guarantee that the elements it walks live next to each other in memory, so the address of element n+1 is exactly &element_n + 1.

The two element addresses differ by exactly sizeof(int). That property has been true of std::vector (when non-empty) since C++03, but C++20 made it part of the iterator's static contract so that templated code can ask the type system whether the guarantee holds, instead of trusting it.

Contiguous iterators matter for low-level code that interoperates with C APIs or uses raw pointer arithmetic. An algorithm written for contiguous iterators can pass the underlying pointer directly to memcpy, read, or write. The standard's std::span (also C++20) is designed around the contiguous-iterator concept.

The exception in the table is std::vector<bool>. Its iterator is technically random access but it points to single bits packed into machine words, so it isn't a real reference to a bool and it isn't contiguous in the C++20 sense. std::vector<bool> predates the contiguous category and remains a special case.

The whole point of categorising iterators is that algorithms can require a minimum category and the compiler enforces it. Some algorithms work on any input; some need to look both ways; some need to compute offsets in constant time. Mismatch the category and the build fails, often with a noisy template error but always at compile time, not runtime.

The classic example is std::sort. Its signature is roughly:

The template parameter is named RandomIt for a reason: std::sort uses an introspective sort algorithm that mixes quicksort with heapsort, both of which require O(1) jumps to partition the range and swap elements at arbitrary positions. A linked list can't provide O(1) jumps without walking the chain, so std::sort doesn't compile against std::list::iterator.

The g++ error message starts with something like error: no match for 'operator-' (operand types are 'std::_List_iterator<int>' and 'std::_List_iterator<int>'). The algorithm tried to compute last - first, the iterator type didn't support it, and the build broke.

The fix isn't to use raw pointers. std::list has its own sort() member function that uses an algorithm appropriate for linked lists (typically merge sort) and runs in O(n log n) without needing random access.

The general rule: if a standard algorithm needs random access and the container doesn't provide it, look for a member function on the container that does the job in a way the storage supports.

std::binary_search is another example. Binary search needs to jump to the midpoint of the range, which is O(1) for random access and O(n) for anything weaker. The algorithm compiles against std::list iterators because they satisfy the formal requirement (forward iterators are enough on paper), but the runtime degrades to O(n log n) instead of O(log n) because each midpoint jump costs O(n).

std::binary_search on a std::list compiles and runs, but it's O(n log n), not O(log n). The halving still happens, but each jump to the midpoint walks the list. For binary search, use a std::vector or std::set/std::map instead.

The minimum category for some common algorithms:

The pattern is that simpler algorithms have weaker requirements, and the requirements track exactly what the algorithm needs to do its job.

Internally, every iterator type advertises its category through a type called its iterator tag. The standard defines five tag types (with one C++20 addition):

The tags are empty struct types, used purely as compile-time labels. The inheritance encodes the refinement hierarchy: a random_access_iterator_tag IS-A bidirectional_iterator_tag, which IS-A forward_iterator_tag, and so on.

Any iterator's tag is available through std::iterator_traits. The traits structure exposes the iterator's properties as nested type aliases, including a iterator_category typedef that holds the tag.

The traits machinery is how generic algorithms find out what their input iterators can do. std::sort looks at std::iterator_traits<It>::iterator_category and refuses to compile if it isn't random_access_iterator_tag (or a refinement of it).

The trick that uses tags at compile time is called tag dispatch: write multiple overloads of an internal helper, each taking a different tag, and call them through a single user-facing wrapper. The compiler picks the right overload based on the iterator's category.

Both calls go through myAdvance, but the overload that runs is determined at compile time by the iterator category of the argument. The vector call resolves to the random-access overload and uses pointer arithmetic. The list call resolves to the bidirectional overload and walks the chain one node at a time. This is how the standard's std::advance is implemented.

The wrapper presents a single, simple interface, but each container gets the most efficient implementation available. The cost decision is made at compile time, so there's no runtime branch.

C++20 modernised this whole machinery with the concepts language feature. A concept is a named constraint that a template parameter must satisfy, expressed in real C++ syntax rather than encoded in tag types. The standard ships concepts for each iterator category in <iterator>:

Where pre-C++20 code wrote tag-dispatching overloads, C++20 code can constrain templates directly:

The concept names what the template needs, and the compiler emits a focused error message when a caller passes the wrong kind of iterator. Compare that to the template-error wall pre-C++20 algorithms produce when constraints fail deep inside the implementation.

The concepts integrate with the C++20 ranges library, which generalises the begin/end pair into a single range object and composes operations as pipelines. That's a separate topic, covered in detail in the Modern C++ section's Ranges chapter, so this chapter just notes that the concept system is the foundation under it.

The tag types still exist and still work; concepts didn't remove them. New code can use either. Tags are universal and work back to C++98; concepts are clearer but require C++20. The standard library uses both: legacy machinery on iterator_traits still hands out tags, while new APIs in <ranges> are written against concepts.

A small program that picks the right container based on the operations needed illustrates the practical impact of iterator categories.

The vector's random access iterators let std::sort run in O(n log n) and let the median lookup be O(1). The list's bidirectional iterators don't support sort or random access, but they support cheap insertion in the middle without invalidating the other iterators, which is what the order-queue case wants. Choosing the wrong container for the access pattern shows up as either an algorithm that won't compile or an algorithm that compiles but runs in the wrong complexity class.