Most C++ code uses iterators handed out by the standard library, but sometimes defining a new one is the better option. A linked-list-like data structure with no STL counterpart, a numeric range generator, a wrapper around an external data source: any of these benefit from exposing an iterator interface so that std::find, std::transform, range-based for, and the rest of the algorithm library work against them. This chapter covers what an iterator type actually has to provide, the trait machinery that ties it into the STL, the iterator categories and how to pick one, and a worked example of an iterator for a small singly-linked list.

Why Write a Custom Iterator

Three situations come up repeatedly. The first is wrapping a container or data structure that isn't part of the STL: a homegrown linked list, a tree, a ring buffer. Providing iterators turns the structure into a drop-in target for STL algorithms.

The second is creating a virtual sequence with no underlying storage. An integer range [0, n), a Fibonacci sequence, the lines of a file: none of these need to materialise every element in memory. A custom iterator can generate each value on ++ and discard it after *.

The third is providing a filtered, transformed, or otherwise modified view over an existing container, in the same spirit as C++20's std::ranges::views::filter and std::ranges::views::transform. Before C++20, a custom iterator was the standard approach for writing a view without copying the underlying data.

The benefit is that one iterator implementation makes the type compatible with the standard algorithms and adapters. The container author writes the iterator once, and callers get every algorithm whose category requirements the iterator satisfies.

What the STL Expects

For a type to be usable as an iterator, it must support a specific set of operations and expose a specific set of type aliases (called iterator traits). The operations are roughly what a pointer does: dereference (*it), advance (++it), and compare (it == other, it != other). The traits tell the STL what category the iterator belongs to, what type of value it dereferences to, and what type to use for distance calculations.

Five typedefs are required, traditionally exposed either as nested type aliases on the iterator class or via a specialisation of std::iterator_traits<It>.

Typedef	Meaning
`value_type`	The type the iterator dereferences to (after stripping references).
`reference`	The exact return type of `operator*` (usually `value_type&` or `const value_type&`).
`pointer`	The return type of `operator->` (usually `value_type` or `const value_type`).
`difference_type`	A signed integer type for `it1 - it2` (usually `std::ptrdiff_t`).
`iterator_category`	One of the iterator tag types describing what operations the iterator supports.

The iterator category tag is a small empty struct whose only purpose is to be passed to template machinery so algorithms can dispatch on iterator capability at compile time.

The inheritance encodes the refinement hierarchy: a random-access iterator is also a bidirectional iterator, which is also a forward iterator, and so on. Algorithms that need at least a forward iterator accept any tag that's forward_iterator_tag or stronger.

Iterator Categories

The category determines which operations the iterator must support, which in turn determines which STL algorithms will accept it. Picking the right category for a custom iterator means thinking about what the underlying data structure can support.

Category	Required operations	Example use
`input_iterator_tag`	`*it` (read), `++it`, `==`, `!=`. Single-pass only.	Reading from a stream
`output_iterator_tag`	`*it = value`, `++it`. Single-pass write.	Writing to a stream or insert iterator
`forward_iterator_tag`	input + can re-traverse, can be default-constructed	Singly-linked list
`bidirectional_iterator_tag`	forward + `--it`	Doubly-linked list, `std::map`, `std::set`
`random_access_iterator_tag`	bidirectional + `it + n`, `it - n`, `it[n]`, `<`, `>`, `<=`, `>=`, `it1 - it2`	Arrays, `std::vector`, `std::deque`
`contiguous_iterator_tag` (C++20)	random access + elements live in contiguous memory	`std::vector`, `std::array`, raw arrays

A custom iterator should report the strongest category it can honestly support. Claiming random_access_iterator_tag when only ++ is implemented is a compile-time error at best and a subtle runtime bug at worst, because algorithms will pick the random-access code path expecting O(1) jumps.

Most custom iterators end up in the forward or bidirectional bucket. Random-access iterators are harder to write because they require O(1) jumps, which only works for array-backed storage.

Quick Check: A custom iterator over a singly-linked list of products supports ++it (move to next node), *it, ==, and !=. Which category should it advertise?

A) std::input_iterator_tag
B) std::forward_iterator_tag
C) std::bidirectional_iterator_tag

<details> <summary>Answer</summary>

B. The iterator supports multi-pass traversal (each node is reachable from the head as many times as needed) but doesn't support -- because the list is singly-linked. That's the exact contract of forward_iterator_tag. input_iterator_tag (A) would be too weak; it implies single-pass. bidirectional_iterator_tag (C) would be a lie; backward stepping isn't supported.

</details>

The Required Operators

Independent of category, every iterator type has to implement at least these operators (assuming a non-output iterator):

That's the minimum for a forward iterator. Bidirectional adds --it and it--. Random access adds +, -, +=, -=, [], and the relational operators.

The operator!= is technically redundant in C++20 (the compiler can synthesise it from operator==), but for C++17 and earlier it has to be defined explicitly.

The post-increment overload is the unusual one. Its parameter is an unnamed int that the compiler passes purely to distinguish the two overloads. The convention is to make a copy of the current iterator, advance the current iterator, and return the copy.

