SyntaxPilot
Courses/C++/Lesson 26

C++ · Lesson 26 of 40 · 11 min

Iterators

queued

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

  1. Print a list<string> of browser pages backwards with rbegin() and rend().
  2. Find the second smallest item of a set<int> using next().
  3. Remove every even number from a list<int> using it = erase(it).
  4. Write a template count_above(first, last, x) that counts items greater than x in 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

  1. 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.
  2. Why is end() one past the last element? So the loop condition is just it != end(), empty ranges have begin() == end(), and last - first is the number of items. Ranges are half-open: [first, last).
  3. Name the iterator categories. Input, output, forward, bidirectional, random access (and contiguous since C++20). Each one adds operations to the one before.
  4. Why can't you use std::sort on a std::list? sort needs random access iterators; list iterators are bidirectional. Use list::sort().
  5. What is iterator invalidation? After some operations an iterator no longer points at valid memory: erase invalidates the erased position (and, in a vector, everything after it); a vector reallocation on push_back invalidates all of its iterators. Using an invalid iterator is undefined behaviour.
  6. How do you erase elements while iterating? it = c.erase(it); when erasing, ++it otherwise. For vectors, prefer the erase-remove idiom.
  7. iterator vs const_iterator? A const_iterator (cbegin()) can read but not modify the element.
  8. How does range-based for work? It is rewritten as for (auto it = begin(c); it != end(c); ++it) { auto& x = *it; ... }.
  9. next(it, n) vs it + n? next works on every iterator kind (walking n steps on a list); + n only 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 a set because 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 at end(), 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 <; use next() to walk, + n only on random access.
  • rbegin()/rend() walk backwards; cbegin()/cend() are read-only.
  • erase invalidates the iterator: write it = 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.