Iterators: A Position That Knows How to Move

Kenji reads the water level of the school's rain tank every hour and keeps the readings in a vector<int>. His function printGaps(v) prints how much the level changed each hour, with v[i] - v[i - 1]. Maria wants the same report for her own tank. Her log takes late readings in the middle, so she keeps it in a std::list, and her very first l[1] stops GCC 12. Does every container need its own copy of the function?

One function for a vector and a list

Maria's first try is Kenji's index read on her list<int> l: cout << l[1] - l[0];. It stops with an error at the runner's flags, once for each index: error: no match for 'operator[]' (operand types are 'std::__cxx11::list<int>' and 'int'). A list has no [], because it cannot jump to position 1 without walking there. What both containers do have is an iterator: a position that can read the element there and move on to the next one.

So Kenji rewrites printGaps to take two iterators, first and last, instead of a vector. The line template <typename It> lets It be any iterator type. The compiler then writes one copy for the vector's iterators and one for the list's. Module 1 lesson 05 showed the idea, and this track writes only this small form of it.

#include <iostream>
#include <iterator>
#include <list>
#include <vector>
using namespace std;

template <typename It>
void printGaps(It first, It last) {
    cout << "gaps:";
    if (first != last) {
        It before = first;
        ++first;
        while (first != last) {
            cout << ' ' << *first - *before;
            before = first;
            ++first;
        }
    }
    cout << '\n';
}

int main() {
    vector<int> kenji{12, 15, 11, 18, 18};
    list<int> maria{12, 15, 11, 18, 18};
    maria.insert(next(maria.begin(), 2), 20);
    printGaps(kenji.begin(), kenji.end());
    printGaps(maria.begin(), maria.end());
    return 0;
}

gaps: 3 -4 7 0
gaps: 3 5 -9 7 0

Inside, the function only compares two iterators with !=, reads with * and steps with ++. Both containers offer those three moves, so the same text compiled for both. Maria's list took 20 in the middle, and her gaps changed with it. So a function written over two iterators serves every container that can walk.

begin() and end() on three shapes of memory

Module 0 lesson 04 met the walk. begin() is the first element, end() is the empty slot one past the last, and the loop runs while it != end(). Together they make the half-open range [begin, end), which any algorithm takes from any container. What changes from container to container is the memory under the walk. The widget plays one loop over the same four values in three containers, five stops each.

The vector keeps its four values side by side in one block, so ++ moves to the next address. The deque keeps fixed-size blocks. The drawing uses blocks of 2, but GCC 12's real block holds 128 ints, so ++ hops to a new block only at a block's edge. Every list node is a separate allocation, wherever free memory happened to be, so ++ follows a link. A program on Compiler Explorer printed the same walk, 12 15 11 18 and then end(), for all three.

So the loop reads the same everywhere, but one ++ is a different move in each container. That difference decides which moves an iterator offers.

Five categories: what an iterator can do

The C++ standard sorts iterators into five categories by the moves they offer. Each container's iterator belongs to one of them. GCC 12 reports it through std::iterator_traits, a lookup that lesson 02 runs. This is the table to keep.

"Except keys" means a set's elements and a map's keys stay read-only, as Modules 8 and 10 showed; a map's value can still be written. One pass means each value is gone once the iterator moves on: a number read from the keyboard cannot be read again. Read the table from the bottom up. A random access iterator does everything, and each row above it gives something up.

The boxes nest because each category can do everything the one inside it can. So std::find, which needs only an input iterator, takes any container. std::sort asks for random access, so a list cannot use it and sorts itself instead, as Module 5 showed. A plain pointer is random access too, which is why a C array works with every algorithm.

#include <forward_list>
#include <iostream>
#include <iterator>
#include <list>
#include <vector>
using namespace std;

int main() {
    cout << contiguous_iterator<vector<int>::iterator> << ' '
         << random_access_iterator<vector<int>::iterator> << ' '
         << random_access_iterator<list<int>::iterator> << ' '
         << bidirectional_iterator<list<int>::iterator> << ' '
         << bidirectional_iterator<forward_list<int>::iterator> << '\n';
    return 0;
}

