skip to content

Why does std::sort not compile on a std::list in C++, and what do iterator categories have to do with it?

level: middleimportance: should knowfreq 52%

answer

  1. what can it + n do
  2. list iterators step one at a time
  3. the member function sorts nodes
  4. C++20 concepts name the failure

basics

~10 s

std::sort needs random access iterators, which jump and subtract in constant time; std::list iterators are only bidirectional. Call the member list::sort() instead, which relinks nodes, keeps iterators valid and is stable.

solid answer

~40 s

Iterator categories describe which operations an iterator supports, and therefore which algorithms may use it: input and output (single pass), forward (multi-pass), bidirectional (adds `--`), random access (adds `it + n`, `it2 - it1` and `<` in constant time), and since C++20 contiguous (elements adjacent in memory). `std::sort` requires random access iterators because its partitioning jumps around the range. `std::list` iterators are bidirectional, so the call fails deep in the library: libc++ reports `invalid operands to binary expression`. C++20's `std::ranges::sort` is constrained with `std::random_access_iterator`, so the diagnostic names the unmet concept instead. The fix is `list::sort()`, a member that relinks nodes, keeps every iterator valid and is stable.

code

cpp · 7 lines
cpp
#include <algorithm>
#include <list>

int main() {
    std::list<int> ratings{4, 1, 3};
    std::ranges::sort(ratings);
}

go deeper

for a junior

Recall that std::sort needs random access iterators and that std::list provides its own sort() member function.

for a middle

Name the categories in order and the operation each adds, map the standard containers onto them, and explain how algorithms such as std::distance choose a faster path by category.

for a senior

Read a concept-based diagnostic quickly, and choose algorithms and containers by the category they need, for example list::sort to keep iterators valid or std::vector plus sort for cache-friendly bulk sorting.

for a principal

Decide whether new generic code in a team is constrained with C++20 iterator concepts so callers get readable errors, and how far to keep supporting the legacy iterator tags.

## What an iterator category promises An **iterator category** is a contract about which operations an iterator supports and how cheaply. Generic algorithms are written against these contracts rather than against containers, so the category of a container's iterators decides which algorithms accept it. The categories form a hierarchy, each adding to the one before: | category | adds | typical source | |---|---|---| | input | read `*it`, `++it`; a single pass | `std::istream_iterator` | | output | write `*it = x`, `++it`; a single pass | `std::back_insert_iterator` | | forward | multi-pass: copies can revisit elements | `std::forward_list`; the hash containers guarantee at least this | | bidirectional | `--it` | `std::list`, `std::map`, `std::set` | | random access | `it + n`, `it2 - it1`, `it[n]`, `<`, all in constant time | `std::deque` | | contiguous (C++20) | elements adjacent in memory | `std::vector`, `std::array`, `std::string` | Output iterators sit beside the input-to-contiguous chain rather than in it. Every random access iterator is also bidirectional, every bidirectional one is forward, and so on. ## Why std::sort rejects std::list `std::sort` requires **random access iterators**. Common implementations, including the introsort in libc++ and libstdc++, partition around pivots chosen by position and jump directly to the middle of a range, which needs `first + (last - first) / 2` in constant time. A linked list can only reach the n-th node by following n links, so `std::list<T>::iterator` is **bidirectional**: `++` and `--`, nothing more. What the compiler says depends on how the algorithm is declared: - **Classic `std::sort(first, last)`** names its template parameter `RandomAccessIterator`, but that name is only a convention: the classic overload is not constrained, even in C++20. The template is instantiated anyway and fails deep inside the implementation. Apple clang with libc++ reports `invalid operands to binary expression ('std::__list_iterator<int, void *>' and 'std::__list_iterator<int, void *>')` from several internal headers. - **C++20 `std::ranges::sort(range)`** is **constrained** on `std::random_access_range`. The call is rejected at the call site, and libc++ explains: `'std::list<int> &' does not satisfy 'random_access_range'`, followed by the iterator failing `random_access_iterator`. ## The right way to sort a list `std::list` provides a member `sort()`, and an overload taking a comparator. The standard specifies approximately N log N comparisons, requires it to be **stable** (equal elements keep their order), and says it does not affect the validity of iterators and references: it relinks nodes instead of moving values. `std::forward_list` has its own `sort()` member for the same reason. Other node-specific members follow the pattern, such as `merge`, `splice`, `remove_if` and `unique`. If the data is sorted often and nothing needs stable iterators, a `std::vector` plus `std::sort` is usually faster in practice because of its contiguous layout. ## Categories decide complexity, not only legality Some utilities accept every category but choose a faster path for stronger ones: - `std::distance(first, last)` computes `last - first` for random access iterators and walks step by step otherwise. - `std::advance(it, n)` and `std::next(it, n)` jump directly or loop n times. - `std::reverse` needs bidirectional iterators, and `std::binary_search` and `std::lower_bound` accept forward iterators but take linear steps to reach the middle when the iterators are not random access. Code that calls `std::distance` on list iterators inside a loop is quietly quadratic. ## Tags and concepts: two ways to ask Before C++20, code asked for the category through `std::iterator_traits<I>::iterator_category`, which names one of the tag types `input_iterator_tag`, `output_iterator_tag`, `forward_iterator_tag`, `bidirectional_iterator_tag` or `random_access_iterator_tag`, and dispatched on it with overloads. C++20 added the **iterator concepts**: `std::input_iterator`, `std::forward_iterator`, `std::bidirectional_iterator`, `std::random_access_iterator` and `std::contiguous_iterator`, plus a `contiguous_iterator_tag`. Generic code constrains a template with them directly. The legacy tag of a vector iterator is still `random_access_iterator_tag`, so older code keeps working, while the concept `std::contiguous_iterator` is satisfied; libc++ signals this through a separate `iterator_concept` member. Code that needs contiguity, such as a function handing a pointer to a C API, should test the concept. ## Map of the standard containers 1. `std::vector`, `std::array`, `std::string`: contiguous. 2. `std::deque`: random access but not contiguous, since its elements live in separate blocks. 3. `std::list`, `std::map`, `std::set` and their multi variants: bidirectional. 4. `std::forward_list`: forward only. The unordered containers are guaranteed only forward iterators ("at least" forward in the standard's words; libc++ provides exactly that), so portable code never applies `--` to them. Knowing this table answers most "why does this algorithm not compile with that container" questions before the compiler does.

  • How does std::distance behave differently on a vector and on a list?
    `std::distance` adapts to the category: for random access iterators it computes `last - first` in constant time, for weaker categories it increments `first` until it reaches `last`, which is linear. The same holds for `std::advance` and `std::next`. Code that calls `std::distance` on list iterators inside a loop can quietly become quadratic.
  • What category does std::vector<int>::iterator report in C++20?
    Two answers coexist. `iterator_traits<...>::iterator_category` is still `random_access_iterator_tag`, so pre-C++20 code is unaffected, while the C++20 concept `std::contiguous_iterator` is satisfied. libc++ exposes this through `iterator_concept = contiguous_iterator_tag` on its vector iterator. Code wanting contiguity should test the concept, not the tag.

  • Says std::sort fails on list because list elements are not comparable
  • Thinks std::list has no way to sort itself
  • Believes std::deque iterators are contiguous like vector iterators
  • Relies on --it working on std::unordered_map iterators
  • Says std::advance on a list iterator is constant time

Assumes C++20 for std::contiguous_iterator, the iterator concepts and std::ranges::sort; the classic iterator categories and std::sort predate C++11.