Iterators and ranges basics

An iterator is a position in a sequence plus the operations to move it and read through it. Every standard algorithm is written against what an iterator can do, not against a container — which is why the same std::ranges::find works on a vector, a list, a string_view, or your own linked list. This lesson is about that contract: the categories, how to satisfy them for your own type, and the C++20 ranges layer on top (sentinels, projections, dangling protection, views).

1. Categories: what an iterator promises

Each category adds guarantees to the one before:

C++20 expresses these as concepts — std::input_iterator, std::forward_iterator, … std::contiguous_iterator — and the range versions std::ranges::forward_range etc. An algorithm's signature says what it needs; pass something weaker and you get a compile error instead of a slow or wrong program:

#include <algorithm>
#include <list>

int main() {
    std::list<int> l{3, 1, 2};
    std::ranges::sort(l);  // sort needs random access; list is bidirectional
}

(std::list has a member l.sort() for exactly this reason.)

2. Half-open ranges

A range is [first, last): first is the first element, last is one past the end and is never dereferenced. Half-open ranges make the empty range trivial (first == last), make the length last - first, and let you split [a, c) into [a, b) and [b, c) with no ±1 fiddling. end() is a position, not an element.

3. What range-for really does

for (auto& x : r) body;
// is (roughly)
{
    auto&& __r = r;
    auto __first = std::ranges::begin(__r);   // member begin() or ADL begin(r)
    auto __last  = std::ranges::end(__r);     // may be a *different type* (a sentinel)
    for (; __first != __last; ++__first) {
        auto& x = *__first;
        body;
    }
}

So a type works in range-for as soon as it has begin()/end() returning things you can compare with !=, increment with prefix ++, and dereference. Since C++17, begin and end may return different types — that's what makes sentinels possible.

Invalidation recap. The loop holds __first and __last for the whole loop. Anything in body that invalidates them — push_back on a vector that reallocates, erase of the current element — is undefined behaviour. Use std::erase_if, or an index loop, when you need to modify the container.

4. Writing a forward iterator

std::forward_iterator<I> requires, in practice:

• using value_type = …; using difference_type = std::ptrdiff_t;
• *it returning a reference (reference is deduced from operator*)
• prefix ++it returning I&, postfix it++ returning the old value as I
• == between iterators (!= comes for free in C++20)
• default-constructible and copyable — the concept checks this

Here's a worked example: an iterator over the integers [lo, hi) that never stores them.

#include <algorithm>
#include <cstddef>
#include <iterator>
#include <print>

class Count {
public:
    class iterator {
    public:
        using value_type = int;
        using difference_type = std::ptrdiff_t;

        iterator() = default;                       // required by forward_iterator
        explicit iterator(int v) : v_(v) {}

        int operator*() const { return v_; }        // a prvalue is fine for value-like ranges
        iterator& operator++() { ++v_; return *this; }
        iterator operator++(int) { iterator old = *this; ++*this; return old; }
        bool operator==(const iterator&) const = default;

    private:
        int v_ = 0;
    };

    Count(int lo, int hi) : lo_(lo), hi_(hi) {}
    iterator begin() const { return iterator{lo_}; }
    iterator end() const { return iterator{hi_}; }

private:
    int lo_, hi_;
};

static_assert(std::forward_iterator<Count::iterator>);

int main() {
    Count c{3, 8};
    for (int x : c) std::print("{} ", x);
    std::println("");
    std::println("count of evens: {}", std::ranges::count_if(c, [](int x) { return x % 2 == 0; }));
    std::println("found 6? {}", std::ranges::find(c, 6) != c.end());
}

Things to notice:

• Postfix ++ returns the old copy. *it++ must read the element before advancing. Writing ++*this; return *this; passes simple loops and breaks every algorithm that relies on it.
• operator== is defaulted. Two iterators are equal when they are at the same position. For a linked list, that means "same node pointer"; the end iterator is the null node.
• static_assert the concept next to your class. When it fails, GCC tells you which requirement is missing — much better than a failure deep inside <algorithm>.

For a container that hands out references (int&), operator* returns int&, and you usually want a second const_iterator that returns const int& so const containers can be iterated.

Faded example — your turn

Countdown{n} should yield n, n-1, …, 1. Fill in the iterator's three missing pieces. What should end() hold?