The post-increment makes a copy, so it's usually slightly slower than pre-increment. Prefer ++it over it++ in algorithm implementations where the result isn't used.

Iterator Traits

The five typedefs can be exposed in two ways. The traditional approach is to nest them inside the iterator class:

The STL then queries them through std::iterator_traits<MyIterator>, which by default forwards to the nested aliases:

The fallback specialisation for raw pointers makes int* work as a random-access iterator out of the box:

That specialisation is the reason std::sort(arr, arr + n) works on a raw array: int* qualifies as a random-access iterator via the trait specialisation, even though int* doesn't have nested typedefs.

The deprecated alternative was to inherit from std::iterator<Category, T> which provided the typedefs for you. std::iterator was deprecated in C++17 and should not be used in new code. Spell out the typedefs explicitly.

A Worked Example: Iterator for a Singly-Linked List

A small product list. Each node holds an id and a pointer to the next node. The list has a head pointer and supports push_front and an iterator-based traversal.

The list owns its nodes and cleans them up in the destructor. The two public iterator member functions return a begin() pointing at the head and an end() pointing at one-past-the-tail (which for a singly-linked list is a nullptr sentinel).

The iterator type itself. It wraps a pointer to a ProductNode and provides exactly the operators the STL needs.

The default constructor produces a "singular" iterator (a forward iterator must be default-constructible). operator* returns a reference to the node's id, which means the algorithm can both read and write through the iterator. operator++ advances to the next node and returns *this. Comparison is pointer-equality of the underlying nodes, which means end() (with node_ == nullptr) compares equal to any iterator that has walked off the end.

The begin() and end() member functions:

end() is a sentinel value: the iterator constructed with nullptr. Any iterator that walks all the way through the list will eventually compare equal to it.

The full program putting it all together:

Output:

Three different STL operations work against the custom container with no extra code: range-based for, std::find, and std::count_if. One iterator implementation enables them all.

A ProductList iterator walks one node per increment, like any linked-list iterator. std::distance(list.begin(), list.end()) is O(n) because there's no shortcut. Random-access algorithms like std::sort won't compile against this iterator: the category tag is forward_iterator_tag, so the compiler rejects calls that need stronger guarantees.

Quick Check: Suppose operator== in the iterator above checked node_->id == other.node_->id instead of node_ == other.node_. What would go wrong?

<details> <summary>Answer</summary>

Iterators are positions, not values. With value-based equality, two different nodes that happen to hold the same id would compare equal, which would break find (it would stop at the first node with a matching id rather than reporting position correctly) and break the loop termination because end() has a null node_ whose dereference is undefined. The correct equality is position-equality: do the two iterators refer to the same underlying node?

</details>

A Worked Example: A Numeric Range Iterator

The second common pattern: an iterator that doesn't wrap any storage. It produces a sequence of numbers on demand. Useful for for (int i : range(0, 10)) style loops without writing out the index variables.

Output:

There's no storage anywhere. The iterator holds a single int. Increment bumps the int. Dereference returns it. Comparison checks if two iterators hold the same int. The range itself is a pair of ints.

A subtlety: reference is int, not int&. The iterator returns by value because there's no underlying element to refer to. That makes this an input iterator, not a forward iterator, because forward iterators are required to return a real reference from operator*. The category tag reflects that.

Returning by value is fine for many algorithms (find, count_if, accumulate), but a few algorithms (like in-place std::transform writing back to the source) need to write through the iterator, and that won't work here. The category tag tells the algorithm that, and the compiler stops anyone from trying.

Const Iterators

Most container types provide both iterator and const_iterator. The const version returns const value_type& from operator* and disallows writes through the iterator. Adding one to a custom iterator class is mostly a matter of templating the iterator on a const-ness flag.

The pattern uses a single class template parameterised on a bool. std::conditional_t swaps the relevant types between const and non-const. The conversion constructor allows an iterator to implicitly convert to a const_iterator (because adding const is always safe), but not the reverse.

For a first custom iterator, the simpler approach is to write two separate classes that share most of the code. Templating is the production-grade solution but adds boilerplate up front.

Making the Iterator Work with Algorithms

Once the iterator has the right typedefs and operators, every algorithm with a matching category requirement works. The compiler picks the algorithm overload based on the iterator's category tag.

Output:

std::any_of, std::accumulate, and std::for_each accept any input iterator, so the forward iterator implementation easily satisfies them. std::for_each is mutating the underlying list elements through the iterator's reference type, which works because the iterator's operator* returns int&.

What doesn't work:

std::sort requires random-access iterators. The forward_iterator_tag on the custom iterator tells the compiler that the requirement isn't met, and the call fails to compile. To sort a singly-linked structure, copy the values into a std::vector, sort that, and copy them back. (std::forward_list has its own member sort() that uses a merge-sort variant tailored to singly-linked structures.)

Sentinel-Based End Iterators (C++20 Preview)

C++20's std::ranges library generalised the end iterator concept by introducing sentinels: an "end" doesn't have to be the same type as the iterator. For the linked list above, end() could return a special EndSentinel type whose only role is to be compared against the iterator.

