The standard library has roughly 15 containers and roughly 100 algorithms. Writing each algorithm for each container would be 1500 functions.

It is not. There are about 100, because algorithms do not take containers — they take iterators.

The idea

#include <iostream>
#include <list>
#include <vector>

// One function, any container — because it takes iterators, not a container.
template <typename Iterator>
void print_range(Iterator first, Iterator last) {
    for (Iterator it = first; it != last; ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";
}

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    std::list<int> l = {10, 20, 30};
    int raw[] = {100, 200};

    print_range(v.begin(), v.end());
    print_range(l.begin(), l.end());
    print_range(raw, raw + 2);          // a pointer is an iterator

    // Half of a vector.
    print_range(v.begin(), v.begin() + 3);
    return 0;
}

1 2 3 4 5 
10 20 30 
100 200 
1 2 3

One function, four completely different sources. A std::vector stores its elements contiguously; a std::list scatters them across the heap with pointers between them; a raw array is neither class. print_range does not know or care.

The last call is the one that shows the real payoff: a range is not a container. v.begin() to v.begin() + 3 is the first half of a vector, and every algorithm in the library accepts it.

What an iterator is

An iterator is anything that behaves like a pointer. Concretely, an iterator supports:

| Operation | Meaning | |---|---| | *it | the element it refers to | | ++it | move to the next one | | it != other | are these two different positions | | it = other | copyable and assignable |

That is the whole minimum. A raw pointer satisfies all four, which is why print_range(raw, raw+2) works — and it is not a coincidence. Iterators were designed by generalising the pointer.

Half-open ranges

end() points one past the last element, not at it. Dereferencing end() is undefined behaviour.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {10, 20, 30, 40, 50};

    auto it = v.begin();
    std::cout << *it << "\n";           // dereference
    ++it;                               // advance
    std::cout << *it << "\n";

    // end() is one PAST the last element. Dereferencing it is undefined.
    std::cout << "distance: " << (v.end() - v.begin()) << "\n";
    std::cout << "last element: " << *(v.end() - 1) << "\n";

    // The half-open range [begin, end) makes the empty case work without
    // a special check: begin == end means empty.
    std::vector<int> empty;
    std::cout << "empty is empty: " << std::boolalpha
              << (empty.begin() == empty.end()) << "\n";

    // Writing through an iterator.
    for (auto i = v.begin(); i != v.end(); ++i) {
        *i += 1;
    }
    for (int x : v) {
        std::cout << x << " ";
    }
    std::cout << "\n";

    // A const_iterator cannot write.
    for (auto i = v.cbegin(); i != v.cend(); ++i) {
        std::cout << *i << " ";
        // *i = 0;   // would not compile
    }
    std::cout << "\n";

    // Reverse iterators walk backwards with the same ++.
    for (auto i = v.rbegin(); i != v.rend(); ++i) {
        std::cout << *i << " ";
    }
    std::cout << "\n";
    return 0;
}

10
20
distance: 5
last element: 50
empty is empty: true
11 21 31 41 51 
11 21 31 41 51 
51 41 31 21 11

The half-open convention [begin, end) looks arbitrary and is not. Three things fall out of it:

• end - begin is the size. With an inclusive end it would be end - begin + 1.
• Empty needs no special case. begin == end means empty, with no off-by-one.
• Ranges compose. The end of one range is the beginning of the next, exactly.

The same convention appears in Python slices and half-open intervals in mathematics, for the same reasons.

Note rbegin()/rend(): a reverse iterator walks backwards, but you still write ++. The direction is in the iterator's type, not at the call site, so the same algorithm sorts forwards or backwards depending on which iterators you hand it.

The four flavours a container gives you

| Member | Returns | Can write? | |---|---|---| | begin() / end() | iterator | yes | | cbegin() / cend() | const_iterator | no | | rbegin() / rend() | reverse_iterator | yes, backwards | | crbegin() / crend() | const_reverse_iterator | no, backwards |

Calling begin() on a const container gives you a const_iterator anyway. The explicit c versions exist for when the container is not const but you want to promise you will not write — which is worth doing, because the compiler then enforces it.

