Iterator
The <iterator> header provides iterator categories, traits, adaptors, stream iterators, and free functions that bridge containers and algorithms.
<iterator>since C++98The <iterator> header defines the category taxonomy, the iterator_traits type trait, adaptor types (reverse, insert, move, stream), and utility functions that let algorithms operate uniformly over any range — container, array, or stream — without coupling to a specific data structure.
Overview
Iterators are the glue between containers and algorithms. An algorithm accepts a half-open range [first, last) and operates through the iterator interface without knowing anything about the underlying data structure. The standard organises iterators into a capability hierarchy; algorithms specialise based on what an iterator can do — advance forward only, step backward, or jump by n in O(1).
#include <iterator> is needed explicitly for adaptors, stream iterators, and utility functions. Container and algorithm headers often pull it in transitively, but relying on that is fragile.
Iterator Categories
C++98 established five iterator categories. C++17 added a sixth (contiguous). C++20 restated the entire hierarchy as composable concepts. The ordering is strictly additive — each category subsumes the capabilities of the one above (output is a separate branch):
| Category | Key Operations | Representative Types |
|---|---|---|
| Input | ++it, *it (read, single-pass) | std::istream_iterator |
| Output | ++it, *it = v (write, single-pass) | std::ostream_iterator, back_inserter |
| Forward | Input + multi-pass + default-constructible | std::forward_list::iterator |
| Bidirectional | Forward + --it | std::list::iterator, std::map::iterator |
| Random Access | Bidirectional + it ± n, it[n], < ordering | std::vector::iterator, std::deque::iterator |
| Contiguous (C++17) | Random access + contiguous memory guarantee | std::vector::iterator, T* |
The contiguous category was formalised as std::contiguous_iterator_tag in C++17 and as the std::contiguous_iterator concept in C++20.
Iterator Traits
std::iterator_traits<Iter> exposes five member type aliases for any iterator or raw pointer:
typename std::iterator_traits<Iter>::value_type // element type
typename std::iterator_traits<Iter>::difference_type // signed distance (usually ptrdiff_t)
typename std::iterator_traits<Iter>::pointer // pointer to element
typename std::iterator_traits<Iter>::reference // reference to element
typename std::iterator_traits<Iter>::iterator_category // one of the _tag typesTag dispatch — routing overloads through the category tag — was the canonical C++98–17 technique for algorithm specialisation:
template<typename Iter>
typename std::iterator_traits<Iter>::difference_type
distance_impl(Iter first, Iter last, std::random_access_iterator_tag) {
return last - first; // O(1)
}
template<typename Iter>
typename std::iterator_traits<Iter>::difference_type
distance_impl(Iter first, Iter last, std::input_iterator_tag) {
typename std::iterator_traits<Iter>::difference_type n = 0;
while (first != last) { ++first; ++n; }
return n; // O(n)
}
template<typename Iter>
auto my_distance(Iter first, Iter last) {
return distance_impl(first, last,
typename std::iterator_traits<Iter>::iterator_category{});
}In C++17, iterator_traits became SFINAE-friendly — instantiating it for a non-iterator type yields an empty specialisation rather than a hard error.
C++20 Iterator Concepts
C++20 supersedes tag dispatch with named concepts declared in <iterator>. They express the same category hierarchy as constraints, giving dramatically better diagnostics:
#include <iterator>
// Only instantiated for qualifying iterators — C++20
template<std::random_access_iterator Iter>
void quicksort(Iter first, Iter last);
// Requires clause form — C++20
template<typename Iter>
requires std::bidirectional_iterator<Iter>
Iter find_last(Iter first, Iter last, const auto& value) {
Iter result = last;
for (auto it = first; it != last; ++it)
if (*it == value) result = it;
return result;
}The concept hierarchy: std::contiguous_iterator ⊃ std::random_access_iterator ⊃ std::bidirectional_iterator ⊃ std::forward_iterator ⊃ std::input_iterator. Foundational building-block concepts include std::weakly_incrementable, std::incrementable, std::sentinel_for, and std::sized_sentinel_for.
Iterator Adaptors
Insert Iterators
Insert iterators convert assignment-through-iterator into container insertion, letting output-only algorithms populate containers without pre-sizing them:
#include <iterator>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
std::vector<int> src{3, 1, 4, 1, 5, 9, 2, 6};
std::vector<int> positive;
std::deque<int> reversed;
std::set<int> unique_vals;
// Appends via push_back
std::copy_if(src.begin(), src.end(),
std::back_inserter(positive), [](int x){ return x > 0; });
// Prepends via push_front (std::deque and std::list only — not std::vector)
std::copy(src.begin(), src.end(), std::front_inserter(reversed));
// Inserts at an arbitrary position via insert()
std::copy(src.begin(), src.end(), std::inserter(unique_vals, unique_vals.begin()));Reverse Iterator
std::reverse_iterator<Iter> adapts any bidirectional iterator so that ++ moves backward. Containers expose rbegin()/rend() which return these wrappers:
std::vector<int> v{1, 2, 3, 4, 5};
// Equivalent to v.rbegin() / v.rend()
std::reverse_iterator rb(v.end());
std::reverse_iterator re(v.begin());
for (auto it = rb; it != re; ++it)
std::cout << *it << ' '; // 5 4 3 2 1*rb dereferences to *(rb.base() - 1), not *rb.base(). This offset is intentional — rend() must be a valid (non-dereferenceable) sentinel — but it causes persistent off-by-one errors when converting between forward and reverse iterator positions.
Move Iterator (C++11)
std::move_iterator wraps any iterator such that dereferencing yields an rvalue reference, enabling move semantics in copy-based algorithms:
#include <iterator>
#include <algorithm>
#include <vector>
#include <string>
std::vector<std::string> src{"alpha", "beta", "gamma"};
std::vector<std::string> dst;
dst.reserve(src.size());
// C++11: moves each element rather than copying
std::copy(std::make_move_iterator(src.begin()),
std::make_move_iterator(src.end()),
std::back_inserter(dst));
// src elements are now valid-but-unspecifiedStream Iterators
std::istream_iterator<T> reads successive values from a stream via operator>>; a default-constructed instance serves as the end-of-stream sentinel. std::ostream_iterator<T> writes to a stream with an optional delimiter:
#include <iterator>
#include <algorithm>
#include <vector>
#include <sstream>
#include <iostream>
std::istringstream ss{"3 1 4 1 5 9 2 6"};
// Parse all ints without an explicit loop
std::vector<int> data(
std::istream_iterator<int>{ss},
std::istream_iterator<int>{}
);
std::sort(data.begin(), data.end());
std::copy(data.begin(), data.end(),
std::ostream_iterator<int>{std::cout, " "});
// Output: 1 1 2 3 4 5 6 9Helper Functions
| Function | Since | Complexity |
|---|---|---|
std::advance(it, n) | C++98 | O(1) random access, O(n) otherwise |
std::distance(first, last) | C++98 | O(1) random access, O(n) otherwise |
std::next(it, n=1) | C++11 | Returns copy advanced by n |
std::prev(it, n=1) | C++11 | Returns copy decremented by n; requires bidirectional |
std::begin(c) / std::end(c) | C++11 | Works for arrays and containers uniformly |
std::cbegin(c) / std::cend(c) | C++14 | Const variants |
std::rbegin(c) / std::rend(c) | C++14 | Reverse variants |
std::size(c) / std::empty(c) / std::data(c) | C++17 | Also work for arrays and std::initializer_list |
Writing a Custom Iterator
Provide the five member type aliases; do not inherit from std::iterator<> (deprecated in C++17). In C++20, verify conformance with a static_assert:
#include <iterator>
#include <cstddef>
template<typename T>
class stride_iterator {
public:
using iterator_category = std::random_access_iterator_tag;
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using reference = T&;
stride_iterator(T* ptr, std::ptrdiff_t stride) : ptr_(ptr), stride_(stride) {}
reference operator*() const { return *ptr_; }
pointer operator->() const { return ptr_; }
reference operator[](difference_type n) const { return ptr_[n * stride_]; }
stride_iterator& operator++() { ptr_ += stride_; return *this; }
stride_iterator operator++(int) { auto t = *this; ++*this; return t; }
stride_iterator& operator--() { ptr_ -= stride_; return *this; }
stride_iterator operator--(int) { auto t = *this; --*this; return t; }
stride_iterator& operator+=(difference_type n) { ptr_ += n * stride_; return *this; }
stride_iterator& operator-=(difference_type n) { ptr_ -= n * stride_; return *this; }
friend stride_iterator operator+(stride_iterator it, difference_type n) { return it += n; }
friend stride_iterator operator+(difference_type n, stride_iterator it) { return it += n; }
friend stride_iterator operator-(stride_iterator it, difference_type n) { return it -= n; }
friend difference_type operator-(stride_iterator a, stride_iterator b) {
return (a.ptr_ - b.ptr_) / a.stride_;
}
bool operator==(const stride_iterator&) const = default; // C++20
auto operator<=>(const stride_iterator& o) const { // C++20
return ptr_ <=> o.ptr_;
}
private:
T* ptr_;
std::ptrdiff_t stride_;
};
static_assert(std::random_access_iterator<stride_iterator<int>>); // C++20Pre-C++20, validate by passing your type to std::sort or std::reverse in a unit test; there is no compile-time conformance check available.
Best Practices
- Constrain algorithms on the weakest iterator category that actually satisfies your needs. Accepting only
std::random_access_iteratorwhenstd::forward_iteratorwould do locks out valid inputs unnecessarily. - Prefer
std::next/std::prevover in-place++/--to avoid mutating an iterator you still need. - In C++20 code, constrain with iterator concepts rather than tag-based
std::enable_if— concepts compose naturally with ranges and produce cleaner error messages. - Never dereference
lastin a[first, last)range; it is a past-the-end sentinel, not a valid position. - Call
std::distanceon non-random-access ranges only when unavoidable — it is O(n) and easy to embed inside a loop accidentally.
Common Pitfalls
Reverse iterator off-by-one: *v.rbegin() is implemented as *(v.end() - 1), but rbegin().base() == v.end(). When converting a reverse iterator back to a forward position (e.g., to pass to an algorithm), you must subtract one from .base().
Iterator invalidation after mutation: Inserting into or erasing from std::vector or std::deque invalidates all iterators to that container. Storing iterators across mutations leads to undefined behaviour; re-obtain them after every structural change.
Forward-only containers and std::prev: std::forward_list and all unordered containers provide only forward iterators. Any code path that calls std::prev or uses rbegin()/rend() on them will fail to compile — the category mismatch is your signal to redesign the traversal.
Signed/unsigned mismatch: std::distance returns difference_type (a signed type). Comparing it against size_t or std::vector::size_type (unsigned) triggers mixed-sign warnings or silent wrap-around on underflow.
Iterator categories and concepts (C++20 ranges)
C++20 unified the category taxonomy into composable concepts that also work with ranges. The <iterator> header defines both the legacy _tag types and the new named concepts; the two systems interoperate through std::iterator_traits.
#include <iterator>
#include <ranges>
#include <vector>
#include <list>
// C++20 — concept hierarchy mirrors the tag hierarchy
static_assert(std::contiguous_iterator<int*>);
static_assert(std::random_access_iterator<std::vector<int>::iterator>);
static_assert(std::bidirectional_iterator<std::list<int>::iterator>);
// Ranges expose begin/end via std::ranges::begin / std::ranges::end,
// which also accept raw arrays and types with .begin() member functions.
void print_range(std::ranges::input_range auto const& r) { // C++20
for (auto const& v : r)
std::cout << v << ' ';
}The std::ranges::iterator_t<R> and std::ranges::sentinel_t<R> helpers extract the iterator and sentinel types from a range type — useful when writing generic range algorithms.
std::advance, std::next, std::prev
std::advance mutates in place; std::next/std::prev return a new copy and leave the original unchanged. Prefer std::next/std::prev whenever you need to keep the original iterator intact.
#include <iterator>
#include <list>
#include <vector>
std::list<int> lst{10, 20, 30, 40, 50};
auto it = lst.begin();
std::advance(it, 3); // C++98 — it now points at 40
auto it2 = std::next(it); // C++11 — it2 points at 50; it unchanged
auto it3 = std::prev(it2, 2); // C++11 — it3 points at 30; it2 unchanged
// std::next / std::prev with random-access iterators are O(1);
// with bidirectional iterators they are O(n).
std::vector<int> v{1, 2, 3, 4, 5};
auto last_valid = std::prev(v.end()); // points at 5std::advance with a negative n requires a bidirectional iterator; passing a negative count to an input or forward iterator is undefined behaviour.
Reverse iterators
std::reverse_iterator<Iter> adapts any bidirectional iterator so that prefix ++ steps backward through the sequence. It satisfies the same iterator category as the underlying iterator.
#include <iterator>
#include <vector>
#include <algorithm>
#include <iostream>
std::vector<int> v{1, 2, 3, 4, 5};
// Explicit construction — equivalent to v.rbegin() / v.rend()
auto rb = std::make_reverse_iterator(v.end()); // C++14
auto re = std::make_reverse_iterator(v.begin()); // C++14
for (auto it = rb; it != re; ++it)
std::cout << *it << ' '; // 5 4 3 2 1
// base() returns the underlying forward iterator — remember the offset:
// *rit == *(rit.base() - 1)
auto rfirst = v.rbegin();
std::cout << *rfirst; // 5
std::cout << *(rfirst.base() - 1); // also 5Converting a reverse iterator back to a forward position for use with erase or insert always requires rit.base(), but that position is one past the element *rit refers to — subtract one before passing to position-sensitive algorithms.
Insert iterators (back_inserter, front_inserter, inserter)
Insert iterators are output iterators that turn assignment into a container insertion call, eliminating the need to pre-size the destination. They are the standard way to populate a container from an algorithm that only writes through an output iterator.
#include <iterator>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <list>
std::vector<int> src{5, 3, 1, 4, 2};
// back_inserter — calls push_back; works with vector, deque, list, string
std::vector<int> dst_back;
std::copy(src.begin(), src.end(), std::back_inserter(dst_back));
// dst_back == {5, 3, 1, 4, 2}
// front_inserter — calls push_front; NOT available for std::vector
std::deque<int> dst_front;
std::copy(src.begin(), src.end(), std::front_inserter(dst_front));
// dst_front == {2, 4, 1, 3, 5} (insertion order reversed)
// inserter — calls insert(pos, value); works with any container with insert()
std::set<int> dst_set;
std::copy(src.begin(), src.end(),
std::inserter(dst_set, dst_set.begin()));
// dst_set == {1, 2, 3, 4, 5}
// Combine with transform to filter-and-convert in one pass
std::vector<std::string> words{"hello", "world", "cpp"};
std::vector<std::string> upper;
std::transform(words.begin(), words.end(), std::back_inserter(upper),
[](std::string s) {
for (auto& c : s) c = std::toupper(c);
return s;
});front_inserter calls push_front, so the resulting sequence is reversed relative to the source. Use std::back_inserter followed by std::reverse if preserving order matters.
Stream iterators
Stream iterators adapt standard iostreams to the iterator interface, enabling algorithms to read from or write to streams without explicit loop boilerplate. Both types live in <iterator>.
#include <iterator>
#include <algorithm>
#include <numeric>
#include <vector>
#include <sstream>
#include <iostream>
// istream_iterator<T> — reads via operator>>, default-constructed == EOF sentinel
std::istringstream ss{"10 20 30 40 50"};
std::vector<int> nums(std::istream_iterator<int>{ss},
std::istream_iterator<int>{});
// nums == {10, 20, 30, 40, 50}
int total = std::accumulate(nums.begin(), nums.end(), 0); // 150
// ostream_iterator<T> — writes via operator<< with optional delimiter
std::ostream_iterator<int> out{std::cout, ", "};
std::copy(nums.begin(), nums.end(), out);
// Output: 10, 20, 30, 40, 50,
// Read from stdin directly (press Ctrl-D / Ctrl-Z to end)
// std::vector<int> from_stdin(
// std::istream_iterator<int>{std::cin},
// std::istream_iterator<int>{});istream_iterator is a single-pass input iterator — it cannot be rewound. Read the stream into a container first if you need to traverse the data more than once.
Sentinel types (C++20)
C++20 decouples the type of the end-of-range sentinel from the type of the iterator, enabling zero-overhead termination conditions that are not representable as an iterator. The constraint std::sentinel_for<S, I> requires only that I and S are equality-comparable — they need not be the same type.
#include <iterator>
#include <ranges>
// A null-terminator sentinel for raw C strings — C++20
struct null_sentinel_t {
bool operator==(const char* p) const noexcept { return *p == '\0'; }
};
inline constexpr null_sentinel_t null_sentinel{};
static_assert(std::sentinel_for<null_sentinel_t, const char*>); // C++20
// Use with a raw char* iterator — no strlen needed
const char* str = "hello";
for (const char* it = str; it != null_sentinel; ++it)
std::cout << *it; // h e l l o
// std::default_sentinel_t — a universal sentinel tag used by ranges views
// and stream iterators; std::default_sentinel is the global instance.
auto sv = std::views::istream<int>(std::cin); // C++20
// sv.end() returns std::default_sentinel_t — distinct type from sv.begin()std::sized_sentinel_for<S, I> additionally requires operator-(sentinel, iterator) to return the distance in O(1), enabling std::ranges::distance to be O(1) for such pairs.
Iterator adaptors in ranges
C++20 <ranges> ships its own set of iterator adaptors as view types; they compose lazily and produce iterators that satisfy the appropriate concept. Unlike the <iterator> adaptors, range views carry their own begin/end and can be chained with |.
#include <ranges>
#include <vector>
#include <iostream>
std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8};
// views::reverse — bidirectional adaptor, no copy made // C++20
for (int x : v | std::views::reverse)
std::cout << x << ' '; // 8 7 6 5 4 3 2 1
// views::filter + views::transform — lazy composition // C++20
auto even_squares = v
| std::views::filter([](int x){ return x % 2 == 0; })
| std::views::transform([](int x){ return x * x; });
// Evaluated element-by-element only during iteration
// std::views::counted — creates a subrange of exactly n elements // C++20
auto first3 = std::views::counted(v.begin(), 3);
// first3 covers {1, 2, 3}
// std::ranges::subrange — explicit iterator + sentinel pair as a range // C++20
auto sub = std::ranges::subrange(v.begin() + 2, v.begin() + 6);
// sub covers {3, 4, 5, 6}Range adaptors are the idiomatic C++20 replacement for raw iterator arithmetic in algorithm calls. They interoperate with legacy [first, last) algorithms via std::ranges::begin / std::ranges::end.
See Also
<ranges>— C++20 composable views that generalise iterator pairs<algorithm>— standard algorithms consuming iterator ranges<numeric>— numeric algorithms (std::accumulate,std::partial_sum,std::inclusive_scan) over iterator ranges