C++ programmers tend to learn the iterator hierarchy in broad strokes — input, output, forward, bidirectional, random access, in increasing order of capability — and mostly stop there. The five categories get listed in introductory material, the random-access category gets the attention because std::sort requires it, and the line between Input and Forward is treated as a small refinement that doesn’t matter in practice. It does matter.
The boundary between the two categories is what separates read-this-stream-once iterators from traverse-this- container-as-many-times-as-you-need iterators, and that single-pass-versus-multi-pass distinction governs which algorithms work, which ones silently corrupt, and which ones won’t compile in the first place.
Three things to take away:
- An input iterator (
InputIt) supports a single pass: each element can be read once, and copying the iterator does not give you an independent view of the same position. - A forward iterator (
ForwardIt) supports multi-pass: you can copy the iterator, traverse the copy, and the original still points at the same valid element. - Algorithms that revisit elements (
adjacent_find, multi-passfind, anything that takes a range twice) requireForwardIt; algorithms that read each element exactly once (find,for_each,accumulate) accept the more permissiveInputIt.
A short tour of the hierarchy
The standard iterator hierarchy has five categories in strictly increasing capability — each refines the one above:
input_iterator → read once, advance
forward_iterator → read repeatedly, multi-pass
bidirectional_iter → also: decrement
random_access_iter → also: jump by N, subscript [], compare with <
contiguous_iter → also: pointer arithmetic into a single buffer (C++20)(Output iterators sit alongside input iterators, but for writing rather than reading; they are the symmetric case and this Nibble glosses over them.)
The standard reference is direct about the two categories this Nibble cares about. Input iterators “permit you to read a sequence in one pass.” Forward iterators “permit unidirectional access to a sequence. You can refer to and assign to an item as many times as you want.” The phrase that matters is “as many times as you want.” That capability is the defining feature of forward iterators, and its absence is the defining limitation of input iterators.
The defining difference: single-pass vs multi-pass
An input iterator’s contract permits the implementation to destroy what it just read. The classic example is std::istream_iterator:
#include <iostream>
#include <iterator>
std::istream_iterator<int> it{ std::cin };
int a = *it; // reads the first integer
++it;
int b = *it; // reads the second integerReading from std::cin consumes characters from the stream; once consumed, they’re gone. There is no way to “go back” and re-read what was at position 0 — the stream itself doesn’t remember. The iterator inherits that limitation. That’s what “single-pass” means: not just “the iterator only goes forward,” but “you cannot examine any position twice.”
A forward iterator makes the stronger guarantee that elements persist. You can copy the iterator, advance the copy, and the original still refers to the same element it always did:
#include <forward_list>
std::forward_list<int> lst = { 1, 2, 3 };
auto it1 = lst.begin(); // points at 1
auto it2 = it1; // independent copy, also points at 1
++it2; // it2 now points at 2
// it1 still points at 1 — *it1 is still validstd::forward_list::iterator is the textbook example of a forward iterator: every node has a stable address, every iterator is essentially a pointer into a linked structure, and copies are fully independent.
The value-category fingerprint
The single-pass vs multi-pass difference shows up at the language level too. Dereferencing an input iterator returns an rvalue — you can read it, but you can’t take a stable reference, can’t bind it to a non-const lvalue reference, can’t reliably compare two reads of the same position to each other:
std::istream_iterator<int> it{ std::cin };
const int& bad = *it; // dangling: the rvalue's lifetime
// ends at the next ++itDereferencing a forward iterator returns a real lvalue reference into stable storage:
auto it = lst.begin();
const int& good = *it; // OK: the element exists somewhere durable
// and remains valid while it points at itThe reference distinction isn’t just stylistic — it’s the mechanism that makes multi-pass possible. If *it returned an rvalue from some internal buffer that gets overwritten on the next read, multi-pass guarantees couldn’t be enforced. The contract is: forward iterators dereference to durable lvalues; input iterators do not.
Which algorithms need which category
Most STL algorithms specify their iterator requirements in their signature’s template parameter names. The standard’s choice of InputIt vs ForwardIt is deliberate — it tells you the minimum guarantee the algorithm needs. Two examples make the distinction concrete.
std::find reads each element once and stops at the first match — single-pass is sufficient:
template <class InputIt, class T>
InputIt find(InputIt first, InputIt last, const T& value);You can call std::find on a stream of integers from std::cin and it works correctly: each element is examined exactly once, in order, and the algorithm stops the first time the predicate matches.
std::adjacent_find looks for two consecutive equal elements, which means it compares *it to *next(it):
template <class ForwardIt>
ForwardIt adjacent_find(ForwardIt first, ForwardIt last);The signature requires ForwardIt. The algorithm needs to read element i, advance, read element i+1, and still have access to the original element i for the comparison. With an input iterator, the read at position i consumed that element; there’s no way to compare it to anything anymore. The signature forbids that mistake at compile time.
A few familiar examples in each category:
| Category | Example algorithms |
|---|---|
| InputIt | find, for_each, count, accumulate, copy (input side), equal |
| ForwardIt | adjacent_find, unique, rotate, partition, replace, fill |
| BidirectIt | reverse, prev, next (with negative step) |
| RandomIt | sort, nth_element, lower_bound (sub-O(n) only here) |
Reading the iterator-parameter name of any STL algorithm is the fastest way to know what kind of input it accepts — and what kind of input you can pass.
Designing your own algorithms
The same rule applies in reverse when you write a generic algorithm. Take the most permissive iterator category your algorithm actually needs:
- If your algorithm reads each element exactly once, in order, template on
InputIt. Callers can then pass anything fromstd::istream_iteratortostd::vector::iterator. - If your algorithm needs to traverse the same range twice, compare adjacent elements, or hold two iterators into the range simultaneously, template on
ForwardIt. This still accepts most callers, but rules out streams. - Reach for
BidirectionalItonly if you genuinely need-it, andRandomAccessItonly if you need O(1) jumps or subscript access.
A common over-constraint is requiring RandomAccessIt when the algorithm could have worked with ForwardIt. The cost is that callers with std::list or std::forward_list cannot use your algorithm, even when the operation makes sense for linear scans.
C++20: same idea, modern syntax
C++20 redesigned iterator categories as concepts in <iterator>: std::input_iterator, std::forward_iterator, std::bidirectional_iterator, std::random_access_iterator, std::contiguous_iterator. The categories and their relationships are unchanged, but the new spelling is checked at compile time and produces dramatically clearer error messages than the C++17 tag-class system did:
template <std::forward_iterator It>
void scan_twice(It first, It last){
for (auto i = first; i != last; ++i) { /* first pass */ }
for (auto i = first; i != last; ++i) { /* second pass */ }
}Pass an std::istream_iterator here and the compiler reports a constraint failure naming forward_iterator directly, rather than emitting a wall of template-instantiation errors ending somewhere inside the algorithm. The mechanism is part of the same C++20 ranges work covered in Nibble #085 — and it’s particularly useful for the iterator-category rules, where the category boundaries are exactly what the concepts encode.
Takeaway
The Input vs Forward boundary is the single-pass vs multi-pass boundary. Input iterators read each element once and may not survive being copied; forward iterators promise that elements persist, that copies are independent, and that dereferencing yields a durable lvalue reference. Algorithms that revisit elements require ForwardIt; algorithms that read each element once accept the more permissive InputIt.
When designing your own generic algorithms, ask the most permissive category your work actually needs — over-constrained templates rule out callers who could have passed valid input. The rule is simple: an input iterator is a one-time read; a forward iterator is a stable pointer into a sequence — and every STL algorithm’s signature tells you which one it expects.