Iterator Categories and What Each Permits

Part I · Module 20 · Chapter 20.2 · Iterator Categories and What Each Permits

1. Five Categories

The standard defines five iterator categories. Each is a named set of required operations, and each container's iterator belongs to exactly one.

Input — single pass, read only. You may dereference it to read, and increment it. You may not go back, and you may not read the same position twice, because incrementing may consume the underlying source. std::istream_iterator is the canonical example.

Output — single pass, write only. You may assign through it and increment it. std::back_insert_iterator and std::ostream_iterator are these.

Forward — multi-pass, one direction. Everything input has, plus the guarantee that you may traverse the range more than once and that two iterators to the same position stay equal. std::forward_list.

Bidirectional — forward, plus --. std::list, std::map, std::set.

Random access — bidirectional, plus + n, - n, - other, [] and ordering, all in constant time. std::vector, std::array, std::deque, and raw pointers.

C++20 adds a sixth, contiguous, above random access: the elements are adjacent in memory, so &*(it + n) == &*it + n. That is what permits a range to be handed to a C API as a pointer, and it is the formal statement of the property Chapter 19.2 §4 measured with memcmp.

2. Reading the Category From the Type

The category is not documentation; it is a type you can inspect. Every iterator exposes it through std::iterator_traits:

template <typename It>
static void row(const char* name)
{
    using C = typename std::iterator_traits<It>::iterator_category;
    const bool ra  = std::is_base_of_v<std::random_access_iterator_tag, C>;
    const bool bid = std::is_base_of_v<std::bidirectional_iterator_tag, C>;
    const bool fwd = std::is_base_of_v<std::forward_iterator_tag, C>;
    /* print */
}

array<int,4>             random access   ++:y  --:y  +n:y  []:y  multi-pass:y
vector<int>              random access   ++:y  --:y  +n:y  []:y  multi-pass:y
deque<int>               random access   ++:y  --:y  +n:y  []:y  multi-pass:y
list<int>                bidirectional   ++:y  --:y  +n:n  []:n  multi-pass:y
map<int,int>             bidirectional   ++:y  --:y  +n:n  []:n  multi-pass:y
set<int>                 bidirectional   ++:y  --:y  +n:n  []:n  multi-pass:y
forward_list<int>        forward         ++:y  --:n  +n:n  []:n  multi-pass:y
istream_iterator<int>    input           ++:y  --:n  +n:n  []:n  multi-pass:n
int* (raw pointer)       random access   ++:y  --:y  +n:y  []:y  multi-pass:y

Three things worth noting. A raw pointer is random access, which is why §1's claim that pointers are full iterators holds all the way to the strongest category. A std::deque is random access despite not being contiguous — Chapter 19.4 §4's two-step lookup is still constant time, so it qualifies. And the categories line up exactly with the containers' structures rather than with anyone's preference: std::map is bidirectional because a tree can be walked in both directions in constant time per step and cannot be indexed at all.

3. The Categories Are a Hierarchy

They are not five alternatives; they nest, and the tag types encode that by inheritance:

random_access is_base_of bidirectional : 1
bidirectional is_base_of forward       : 1
forward is_base_of input               : 1

So random_access_iterator_tag derives from bidirectional_iterator_tag, which derives from forward_iterator_tag, which derives from input_iterator_tag. The practical consequence is the one the measurement states: an algorithm requiring "forward" accepts random access too, because a random-access iterator is-a forward iterator — the same Liskov substitution relationship Chapter 16.3 §2 established for public inheritance, used here as a compile-time classification rather than for run-time dispatch.

That is why algorithm requirements are always stated as the weakest category that suffices. std::find requires input, which means it accepts everything. std::sort requires random access, which means it accepts only the top of the hierarchy. The output category sits outside this chain, which is why it is listed separately.

4. The Category Is a Cost Contract

This is the half that is easy to miss. A bidirectional iterator does not lack + n as an oversight — it lacks it because the structure behind it cannot do that in constant time, and the library refuses to offer a constant-looking syntax for a linear operation. Chapter 19.4 §7 made the same argument for std::list having no operator[].

The proof is std::distance, which the library provides for every category by dispatching on the tag. One call, two implementations:

         n     vector (ns)       list (ns)  list ns/el
     62500             0.6          119500        1.91
    250000             0.6          553917        2.22
   1000000             0.6         2189958        2.19

The vector column is flat across a sixteen-fold increase in n. Over thirty samples — ten runs at three sizes — it ranged from 0.00 to 1.30 nanoseconds with a median of 0.60, and several readings were literally 0.00: the clock could not resolve the operation at all. That is the strongest available form of the point. It is end - begin, one subtraction, and the container's size is irrelevant.

