Step 3 of 5

Iterator concepts and algorithms

Standard algorithms need to know what kind of iterator they're given. Can it go backwards? Jump ahead by 100 in one step? The answers decide which algorithms are allowed and how fast they are. The main categories:

C++20 checks these with concepts such as std::forward_iterator<It>. For your iterator to qualify as a forward iterator, it must declare a few member types and support a couple more operations:

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <iterator>

class Evens {                           // 0, 2, 4, ... below a limit
public:
    explicit Evens(int limit) : limit_(limit) {}

    class Iterator {
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = int;
        using difference_type = std::ptrdiff_t;

        Iterator() = default;                          // required: default constructible
        explicit Iterator(int v) : v_(v) {}
        int operator*() const { return v_; }
        Iterator& operator++() { v_ += 2; return *this; }
        Iterator operator++(int) { Iterator old = *this; ++*this; return old; }   // it++
        bool operator==(const Iterator& o) const { return v_ == o.v_; }

    private:
        int v_ = 0;
    };

    Iterator begin() const { return Iterator(0); }
    Iterator end() const { return Iterator(limit_ % 2 == 0 ? limit_ : limit_ + 1); }

private:
    int limit_;
};

static_assert(std::forward_iterator<Evens::Iterator>);

int main() {
    Evens e(10);
    std::cout << std::count_if(e.begin(), e.end(), [](int x) { return x % 4 == 0; }) << "\n";
    std::cout << std::ranges::distance(e) << "\n";
    auto it = std::ranges::find(e, 6);
    std::cout << *it << " found\n";
}

3
5
6 found

How it works

• The three using lines tell algorithms what the iterator is (iterator_category), what it yields (value_type) and what type measures distances between two of them (difference_type).
• Post-increment it++ must return the old position. The int parameter is a dummy that tells the compiler this is the postfix version. The usual implementation copies *this, advances with prefix ++, and returns the copy.
• static_assert(std::forward_iterator<...>) is checked at compile time. If something is missing, the build fails here, with a message about which requirement isn't met.
• Once the concept is satisfied, std::ranges:: algorithms accept the whole range directly.

Your turn: make Countdown::Iterator a proper forward iterator: add the three member types, a default constructor, and post-increment. Countdown(n) yields n, n-1, ..., 1.

Previous: Writing an iterator class Next: A lazy range