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 task

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.

Challenge 2

Make Lines::Iterator a proper input iterator that reads a stream line by line: all five member types (iterator_category = std::input_iterator_tag, value_type = std::string, difference_type = std::ptrdiff_t, pointer = const std::string* and reference = const std::string&; the older algorithms need all five), operator* returning the current line, ++ reading the next one, and ==. An iterator whose stream pointer is nullptr is the end; reading past the last line turns an iterator into the end.

Challenge 3

A bidirectional iterator can also go back with --. Write Span(lo, hi), a range of the ints lo to hi - 1, whose iterator satisfies std::bidirectional_iterator: the member types (std::bidirectional_iterator_tag), a default constructor, *, ==, and pre- and post- ++ and --. The tests walk it backwards with std::reverse_iterator.

Previous: Writing an iterator class Next: A lazy range