Skip to content
Tutorials Center
My learning

Topics

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.

C++
#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

C++ Reading the category of a container

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.

C++ Why the category matters

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::rotate or std::search) need forward iterators.
  • std::vector<bool> iterators are random access but not contiguous, because the elements are bits packed into words.
  • std::deque iterators 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) and iterator_category or iterator_concept.
  • Unordered containers have forward iterators only, and the traversal order is unspecified.