1 1 0 1 0

The four ends: begin, end, rbegin and rend

A container that can walk backwards gives two more ends. rbegin() is a reverse iterator on the last element, and rend() is the empty slot before the first. A reverse iterator turns ++ around, so each ++ moves one element towards the front. The backward loop is the forward loop with an r in front of two names.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v{12, 15, 11, 18};
    cout << "*begin() " << *v.begin() << ", *rbegin() " << *v.rbegin() << '\n';
    cout << "forward: ";
    for (auto it = v.begin(); it != v.end(); ++it) {
        cout << ' ' << *it;
    }
    cout << "\nbackward:";
    for (auto it = v.rbegin(); it != v.rend(); ++it) {
        cout << ' ' << *it;
    }
    cout << '\n';
    cout << "end() - begin() = " << v.end() - v.begin() << ", rend() - rbegin() = " << v.rend() - v.rbegin() << '\n';
    return 0;
}

*begin() 12, *rbegin() 18
forward:  12 15 11 18
backward: 18 11 15 12
end() - begin() = 4, rend() - rbegin() = 4

*rbegin() read 18, the last value, and the backward walk stopped at rend() without reading it. Both ranges hold four elements: rend() - rbegin() is 4, like end() - begin(). Every container with a bidirectional or random access iterator has rbegin(). A forward_list has none: GCC 12 says error: 'class std::forward_list<int>' has no member named 'rbegin'; did you mean 'begin'?, and an unordered_set gets the same answer. So walk backwards with rbegin() and rend(), and keep != as the test.

cbegin(): a walk that only reads

cbegin() and cend() are begin() and end() for a walk that promises not to write. They return a const_iterator, which reads *it but refuses *it = x. crbegin() and crend() make the same promise backwards. Use them when a loop only looks, and the compiler will hold you to it. Example 3 below shows the refusal in GCC 12's words.

What a list iterator refuses

A list iterator is bidirectional: it steps with ++ and --, one link at a time. It has no + n and no <, because neither is a single step along a link. GCC 12 refuses l.begin() + 2 and it < l.end(), and mistakes 2 and 3 quote its messages. Move k steps with std::next(it, k) instead, and end every loop with !=.

#include <iostream>
#include <iterator>
#include <list>
using namespace std;

int main() {
    list<int> l{12, 15, 11, 18};
    auto third = next(l.begin(), 2);
    cout << "third: " << *third << '\n';
    --third;
    cout << "one back: " << *third << '\n';
    int steps = 0;
    for (auto it = l.begin(); it != l.end(); ++it) {
        steps++;
    }
    cout << "steps to end(): " << steps << '\n';
    return 0;
}

third: 11
one back: 15
steps to end(): 4

next(l.begin(), 2) followed two links to 11, and --third stepped back to 15. The loop with != took four steps to reach end(). On a vector, next jumps in one move, while on a list it walks; lesson 02 measures the difference. So write next and !=, and the same code runs on every container.

When an iterator stops being valid

An iterator is only a position. If the container moves its elements, a saved iterator still points at the old place, and it is invalidated. Reading through it is undefined behaviour: the C++ standard promises nothing about what happens. A vector moves everything when it outgrows its block, as Module 2 showed. This program fills a vector up to its capacity of 4, then adds a fifth value.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v;
    v.reserve(4);
    for (int x : {10, 20, 30, 40}) v.push_back(x);
    const int* before = v.data();
    cout << "size " << v.size() << ", capacity " << v.capacity() << '\n';
    v.push_back(50);
    cout << "size " << v.size() << ", capacity " << v.capacity() << '\n';
    cout << "first element moved: " << (v.data() != before) << '\n';
    return 0;
}

size 4, capacity 4
size 5, capacity 8
first element moved: 1

The fifth value did not fit, so the vector took a new block of 8, moved all four values over and freed the old block. An iterator saved before push_back(50) still points into that freed block. Nothing warns you, and the program may even print the old value by luck. So after anything that may grow a vector, take fresh iterators from begin(). Lesson 02 gives the rules for every container, and lesson 05 replays the move step by step.

