Range Over Iterators in C++

Starting with version 1.23, Go has added support for iterators, which lets us range over pretty much anything!

Let’s look at the List type from the previous example again. In that example we had an AllElements method that returned a slice of all elements in the list. With Go iterators, we can do it better - as shown below.

#include <iostream>
#include <vector>
#include <functional>

template <typename T>
struct element {
    element* next;
    T val;
};

template <typename T>
struct List {
    element<T>* head;
    element<T>* tail;

    List() : head(nullptr), tail(nullptr) {}

    void Push(T v) {
        if (tail == nullptr) {
            head = new element<T>{nullptr, v};
            tail = head;
        } else {
            tail->next = new element<T>{nullptr, v};
            tail = tail->next;
        }
    }

    std::function<void(std::function<bool(T)>)> All() {
        return [this](std::function<bool(T)> yield) {
            for (element<T>* e = head; e != nullptr; e = e->next) {
                if (!yield(e->val)) {
                    return;
                }
            }
        };
    }
};

std::function<void(std::function<bool(int)>)> genFib() {
    return [](std::function<bool(int)> yield) {
        int a = 1, b = 1;
        while (true) {
            if (!yield(a)) return;
            int temp = a;
            a = b;
            b = temp + b;
        }
    };
}

int main() {
    List<int> lst;
    lst.Push(10);
    lst.Push(13);
    lst.Push(23);

    // Since List.All returns a function, we can use it similarly to a range
    lst.All()([](int e) {
        std::cout << e << std::endl;
        return true;
    });

    // Collect all values from the iterator into a vector
    std::vector<int> all;
    lst.All()([&all](int e) {
        all.push_back(e);
        return true;
    });
    std::cout << "all:";
    for (const auto &val : all) {
        std::cout << " " << val;
    }
    std::cout << std::endl;

    // Fibonacci generator
    genFib()([](int n) {
        if (n >= 10) return false;
        std::cout << n << std::endl;
        return true;
    });

    return 0;
}

All returns an iterator, which in this example is a function that takes another function as a parameter, called yield by convention (but the name can be arbitrary). It will call yield for every element we want to iterate over and note yield’s return value for a potential early termination.

Iteration doesn’t require an underlying data structure and doesn’t even have to be finite! Here’s a function returning an iterator over Fibonacci numbers: it keeps running as long as yield keeps returning true.

Since List.All returns a function, we can use it similarly to a range loop. For example, we can iterate and print values from the list.

Packages like slices have a number of useful functions to work with iterators. For example, Collect takes any iterator and collects all its values into a vector.

Once the loop hits break or an early return, the yield function passed to the iterator will return false.

Generics in C++

Errors in C++

Learn X By Example

Title here

Range Over Iterators in C++