C++ Reference ยท Containers
C++ iterator categories
Reference for the C++ iterator categories: input, output, forward, bidirectional, random access and contiguous, what each allows and how algorithms use them.
An iterator is any object that can point into a sequence and move through it. C++ sorts iterators into categories according to the operations they support. The category tells an algorithm how much it can do: a single pass, a walk in both directions, or jumping to any position in constant time. Algorithms such as std::sort require a stronger category than std::find, and the compiler reports an error if you hand them a weaker iterator.
The categories form a hierarchy. Each one supports everything the previous one does and more: input, forward, bidirectional, random access, contiguous (C++20), plus output iterators on a separate branch. Pointers are the strongest iterators of all, which is why algorithms work on plain arrays.
#include <iterator> using Cat = std::iterator_traits<std::vector<int>::iterator>::iterator_category;
The categories
| Category | Adds | Typical sources |
|---|---|---|
| Input | Single-pass read with *it, ++it, == |
std::istream_iterator |
| Output | Single-pass write with *it = x, ++it |
std::back_inserter, std::ostream_iterator |
| Forward | Multi-pass: copies stay valid, can re-read | std::forward_list, std::unordered_set |
| Bidirectional | --it |
std::list, std::set, std::map |
| Random access | it + n, it[n], it - it, < |
std::deque, std::vector, std::array, pointers |
| Contiguous (C++20) | Elements adjacent in memory (std::to_address works) |
std::vector, std::array, std::string, pointers |
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
How algorithms use categories
Standard algorithms are specified by the weakest category they need, and many pick a faster implementation when the category allows it. std::distance and std::advance take O(1) steps for random access iterators and O(n) steps for the others. std::sort needs random access; std::list therefore has its own sort member. std::reverse needs bidirectional iterators; std::find needs only input iterators.
Since C++20 the same ideas are expressed as concepts: std::input_iterator, std::forward_iterator, std::bidirectional_iterator, std::random_access_iterator and std::contiguous_iterator. These describe what the iterator can do. The older iterator_category tag types still exist, but for a few iterators the two disagree (for example, a proxy-returning iterator may be an input iterator by the old tag and a stronger one by the concept), so constrained code should use the concepts.
Usage notes
- Input and output iterators are single-pass. After incrementing a copy, the old copy may be invalid. Algorithms that need to traverse twice (such as
std::rotateorstd::search) need forward iterators. std::vector<bool>iterators are random access but not contiguous, because the elements are bits packed into words.std::dequeiterators are random access but not contiguous: the elements are stored in blocks.- Sentinels (C++20): a range's end can be a different type than its begin if the two are comparable; the iterator concepts only constrain the beginning iterator.
- Writing your own iterator: provide
value_type,difference_type,reference,pointer(or the C++20 equivalents) anditerator_categoryoriterator_concept. - Unordered containers have forward iterators only, and the traversal order is unspecified.
Related
- Iterators, Iterator invalidation,
std::vector,std::list, Range-basedfor - Lessons: Iterators, Ranges