Lazy Sequences with std::generator in C++

Introduced in C++23, std::generator provides a standard, vocabulary-type interface for producing synchronous, lazy sequences using C++20 coroutines. This article explains how std::generator operates under the hood, detailing the interaction between its coroutine promise type, suspension points, and iterator protocol to evaluate elements on demand while maintaining minimal memory overhead and full compatibility with the C++ Ranges library.

The Foundation: Coroutine Mechanics

Traditional C++ functions execute to completion and return a single value, discarding their stack frames upon return. C++20 coroutines alter this control flow by allowing functions to suspend execution and resume later, storing their local state inside a dynamically or elastically allocated coroutine frame.

A function becomes a coroutine as soon as it contains any of the three coroutine keywords: co_await, co_return, or co_yield. The std::generator<Ref, Value> template, defined in the <generator> header, acts as the return type for coroutines designed specifically to produce values synchronously on request.

How std::generator Leverages the Promise Type

Every coroutine relies on an associated promise object defined by its return type—in this case, std::generator::promise_type. The compiler interacts with this promise type at designated lifecycle hooks:

  1. Lazy Initialization (initial_suspend): When a std::generator-returning function is invoked, it does not immediately execute user code. Instead, its initial_suspend() method returns std::suspend_always. This immediately suspends the coroutine at its initial boundary and returns the std::generator object to the caller. No elements are computed until the caller actively requests one.
  2. Value Capture (yield_value): When the coroutine encounters co_yield expr, the compiler translates this expression into co_await promise.yield_value(expr). The promise stores an address or reference to the evaluated expression inside the coroutine frame and returns a suspension point.
  3. Execution Suspension: Upon yielding, execution suspends, and control transfers back to the consumer. The consumer reads the value directly from the promise object without performing unnecessary copies.
  4. Completion (return_void): Once the coroutine reaches co_return or drops off the end of the function body, return_void() is called, setting the coroutine's state to "done."

The Iterator Protocol and Resumption

The bridge between C++ ranges and coroutine suspension is the std::generator::iterator.

When a consumer calls generator.begin(), the generator resumes the coroutine via its underlying std::coroutine_handle. Execution proceeds until the first co_yield is hit, where it suspends. The iterator dereference operator (*it) accesses the value stored in the promise during that yield.

Advancing the iterator (++it) invokes handle.resume(). The coroutine picks up directly after the previous co_yield point, executes until the next co_yield, and suspends again. If the coroutine finishes, the iterator becomes equal to generator.end().

#include <generator>
#include <iostream>

std::generator<int> fibonacci() {
    int a = 0, b = 1;
    while (true) {
        co_yield a;
        auto next = a + b;
        a = b;
        b = next;
    }
}

int main() {
    // Generates values strictly on demand
    for (int val : fibonacci()) {
        if (val > 20) break;
        std::cout << val << ' ';
    }
}

Recursive Flattening and Nested Yields

A major performance feature of std::generator is built-in support for nested generator calls via co_yield std::ranges::elements_of(...).

In naive coroutine implementations, yielding from a nested coroutine incurs a chain of suspensions and resumptions proportional to the recursion depth, leading to quadratic overhead (\(O(N^2)\)). std::generator solves this by symmetrically transferring control directly between nested coroutine handles inside the promise type, flattening recursive traversals (such as tree walks) into linear time (\(O(N)\)) without deep stack growth.

Memory and Performance Characteristics

  • Memory Efficiency: Because values are computed lazily, std::generator avoids materializing sequences into memory buffers (e.g., std::vector), reducing space complexity to \(O(1)\) for sequence tracking.
  • Allocation Elision: While coroutines allocate a frame on the heap, modern compilers can optimize this allocation away through Coroutine Elision (HALO—Heap Allocation of Lookup and Overallocation) if the generator's lifetime is bounded and strictly nested within the caller's stack frame.
  • Range Integration: std::generator models std::ranges::input_range, allowing seamless composition with standard range adaptors like std::views::take, std::views::transform, and std::views::filter.