The syntax you need on day one

c.begin()    c.end()          the first element, and the empty slot past the last
c.rbegin()   c.rend()         the last element, and the empty slot before the first
c.cbegin()   c.cend()         begin and end for a walk that only reads
*it                           the element it points at (never *c.end())
++it                          one step forward, on every container
--it                          one step back (not forward_list, not unordered)
it != c.end()                 the loop test that works on every container
next(it, k)   prev(it, k)     a copy of it moved k steps forward or back

template <typename It>
void f(It first, It last)     one function for any container's range

So one loop shape, begin() to end() with != and ++, walks every container on this track.

#include <iostream>
#include <iterator>
#include <list>
#include <string>
#include <vector>
using namespace std;

template <typename It>
void printAll(It first, It last) {
    cout << '[';
    for (It it = first; it != last; ++it) {
        if (it != first) {
            cout << ", ";
        }
        cout << *it;
    }
    cout << "]\n";
}

int main() {
    vector<int> marks{4, 8, 15};
    list<string> snacks{"tea", "bun", "jam"};
    printAll(marks.begin(), marks.end());
    printAll(snacks.begin(), snacks.end());
    printAll(next(snacks.begin()), snacks.end());
    printAll(marks.end(), marks.end());
    return 0;
}

[4, 8, 15]
[tea, bun, jam]
[bun, jam]
[]

#include <iostream>
#include <iterator>
#include <list>
#include <string>
using namespace std;

int main() {
    list<string> history{"home", "news", "maps", "mail"};
    history.push_back("music");
    cout << "newest first:\n";
    int n = 1;
    for (auto it = history.rbegin(); it != history.rend(); ++it) {
        cout << n << ". " << *it << '\n';
        n++;
    }
    cout << "now on " << *history.rbegin() << ", Back goes to " << *next(history.rbegin()) << '\n';
    return 0;
}

newest first:
1. music
2. mail
3. maps
4. news
5. home
now on music, Back goes to mail

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> price{120, 45, 80, 300, 60};
    int total = 0;
    int over100 = 0;
    for (auto it = price.cbegin(); it != price.cend(); ++it) {
        total += *it;
        if (*it > 100) {
            over100++;
        }
    }
    cout << "total " << total << ", over 100: " << over100 << '\n';
    cout << "first price still " << price[0] << '\n';
    return 0;
}

total 605, over 100: 2
first price still 120

list<int> l{12, 15, 11, 18};
cout << l[1] - l[0] << '\n';

list<int> l{12, 15, 11, 18};
auto it = l.begin() + 2;

for (auto it = l.begin(); it < l.end(); ++it) {
    cout << *it << ' ';
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v{10, 20, 30, 40};
    cout << *v.rbegin() << ' ' << (v.rbegin().base() == v.end()) << '\n';
    return 0;
}

#include <deque>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Every height until the input ends: lesson 02 explains this line.
    vector<int> height(istream_iterator<int>(cin), {});

    deque<int> view;   // the positions with a sea view, west to east
    // Walk from the sea end with a reverse iterator and keep the tallest
    // height seen so far. A building taller than all of them has the view:
    // put its position, counted from 1, at the front of view.

    cout << view.size() << '\n';
    // Print the positions in view, separated by single spaces.
    return 0;
}

#include <iostream>
#include <iterator>
#include <list>
#include <string>
using namespace std;

int main() {
    string line;
    cin >> line;
    list<char> days(line.begin(), line.end());   // one letter per day

    // Walk days with an iterator. For every run of equal letters, print the
    // letter and the length of the run, the runs separated by single spaces.

    return 0;
}

#include <cstdlib>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;

int main() {
    int n, d;
    cin >> n >> d;
    vector<int> readings(n);
    for (int& x : readings) {
        cin >> x;
    }

    // Walk readings with an iterator. Between two neighbours that differ by
    // more than d, insert their average (their sum divided by 2, rounded
    // down). A value you inserted is never compared again. Then print
    // readings on one line, separated by single spaces.

    return 0;
}

Next, lesson 02 takes every iterator operation one by one, with what it costs on each category.