class Countdown {
public:
    class iterator {
    public:
        using value_type = int;
        using difference_type = std::ptrdiff_t;
        iterator() = default;
        explicit iterator(int v) : v_(v) {}
        int operator*() const { return /* ??? */; }
        iterator& operator++() { /* ??? */ return *this; }
        iterator operator++(int) { iterator old = *this; ++*this; return old; }
        bool operator==(const iterator&) const = default;
    private:
        int v_ = 0;
    };
    explicit Countdown(int n) : n_(n) {}
    iterator begin() const { return iterator{n_}; }
    iterator end() const { return iterator{/* ??? */}; }
private:
    int n_;
};

5. Sentinels: "end" doesn't have to be an iterator

Some sequences don't know where they end until they get there: a C string ends at '\0', input ends at EOF. Rather than scanning first to build an end iterator, C++20 lets end() return a sentinel — a different type that compares equal to an iterator when the iterator has reached the end:

#include <algorithm>
#include <iterator>
#include <print>

// Iterate ints until (not including) the first negative value.
struct NegativeSentinel {
    friend bool operator==(const int* it, NegativeSentinel) { return *it < 0; }
};

struct UntilNegative {
    const int* p;
    const int* begin() const { return p; }
    NegativeSentinel end() const { return {}; }
};

static_assert(std::sentinel_for<NegativeSentinel, const int*>);

int main() {
    int data[] = {4, 8, 15, -1, 16, 23};
    UntilNegative r{data};
    for (int x : r) std::print("{} ", x);
    std::println("");
    std::println("distance = {}", std::ranges::distance(r));
}

One operator==(iterator, sentinel) is enough: C++20 synthesises the reversed and != forms. Classic algorithms like std::find(first, last, x) need both arguments to be the same type, so sentinel ranges only work with the std::ranges:: versions.

6. std::ranges algorithms

The std::ranges:: algorithms take a whole range, check the iterator category with concepts, accept sentinels, and add two useful features.

Projections apply a function to each element before comparing — no lambda boilerplate for "sort by member":

#include <algorithm>
#include <print>
#include <string>
#include <vector>

struct Person {
    std::string name;
    int age;
};

int main() {
    std::vector<Person> people{{"ada", 36}, {"alan", 41}, {"grace", 30}};
    std::ranges::sort(people, {}, &Person::age);                 // compare ages with std::less
    for (const auto& p : people) std::print("{} ", p.name);
    std::println("");
    auto oldest = std::ranges::max_element(people, {}, &Person::age);
    std::println("oldest: {}", oldest->name);
}

Dangling protection. If you pass a temporary range to an algorithm that returns an iterator, the iterator would point into a destroyed object. Instead of silently returning it, std::ranges returns std::ranges::dangling, which can't be dereferenced — a compile error at the point of misuse:

#include <algorithm>
#include <vector>

std::vector<int> make() { return {1, 2, 3}; }

int main() {
    auto it = std::ranges::find(make(), 2);  // it is std::ranges::dangling
    return *it;                              // error: no operator*
}

Views like std::span and std::string_view are borrowed ranges — their iterators don't point into the view object itself — so passing a temporary view is fine.

7. A first look at views

A view is a lazy, cheap-to-copy range that adapts another range. They compose with |:

#include <print>
#include <ranges>

int main() {
    auto odd_squares = std::views::iota(1)                       // 1, 2, 3, … (infinite)
                     | std::views::filter([](int x) { return x % 2 == 1; })
                     | std::views::transform([](int x) { return x * x; })
                     | std::views::take(5);
    for (int x : odd_squares) std::print("{} ", x);
    std::println("");
}

Nothing is computed until you iterate, and the infinite iota is fine because take(5) stops after five elements. Order matters: take before filter takes five candidates, not five results. Views work on your own containers too, as long as they model the right range concept — which is why making a proper forward iterator pays off. (Pipelines in depth — views::concat, to, caching gotchas — are Level 7.)

Summary

• Algorithms are written against iterator categories; the concepts make mismatches a compile error.
• Ranges are half-open; end() is a position, never dereferenced.
• Range-for is begin/end/!=/++/* — modifying the container inside can invalidate the hidden iterators.
• A forward iterator needs value_type, difference_type, *, prefix and postfix-returning-the-old-value ++, ==, and a default constructor. static_assert(std::forward_iterator<It>) next to it.
• Sentinels let end() be a different type; use them with std::ranges::.
• std::ranges adds projections and dangling protection; views are lazy and compose with |.