C++ Iterators

  • Description: A note on iterator categories, std::iterator_traits, common iterator operations, iterator adaptors, writing custom iterators, C++20 iterator concepts, and iterator invalidation
  • My Notion Note ID: K2A-B1-12
  • Created: 2018-10-10
  • Updated: 2026-02-28
  • License: Reuse is very welcome. Please credit Yu Zhang and link back to the original on yuzhang.io

Table of Contents

1. Iterator Categories

Iterators are classified by what operations they support. Each category subsumes all operations of weaker categories.

Category What you can do Example
Input Read once, advance forward std::istream_iterator
Output Write once, advance forward std::ostream_iterator, std::back_inserter
Forward Read/write, advance forward, multi-pass std::forward_list::iterator
Bidirectional + go backward std::list, std::map, std::set iterators
Random access + jump by N, compare with <, +/- std::deque iterators
Contiguous (C++20) Random access + addresses are contiguous in memory std::vector, std::array, raw arrays

The hierarchy:

       Input  ──────► Forward ──► Bidirectional ──► Random access ──► Contiguous
       Output                                                              ▲
                                                                           │
                                                              std::vector iterator

A function template can require a particular category:

template <typename It>
void example(It first, It last) {
    // For input iterators: only one pass through [first, last)
    // For random access: can use first[i], first + n, last - first
}

Algorithms that need backward iteration (std::reverse) require bidirectional; ones that need O(1) distance computation (std::sort) require random access.

2. std::iterator_traits

std::iterator_traits<It> (<iterator>) exposes type metadata about an iterator:

#include <iterator>

using It = std::vector<int>::iterator;

std::iterator_traits<It>::value_type;        // int
std::iterator_traits<It>::reference;         // int&
std::iterator_traits<It>::pointer;           // int*
std::iterator_traits<It>::difference_type;   // ptrdiff_t (for it1 - it2)
std::iterator_traits<It>::iterator_category; // std::random_access_iterator_tag

Generic algorithms use iterator_traits to access these types without knowing the concrete iterator type:

template <typename It>
typename std::iterator_traits<It>::value_type
sum(It first, It last) {
    typename std::iterator_traits<It>::value_type total{};
    for (; first != last; ++first) total += *first;
    return total;
}

In C++20+, concepts (std::input_iterator, etc.) make these requirements much cleaner — see § 6.

3. Common Iterator Operations

#include <iterator>

std::vector<int> v = {1, 2, 3, 4, 5};
auto it = v.begin();

++it;           // advance one
*it;            // dereference (returns reference to element)
it->member;     // member access (for class types)
it1 == it2;     // equality
it2 - it1;      // distance (random-access only)

// Generic forms (work on any iterator category):
std::advance(it, 3);              // advance by 3 (uses += for RA, loops for input)
auto next_it = std::next(it, 2);  // = it + 2 for RA, multi-step for others
auto prev_it = std::prev(it);     // bidirectional or RA
auto d = std::distance(it1, it2); // it2 - it1 for RA, count for others

// Insertion-style "iterators" don't really iterate; they consume writes
auto out = std::back_inserter(v);
*out++ = 99;     // calls v.push_back(99)

std::next/std::prev/std::advance/std::distance work on any iterator category and pick the most efficient implementation based on iterator_category.

4. Iterator Adaptors

<iterator> provides adaptors that turn one kind of iterator into another.

Adaptor Effect
std::back_inserter(c) Output iterator that calls c.push_back(x)
std::front_inserter(c) c.push_front(x)
std::inserter(c, pos) c.insert(pos, x)
std::reverse_iterator Walks backward (vector::rbegin/rend)
std::move_iterator Dereferences as rvalue (move instead of copy)
std::istream_iterator<T>(stream) Reads Ts from a stream
std::ostream_iterator<T>(stream, sep) Writes Ts with a separator 
// Copy from input stream into a vector
std::vector<int> v;
std::copy(std::istream_iterator<int>{std::cin},
          std::istream_iterator<int>{},      // sentinel for EOF
          std::back_inserter(v));

