Not every iterator can do everything. A std::list iterator cannot jump five positions in one step, because a list has no way to find the fifth element without walking to it.

The standard library organises this into categories, and an algorithm states which one it needs.

The five categories

Each category adds capabilities to the one before it:

| Category | Adds | Example | |---|---|---| | Input | read once, forward only | std::istream_iterator | | Output | write once, forward only | std::back_insert_iterator | | Forward | read repeatedly, multi-pass | std::forward_list | | Bidirectional | --it | std::list, std::map, std::set | | Random access | it + n, it[n], it1 < it2 | std::vector, std::deque, std::array, T* |

C++20 adds contiguous, a refinement of random access guaranteeing the elements are adjacent in memory — true for vector and array, but not deque.

Each is a superset of the previous, so a random-access iterator satisfies every requirement above it. An algorithm asking for a forward iterator happily accepts a std::vector's.

Reading the category from a type

#include <forward_list>
#include <iostream>
#include <iterator>
#include <list>
#include <vector>

template <typename It>
void report() {
    using Cat = typename std::iterator_traits<It>::iterator_category;
    if constexpr (std::is_same_v<Cat, std::random_access_iterator_tag>) {
        std::cout << "random access\n";
    } else if constexpr (std::is_same_v<Cat, std::bidirectional_iterator_tag>) {
        std::cout << "bidirectional\n";
    } else if constexpr (std::is_same_v<Cat, std::forward_iterator_tag>) {
        std::cout << "forward\n";
    } else if constexpr (std::is_same_v<Cat, std::input_iterator_tag>) {
        std::cout << "input\n";
    }
}

int main() {
    std::cout << "vector:       "; report<std::vector<int>::iterator>();
    std::cout << "list:         "; report<std::list<int>::iterator>();
    std::cout << "forward_list: "; report<std::forward_list<int>::iterator>();
    std::cout << "int*:         "; report<int*>();
    std::cout << "istream_iterator: "; report<std::istream_iterator<int>>();
    return 0;
}

vector:       random access
list:         bidirectional
forward_list: forward
int*:         random access
istream_iterator: input

std::iterator_traits<It>::iterator_category is a tag type — an empty struct whose only job is to identify the category. Algorithms dispatch on it: std::advance has one implementation for random access and another for everything else, selected at compile time by the tag.

This is the specialization pattern from lesson 12.4 doing real work in the standard library.

Why the categories are not arbitrary

They correspond to what the data structure can physically do.

std::vector stores elements contiguously, so element n is at base + n * sizeof(T). Jumping is one multiply and one add — random access.

std::list is nodes connected by pointers. Element n can only be reached by following n pointers. Jumping is possible but costs O(n), so it is deliberately not offered — the category system refuses to let you write code whose cost is invisible.

std::forward_list has only a next pointer, so it cannot go backwards at all. Forward.

std::istream_iterator reads from a stream. Once a value is consumed it is gone; you cannot go back and you cannot read the same position twice. Input.

That last one is why input iterators are called single-pass. An algorithm that walks a range twice is silently wrong on an input iterator, so the category system forbids it at compile time.

What it costs, measured

std::advance(it, n) works on any category. Its cost does not:

#include <chrono>
#include <iostream>
#include <iterator>
#include <list>
#include <vector>

int main() {
    const int N = 200000;
    std::vector<int> v(N, 1);
    std::list<int> l(N, 1);

    // std::advance and std::distance work on any category, but their cost
    // depends on it: O(1) for random access, O(n) otherwise.
    auto t0 = std::chrono::steady_clock::now();
    auto vit = v.begin();
    std::advance(vit, N - 1);
    auto t1 = std::chrono::steady_clock::now();

    auto lit = l.begin();
    std::advance(lit, N - 1);
    auto t2 = std::chrono::steady_clock::now();

    auto vus = std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count();
    auto lus = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();

    std::cout << "vector advance: " << vus << " us\n";
    std::cout << "list advance:   " << lus << " us\n";
    std::cout << "both landed on: " << *vit << " and " << *lit << "\n";
    return 0;
}

Timings vary between runs and machines, so treat the exact numbers as indicative. Three consecutive runs of that program, compiled -O2:

vector advance: 0 us     list advance: 888 us
vector advance: 0 us     list advance: 1168 us
vector advance: 0 us     list advance: 861 us

The vector's advance is below the clock's resolution — it is a single pointer addition. The list's takes roughly a millisecond, because it follows 199,999 pointers.

Same call, same result, wildly different cost. The category is the compiler's way of telling you which you are getting.

Which algorithms need what

// std::find, std::copy, std::for_each      — input iterators
// std::replace, std::fill                  — forward iterators
// std::reverse, std::rotate                — bidirectional iterators
// std::sort, std::nth_element,
// std::binary_search, std::random_shuffle  — RANDOM ACCESS iterators

The last line is the one that bites. std::sort requires random access, so:

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

The error is the wall of text from lesson 12.8, because std::sort is not constrained by a concept in the classic version.

std::list provides its own member sort() instead, which relinks the nodes rather than moving the elements:

// l.sort();                          // fine — O(n log n) by relinking pointers

That is a general pattern: when a container offers a member function with the same name as an algorithm (sort, remove, unique, merge, reverse), the member exists because it can do the job better, and you should prefer it.

Where the categories show up in your own templates

Constrain by category rather than by container, and your function works on everything that can support it:

// C++20 concepts, from <iterator>:
//
//   template <std::input_iterator It>
//   auto count_of(It first, It last);
//
//   template <std::random_access_iterator It>
//   void quicksort(It first, It last);
//
// The second one rejects a std::list at the call site with a readable
// message, rather than failing deep inside the body.

This is the same argument as lesson 12.7, applied to the library's own vocabulary.

Try it

Checkpoint

• Iterators come in categories: input, output, forward, bidirectional, random access, contiguous.
• Each category is a superset of the previous, expressed by tag types that inherit from each other.
• The category reflects what the data structure can physically do, not an arbitrary label.
• std::iterator_traits<It>::iterator_category gives the tag; algorithms dispatch on it.
• vector and T* are random access; list and map are bidirectional; forward_list is forward.
• std::istream_iterator is input — single-pass, so an algorithm cannot walk it twice.
• std::advance works on all of them; it is O(1) on random access and O(n) otherwise.
• std::sort needs random access, so it does not compile for std::list — use l.sort().
• When a container has a member with an algorithm's name, the member is there because it is better.
• Constrain your own templates by category (std::random_access_iterator), not by container.