The list column grows with n in total, because it counts steps — counting being the only way a linked structure can answer the question. Per element it ranged from 1.29 to 3.22 ns over the same thirty samples, median 2.13, with a mild upward trend by size: medians of 1.77, 2.09 and 2.34 for the three n values. That trend is cache pressure rather than algorithmic, and under heavier machine load the figure reached 5.4.

A note on the instrument, because the first version of this measurement was misleading. A single timing of each would have produced a meaningless ratio — the vector's figure is below timer resolution, so dividing one by the other yielded a nonsense number in the millions. What is measurable is the shape: flat versus linear. And a fourth size, n = 4,000,000, was measured and then dropped: 96 MB of list nodes made two of seven runs report 118 to 138 ns per element against 3 to 5 for the rest, which is this machine paging under load rather than a property of std::distance. A size whose readings are bimodal cannot support a claim in either direction.

So when an algorithm says it needs random access, part of what it is saying is that it will perform operations whose cost it is assuming to be constant.

5. Input Iterators Are Single-Pass, and That Changes the Rules

The multi-pass column in §2's table is the only one that is not about which operators exist, and it is the most consequential.

std::istringstream in("10 20 30 40");
std::istream_iterator<int> b(in), e;
std::vector<int> got(b, e);               // consumes the stream
std::istream_iterator<int> b2(in), e2;
std::vector<int> again(b2, e2);           // and again?

read 4 values from the stream: 10 20 30 40
reading AGAIN from the same stream gives 0 values
-> the range was consumed; a single-pass iterator cannot be rewound

The second read returned nothing, because incrementing the first iterator consumed the characters. A forward iterator guarantees the opposite: you may traverse [begin, end) as many times as you like and get the same elements, and two iterators to the same position compare equal and stay equal.

Algorithms depend on this. std::find passes over the range once and so requires only input. std::equal compares two ranges and needs each read once, so input suffices. But std::sort reads elements repeatedly and writes them back; std::reverse reads from both ends; std::unique compares each element with its neighbour after possibly moving things. None of those can work from a source that can only be read once, which is why a stream iterator is accepted by a much smaller set of algorithms than people expect.

The practical rule: if a range comes from a stream, copy it into a container first unless the single algorithm you are calling genuinely only needs one pass.

6. Which Algorithms Need Which

find / count / for_each / transform : input    (single pass is enough)
copy / fill / replace               : forward  (multi-pass, one direction)
reverse / rotate                    : bidirectional
sort / nth_element / binary_search  : RANDOM ACCESS

And the demonstration that the boundary is real:

std::list<int> l{5,3,1,4,2};
std::reverse(l.begin(), l.end());          // bidirectional: fine
l.sort();                                  // the member substitute

reverse on a list works: 2 4 1 3 5
l.sort() is the member substitute: 1 2 3 4 5

std::reverse needs to walk inwards from both ends, which bidirectional provides, so it compiles and runs on a list. std::sort needs to index and to compute distances in constant time, which bidirectional does not provide, so it does not compile at all.

That is why std::list and std::forward_list have member sort functions: the generic algorithm cannot serve them, and the member version does something the generic one could not anyway — Chapter 19.4 §5 measured it relinking nodes with zero copies and zero moves. The same reasoning gives std::list its own remove, unique, merge and reverse members.

std::map and std::set need no member sort because they are always sorted, and they offer find as a member because the generic std::find would be a linear scan where the tree can do O(log n) — the general principle being that a member function exists when the container can beat the generic algorithm or when the generic algorithm cannot apply.

7. The Diagnostic When You Ignore the Requirement

std::list<int> l{3,1,2};
std::sort(l.begin(), l.end());

/usr/include/c++/v1/__algorithm/make_heap.h:35:34: error: invalid operands to
    binary expression ('std::__list_iterator<int, void *>' and
    'std::__list_iterator<int, void *>')
/usr/include/c++/v1/__algorithm/partial_sort.h:43:85: error: invalid operands to
    binary expression (...)

Four errors across 138 diagnostic lines, and this is the part that matters: the first error is reported inside make_heap.h, a header you have never opened, about an expression you did not write. Your own file appears only as the call site in an "in instantiation of" note. The compiler is telling you, in the most roundabout way available, that it - it is not defined for a list iterator — which is std::sort needing random access.

