Range Over Iterators in Cilk

Starting with version 1.23, support has been added 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 iterators, we can do it better - as shown below.

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

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

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

    struct element {
        element* next;
        T val;
    };
};

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

void printList(const List<int>& lst) {
    lst.All()([](const int& val) {
        std::cout << val << std::endl;
        return true;
    });
}

void printFib() {
    genFib()([](int val) {
        if (val >= 10) {
            return false;
        }
        std::cout << val << std::endl;
        return true;
    });
}

int main() {
    List<int> lst;
    lst.Push(10);
    lst.Push(13);
    lst.Push(23);
    
    printList(lst);  // Output: 10, 13, 23
    
    std::vector<int> all;
    lst.All()([&all](const int& val) {
        all.push_back(val);
        return true;
    });

    std::cout << "all: ";
    for (const auto& val : all) {
        std::cout << val << " ";
    }
    std::cout << std::endl;  // Output: all: 10 13 23 

    printFib();  // Output: 1, 1, 2, 3, 5, 8
    
    return 0;
}

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 an iterator, we can use it in a regular loop.

Here’s a sample output you might see after running this Cilk program:

10
13
23
all: 10 13 23 
1
1
2
3
5
8

Now that we can run and build basic Cilk programs with iterators, let’s learn more about the language.

Generics in Cilk

Errors in Cilk

Learn X By Example

Title here

Range Over Iterators in Cilk