{"id":35153,"date":"2025-02-24T17:03:51","date_gmt":"2025-02-24T17:03:51","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/cppblog\/?p=35153"},"modified":"2025-02-24T17:06:35","modified_gmt":"2025-02-24T17:06:35","slug":"std-generator-standard-library-coroutine-support","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/cppblog\/std-generator-standard-library-coroutine-support\/","title":{"rendered":"std::generator: Standard Library Coroutine Support"},"content":{"rendered":"

std::generator<\/a><\/code> is a C++23 feature that enables you to write concise, straightforward functions that generate sequences of values on-demand without manually managing state. It builds upon C++20\u2019s coroutines<\/a>, providing some standard library support for this powerful, but complex, language feature. As of Visual Studio 2022 version 17.13, we ship an implementation of std::generator<\/code> in our standard library<\/a>.<\/p>\n

This blog post will walk through an example of how to use the feature, compare it to implementing custom ranges, consider some of the design decisions made, and briefly look at the performance implications.<\/p>\n

Motivating Example<\/h2>\n

Here\u2019s a short motivating example from P2502<\/a>, which proposed the feature:<\/p>\n

std::generator<int> fibonacci() {\r\n    int a = 0, b = 1;\r\n    while (true) {\r\n        co_yield std::exchange(a, std::exchange(b, a + b));\r\n    }\r\n}\r\n\r\nint answer_to_the_universe() {\r\n    auto rng = fibonacci() | std::views::drop(6) | std::views::take(3);\r\n    return std::ranges::fold_left(std::move(rng), 0, std::plus{});\r\n}<\/code><\/pre>\n
Here, fibonacci<\/code> is a coroutine, because it uses the co_yield<\/code> keyword. Coroutines are a generalization of a subroutine. A subroutine begins its execution when it is called and completes its execution when it returns to the caller (forgetting about things like exceptions for simplicity). A coroutine\u2019s execution similarly begins when it is called, but it need not complete execution to return control flow back to the caller: it can suspend<\/em> its execution and be resumed later.<\/p>\n
Note that, in the above example, fibonacci<\/code> contains an infinite loop. This is not a problem, because when the co_yield<\/code> statement is executed, the coroutine yields<\/em> both control flow and a value back to the caller, suspending the coroutine’s execution. std::exchange<\/a><\/code> is a small helper utility that assigns a new value to a variable and returns the old one.<\/p>\n
The behavior of operations like co_yield<\/code> in a coroutine are determined by the coroutine\u2019s return type, in this case std::generator<\/code>.<\/p>\n
The answer_to_the_universe<\/code> function uses the std::generator<\/code> object returned by fibonacci<\/code> in tandem with range adaptors. It pipes<\/em> the generator into two range adaptors. The first says to drop the first 6 elements from the range, while the second says to take the next 3 elements. Note that these range adaptors are not executed eagerly; elements are only dropped or taken when a value is requested from the resulting range.<\/p>\n
After building a range to operate on, the answer_to_the_universe<\/code> function sums the values in the range using the std::ranges::fold_left<\/code><\/a> algorithm. This is a range-based version of std::accumulate<\/code><\/a>. Folding over the values of the range will continually request values from the range, which will generate those values by resuming execution of the coroutine and forwarding on the yielded results. At the end, we end up with the obvious<\/a> answer: 42.<\/p>\n
Comparison With Custom Ranges<\/h2>\n
Let\u2019s look at how std::generator<\/code> makes it much easier to write code that generates sequences of values that are compatible with the ranges algorithms and views in the standard library.<\/p>\n
Say we want to represent an infinite range of random numbers using the xorshift<\/a> pseudorandom number generator<\/a> (PRNG), which looks like this:<\/p>\n
std::uint64_t xorshift(std::uint64_t state) {\r\n\u00a0 \u00a0 state ^= state << 13;\r\n\u00a0 \u00a0 state ^= state >> 7;\r\n\u00a0 \u00a0 state ^= state << 17;\r\n\u00a0 \u00a0 return state;\r\n}<\/code><\/pre>\n
Given the current state of the PRNG, which is a 64-bit integer, xorshift(state)<\/code> generates the next random number in the sequence. Don\u2019t ask me where those numbers come from, they\u2019re magic.<\/p>\n
Writing a custom range type for this is achievable, but it is quite verbose and requires a somewhat in-depth understanding of ranges. Let\u2019s give it a shot.<\/p>\n
We\u2019ll write a type called xorshift_range<\/code>, which we should be able to use like this:<\/p>\n
int main() {\r\n\u00a0 \u00a0 auto is_even = [](auto i) { return i % 2 == 0; };\r\n\u00a0 \u00a0 auto ten_even_numbers = xorshift_generator(std::random_device{}())\r\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 | std::views::filter(is_even)\r\n\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 | std::views::take(10);\r\n\u00a0 \u00a0 for (auto i : ten_even_numbers) {\r\n\u00a0 \u00a0 \u00a0 \u00a0 std::cout << i << ' ';\r\n\u00a0 \u00a0 }\r\n}<\/code><\/pre>\n
The constructor should take a seed for the PRNG, and we should be able to pipe the result into existing range adaptors to, for example, retrieve ten even random numbers.<\/p>\n
Let\u2019s start with a definition for the type:<\/p>\n
class xorshift_range {\r\npublic:\r\n\u00a0 \u00a0 explicit xorshift_range(std::uint64_t seed)\r\n\u00a0 \u00a0 \u00a0 \u00a0 : seed_(seed) {\r\n\u00a0 \u00a0 }\r\n\u00a0 \u00a0 class iterator;\r\n\r\n\u00a0 \u00a0 iterator begin() const;\r\n\u00a0 \u00a0 std::unreachable_sentinel_t end() const {\r\n\u00a0 \u00a0 \u00a0 \u00a0 return {};\r\n\u00a0 \u00a0 }\r\nprivate:\r\n\u00a0 \u00a0 std::uint64_t seed_;\r\n};<\/code><\/pre>\n
Reasonably straightforward for now. The constructor takes a seed and stores it in a member. We declare an iterator type, which will implement the generation logic, and a begin<\/code> function that will return an instance of the iterator type. The iterator will be infinite, so it will always compare not equal to end()<\/code>. As such, end returns a std::unreachable_sentinel_t<\/code>, which compares not equal to everything.<\/p>\n
The implementation of the iterator type is more complex, so we\u2019ll take it a bit at a time.<\/p>\n
class xorshift_range::iterator {\r\npublic:\r\n\u00a0 \u00a0 using difference_type = std::ptrdiff_t;\r\n\u00a0 \u00a0 using value_type = std::uint64_t;\r\n\u00a0 \u00a0 using iterator_concept = std::forward_iterator_tag;<\/code><\/pre>\n
We first provide some member types to indicate some information about our iterator. We won\u2019t use difference_type<\/code> in the implementation of the iterator, but it\u2019s required for compatibility with ranges, so we pick a reasonable default of std::ptrdiff_t<\/code>. value_type<\/code> is std::uint64_t<\/code> becuause we produce unsigned 64-bit integers. Our iterator cannot move backwards, but you can copy instances of it and increment them independently, which corresponds to std::forward_iterator<\/a><\/code>, so we set iterator_concept<\/code> to std::forward_iterator_tag<\/code>.<\/p>\n
Next come the constructors:<\/p>\n
\u00a0 \u00a0 iterator() = default;\r\n\u00a0 \u00a0 explicit iterator(std::uint64_t seed)\r\n\u00a0 \u00a0 \u00a0 \u00a0 : state_(seed) {\r\n\u00a0 \u00a0 \u00a0 \u00a0 ++(*this);\r\n\u00a0 \u00a0 }<\/code><\/pre>\n
C++20 iterators must be default-constructible, so we define a zero-argument constructor. We also define a constructor that takes a seed, stores it in a state_<\/code> member (which we\u2019ll define soon), and drives the iterator forward to generate the first random number.<\/p>\n
The operator overloads deal with generating the next number and returning it to client code:<\/p>\n
\u00a0 \u00a0 std::uint64_t operator*() const {\r\n\u00a0 \u00a0 \u00a0 \u00a0 return state_;\r\n\u00a0 \u00a0 }\r\n\u00a0 \u00a0 iterator& operator++() {\r\n\u00a0 \u00a0 \u00a0 \u00a0 state_ = xorshift(state_);\r\n\u00a0 \u00a0 \u00a0 \u00a0 return *this;\r\n\u00a0 \u00a0 }\r\n\u00a0 \u00a0 iterator operator++(int) {\r\n\u00a0 \u00a0 \u00a0 \u00a0 auto copy = *this;\r\n\u00a0 \u00a0 \u00a0 \u00a0 ++(*this);\r\n\u00a0 \u00a0 \u00a0 \u00a0 return copy;\r\n\u00a0 \u00a0 }<\/code><\/pre>\n
The dereference operator returns the current number. The preincrement operator generates the next random number in the sequence using the xorshift<\/code> function we saw earlier. We implement the postincrement operator in terms of the prefix one.<\/p>\n
We also need equality operators and the state_<\/code> member:<\/p>\n
\u00a0 \u00a0 friend bool operator==(const iterator&, const iterator&) = default;\r\nprivate:\r\n\u00a0 \u00a0 std::uint64_t state_ = 0;\r\n};<\/code><\/pre>\n
The default equality operator<\/a> will check equality based on the current state.<\/p>\n
Finally, we need the implementation of begin and one more piece of ranges magic:<\/p>\n
xorshift_range::iterator xorshift_range::begin() const {\r\n\u00a0 \u00a0 return iterator{seed_};\r\n}\r\nnamespace\u00a0std::ranges\u00a0{\r\n\u00a0\u00a0\u00a0\u00a0template<>\r\n\u00a0\u00a0\u00a0\u00a0constexpr\u00a0bool\u00a0enable_borrowed_range<xorshift_range>\u00a0=\u00a0true;\r\n}<\/code><\/pre>\n
The begin<\/code> function just returns an iterator with the supplied seed. The specialization of std::ranges::enable_borrowed_range<\/code> allows us to use xorshift_range<\/code> as an rvalue<\/a> in some contexts, because the iterators can safely outlive the parent xorshift_range<\/code> object without any dangling references.<\/p>\n
Phew, that was a lot of work. Want to see the std::generator<\/code> version?<\/p>\n
std::generator<std::uint64_t> xorshift_generator(std::uint64_t seed) {\r\n\u00a0 \u00a0 while (true) {\r\n\u00a0 \u00a0 \u00a0 \u00a0 seed = xorshift(seed);\r\n\u00a0 \u00a0 \u00a0 \u00a0 co_yield seed;\r\n\u00a0 \u00a0 }\r\n}<\/code><\/pre>\n
That\u2019s it. That\u2019s the entire code.<\/p>\n
It\u2019s not entirely the same as the range version, but is clearly a lot easier to implement and maintain. Here are a few differences:<\/p>\n