C++ / ITERATORS, ALGORITHMS, AND RANGES
Iterators and their categories
Tell input, forward, bidirectional, random access and contiguous iterators apart, and pick the weakest category your own algorithm needs.
What you will learn
- Name what each iterator category adds: multi-pass, --, it + n, a raw pointer
- Read a category from std::iterator_traits or test it with C++20 iterator concepts
- Predict whether std::advance and std::distance cost O(1) or O(n)
- Constrain your own templates on the weakest category that still works
Understanding Iterators and their categories
An iterator's type says what you get when you dereference it; its category says what else you are allowed to do with it. C++ defines a ladder: input and output iterators support one pass with *it and ++it; forward iterators add the multi-pass guarantee, so a saved copy walks the same elements again; bidirectional iterators add --it; random access iterators add it + n, it2 - it1 and it[n] in constant time; contiguous iterators (C++20) add the promise that elements sit in one unbroken block, so std::to_address(it) yields a pointer valid across the range. Each rung includes everything below it, which is why the tag types actually inherit: std::random_access_iterator_tag derives from std::bidirectional_iterator_tag, which derives from std::forward_iterator_tag.
The categories are not levels of generosity, they are the most a given memory layout can honestly promise. A singly linked node knows only its successor, so std::forward_list hands out forward iterators; a doubly linked node knows both neighbours, so std::list hands out bidirectional ones; a vector iterator is an offset into a single array, so skipping n elements is one addition. std::istream_iterator is single-pass for a sharper reason: incrementing it consumes characters from the stream, so two copies share one hidden position and there is nothing behind them to revisit.
Algorithms publish the category they need, and that is why some calls simply refuse to compile: std::find needs only input iterators, std::reverse needs bidirectional because it walks in from both ends, and std::sort needs random access because picking a midpoint and jumping to it must be cheap. Before C++20 the requirement is carried as a tag in std::iterator_traits<It>::iterator_category and selected with overloads; since C++20 you can name it directly with concepts such as std::forward_iterator<It>. The same hierarchy encodes cost, so std::distance and std::advance are O(1) on random access iterators and O(n) otherwise, and std::distance(l.begin(), it) inside a loop over a std::list quietly makes a linear pass quadratic.
<forward_list>
<iostream>
<iterator>
<list>
<type_traits>
<vector>
template <class It>
const char* category_name() {
using C = typename std::iterator_traits<It>::iterator_category;
if constexpr (std::is_base_of_v<std::random_access_iterator_tag, C>)
return "random access";
else if constexpr (std::is_base_of_v<std::bidirectional_iterator_tag, C>)
return "bidirectional";
else if constexpr (std::is_base_of_v<std::forward_iterator_tag, C>)
return "forward";
else
return "input";
}
int main() {
std::vector<int> v{1, 2, 3, 4, 5};
std::list<int> l{1, 2, 3, 4, 5};
std::forward_list<int> f{1, 2, 3, 4, 5};
std::cout << "vector: " << category_name<std::vector<int>::iterator>() << '\n';
std::cout << "list: " << category_name<std::list<int>::iterator>() << '\n';
std::cout << "forward_list: " << category_name<std::forward_list<int>::iterator>() << '\n';
std::cout << "istream: " << category_name<std::istream_iterator<int>>() << '\n';
auto vi = v.begin() + 3; // one addition: vector iterators are random access
auto li = l.begin();
std::advance(li, 3); // three ++ steps: list iterators are not
std::cout << "fourth: " << *vi << ' ' << *li << '\n';
std::cout << "length: " << std::distance(f.begin(), f.end()) << '\n';
}
An iterator's category is a contract about which operations are valid and what they cost, and that contract, not the container it came from, decides which algorithms compile.
Worked examples
Single pass means single pass
Shows that advancing an istream_iterator consumes the stream, so the range cannot be walked twice.
<algorithm>
<iostream>
<iterator>
<sstream>
int main() {
std::istringstream in("10 20 30 40");
std::istream_iterator<int> first(in), last;
auto hit = std::find(first, last, 20);
std::cout << "found: " << *hit << '\n';
std::cout << "left over:";
for (std::istream_iterator<int> it(in); it != last; ++it)
std::cout << ' ' << *it;
std::cout << '\n';
}
Example explained
Line 1std::istream_iterator<int> first(in) extracts one int immediately, so the iterator always caches a value it has already read.
Line 2std::find works on its own copy of first, and every ++ inside it pulls the next int out of in, a side effect on the stream rather than on the copy.
Line 3By the time find returns, 10 and 20 are gone, so a fresh iterator over the same stream starts at 30.
Line 4first is now a stale copy whose cached 10 no longer matches the stream position; that unrepeatable traversal is exactly what the input category refuses to guarantee.
One function, two strategies
Uses if constexpr on iterator concepts so the same skip function jumps for vector and walks for forward_list.
<algorithm>
<cstddef>
<forward_list>
<iostream>
<iterator>
<vector>
template <std::input_iterator It>
It skip(It first, It last, std::ptrdiff_t n) {
if constexpr (std::random_access_iterator<It>) {
std::cout << "jump ";
return first + std::min(n, last - first);
} else {
std::cout << "walk ";
while (n-- > 0 && first != last) ++first;
return first;
}
}
int main() {
std::vector<int> v{10, 20, 30, 40, 50};
std::forward_list<int> f{10, 20, 30, 40, 50};
std::cout << *skip(v.begin(), v.end(), 3) << '\n';
std::cout << *skip(f.begin(), f.end(), 3) << '\n';
}
Example explained
Line 1template <std::input_iterator It> is the floor: the function needs only *it and ++it to be meaningful at all.
Line 2if constexpr (std::random_access_iterator<It>) is decided at compile time, so first + n and last - first are never instantiated for the forward_list iterator and cause no error.
Line 3The walk branch has to count steps by hand because a forward iterator offers no subtraction and no way to clamp n against the end in one operation.
Line 4Both calls land on 40, but the vector version costs one addition while the forward_list version costs three node hops, which is the practical meaning of the category difference.
Random access is not contiguity
Compares vector and deque iterators to show that constant-time jumps do not imply one block of memory.
<deque>
<iostream>
<iterator>
<memory>
<vector>
int main() {
std::vector<int> v{7, 8, 9};
std::deque<int> d{7, 8, 9};
std::cout << std::boolalpha;
std::cout << "vector random access: " << std::random_access_iterator<std::vector<int>::iterator> << '\n';
std::cout << "vector contiguous: " << std::contiguous_iterator<std::vector<int>::iterator> << '\n';
std::cout << "deque random access: " << std::random_access_iterator<std::deque<int>::iterator> << '\n';
std::cout << "deque contiguous: " << std::contiguous_iterator<std::deque<int>::iterator> << '\n';
int* p = std::to_address(v.begin());
std::cout << "through the pointer: " << p[0] << ' ' << p[1] << ' ' << p[2] << '\n';
}
Example explained
Line 1A concept name used in an expression is just a bool, so std::random_access_iterator<It> can be streamed directly.
Line 2The deque iterator answers true for random access because it can compute a chunk plus an offset in constant time, and false for contiguous because its chunks are separate allocations.
Line 3std::to_address(v.begin()) hands back the int* behind the iterator; the contiguous_iterator concept is precisely the promise that this pointer covers the whole range.
Line 4The same trick spelled &*d.begin() would compile for the deque, but indexing past the end of the first chunk reads unrelated memory.
Important notes
Random access and contiguous are different promises: std::deque jumps in constant time, yet a pointer taken from &*d.begin() is valid only for that single element, not for the range.
The concept spellings (std::forward_iterator, std::contiguous_iterator) need C++20; in older code the same information is the tag in std::iterator_traits, and note that vector's iterator_category still reads random_access_iterator_tag even though the iterator models contiguous_iterator.
Common mistakes
Writing it + 2 or end - begin on a std::list, std::set or std::map iterator: those are bidirectional, so the code fails with a wall of template errors, and the std::next(it, 2) or std::distance replacement compiles but silently costs O(n).
Calling std::sort(l.begin(), l.end()) on a std::list: sort requires random access to compute midpoints, so it cannot compile no matter how the elements are stored; the member function l.sort() exists exactly because of this.
Treating an istream_iterator range as if it could be scanned twice, for example counting elements and then averaging them: the second pass sees only the leftovers, and nothing in the compiler warns you because both passes only use ++ and *.
Try it yourself
Change, predict, then run
Write template <class It> It middle(It first, It last) that returns an iterator to the middle element, using first + (last - first) / 2 under if constexpr (std::random_access_iterator<It>) and a slow/fast two-iterator walk otherwise. Print the middle value of a 7-element std::vector<int> and a 7-element std::forward_list<int> with the same call.
Open the C++ workspaceCheck your understanding
A function template only ever uses *it and ++it, but it saves a copy of first and traverses the range a second time from that copy. What is the weakest iterator category it can correctly accept?
- input iterator
- output iterator
- forward iterator
- bidirectional iterator
Show answer
The second traversal needs the multi-pass guarantee, and that guarantee is what forward iterators add over input iterators. Answering input is tempting because * and ++ are the only operations used, but with an input iterator such as std::istream_iterator the saved copy shares a consumed position and the second pass reads different elements or nothing at all. Bidirectional would work, yet it demands -- that the function never calls and would needlessly reject std::forward_list.