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

1. Iterator Categories

Iterators classified by supported ops. Each category subsumes weaker ones.

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

Hierarchy:

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

Function template can require a 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
}

std::reverse needs bidirectional. std::sort needs random access (O(1) distance).

2. `std::iterator_traits`

std::iterator_traits<It> (<iterator>) — type metadata for 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 it to access types without knowing concrete iterator:

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;
}

C++20+: concepts (std::input_iterator, etc.) — 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)

next/prev/advance/distance — work on any iterator category, pick most efficient impl from iterator_category.

4. Iterator Adaptors

<iterator> provides adaptors that turn one iterator kind 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 `T`s from a stream
`std::ostream_iterator<T>(stream, sep)`	Writes `T`s 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 → reuse generic algorithms for I/O, container insertion, reverse traversal without custom loops.

5. Writing a Custom Iterator

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_;
};

C++20: std::ranges::iterator_t<R> + concepts give cleaner constraints for consumers.
For producing iterators: std::generator<T> (C++23 coroutines) is often easier than a hand-written iterator class.

6. Iterator Concepts (C++20)

C++20 added named concepts per iterator category → better errors + cleaner 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);

Sentinels in C++20 ranges — "end" need not be same type as iterator. std::ranges::range uses (begin, sentinel) pairs → "until null terminator" or "until predicate" without dummy past-the-end iterators.

7. Iterator Invalidation

After certain container ops, existing iterators may become invalid. 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

Erase-remove idiom — 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 — reserve(n) upfront avoids rehashing, keeps iterators stable.
General rule: don't hold an iterator across a container modification unless you've checked the invalidation rules.

C++ Iterators

Table of Contents

1. Iterator Categories

2. `std::iterator_traits`

3. Common Iterator Operations

4. Iterator Adaptors

5. Writing a Custom Iterator

6. Iterator Concepts (C++20)

7. Iterator Invalidation

Table of Contents

1. Iterator Categories

2. std::iterator_traits

3. Common Iterator Operations

4. Iterator Adaptors

5. Writing a Custom Iterator

6. Iterator Concepts (C++20)

7. Iterator Invalidation

2. `std::iterator_traits`