This is Chapter 18.6 §5's diagnostic shape at its worst, and it is precisely the problem C++20's concepts were introduced to fix. Chapter 21.8 covers them; the short version is that a constrained std::sort reports "the iterator does not satisfy random_access_iterator" at your call site in a line or two, because the requirement is stated in the signature rather than discovered in the body. Chapter 18.10 §6's static_assert is the pre-C++20 way to get the same effect in your own templates, and the 370-lines-to-7 measurement there is the same phenomenon.

The practical skill until then: when a diagnostic begins inside a standard header, do not read it top to bottom. Find the last "in instantiation of" note naming your file, look at what you called, and check the algorithm's category requirement.

8. Writing an Algorithm That Adapts

Since the category is a type, your own code can dispatch on it the way std::distance does. The modern form uses if constexpr — Chapter 18.8 §9's mechanism:

template <typename It>
void advanceBy(It& it, std::ptrdiff_t n)
{
    using C = typename std::iterator_traits<It>::iterator_category;
    if constexpr (std::is_base_of_v<std::random_access_iterator_tag, C>)
        it += n;                                   // O(1)
    else
        for (std::ptrdiff_t k = 0; k < n; ++k) ++it;   // O(n)
}

Both branches are compiled only for the types that reach them, which is why the it += n does not break the list instantiation — the measured property from Chapter 18.8 §9.

Two cautions. First, do not write this: std::advance already exists and does exactly it. The value of knowing the pattern is reading library code and dispatching on properties that have no standard helper. Second, prefer constraining to adapting when the slow branch is a trap — a function that silently becomes O(n) on a list is worse than one that refuses to compile, which is §9's argument.

9. Constrain Rather Than Adapt

A corollary worth stating on its own, because it is a design decision this module makes repeatedly.

When an operation is O(1) for one category and O(n) for another, you have two options: write the adaptive version from §8, or require the fast category and refuse the rest. The library makes both choices in different places, deliberately.

std::distance and std::advance adapt, because they are explicitly utilities for writing category-generic code, and the caller who reaches for them has accepted that the cost depends on the argument.

std::sort constrains, because sorting through a bidirectional iterator would be quietly catastrophic — and the right answer for a list is a different algorithm, not the same algorithm slower.

std::list::operator[] does not exist at all, which is the most aggressive form of the same choice: Chapter 19.4 §7's argument that the syntax would hide the cost.

For your own code the test is whether the slow path is acceptable or merely possible. A function that works on any container but is linear instead of constant on some of them is fine when the caller can see that; it is a trap when the function looks like a cheap accessor. When in doubt, constrain, because a compile error is a conversation and a silent O(n²) is a production incident.

10. The Category Table

11. What to Actually Do

• Check the algorithm's category requirement before writing the call with four questions: does it go backwards, jump, compute a distance, or read the range twice?
• Use the member function when the container has one — l.sort(), m.find(), l.remove() — because it exists for a reason.
• Read iterator_traits<It>::iterator_category when you need to know, rather than guessing from the container.
• State requirements as the weakest category that suffices, so the hierarchy admits everything stronger.
• Use std::distance / std::advance / std::next instead of arithmetic in category-generic code.
• Copy a stream into a container before running anything that needs more than one pass.
• Prefer constraining to adapting when the slow path would be a trap rather than a visible cost.
• When a diagnostic starts inside a standard header, jump to the last "in instantiation of" note naming your file.
• Reach for a static_assert on the category in your own templates until you can use C++20 concepts.

12. Mistakes Worth Making Once

std::sort on a std::list. Four errors, 138 lines, none of them yours. The fix is l.sort().

Expecting std::deque to be contiguous because it is random access. Two different properties; Chapter 19.2 §4 measured the one it lacks.

Reading a stream range twice. Measured: the second read returned zero values and no error.

Calling std::distance in a loop condition on a bidirectional iterator. O(n) per call, so O(n²) overall, and it looks deliberate.

Writing it + 1 in a template. Compiles while you test on a vector, fails the day someone passes a list. std::next(it) always works.

Assuming an algorithm that compiles is an algorithm that is efficient. A category mismatch is a compile error; an algorithmic mismatch, like std::find on a std::map, compiles fine and is a linear scan where m.find is logarithmic.

Writing your own tag-dispatch version of std::advance. It exists. Learn the pattern, use the library.

13. Interview Relevance

The frozen curriculum marks this chapter High, and the sort-on-a-list question is a staple.

"Why can't you std::sort a std::list?" std::sort requires random-access iterators; a list provides bidirectional. The strong answer continues to why — sorting needs to jump to midpoints and compute distances in constant time — and notes that std::list::sort exists and relinks nodes rather than moving elements.

