C++23’s New Fold Algorithms
C++20 added new versions of the standard library algorithms which take ranges as their first argument rather than iterator pairs, alongside other improvements. However, key algorithms like std::accumulate were not updated. This has been done in C++23, with the new std::ranges::fold_* family of algorithms. The standards paper for this is P2322 and was written by Barry Revzin. It been implemented in Visual Studio 2022 version 17.5. In this post I’ll explain the benefits of the new “rangified” algorithms, talk you through the new C++23 additions, and explore some of the design space for fold algorithms in C++. Background: Rangified Algorithms C++20’s algorithms make several improvements to the old iterator-based ones. The most obvious is that they now can take a range instead of requiring you to pass iterator pairs. But they also allow passing a “projection function” to be called on elements of the range before being processed, and the use of C++20 concepts for constraining their interfaces more strictly defines what valid uses of these algorithms are. These changes allow you to make refactors like: // C++17 algorithm cat find_kitten(const std::vector& cats) { return *std::find_if(cats.begin(), cats.end(), [](cat const& c) { return c.age == 0; }); } // C++20 algorithm cat find_kitten(std::span cats) { return *std::ranges::find(cats, 0, &cat::age); } The differences here are: Instead of having to pass cats.begin() and cats.end(), we just pass cats itself. Since we are comparing a member variable of the cat to 0, in C++17 we need to use std::find_if and pass a closure which accesses that member and does the comparison. Since the rangified algorithms support projections, in C++20 we can use std::ranges::find and pass &cat::age as a projection, getting rid of the need for the lambda completely. These improvements can greatly clean up code which makes heavy use of the standard library algorithms. Unfortunately, alongside the algorithms which reside in the header, there are also several important ones in the header, and these were not rangified in C++201. In this post we’re particularly interested in std::accumulate and std::reduce. accumulate and reduce std::accumulate and std::reduce are both fold operations. They “fold” or “reduce” or “combine” multiple values into a single value. Both take two iterators, an initial value, and a binary operator (which defaults to +). They then run the given operator over the range of values given by the iterators, collecting a result as they go. For instance, given std::array arr = {1,2,3}, std::accumulate(begin(arr), end(arr), 0, std::plus()) will run (((0 + 1) + 2) + 3). Or std::accumulate(begin(arr), end(arr), 0, f) will run f(f(f(0, 1), 2), 3). These functions are both what are called left folds because they run from left to right. There’s also right folds, which as you may guess, run from right to left. For the last example a right fold would look like f(1, f(2, f(3, 0))). For some operations, like +, these would give the same result, but for operations which are not associative (like -), it could make a difference. So why do we have both std::accumulate and std::reduce? std::reduce was added in C++17 as one of the many parallel algorithms which let you take advantage of parallel execution for improved performance. The reason it has a different name than std::accumulate is because it has different constraints on what types and operations you can use: namely the […]