Range-for is iterators

for (int x : v) { ... }

is, near enough, this:

// {
//     auto __first = v.begin();
//     auto __last  = v.end();
//     for (; __first != __last; ++__first) {
//         int x = *__first;
//         ...
//     }
// }

Which is why range-for works on anything with begin() and end() — including your own types:

#include <cstddef>
#include <iostream>

// A minimal container with a minimal iterator, to show what range-for needs.
class Countdown {
    int start;

public:
    explicit Countdown(int s) : start(s) {}

    class Iterator {
        int value;

    public:
        explicit Iterator(int v) : value(v) {}

        int operator*() const { return value; }
        Iterator& operator++() { --value; return *this; }
        bool operator!=(const Iterator& other) const { return value != other.value; }
    };

    Iterator begin() const { return Iterator(start); }
    Iterator end() const { return Iterator(0); }
};

int main() {
    // range-for needs exactly: begin(), end(), operator*, operator++, operator!=
    for (int n : Countdown(5)) {
        std::cout << n << " ";
    }
    std::cout << "\n";
    return 0;
}

5 4 3 2 1

Countdown stores nothing and owns nothing. Its "iterator" is an int that counts down. Yet range-for accepts it, because range-for asks for behaviour, not for a container.

That is the whole design in one example: the library is built on what a type can do, not on what it is.

Iterator invalidation

An iterator points into a container's storage. If the container moves that storage, the iterator is left pointing at freed memory — a dangling pointer (lesson 8.5) by another name.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3};
    v.reserve(3);
    std::cout << "capacity " << v.capacity() << "\n";

    auto it = v.begin();
    std::cout << "before: " << *it << "\n";

    v.push_back(4);        // capacity exceeded: reallocates, invalidating `it`

    // Reading *it now is a use-after-free. ASan reports:
    //   heap-use-after-free ... READ of size 4
    std::cout << "size " << v.size() << " capacity " << v.capacity() << "\n";
    return 0;
}

capacity 3
before: 1
size 4 capacity 6

Add std::cout << *it after the push_back and build with -fsanitize=address:

==5600==ERROR: AddressSanitizer: heap-use-after-free on address 0x502000000010
READ of size 4 at 0x502000000010 thread T0
    #0 ... in main invalidation.cpp:16

This is Module 11's tooling meeting Module 13's content. The bug is invisible without a sanitizer — the plain build printed a plausible-looking number.

Which operations invalidate what:

| Container | Invalidated by | |---|---| | vector | any reallocation (push_back, insert, resize); erase invalidates from the erase point on | | deque | insert or erase anywhere invalidates all iterators | | list, forward_list | only iterators to the erased element | | map, set | only iterators to the erased element | | unordered_map, unordered_set | rehashing invalidates all iterators |

The pattern: node-based containers are stable, contiguous ones are not. That is a real reason to choose std::list or std::map occasionally, despite their worse cache behaviour (lesson 13.12).

The safe habits are to not hold an iterator across a modification, and to use the return value of erase, which is the iterator to the next element:

// for (auto it = v.begin(); it != v.end(); ) {
//     if (should_remove(*it)) {
//         it = v.erase(it);      // erase returns the next valid iterator
//     } else {
//         ++it;
//     }
// }

Try it

Checkpoint

• Algorithms take iterators, not containers — which is why 100 algorithms cover 15 containers.
• An iterator is anything supporting *it, ++it, it != other, and copying.
• A raw pointer is an iterator; iterators were designed by generalising the pointer.
• end() is one past the last element; dereferencing it is undefined.
• Half-open ranges make size a subtraction, empty a comparison, and ranges composable.
• cbegin/cend give read-only iterators; rbegin/rend walk backwards with the same ++.
• Range-for works on anything with begin() and end(), including your own types.
• Modifying a container can invalidate its iterators — a dangling pointer under another name.
• Node-based containers (list, map) are stable; contiguous ones (vector) are not.
• erase returns the next valid iterator; use it rather than guessing.