C++ Iterators: Categories, Adapters & Custom Iterator Guide
Table of Contents
What Are Iterators?
Iterators are generalized pointers that provide a uniform way to traverse elements in any STL container. They’re the bridge between containers and algorithms — algorithms don’t know which container holds the data, and containers don’t know which algorithms will process it. Iterators connect them with a common interface: dereference (*it), advance (++it), and compare (it != end).
This design means M containers × N algorithms only need M + N implementations instead of M × N. std::sort works with vector, array, deque, and any custom container that provides the right iterator type — all without knowing anything about those containers.
Iterator Basics
#include <vector>
#include <iostream>
int main() {
std::vector<int> v = {10, 20, 30, 40, 50};
// begin() points to first element, end() points past the last
auto it = v.begin(); // points to 10
auto last = v.end(); // points past 50 (not dereferenceable!)
// Dereference — access the element
std::cout << *it << "\n"; // 10
// Advance
++it;
std::cout << *it << "\n"; // 20
// Modify through iterator
*it = 25;
std::cout << v[1] << "\n"; // 25
// Iterator loop (equivalent to range-based for)
for (auto it = v.begin(); it != v.end(); ++it) {
std::cout << *it << " ";
}
std::cout << "\n";
// Range-based for is syntactic sugar for:
// auto __begin = v.begin();
// auto __end = v.end();
// for (; __begin != __end; ++__begin) {
// auto& elem = *__begin;
// }
// Arrow operator for class elements
std::vector<std::string> words = {"hello", "world"};
auto wit = words.begin();
std::cout << wit->size() << "\n"; // 5 (hello.size())
}Iterator Categories
Iterators form a hierarchy of capabilities. Each category adds operations on top of the previous one:
// Input Iterator — read once, forward only
// Operations: *it (read), ++it, it != end
// Used by: std::istream_iterator
// Containers: none directly (stream input)
// Output Iterator — write once, forward only
// Operations: *it = val, ++it
// Used by: std::ostream_iterator, std::back_inserter
// Forward Iterator — read/write, forward, multi-pass
// Operations: *it (read/write), ++it, it != end, copy/compare
// Containers: forward_list, unordered_set, unordered_map
// Bidirectional Iterator — + backward
// Operations: all Forward ops + --it
// Containers: list, set, map, multiset, multimap
// Random Access Iterator — + jumps, arithmetic
// Operations: all Bidirectional ops + it += n, it -= n, it[n], it1 - it2, it1 < it2
// Containers: vector, deque, array, string
// Contiguous Iterator (C++20) — guarantees contiguous memory
// Operations: all Random Access ops + contiguous memory guarantee
// Containers: vector, array, string (NOT deque)
// Algorithm requirements:
// std::find → Input Iterator (reads forward)
// std::copy → Input + Output
// std::replace → Forward Iterator (multi-pass)
// std::reverse → Bidirectional Iterator (needs --)
// std::sort → Random Access Iterator (needs jumps)If you pass a bidirectional iterator to std::sort (which needs random-access), you’ll get a compile error. This is why std::list has its own .sort() member function — the generic std::sort can’t work with list’s bidirectional iterators.
Const and Reverse Iterators
#include <vector>
std::vector<int> v = {1, 2, 3, 4, 5};
// Regular iterator — read and write
auto it = v.begin();
*it = 10; // OK
// Const iterator — read only
auto cit = v.cbegin();
// *cit = 10; // ERROR: can't modify through const_iterator
std::cout << *cit << "\n"; // OK to read
// Reverse iterator — iterate backwards
for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
std::cout << *rit << " "; // 5 4 3 2 1
}
// Const reverse iterator
for (auto crit = v.crbegin(); crit != v.crend(); ++crit) {
std::cout << *crit << " ";
}
// Convert reverse to forward iterator
auto rit = v.rbegin();
std::advance(rit, 2); // points to 3 (in reverse)
auto fwd = rit.base(); // forward iterator to element AFTER 3 → points to 4
// Note: .base() returns iterator to element AFTER the reverse iterator's element
// Common pattern: erase with reverse iterator
// v.erase(std::next(rit).base()); // erase the element rit points toIterator Utility Functions
#include <iterator>
#include <vector>
#include <list>
std::vector<int> v = {10, 20, 30, 40, 50};
std::list<int> lst = {10, 20, 30, 40, 50};
// std::advance — move iterator forward/backward
auto it = v.begin();
std::advance(it, 3); // O(1) for random-access
std::cout << *it << "\n"; // 40
auto lit = lst.begin();
std::advance(lit, 3); // O(n) for bidirectional — walks 3 steps
// std::next / std::prev (C++11) — non-modifying
auto it2 = std::next(v.begin(), 2); // returns iterator to 3rd element
auto it3 = std::prev(v.end()); // returns iterator to last element
auto it4 = std::next(v.begin()); // default step is 1
// std::distance — count elements between iterators
auto dist = std::distance(v.begin(), v.end()); // 5
// O(1) for random-access, O(n) for forward/bidirectional
// std::begin / std::end — work with raw arrays too!
int arr[] = {1, 2, 3, 4, 5};
auto arr_begin = std::begin(arr); // int*
auto arr_end = std::end(arr); // int* past last element
auto arr_size = std::distance(arr_begin, arr_end); // 5
// std::size (C++17)
auto sz = std::size(v); // 5
auto asz = std::size(arr); // 5
// std::ssize (C++20) — returns signed size
auto ssz = std::ssize(v); // ptrdiff_t, not size_tIterator Adapters
Iterator adapters wrap containers or other iterators to modify their behavior:
#include <iterator>
#include <vector>
#include <algorithm>
std::vector<int> src = {1, 2, 3, 4, 5};
// back_inserter — calls push_back on assignment
std::vector<int> dest;
std::copy(src.begin(), src.end(), std::back_inserter(dest));
// dest = {1, 2, 3, 4, 5}
// front_inserter — calls push_front (for deque, list)
std::list<int> lst;
std::copy(src.begin(), src.end(), std::front_inserter(lst));
// lst = {5, 4, 3, 2, 1} — reversed because each goes to front
// inserter — inserts at a specific position
std::vector<int> v = {10, 50};
std::copy(src.begin(), src.end(), std::inserter(v, std::next(v.begin())));
// v = {10, 1, 2, 3, 4, 5, 50}
// move_iterator — moves instead of copies
std::vector<std::string> words = {"hello", "world", "foo"};
std::vector<std::string> moved;
std::copy(std::make_move_iterator(words.begin()),
std::make_move_iterator(words.end()),
std::back_inserter(moved));
// moved = {"hello", "world", "foo"}
// words = {"", "", ""} — moved-from
// reverse_iterator — already covered above
// Useful in algorithms:
// Sort descending
std::sort(v.begin(), v.end());
// Or iterate backwards with algorithms
auto rit = std::find(v.rbegin(), v.rend(), 3); // find last occurrenceStream Iterators
#include <iterator>
#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
// ostream_iterator — write to output stream
std::vector<int> v = {1, 2, 3, 4, 5};
std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
// Output: 1 2 3 4 5
std::cout << "\n";
// istream_iterator — read from input stream
std::istringstream input("10 20 30 40 50");
std::vector<int> data(
std::istream_iterator<int>(input),
std::istream_iterator<int>() // end-of-stream sentinel
);
// data = {10, 20, 30, 40, 50}
// Combine: read from stdin, sort, write to stdout
// std::vector<int> nums(
// std::istream_iterator<int>(std::cin),
// std::istream_iterator<int>());
// std::sort(nums.begin(), nums.end());
// std::copy(nums.begin(), nums.end(),
// std::ostream_iterator<int>(std::cout, "\n"));Writing a Custom Iterator
You can write iterators for your own data structures. Here’s a minimal forward iterator for a simple range:
#include <iterator>
#include <iostream>
class IntRange {
int start_, end_;
public:
IntRange(int start, int end) : start_(start), end_(end) {}
class iterator {
int current_;
public:
// Iterator traits (required for STL compatibility)
using iterator_category = std::forward_iterator_tag;
using value_type = int;
using difference_type = std::ptrdiff_t;
using pointer = const int*;
using reference = int;
explicit iterator(int val) : current_(val) {}
int operator*() const { return current_; }
iterator& operator++() { ++current_; return *this; }
iterator operator++(int) { auto tmp = *this; ++current_; return tmp; }
bool operator==(const iterator& other) const { return current_ == other.current_; }
bool operator!=(const iterator& other) const { return current_ != other.current_; }
};
iterator begin() const { return iterator(start_); }
iterator end() const { return iterator(end_); }
};
int main() {
// Use in range-based for
for (int i : IntRange(1, 6)) {
std::cout << i << " "; // 1 2 3 4 5
}
std::cout << "\n";
// Use with STL algorithms
IntRange range(1, 11);
auto it = std::find(range.begin(), range.end(), 7);
if (it != range.end()) {
std::cout << "Found: " << *it << "\n"; // Found: 7
}
int sum = 0;
for (int n : IntRange(1, 101)) sum += n;
std::cout << "Sum 1-100: " << sum << "\n"; // 5050
}C++20 Sentinel Model
C++20 ranges introduced the sentinel concept — the end of a range doesn’t need to be the same type as the iterator. This enables more flexible termination conditions:
#include <ranges>
#include <iostream>
#include <string>
// C-string example: the sentinel is '\0', not another pointer
// In C++20 ranges, std::ranges::find handles this:
// const char* str = "hello";
// auto it = std::ranges::find(str, '\0', 'l');
// std::unreachable_sentinel — for when you KNOW the search will succeed
// Skips the end check entirely (dangerous but fast)
// Views use sentinels naturally:
for (int i : std::views::iota(1) | std::views::take(5)) {
std::cout << i << " "; // 1 2 3 4 5
}
// iota(1) is an infinite range — take(5) provides the sentinel
// Ranges algorithms accept iterator + sentinel
std::string s = "Hello, World!";
auto it = std::ranges::find(s, ',');
// it is an iterator, s.end() would be the sentinelCommon Mistakes
Dereferencing end(). end() points past the last element and must never be dereferenced. Always check it != container.end() before using *it.
Iterator invalidation. Modifying a container (insert, erase, push_back) can invalidate existing iterators. Vector invalidates all iterators on reallocation. List only invalidates erased iterators. Know the rules for your container.
Using wrong iterator category. Passing a bidirectional iterator to an algorithm that requires random-access gives cryptic compile errors. Check the algorithm’s requirements.
Off-by-one with reverse_iterator::base(). rit.base() returns a forward iterator to the element after *rit. This confuses many developers when erasing with reverse iterators.
Forgetting std::advance is O(n) for non-random-access. std::advance(list_it, 1000) walks 1000 nodes one by one. It’s not like vector_it += 1000 which is O(1).
Summary
Iterators are generalized pointers that decouple containers from algorithms. They form a hierarchy: Input → Forward → Bidirectional → Random Access → Contiguous, each adding capabilities. Utility functions (std::advance, std::next, std::distance) work generically across categories. Iterator adapters (back_inserter, move_iterator, stream iterators) extend iterator capabilities. C++20 introduces sentinels for flexible range termination. In the next lesson, you’ll master sorting and searching algorithms — the workhorses of the STL that rely on iterators to process data efficiently.
