Left folds and other reductions: The 114 C++ algorithms series
Welcome to the fifth instalment of the 114 standard C++ algorithms. In this chapter, we will talk about reduction algorithms, that is, algorithms that reduce a range into a single value.
We will cover three groups of algorithms, the left folds that operate strictly linearly, generalised reductions from C++17 and boolean reductions. We will also make a slight detour and talk about the caveats of mixing numerical types in C++.
The series:
- Introduction
- Sorting and partitioning algorithms
- Algorithms that operate on sorted or partitioned ranges
- Transformation algorithms
- Left folds and other reductions
- Generators, copies and moves
- Heap and heap
- Searching and min-max
- Conclusion (coming soon)
All algorithms we will discuss today (except for the boolean reductions) come from the <numeric> header and do not have counterparts in the C++20 ranges library (some support to land in C++23).
accumulate, inner_product
We start with the left folds, algorithms that operate strictly left to right, evaluating accumulator = op(accumulator, element) for each element and returning the final accumulator value.
Due to the strictly linear operation, we do not have access to parallel versions of these algorithms. The default version of accumulate uses the binary operator+, and if specified, the binary functor is not permitted to modify the elements in the range or invalidate iterators.
To turn any of the left fold algorithms into a right fold, we can use rbegin() and rend() (as long as the range is bidirectional).
By adding another range and a join operation, we arrive at inner_product. The left fold operation changes to accumulator = op(accumulator, join(elem1, elem2)), where elem1 comes from the first range and elem2 from the second range.
The default version uses operator+ for the accumulation and operator* for the join. If specified, neither functor is permitted to modify the elements or invalidate iterators.
Naturally, we can also use inner_product with a single range, for example, to calculate the sum of absolute differences between consecutive elements:
A short arithmetic detour
The algorithms in the <numeric> header can have sharp edges. This mainly has to do with the way C++ handles mixed numerical types and how template deduction works. For example, the following is an easy mistake to make:
Because we are passing a 0 as the initial value of the accumulator, which is a constant of type int, the accumulator ends up as int. Each fold operation then adds an integer and a double, resulting in a floating-point value. However, it immediately stores it in an integer variable, truncating the value.
If you want to avoid this problem, you need to be familiar with literal suffixes:
The second problem arises when mixing different integer types, particularly signed and unsigned integers. Again, as long as you do not mix types, you will not run into issues, but remember that the types that matter are the element types, the initial accumulator value and the functor arguments and return type.
These are arguably very synthetic examples and shouldn’t appear in production codebases.
If you are interested in more details about integer conversions and promotions, there is an excellent cheatsheet from hackingcpp on this topic.
partial_sum
The partial_sum algorithm is a bit of an outlier here, as it’s not a strict reduction algorithm. Instead, it computes partial sums on the given range. The nth generated element is the sum of the first n elements from the source range.
The output iterator is permitted to be the input ranges’ begin iterator. The default operation is the binary plus, and a custom functor is not permitted to modify elements or invalidate iterators.
reduce, transform_reduce
The previous algorithms we talked about are all left folds. They evaluate strictly linearly from left to right, which removes any potential for parallel execution.
However, when we work with operations that are associative op(a, op(b,c)) == op(op(a,b),c) and commutative op(a,b) == op(b,a), it really doesn’t matter what permutation of elements and order of operations we evaluate, we will always arrive at the same result.
In C++17, along with the other parallel algorithms, we have received reduce, inclusive_scan and exclusive_scan, which are relaxed versions of accumulate, inner_product and partial_sum that require an associative and commutative operation to produce deterministic results.
On top of the accumulate equivalents, we get one more overload that does away with the initial accumulator value, reducing the aforementioned numerical problems.
The accumulator will be of the type of the ranges’ elements and will be value initialised. So, the accumulator will be type double and initialised to zero in this example.
Of course, this also works for custom types:
The initial value of the accumulator will be “Quack”. Adding the other two ducks, we end up with “QuackQuackQuack”.
The counterpart to inner_product is transform_reduce, with additional overloads for the unary case (single range).
Same as reduce, provided functors must not modify the elements or invalidate iterators. In addition, the reduction functor must be associative and commutative.
exclusive_scan, inclusive_scan, transform_exclusive_scan, transform_inclusive_scan
The last left-fold algorithm without a parallel counterpoint is partial_sum.
The 1:1 counterpoint to partial_sum is inclusive_scan, which follows the same logic: nth generated element is the sum of the first n source elements. On top of that, we also get exclusive_scan, where the nth generated element is the sum of the first n-1 source elements. Or: the inclusive version includes the element on the nth position, and the exclusive version excludes it.
Consequently, for the exclusive_scan algorithm, we must specify an initial value of the accumulator, which will be the value of the first generated element.
The transform variants of inclusive_scan and exclusive_scan apply a unary transformation to each element. Unfortunately, we do not get an overload that would operate on two input ranges (in the style of inner_product).
all_of, any_of, none_of
Finally, we switch back to the <algorithm> header, where we have three boolean reductions.
The algorithms follow the expected boolean logic.
Note that any_of requires a positive presence; it only returns true if there is at least one element for which the predicate returns true and returns false on an empty range.
Thank you for reading
Don’t forget to follow so you don’t miss other articles in the series. For example, the following article will be about algorithms that generate values and algorithms that copy or move elements.
I also publish videos on YouTube. Do you have questions? Hit me up on Twitter or LinkedIn.