// Print a vector with a separator
std::copy(v.begin(), v.end(),
          std::ostream_iterator<int>{std::cout, ", "});

// Move elements out of a source vector
std::vector<std::string> dst;
std::copy(std::make_move_iterator(src.begin()),
          std::make_move_iterator(src.end()),
          std::back_inserter(dst));

Adaptors let you reuse generic algorithms for I/O, container insertion, and reverse traversal without writing custom loops.

5. Writing a Custom Iterator

A minimal random-access iterator over a contiguous buffer:

#include <iterator>
#include <cstddef>

template <typename T>
class MyIter {
public:
    using value_type        = T;
    using reference         = T&;
    using pointer           = T*;
    using difference_type   = std::ptrdiff_t;
    using iterator_category = std::random_access_iterator_tag;

    MyIter(T* p) : p_(p) {}

    reference operator*()  const { return *p_; }
    pointer   operator->() const { return  p_; }

    MyIter& operator++()    { ++p_; return *this; }
    MyIter  operator++(int) { auto t = *this; ++p_; return t; }
    MyIter& operator--()    { --p_; return *this; }
    MyIter  operator--(int) { auto t = *this; --p_; return t; }

    MyIter& operator+=(difference_type n) { p_ += n; return *this; }
    MyIter& operator-=(difference_type n) { p_ -= n; return *this; }
    MyIter  operator+ (difference_type n) const { return MyIter(p_ + n); }
    MyIter  operator- (difference_type n) const { return MyIter(p_ - n); }
    difference_type operator-(MyIter o)   const { return p_ - o.p_; }

    reference operator[](difference_type n) const { return p_[n]; }

    auto operator<=>(const MyIter&) const = default;   // C++20: all comparisons

private:
    T* p_;
};

In C++20, std::ranges::iterator_t<R> + concepts give you cleaner constraints when consuming custom iterators. For producing iterators in modern code, std::generator<T> (C++23 coroutines) is often easier than writing the iterator class by hand.

6. Iterator Concepts (C++20)

C++20 added named concepts that capture each iterator category. These give better error messages and cleaner template constraints.

Concept Replaces
std::input_or_output_iterator Base of all iterators
std::input_iterator Input category
std::output_iterator<T> Output category writing T
std::forward_iterator Forward category
std::bidirectional_iterator Bidirectional category
std::random_access_iterator Random-access category
std::contiguous_iterator Contiguous category
std::sentinel_for<I> Sentinel that terminates iteration of I 
template <std::random_access_iterator It>
void quicksort(It first, It last);

template <std::input_iterator It, std::sentinel_for<It> Sent>
auto count_until(It first, Sent last);

In C++20+ ranges, sentinels (the "end" position) need not be the same type as the iterator — std::ranges::range uses a (begin, sentinel) pair, allowing iterations like "until null terminator" or "until predicate" without dummy "past-the-end" iterators.

7. Iterator Invalidation

After certain container operations, existing iterators may no longer point to valid elements. The exact rules differ per container.

Container Invalidates
std::vector, std::string All iterators on reallocation (e.g. push_back past capacity); iterators at-or-after the modification point on insert/erase
std::deque All iterators on push_front or push_back; all on insert in the middle
std::list, std::forward_list Only iterators to erased elements
std::set, std::map (and their multi/unordered variants) Only iterators to erased elements
std::unordered_* Iterators invalidated on rehash; references and pointers to elements remain valid

The "erase-remove" idiom illustrates a common safe pattern:

// vector::erase invalidates iterators at-or-after the erase point.
// Use the returned iterator to continue safely:
for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0) {
        it = v.erase(it);   // erase returns iterator to next element
    } else {
        ++it;
    }
}

For unordered_map / unordered_set, calling reserve(n) upfront can avoid rehashing, keeping iterators stable.

The general rule: don't hold an iterator across a container modification unless you've checked the container's invalidation rules.