The benefit shows up most clearly for input streams and generator-style iterators where the "I'm at the end" check is naturally asymmetric. Pre-C++20 algorithms require iterator-equals-iterator, so the workaround is to make the sentinel type implicitly convertible to the iterator type, or to have the iterator hold an is_end flag. C++20 ranges algorithms accept the sentinel pattern natively.

That's the direction custom iterators are heading. For pre-C++20 code, the sentinel-as-iterator pattern shown in the ProductList example (an iterator wrapping nullptr) is the practical equivalent.

Common Pitfalls

Several mistakes recur when writing a first custom iterator.

Missing or wrong typedefs. Without iterator_category, value_type, and difference_type, algorithms that use std::iterator_traits fail to compile, often with messages that don't obviously point at the missing trait. Always define all five.

Wrong category tag. Claiming random_access_iterator_tag on an iterator that only walks forward leads to compile errors at the algorithm site (when it + n is attempted). Pick the strongest category the iterator can honestly support and no stronger.

**Returning a temporary from operator*.** Returning value_type by value instead of value_type& makes the iterator an input iterator, not a forward iterator. That's fine if it matches the actual capability, but it has algorithm implications: anything that writes through the iterator won't work.

Forgetting `operator->`. Some algorithms use it->member rather than (*it).member. Implementing only operator* and not operator-> causes those algorithms to fail.

Post-increment returning a reference. The post-increment must return by value (a copy of the pre-modification iterator), not a reference. Returning a reference would either dangle or fail to capture the pre-modification state.

Comparing values instead of positions. Iterator equality means "do they refer to the same position in the same sequence?", not "do they refer to elements with equal values?". Comparing the underlying values breaks algorithms that rely on position semantics.

A Compact Checklist

Before considering a custom iterator finished, walk through this list.

Item	Reason
All five `using` typedefs defined	Required by `std::iterator_traits`
Default constructor (for forward and above)	Required by the category contract
`operator*` returns the right type for the category	Forward needs a real reference; input may return by value
`operator->` defined when `operator*` returns a class or struct	Many algorithms use the arrow form
Pre-increment and post-increment both defined	Some algorithms use one, some the other
`operator==` and `operator!=` defined	Required for any iterator
Category tag matches actual capability	Prevents misuse, allows compile-time dispatch
`end()` returns a sentinel that compares equal to a fully-advanced iterator	Required for termination

Once those boxes are checked, range-based for, the algorithms with matching category requirements, and the iterator adapters all become available.

Interview Questions

Q1: What's the difference between an iterator's `value_type` and its `reference` type?

value_type is the type of element the iterator logically points at, after stripping references and const. reference is the exact return type of operator*, which for most iterators is value_type& (for non-const) or const value_type& (for const iterators). They diverge for input iterators that return a generated value rather than referring to stored data: in those cases reference may be value_type by value, which signals "this is single-pass, you can't write back through this iterator."

Q2: Why do iterator categories use empty tag types instead of a runtime enum?

The category influences which algorithm implementation the compiler selects. With tag types, the dispatch happens at compile time via overload resolution, with no runtime cost. A runtime enum would require an if/switch at every algorithm boundary, which is slower and prevents the compiler from inlining the category-specific code. The tag dispatch idiom (std::advance selecting O(n) loop versus O(1) addition based on the tag) is the classic example.

Q3: When should a custom iterator be an input iterator instead of a forward iterator?

When the iterator can be incremented only once per element, when copies of the iterator share state, or when operator* returns a temporary value rather than a reference into stable storage. Stream iterators are a clear example: each ++ consumes one value from the stream, and there's no way to re-read it. Generator-style iterators that compute values on demand are also input iterators. The forward iterator contract requires multi-pass traversal, which generators can't honour without buffering all values.

Q4: What does `std::iterator_traits<It>` do, and when would you specialise it?

std::iterator_traits<It> is the standard way the STL queries an iterator type for its value_type, reference, pointer, difference_type, and iterator_category. The default implementation forwards to nested typedefs on It. You'd specialise it explicitly for two reasons: when the iterator type is a raw pointer (the standard already specialises for T*), or when you can't or don't want to add the typedefs directly to the iterator class. Most user-defined iterators add the typedefs as nested aliases, and iterator_traits then works without a custom specialisation.

Q5: Why does `std::sort` not compile against a `std::list` iterator, but `std::find` does?

std::list provides bidirectional iterators. std::sort requires random-access iterators because its implementation (introsort) needs O(1) jumps to pivot around midpoints. std::find only walks the range forward and needs no random access, so its signature accepts any input iterator. The compile error happens at the call site, triggered by the algorithm using an operation the iterator doesn't support. The fix for sorting a std::list is to use list.sort(), which is a member function tailored to linked storage.

Exercises

Exercise 1: Add an operator-> to the IntRange::iterator above so that it->some_member would work if the value type had members. Since the value type is int, document why the pointer typedef is const int* rather than int*.

Expected behaviour: the code compiles, and pointer is const int* because the iterator returns by value (a temporary int), and pointing into a temporary requires the pointer to be const.