"Name the iterator categories." Input, output, forward, bidirectional, random access, plus contiguous in C++20. Saying they form a hierarchy, and that an algorithm states the weakest it needs, is the part that distinguishes a real answer.

"What makes a forward iterator different from an input iterator?" The multi-pass guarantee. An input iterator may consume its source; measured, re-reading a stream range returned zero values.

"What category does std::deque provide?" Random access — but not contiguous, which is a separate property it lacks.

"How would you write a function that is efficient for both a vector and a list?" Dispatch on iterator_traits, with if constexpr in C++17 or tag dispatch before it — and then volunteer that std::distance and std::advance already do this, and that constraining is often better than adapting.

"Why is the std::sort-on-a-list error so long?" Because the requirement is not stated in the signature, so the violation is discovered inside an instantiation and reported there. C++20 concepts move the check to the call site.

14. What You Should Be Able to Say Now

• The five categories, what each adds, and that C++20 adds contiguous.
• That the categories form a hierarchy, verified by is_base_of on the tag types, so the weakest stated requirement admits everything stronger.
• That the category is read from std::iterator_traits, not from documentation.
• That a raw pointer is random access and a std::deque is random access but not contiguous.
• That the category is a cost contract: measured over 30 samples, std::distance was flat at 0.00–1.30 ns (median 0.60) for a vector across a 16× size range — some readings below clock resolution — and 1.29–3.22 ns per element for a list.
• That an input iterator is single-pass, measured by a stream range yielding nothing on a second read.
• Why std::reverse works on a list and std::sort does not, and what the member sort does instead.
• That ignoring the requirement produced 4 errors across 138 lines, first reported inside make_heap.h.

15. Exercises

Exercise 1 — the table. Reproduce §2's category table and add std::string::iterator, std::unordered_map::iterator and std::ostream_iterator<int>. Predict each before running it.

Exercise 2 — the hierarchy. Write a static_assert for each of the three is_base_of relationships in §3, then write one that is false and read the error.

Exercise 3 — the shape. Reproduce §4's sweep. Extend it to std::deque and std::set and state which column each resembles.

Exercise 4 — single pass. Write a function template that counts a range twice and returns both counts. Call it with a vector and with a stream range, and explain the second result.

Exercise 5 — the boundary. For ten algorithms of your choosing, look up the required category and then try each on a std::forward_list. Tabulate which compile.

Exercise 6 — the diagnostic. Compile std::sort on a list and count the errors and lines on your platform. Then add a static_assert on the category in a wrapper and compare the output.

Exercise 7 — adapt. Implement §8's advanceBy and verify with a counting iterator that the list branch performs exactly n increments.

Exercise 8 — constrain instead. Rewrite advanceBy to refuse non-random-access iterators with a readable static_assert message, and argue in two sentences which version you would ship.

16. Summary

• Five categories — input, output, forward, bidirectional, random access — plus contiguous in C++20.
• Measured from iterator_traits: array/vector/deque/int* random access; list/map/set bidirectional; forward_list forward; istream_iterator input.
• They form a hierarchy, verified by is_base_of on the tags, so an algorithm requiring the weakest category accepts everything stronger.
• A category is also a COST contract. Measured over 30 samples: std::distance flat at 0.00–1.30 ns, median 0.60 for a vector across a 16× size range — several readings below clock resolution — and 1.29–3.22 ns per element, median 2.13 for a list, growing linearly in total. One call, two implementations, chosen by the tag.
• Measured: an input iterator is single-pass — re-reading the same stream range returned 0 values.
• std::reverse works on a list; std::sort does not — and measured, the attempt gave 4 errors across 138 diagnostic lines, the first inside make_heap.h, naming no line of mine but the call.
• Member functions exist where the generic algorithm cannot apply or can be beaten — l.sort() relinks nodes; m.find() is O(log n) where std::find is O(n).
• Prefer constraining to adapting when the slow path is a trap rather than a visible cost.
• A single timing of distance was meaningless — the vector's figure is below timer resolution, so the shape is the measurement, and a bimodal size was dropped rather than reported.

That is the contract between containers and algorithms fully stated: positions from Chapter 20.1, capabilities from this chapter, and an algorithm that declares what it needs. What has not yet been argued is why you should use those algorithms at all, when a hand-written loop is three lines and obviously correct. Chapter 20.4 makes that case, and makes it carefully, because the usual version of the argument — that the library is faster — turns out not to survive measurement. The real reasons are different and better, and one of them is the subject of Chapter 20.3: the loop you write by hand can contain a bug that the named algorithm structurally cannot, and that bug is undetectable by every tool on this machine.