Iterators
Iterators are the generalized pointers that let a single algorithm like std::sort work identically on a vector, a deque, or a list — understanding their categories explains why some containers support operations others quietly refuse.
Every container in the STL organizes its elements differently under the hood — a vector's elements sit in one contiguous block, a list's elements are scattered nodes linked by pointers, a map's elements live in a tree. If every algorithm had to know these details to traverse a container, you'd need a separate sort, find, and count for every container type. Iterators solve that problem by acting as a uniform, pointer-like interface: any container that can produce iterators satisfying a given set of requirements can be traversed by any algorithm written against those requirements, regardless of what's actually happening in memory underneath. This page covers what an iterator actually is, the standard ways of obtaining one, the hierarchy of iterator categories that determines which operations are legal, and the invalidation rules that trip up almost everyone at some point.
What Is an Iterator?
An iterator is an object that behaves like a pointer: it can be dereferenced with * to access the element it refers to, and advanced with ++ to move to the next element. That's the whole idea — iterators generalize the pointer arithmetic you'd use to walk a raw array (int *p = arr; *p; ++p;) so it also works for containers where "the next element" isn't just "the next memory address," such as a linked list or a tree.
nums.begin() returns an iterator pointing at the first element; nums.end() returns an iterator representing one-past-the-last element, never a valid element to dereference. *it reads the current element, and ++it advances the iterator — exactly the pattern you'd use with a raw pointer, except it works unchanged on a std::list<int> too.
The end() iterator is intentionally not dereferenceable — it exists purely as a sentinel to compare against, so a loop knows when to stop. Dereferencing end() (or an iterator that has been advanced past it) is undefined behavior, exactly like dereferencing a pointer one past the end of an array.
#include <vector>
#include <iostream>
int main()
{
std::vector<int> nums{10, 20, 30};
std::vector<int>::iterator it = nums.begin();
while (it != nums.end())
{
std::cout << *it << " ";
++it;
}
std::cout << "\n";
return 0;
}begin(), end(), cbegin(), cend()
Every standard container provides begin() and end() as member functions, and also as free functions std::begin(container) / std::end(container) that additionally work on raw arrays. The const-qualified variants cbegin() and cend() always return a const_iterator — one that lets you read elements but not modify them through it — regardless of whether the container itself is const.
Using cbegin()/cend() documents intent directly in the code: this loop only reads nums, and the compiler enforces that by refusing any attempt to assign through *it. Preferring cbegin()/cend() (or begin()/end() on a container you've declared const) over a mutable iterator is good practice whenever a loop genuinely doesn't need to modify elements.
There are reverse counterparts too: rbegin()/rend() (and crbegin()/crend()) return reverse_iterators that walk the container from the last element to the first, letting you write a backward traversal without changing the loop's shape at all.
#include <vector>
#include <iostream>
int main()
{
std::vector<int> nums{1, 2, 3};
for (auto it = nums.cbegin(); it != nums.cend(); ++it)
{
std::cout << *it << " ";
// *it = 100; // would not compile: *it is const int&
}
std::cout << "\n";
return 0;
}Iterator Categories
Not every iterator supports the same set of operations, because not every container can support them efficiently. The standard defines a hierarchy of iterator categories, each one a strict superset of the operations the previous category supports, and each STL container's iterators belong to exactly the strongest category that container's internal layout can actually support.
Each category up the hierarchy adds capability: an input iterator can be read from and advanced but only once per element (a single pass); a forward iterator can be read multiple times by copying and re-walking; a bidirectional iterator adds -- to step backward; a random-access iterator adds arithmetic (it + 5, it2 - it1, it[3]) so you can jump directly to any position; and a contiguous iterator (added in C++17/20) additionally guarantees the underlying elements sit in one unbroken block of memory, the way vector and array's do.
vector's iterators support + directly because jumping to any index is O(1) in contiguous storage. list's iterators don't support + at all, because "jump 3 nodes ahead" on a linked list can only be done by following next pointers one at a time — std::advance hides that loop behind a uniform interface that works on any iterator category, doing it in O(1) for random-access iterators and O(n) for anything weaker.
Category Supports Example container
------------------------------------------------------------------------
Input read, ++ (single pass, forward only) std::istream_iterator
Output write, ++ (single pass, forward only) std::ostream_iterator
Forward read/write, ++ (multi-pass) std::forward_list
Bidirectional Forward, plus -- std::list, std::set, std::map
Random-access Bidirectional, plus +n, -n, [], <, > std::deque
Contiguous Random-access, elements adjacent in memory std::vector, std::array#include <vector>
#include <list>
#include <iostream>
int main()
{
std::vector<int> v{1, 2, 3, 4, 5};
auto vit = v.begin();
vit = vit + 3; // OK: vector has random-access iterators
std::cout << *vit << "\n"; // 4
std::list<int> l{1, 2, 3, 4, 5};
auto lit = l.begin();
// lit = lit + 3; // does NOT compile: list only has bidirectional iterators
std::advance(lit, 3); // this is how you move a non-random-access iterator by n
std::cout << *lit << "\n"; // 4
return 0;
}Iterator Arithmetic and Distance
For random-access iterators, the STL supports the same arithmetic you'd expect from a raw pointer: it + n and it - n move n positions, it1 - it2 computes the number of elements between two iterators, and it[n] indexes n positions ahead without an intermediate variable. For iterators of any category, std::distance(first, last) computes how many increments it takes to get from first to last — O(1) for random-access iterators, O(n) otherwise.
std::distance(first, last) here returns 5, the number of elements in nums. Adding half of that to first lands on index 2, so *middle reads 30. Because nums is a vector, this whole computation is O(1); the same code would still compile for a std::list, but std::distance would then have to walk the list, making it O(n).
#include <vector>
#include <iostream>
#include <iterator>
int main()
{
std::vector<int> nums{10, 20, 30, 40, 50};
auto first = nums.begin();
auto last = nums.end();
std::cout << "distance: " << std::distance(first, last) << "\n";
auto middle = first + std::distance(first, last) / 2;
std::cout << "middle element: " << *middle << "\n";
return 0;
}Range-Based for Loops
The range-based for loop introduced in C++11, for (auto& x : container), is syntactic sugar over exactly the iterator pattern shown earlier — the compiler rewrites it into a call to begin()/end() (or std::begin()/std::end() for a raw array) and a loop that dereferences and increments an iterator automatically.
Using int& n (a reference) lets the loop body modify the actual elements in nums; using int n by value would modify only a copy, leaving nums unchanged. This is the same distinction that matters for *it versus a copied value in the explicit iterator version.
Because range-based for is built on the exact same begin()/end() machinery, it works unmodified on any type that provides those two functions (member or free), which is why user-defined container types only need to implement begin() and end() to gain range-for support for free.
std::vector<int> nums{1, 2, 3};
// range-based for:
for (int& n : nums)
n *= 2;
// exactly equivalent to:
for (auto it = nums.begin(); it != nums.end(); ++it)
*it *= 2;Iterator Invalidation
An iterator is only valid as long as the container hasn't changed in a way that disturbs the element (or memory) the iterator points to. Different containers invalidate iterators under different circumstances, and the rules are specific enough that they're a frequent source of subtle bugs.
vector::erase(it) invalidates it and every iterator after it, since elements shift left to fill the gap — but it returns a new, valid iterator pointing at the element that took the erased element's place, which is exactly why the loop reassigns it = nums.erase(it) instead of erasing and then separately calling ++it.
it starts at nums.begin(), pointing at 1 (odd) — the else branch runs, it advances to 2.
*it is 2 (even) — nums.erase(it) removes it and returns an iterator now pointing at 3; it is reassigned to that.
The loop continues: 3 is odd, advance; 4 is even, erase (returns iterator at 5); 5 is odd, advance to end().
Final result: nums is {1, 3, 5}.
Container Invalidated by
---------------------------------------------------------------
vector Any insertion/erase that reallocates, or any erase
before the iterator's position (elements shift)
deque Insertion/erase anywhere except at an end typically
invalidates all iterators
list/forward_list Only iterators to an erased element are invalidated;
all others remain valid
set/map Only iterators to an erased element are invalidated;
insertion never invalidates existing iterators
unordered_set/map Insertion may invalidate all iterators if it triggers
a rehash#include <vector>
#include <iostream>
int main()
{
std::vector<int> nums{1, 2, 3, 4, 5};
for (auto it = nums.begin(); it != nums.end(); )
{
if (*it % 2 == 0)
it = nums.erase(it); // erase returns the next valid iterator
else
++it;
}
for (int n : nums)
std::cout << n << " ";
std::cout << "\n";
return 0;
}Best Practices
Prefer auto for iterator types — std::vector<std::pair<std::string,int>>::iterator is painful to write and easy to typo, while auto it = container.begin(); is always correct and self-updating if the container's element type changes later. Prefer cbegin()/cend() when a loop only reads. Never dereference end() or an iterator that has been invalidated. When you need to move an iterator by n positions and don't know (or don't want to assume) its category, use std::advance, std::next, and std::prev instead of raw + and -, since those work uniformly across every iterator category. And whenever you erase from a container while iterating it, capture and use the iterator that erase() itself returns rather than assuming the old one, or any manually-incremented iterator, is still valid.
What is the fundamental idea behind an iterator, and why does it let a single algorithm like std::sort work on any container that provides the right kind of iterator?
An iterator is an object that behaves like a pointer — it can be dereferenced to read/write the element it refers to and advanced to move to the next one — regardless of how the container actually stores its elements underneath. Because algorithms are written purely in terms of these iterator operations rather than any specific container's internals, any container that exposes iterators supporting the required operations can be used with that algorithm unchanged.
Why does list::iterator not support it + 5, while vector::iterator does?
vector's elements are stored contiguously, so the address of the element 5 positions ahead can be computed directly in O(1) by adding to the current address — the definition of random-access. list's elements are separate heap-allocated nodes connected only by next/prev pointers, so reaching the node 5 positions ahead requires following those pointers one at a time, an O(n) operation, which is exactly what list's weaker bidirectional category reflects: it deliberately doesn't offer an operation it can't perform efficiently.
Why is nums.end() not something you should ever dereference?
end() is a sentinel representing one position past the last valid element, used only for comparison to detect when a traversal has finished — it doesn't refer to an actual element in the container. Dereferencing it (or any iterator that has advanced to or past it) reads memory that either doesn't hold an element or doesn't belong to the container at all, which is undefined behavior.
In the erase-while-iterating loop pattern it = nums.erase(it); (in the else branch, ++it), why is it critical to reassign it from erase's return value rather than calling erase(it) followed by a separate ++it?
vector::erase invalidates the iterator passed to it, along with every iterator after that position, because erasing shifts later elements left to fill the gap. Calling ++it on that now-invalidated iterator is undefined behavior. erase() itself returns a fresh, valid iterator pointing at whatever element now occupies the erased position (or end() if the last element was erased), which is exactly what the loop needs to continue safely.
What does std::distance(first, last) compute, and why is its cost O(1) for a vector's iterators but O(n) for a list's iterators?
std::distance computes the number of increments needed to get from the first iterator to the last. For random-access iterators like vector's, this is a single subtraction (last - first) because the underlying addresses make that arithmetic direct, so it's O(1). For weaker iterator categories like list's bidirectional iterators, there's no such shortcut, so std::distance has to actually walk from first to last one increment at a time, counting as it goes — O(n).
Write a C++ program that uses explicit iterators (not a range-based for loop) to print a std::vector<int> in reverse order, using rbegin() and rend().
rbegin() returns a reverse_iterator pointing at the last element, and rend() represents one-before-the-first. Incrementing a reverse_iterator with ++ actually moves it backward through the underlying container, so this loop visits 5, 4, 3, 2, 1 in that order without needing any manual index arithmetic.
What does this code print, and what would go wrong if it were rewritten as it = it + 2;?
It prints 3 — std::advance moves it forward two positions from the start of the list, landing on the third element (1, 2, then 3). Rewriting it as it = it + 2 would fail to compile, because std::list only provides bidirectional iterators, which support ++ and -- but not + or - ; only random-access iterators (like vector's or deque's) support arithmetic operators directly.
Write a C++ program that safely removes every element equal to 0 from a std::vector<int> while iterating it, using the erase-returns-next-iterator pattern (not the erase-remove idiom).
Whenever *it equals 0, nums.erase(it) removes that element and returns a fresh, valid iterator pointing at the element that shifted into its place, so it is reassigned to that rather than incremented separately. Non-zero elements simply advance it normally with ++it. The result is 1 2 3 4, with every 0 removed and no invalidated-iterator undefined behavior.
Why does this code fail to compile?
cbegin() always returns a const_iterator, whose dereference yields a const int&, regardless of whether v itself is declared const. Assigning through *it therefore attempts to modify a const-qualified reference, which the compiler rejects — const_iterator exists precisely to let code express (and have enforced) 'this traversal only reads, it never writes.'
std::list<int> lst{1, 2, 3, 4, 5};
auto it = lst.begin();
std::advance(it, 2);
std::cout << *it << "\n";std::vector<int> v{1,2,3};
std::vector<int>::const_iterator it = v.cbegin();
*it = 99;