These are the notes for C++ episode 26. By now you've met vector, list, deque, map, set, the hash tables, stack, queue and priority_queue. They are all built differently inside: a row of boxes, a chain of nodes, a tree, buckets. In this episode you invent the one idea that lets a single loop walk through almost all of them: the iterator. Every example below was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13.3, the same command as the SyntaxPilot compiler) and run; outputs and error messages are copied from those runs.
The problem: the index loop breaks
A class teacher keeps marks in a vector and prints them with the loop you've written a hundred times:
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> marks = {72, 95, 58, 88, 95};
for (int i = 0; i < marks.size(); i++)
cout << marks[i] << " ";
cout << endl;
return 0;
}
Output:
72 95 58 88 95
Then the principal asks for the distinct marks, sorted. In episode 23 you learned the perfect container for that: a set. The teacher changes one word, vector becomes set, and keeps the same loop:
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> marks = {72, 95, 58, 88, 95}; // sorted, no repeats
for (int i = 0; i < marks.size(); i++)
cout << marks[i] << " ";
cout << endl;
return 0;
}
g++ says:
main.cpp:8:22: error: no match for ‘operator[]’ (operand types are ‘std::set<int>’ and ‘int’)
Why it fails: a vector is one row of boxes in memory, so "box number 2" is one quick calculation away. A set is a tree of nodes, and a list is a chain of nodes scattered across memory. There is no "box number 2". To reach the third item, you have to walk there, one step at a time. So these containers simply don't offer [].
What we need is a way to walk a container without knowing its shape.
Step 1: inventing the iterator (the ticket checker)
Real-life example: the ticket checker (TTE) on a train. They don't need seat numbers:
| On a train | In C++ | What it means |
|---|---|---|
| Start at the first seat of the first coach | c.begin() |
an iterator pointing at the first item |
| Check the passenger in front of you | *it |
the item the iterator points at |
| Walk to the next seat (the train knows the way) | ++it |
move to the next item |
| Stop at the door after the last coach (nobody sits there) | c.end() |
one past the last item: a stop sign, never read it |
An iterator is an object that remembers a position inside a container and knows how to move to the next position. It behaves like a pointer: *it reads, ++it moves. Each container decides what "next" means: the next box in a vector, the next node in a list, the next bigger key in a set.
The loop that uses all four moves:
for (auto it = c.begin(); it != c.end(); ++it)
cout << *it << " ";
Here it is on a vector, first by hand, then in a loop. The full type of a vector's iterator is vector<int>::iterator; auto lets the compiler work that out.
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> marks = {72, 95, 58, 88};
vector<int>::iterator it = marks.begin(); // the first seat
cout << "first: " << *it << endl; // look at it
++it; // step to the next
cout << "second: " << *it << endl;
for (auto it = marks.begin(); it != marks.end(); ++it)
cout << *it << " ";
cout << endl;
return 0;
}
Output:
first: 72
second: 95
72 95 58 88
Why end() is one past the last
If end() pointed at the last item, the loop would need a special case to also print it, and an empty container would have no sensible end(). With "one past the last":
- the loop condition is simply
it != c.end(); - an empty container has
begin() == end(), so the loop runs zero times; - the number of items in a range is
last - first(for vectors).
A range written [first, last) means: first is included, last is not.
Step 2: one loop, every container
The same loop on the set that refused [], and on a list:
#include <iostream>
#include <set>
#include <list>
using namespace std;
int main() {
set<int> marks = {72, 95, 58, 88, 95};
for (auto it = marks.begin(); it != marks.end(); ++it)
cout << *it << " ";
cout << endl;
list<string> queue = {"Asha", "Ravi", "Meena"};
for (auto it = queue.begin(); it != queue.end(); ++it)
cout << *it << " ";
cout << endl;
return 0;
}
Output:
58 72 88 95
Asha Ravi Meena
The set prints 58 72 88 95: sorted, and the repeated 95 stored once. The container decides how to step; the loop never changes.
Maps: it->first and it->second
Each item of a map is a pair (key, value). it->first is the key, it->second is the value (it->x is short for (*it).x).
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
map<string, int> marks = {{"Ravi", 58}, {"Asha", 95}, {"Meena", 88}};
for (auto it = marks.begin(); it != marks.end(); ++it)
cout << it->first << ": " << it->second << endl;
for (auto& [name, m] : marks) // the same loop, shorter
cout << name << " ";
cout << endl;
return 0;
}
Output:
Asha: 95
Meena: 88
Ravi: 58
Asha Meena Ravi
The second loop is the range-based for you've used for weeks. The compiler turns for (auto& x : c) into exactly the begin / != end / ++ loop. Every range-for was secretly using iterators; that's why it works on any container that has begin() and end(), and why it doesn't work on stack or queue (they have no iterators).
Step 3: two traps, and the kinds of iterators
Trap 1: writing it < c.end() instead of it != c.end():
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> marks = {72, 95, 58, 88};
for (auto it = marks.begin(); it < marks.end(); ++it)
cout << *it << " ";
return 0;
}
g++ says:
main.cpp:7:38: error: no match for ‘operator<’ (operand types are ‘std::_Rb_tree_const_iterator<int>’ and ‘std::set<int>::iterator’ {aka ‘std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator’})
In a tree, "is this node's position less than that one's?" has no cheap answer, so set iterators don't support <. Always write !=.
Trap 2: jumping with it + 2 on a list:
#include <iostream>
#include <list>
#include <iterator>
using namespace std;
int main() {
list<int> marks = {72, 95, 58, 88};
auto it = marks.begin();
cout << *(it + 2) << endl; // jump two seats?
return 0;
}
g++ says:
main.cpp:9:18: error: no match for ‘operator+’ (operand types are ‘std::_List_iterator<int>’ and ‘int’)
A list node only knows its neighbours. It can walk, but it can't jump.
The kinds of iterators
| Kind | Can do | Containers |
|---|---|---|
| Forward | ++it, *it, ==, != |
forward_list, unordered_map, unordered_set |
| Bidirectional | everything above, plus --it |
list, set, map, multiset, multimap |
| Random access | everything above, plus it + n, it - n, it2 - it1, <, it[n] |
vector, deque, array, plain arrays, string |
Random access works for vector, deque and arrays because their items sit in a row (or rows), so jumping n places is a quick calculation.
To move n steps on any kind, use next(it, n) and prev(it, n) from <iterator> (n defaults to 1). On a list they really walk n nodes (O(n)); on a vector they jump (O(1)).
#include <iostream>
#include <list>
#include <vector>
#include <iterator>
using namespace std;
int main() {
list<int> marks = {72, 95, 58, 88};
auto it = next(marks.begin(), 2); // walk two steps
cout << "list, 2 steps: " << *it << endl;
cout << "one back: " << *prev(it) << endl;
vector<int> v = {72, 95, 58, 88};
auto j = v.begin() + 2; // a vector can jump
cout << "vector, jump 2: " << *j << ", left: " << v.end() - j << endl;
return 0;
}
Output:
list, 2 steps: 58
one back: 95
vector, jump 2: 58, left: 2
Step 4: walking backwards, and read-only iterators
Reverse iterators: rbegin() and rend()
The principal wants a rank list, highest first. A set is sorted smallest first. No need to copy and reverse it: rbegin() points at the last item, and ++ on a reverse iterator walks backwards until rend() (one before the first).
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> marks = {72, 95, 58, 88};
cout << "Rank list: ";
for (auto it = marks.rbegin(); it != marks.rend(); ++it)
cout << *it << " ";
cout << endl;
return 0;
}
Output:
Rank list: 95 88 72 58
Changing items through an iterator
*it is the item itself, not a copy, so you can assign to it. Five grace marks for everyone:
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> marks = {72, 95, 58, 88};
for (auto it = marks.begin(); it != marks.end(); ++it)
*it = *it + 5; // grace marks
for (int m : marks) cout << m << " ";
cout << endl;
return 0;
}
Output:
77 100 63 93
const iterators: cbegin() and cend()
A report-printing function should never change marks. cbegin() / cend() give a const iterator: you can read through it, but not write.
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> marks = {72, 95, 58, 88};
for (auto it = marks.cbegin(); it != marks.cend(); ++it)
*it = *it + 5; // grace marks?
return 0;
}
g++ says:
main.cpp:8:13: error: assignment of read-only location ‘it.__gnu_cxx::__normal_iterator<const int*, std::vector<int> >::operator*()’
Rule of thumb: read with cbegin(), write with begin(). (Inside a function that takes const vector<int>& v, v.begin() already returns a const iterator.)
Step 5: erasing while you walk
New problem: remove every failed student (below 40) from 72, 35, 21, 88. The obvious way, erase as you meet them:
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> marks = {72, 35, 21, 88}; // below 40 = fail
for (auto it = marks.begin(); it != marks.end(); ++it)
if (*it < 40) marks.erase(it); // remove the fails
for (int m : marks) cout << m << " ";
cout << endl;
return 0;
}
Output:
72 21 88
21 is a fail, and it survived. Here's what happened, step by step:
| Step | it points at |
What the loop does |
|---|---|---|
| 1 | 72 | pass, ++it |
| 2 | 35 | fail: erase(it); 21 slides into this box; then ++it jumps over it |
| 3 | 88 | pass, ++it |
| 4 | end() |
stop |
Worse, after erase(it) the iterator it is invalidated: officially dead. Using it again (even ++it) is undefined behaviour. With a fail as the very last item, ++it can step past end() and the program can crash or loop forever. Iterators are also invalidated when a vector grows (push_back may move everything to a bigger block), so don't keep vector iterators across a push_back.
The fix: it = c.erase(it)
erase returns a fresh iterator to the item after the erased one. So:
- erased? take the returned iterator, and don't step;
- kept? step.
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> marks = {72, 35, 21, 88}; // below 40 = fail
for (auto it = marks.begin(); it != marks.end(); ) {
if (*it < 40) it = marks.erase(it); // the next seat
else ++it;
}
for (int m : marks) cout << m << " ";
cout << endl;
return 0;
}
Output:
72 88
This pattern works for vector, list, deque, map and set (all their erase functions return the next iterator). In episode 27 you'll see a one-line way for vectors: the erase-remove idiom.
Step 6: one function for every container
A TTE learns the job once and checks any train, and can be told "only coaches S3 to S7". Let's write one show function that takes any kind of iterator (a template, from episode 20) and works on a range [first, last):
#include <iostream>
#include <vector>
#include <list>
#include <set>
using namespace std;
template <typename It>
void show(It first, It last) {
for (It it = first; it != last; ++it)
cout << *it << " ";
cout << endl;
}
int main() {
vector<int> v = {72, 95, 58, 88};
list<string> l = {"Asha", "Ravi", "Meena"};
set<char> s = {'c', 'a', 'b'};
show(v.begin(), v.end());
show(l.begin(), l.end());
show(s.begin(), s.end());
show(v.begin() + 1, v.end() - 1); // just the middle
return 0;
}
Output:
72 95 58 88
Asha Ravi Meena
a b c
95 58
One function printed a vector, a list, a set, and just the middle of the vector (begin() + 1 to end() - 1: 95 and 58). This is exactly why the standard library's algorithms take two iterators, like sort(v.begin(), v.end()). They don't care which container they're working on; they only need a range. That's the next episode.
Common mistakes (and the real g++ messages)
| Mistake | What happens | Fix |
|---|---|---|
marks[i] on a set or list |
error: no match for ‘operator[]’ (operand types are ‘std::set<int>’ and ‘int’) |
walk it with an iterator or range-for |
it < s.end() on a set |
error: no match for ‘operator<’ (operand types are ‘std::_Rb_tree_const_iterator<int>’ and ...) |
it != s.end() |
it + 2 on a list |
error: no match for ‘operator+’ (operand types are ‘std::_List_iterator<int>’ and ‘int’) |
next(it, 2) |
*it = ... with cbegin() |
error: assignment of read-only location ... |
use begin() if you really mean to change it |
v.erase(it); then ++it |
compiles; skips items, undefined behaviour | it = v.erase(it); and don't step |
*v.end() |
compiles; undefined behaviour (reads past the last item) | v.back() or *prev(v.end()) (check not empty) |
Keeping a vector iterator across push_back |
compiles; may point at freed memory | get a fresh iterator after the vector changes |
Mini project: the attendance register
Students below 75% attendance may not sit the exam. A map keeps the register sorted by name; we print it, remove the detained students while walking (map::erase also returns the next iterator), and print the allowed list Z to A with a reverse iterator.
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
// attendance percentage of each student, kept sorted by name
map<string, int> attendance = {{"Ravi", 62}, {"Asha", 91}, {"Meena", 78}, {"Kiran", 70}, {"Dev", 85}};
cout << "Full register:" << endl;
for (auto it = attendance.begin(); it != attendance.end(); ++it)
cout << " " << it->first << " " << it->second << "%" << endl;
// below 75% may not sit the exam: remove them while walking
for (auto it = attendance.begin(); it != attendance.end(); ) {
if (it->second < 75) {
cout << "Detained: " << it->first << endl;
it = attendance.erase(it); // map::erase returns the next item too
} else {
++it;
}
}
cout << "Allowed, Z to A:";
for (auto it = attendance.rbegin(); it != attendance.rend(); ++it)
cout << " " << it->first;
cout << endl;
return 0;
}
Output:
Full register:
Asha 91%
Dev 85%
Kiran 70%
Meena 78%
Ravi 62%
Detained: Kiran
Detained: Ravi
Allowed, Z to A: Meena Dev Asha
Practice
- Print a
list<string>of browser pages backwards withrbegin()andrend(). - Find the second smallest item of a
set<int>usingnext(). - Remove every even number from a
list<int>usingit = erase(it). - Write a template
count_above(first, last, x)that counts items greater thanxin any range.
Solutions
1. A reverse iterator starts at the last item and ++ walks backwards.
#include <iostream>
#include <list>
#include <string>
using namespace std;
int main() {
list<string> pages = {"home", "search", "product", "cart"};
for (auto it = pages.rbegin(); it != pages.rend(); ++it)
cout << *it << " ";
cout << endl;
return 0;
}
Output:
cart product search home
2. A set is sorted, so the second item is the second smallest. Repeats are stored once, so 58 appears only once.
#include <iostream>
#include <set>
#include <iterator>
using namespace std;
int main() {
set<int> marks = {72, 95, 58, 88, 58};
if (marks.size() >= 2)
cout << "second smallest: " << *next(marks.begin()) << endl;
return 0;
}
Output:
second smallest: 72
3. Erase: take the returned iterator. Keep: step.
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> nums = {1, 2, 4, 5, 6, 7, 8};
for (auto it = nums.begin(); it != nums.end(); ) {
if (*it % 2 == 0) it = nums.erase(it); // erase: don't step
else ++it; // keep: step
}
for (int n : nums) cout << n << " ";
cout << endl;
return 0;
}
Output:
1 5 7
4. Two template parameters: the iterator type and the value type. It works on any range, even part of a vector.
#include <iostream>
#include <vector>
#include <set>
using namespace std;
template <typename It, typename T>
int count_above(It first, It last, T x) {
int c = 0;
for (It it = first; it != last; ++it)
if (*it > x) c++;
return c;
}
int main() {
vector<int> marks = {72, 95, 58, 88};
set<double> prices = {9.5, 120.0, 49.99};
cout << count_above(marks.begin(), marks.end(), 70) << endl;
cout << count_above(prices.begin(), prices.end(), 10.0) << endl;
cout << count_above(marks.begin() + 2, marks.end(), 70) << endl;
return 0;
}
Output:
3
2
1
Quick quiz
What does this print?
vector<int> v = {10, 20, 30, 40};
auto it = v.begin();
it += 2;
cout << *it << " " << *(it - 1) << " "
<< v.end() - it;
Answer
30 20 2. it starts at 10; += 2 jumps to 30 (a vector iterator is random access). *(it - 1) is 20. From 30 up to end() there are two items, 30 and 40, so v.end() - it is 2.
Interview questions
- What is an iterator? An object that points at a position in a container and can move to the next position; it gives every container the same interface (
*,++,==,!=), so algorithms can work on all of them. - Why is
end()one past the last element? So the loop condition is justit != end(), empty ranges havebegin() == end(), andlast - firstis the number of items. Ranges are half-open:[first, last). - Name the iterator categories. Input, output, forward, bidirectional, random access (and contiguous since C++20). Each one adds operations to the one before.
- Why can't you use
std::sorton astd::list?sortneeds random access iterators; list iterators are bidirectional. Uselist::sort(). - What is iterator invalidation? After some operations an iterator no longer points at valid memory:
eraseinvalidates the erased position (and, in a vector, everything after it); a vector reallocation onpush_backinvalidates all of its iterators. Using an invalid iterator is undefined behaviour. - How do you erase elements while iterating?
it = c.erase(it);when erasing,++itotherwise. For vectors, prefer the erase-remove idiom. iteratorvsconst_iterator? Aconst_iterator(cbegin()) can read but not modify the element.- How does range-based for work? It is rewritten as
for (auto it = begin(c); it != end(c); ++it) { auto& x = *it; ... }. next(it, n)vsit + n?nextworks on every iterator kind (walking n steps on a list);+ nonly on random access iterators.
Glossary
| Term | Meaning, with an example |
|---|---|
| iterator | An object that remembers a position in a container and can move to the next one, like a TTE walking a train: auto it = marks.begin(); |
begin() |
An iterator to the first item. |
end() |
An iterator one past the last item; a stop sign, never read through it. |
*it (dereference) |
The item the iterator points at: cout << *it; |
++it |
Move the iterator to the next item. |
it->first, it->second |
The key and value of a map item; it->x means (*it).x. |
range [first, last) |
All items from first up to but not including last. |
| range-based for | for (auto x : c), which the compiler turns into a begin/end iterator loop. |
| forward iterator | Can only move forward (++): unordered_map, forward_list. |
| bidirectional iterator | Can move forward and back (++, --): list, set, map. |
| random access iterator | Can also jump (+ n, - n, <): vector, deque, arrays. |
next(it, n), prev(it, n) |
Return an iterator n steps forward / back; work on every kind (<iterator>). |
| reverse iterator | Walks backwards: rbegin() is the last item, rend() is one before the first. |
| const iterator | Read-only iterator from cbegin() / cend(); *it = 5 won't compile. |
| invalidated iterator | An iterator that no longer points at a valid item, e.g. after erase(it); using it is undefined behaviour. |
| undefined behaviour | Code whose result C++ doesn't define, like reading *v.end(): it may print garbage or crash. |
| template | A function written once for any type: template <typename It> void show(It first, It last). |
set |
A sorted container without repeats, stored as a tree (episode 23). |
list |
A chain of nodes; fast insert/erase anywhere, no index (episode 22). |
Summary
marks[i]failed on asetbecause a tree (and a list) has no box numbers. You have to walk it.- An iterator walks any container with four moves:
begin(),*it,++it, and stop atend(), which is one past the last. - One loop,
for (auto it = c.begin(); it != c.end(); ++it), works on vector, list, set and map; range-for is this loop. - Iterators come in kinds: forward, bidirectional, random access. Use
!=, not<; usenext()to walk,+ nonly on random access. rbegin()/rend()walk backwards;cbegin()/cend()are read-only.eraseinvalidates the iterator: writeit = c.erase(it);and step only when you keep the item.- A template taking
[first, last)works on any part of any container. That is how the standard algorithms are built.
Next episode: the standard library already has over a hundred functions like show, ready-made: sort, find, count, accumulate and more. STL algorithms.