C++23 Fold Algorithms

Similar to std::reduce() and std::accumulate() from the previous lesson, these algorithms are designed to work on collections of objects and to return a single result.

For example, were we to have a collection of objects in our shopping basket, and we wanted to total cost of all the objects, the fold algorithms are ideal.

They give us some additional options over std::reduce() and std::accumulate(). Most notably, there are 6 different variants, giving us more control over how our collection is combined.

They’re also range-based algorithms, thereby giving us more control over how we define the collection of objects that we want to be the input.

All the algorithms in this lesson are available within the <algorithm> header:

1#include <algorithm>

fold_left()

The std::ranges::fold_left() algorithm works very similarly to std::accumulate from the previous lesson. In its most basic usage, we provide three arguments:

1. A range of elements
2. An initial value to "fold" the elements into
3. A binary operation - to use with each successive fold

Below, we provide a std::vector of integers, an initial value of 0, and an operation that will add each successive number together:

1#include <algorithm>
2#include <vector>
3#include <iostream>
4
5int main(){
6  std::vector Numbers{1, 2, 3, 4, 5};
7
8  std::cout << "Result: " <<
9    std::ranges::fold_left(Numbers, 0,
10                           std::plus{});
11}

1Result: 15

fold_left() and all the other algorithms in this lesson use the C++20 ranges concepts, so they also work with an iterator and sentinel pair. Below, we use this to exclude the first and last element from our calculation:

1#include <algorithm>
2#include <vector>
3#include <iostream>
4
5int main(){
6  std::vector Numbers{1, 2, 3, 4, 5};
7
8  std::cout << "Result: " <<
9    std::ranges::fold_left(Numbers.begin() + 1,
10                           Numbers.end() - 1, 0,
11                           std::plus{});
12}

1Result: 9

Defining Ranges using Sentinels

An alternative way of defining ranges, and why we sometimes need to use them

Custom Operators

In the previous examples, we’re constructing an object from std::plus to provide as the operator. This standard library helper creates a callable that simply accepts two arguments and returns the result of combining them using the + operator.

We’re not restricted to simple operations - we can provide any callable we want. Below, we provide a lambda that will return the sum of the absolute values of our input objects:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector Numbers{1, -2, 3, -4, 5};
7
8  std::cout << "Result: "
9    << std::ranges::fold_left(
10      Numbers, 0, [](int x, int y){
11        return std::abs(x) + std::abs(y);
12      });
13}

1Result: 15

Folding to a different type

The type that is returned by our fold calls is defined by the type we provide as the initial value argument. This will often have the same time as our inputs, and be the identity of our operation.

That was the case in our previous examples, where we provided the integer 0 - that is, the identity of integer addition.

But it doesn’t need to be - below, we provide 0.5f, causing our fold algorithm to return a float:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector Numbers{1, 2, 3, 4, 5};
7
8  std::cout << "Result: "
9    << std::ranges::fold_left(
10      Numbers,
11      0.5f,
12      std::plus{});
13}

1Result: 15.5

We can provide any type we want. The requirements are simply that:

• It supports the operator we provided, where our input type will be the right operand
• The operator returns something that also supports this, thereby allowing more objects to be folded in

Below, we demonstrate this with a custom type:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5struct Accumulator {
6  Accumulator operator+(int n){
7    return Accumulator{sum + n, ++count};
8  }
9
10  void Log(){
11    std::cout << "Count: " << count
12      << "\nSum: " << sum;
13  }
14
15  int sum;
16  int count;
17};
18
19int main(){
20  std::vector Numbers{1, 2, 3, 4, 5};
21
22  std::ranges::fold_left(
23    Numbers.begin(), Numbers.end(),
24    Accumulator{},
25    std::plus{}).Log();
26}

1Count: 5
2Sum: 15

fold_left_with_iter()

When our range is defined by an iterator and sentinel pair, and where our sentinel is not trivial, we may not know where our input range ends.

Below, we fold over a range that ends as soon as it encounters a 0:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5template <typename T>
6struct ZeroSentinel {
7  bool operator==(T Iter) const{
8    return Iter == ContainerEnd || *Iter == 0;
9  }
10
11  T ContainerEnd;
12};
13
14int main(){
15  std::vector Numbers{1, 3, 5, 0, 10};
16
17  int Result{
18    std::ranges::fold_left(
19      Numbers.begin(),
20      ZeroSentinel{Numbers.end()},
21      1, std::multiplies{}
22  )};
23
24  std::cout << "Result: " << Result;
25}

1Result: 15

In real-world use cases, we’re often going to have follow-up operations that need to know where our range ended. That is, where our sentinel returned true.

For a few reasons, including performance considerations, we don’t want to run a second algorithm just to figure out where our range ends.

Our fold_left() algorithm naturally needed to figure out where our range ended to return the correct result. But we have no way to access that information.

For this reason, the standard library includes a variation of the algorithm: fold_left_with_iter():

1std::ranges::fold_left_with_iter(
2  Numbers.begin(),
3  ZeroSentinel{Numbers.end()},
4  1, std::multiplies{}
5)

This algorithm uses the same arguments as fold_left(), but has a different return type.

Specifically, it returns a ranges::in_value_result which is a fairly common type. It is used by many range-based algorithms that take a single range as an input, and return a single value as a result.

The return type has two data members:

• in - An iterator pointing to where our input range ended
• value - The result of the fold algorithm - the same as what would have been returned by an equivalent call to std::ranges::fold_left()

Below, we show an example of how we can use this return value. We’re displaying the result of the fold as usual. But, we also now use the additional in value, which we’ve called Iter via structured binding.

This value lets us understand where our range ended, which we’ve used for some simple example follow-up operations:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
ZeroSentinel Struct (Unchanged)|Show
5struct ZeroSentinel {/*...*/};
14
15int main(){
16  std::vector Numbers{1, 3, 5, 0, 10};
17
18  auto [Iter, Result]{
19    std::ranges::fold_left_with_iter(
20      Numbers.begin(),
21      ZeroSentinel{Numbers.end()}, 1,
22      std::multiplies{})};
23
24  std::cout << "Result: " << Result << '\n';
25
26  if (Iter != Numbers.end()) {
27    std::cout << "The input had a zero";
28  }
29
30  std::cout << "\nNumber before sentinel: "
31    << *(Iter - 1);
32
33  std::cout << "\nSize of range: "
34    << Iter - Numbers.begin();
35}

1Result: 15
2The input had a zero
3Number before sentinel: 5
4Size of range: 3

fold_left_first()

The fold_left_first() variation of the algorithm does not require us to provide an initial value:

1#include <algorithm>
2#include <vector>
3
4int main(){
5  std::vector Numbers{1, 2, 3, 4, 5};
6
7  std::ranges::fold_left_first(
8    Numbers, std::plus{});
9}

We can think of it as just using the first object in our range as the initial value, and then folding the rest of the range into it.

In our previous lesson, we introduced how we could manually implement a similar technique using std::reduce() and std::accumulate().

Aside from being easier to use, the fold_left_first() algorithm also takes care of the edge case where our input range has no elements. It does this by returning a std::optional,

Nullable Values using std::optional

A comprehensive guide to using std::optional to represent values that may or may not be present.

In most cases, the optional will have a value:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector Numbers{1, 2, 3, 4, 5};
7
8  std::optional Result{
9    std::ranges::fold_left_first(
10      Numbers, std::plus{})};
11
12  if (Result.has_value()) {
13    std::cout << "Result: " << Result.value();
14  }
15}

1Result: 15

But, in the edge case where our input has no objects, the algorithm will simply return an empty optional:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector<int> Numbers{};
7
8  std::optional Result{
9    std::ranges::fold_left_first(
10      Numbers, std::plus{})};
11
12  if (!Result.has_value()) {
13    std::cout << "Result is empty";
14  }
15}

1Result is empty

fold_left_first_with_iter()

As we’d probably expect, the fold_left_first_with_iter() combines both of the techniques of the previous two std::fold_left() variations.

Specifically, it takes its initial value from the input range, similar to fold_left_first()

Additionally, it returns an object with two members:

1. in - An iterator pointing to where our input range ended, similar to what is returned by fold_left_with_iter()
2. value - A std::optional with the result of the fold algorithm, similar to what is returned by fold_left_first()

Below is an example of the algorithm in use:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
ZeroSentinel Struct (Unchanged)|Show
5struct ZeroSentinel {/*...*/};
14
15int main(){
16  std::vector Numbers{1, 3, 5, 0, 10};
17
18  auto [Iter, Result]{
19    std::ranges::fold_left_first_with_iter(
20      Numbers.begin(),
21      ZeroSentinel{Numbers.end()},
22      std::multiplies{})};
23
24  if (Result.has_value()) {
25    std::cout << "Result: " << Result.value() <<
26      '\n';
27  }
28
29  if (Iter != Numbers.end()) {
30    std::cout << "The input had a zero";
31  }
32
33  std::cout << "\nNumber before sentinel: " << *
34    (Iter - 1);
35
36  std::cout << "\nSize of range: " << Iter -
37    Numbers.begin();
38}

1Result: 15
2The input had a zero
3Number before sentinel: 5
4Size of range: 3

fold_right()

The fold_left() algorithm is also available in a "right" variation as std::ranges::fold_right().

The main implication of left vs right is how operations are grouped. Left folding combines objects at the start of our input first, whilst right folding operates on the later elements first.

Because of this, right folding requires our input to support reverse iteration - that is, it must be a bidirectional range.

Depending on the operation we’re using, the fold direction can affect the return value of the algorithm:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector Numbers{1, 2, 3};
7
8  // ((0-1)-2)-3 = -6
9  int LeftResult{
10    std::ranges::fold_left(
11      Numbers,
12      0,
13      std::minus{})};
14
15  std::cout << "Left Fold: " << LeftResult;
16
17  int RightResult{
18    std::ranges::fold_right(Numbers, 0,
19                            std::minus{})};
20
21  // 1-(2-(3-0)) = 1-(-1) = 2
22  std::cout << "\nRight Fold: " <<
23    RightResult;
24}

1Left Fold: -6
2Right Fold: 2

This also has implications when using non-identity initial values. When left-folding, the "initial value" is the leftmost operand, but when right-folding, it is the rightmost operand:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector Numbers{1};
7
8  // 10-1 = 9
9  int LeftResult{
10    std::ranges::fold_left(Numbers, 10,
11                           std::minus{})};
12
13  std::cout << "Left Fold: " << LeftResult;
14
15  int RightResult{
16    std::ranges::fold_right(Numbers, 10,
17                            std::minus{})};
18
19  // 1-10 = -9
20  std::cout << "\nRight Fold: " <<
21    RightResult;
22}

1Left Fold: 9
2Right Fold: -9

Even when working with an operation that will return the same value regardless of the fold direction, the fold direction may still have implications if our operator has any side effects.

Below, we’re using addition as our operator. Addition is commutative and associative, so our return value will be the same regardless of our fold direction.

But our operation also has side effects (logging, in this case), so our program’s behavior still varies based on the fold direction:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int Op(int x, int y){
6  std::cout << x << "+" << y << ", ";
7  return x + y;
8}
9
10int main(){
11  std::vector Numbers{1, 2, 3};
12
13  std::cout << "Left: ";
14  std::ranges::fold_left(Numbers, 0, Op);
15
16  std::cout << "\nRight: ";
17  std::ranges::fold_right(Numbers, 0, Op);
18}

1Left: 0+1, 1+2, 3+3,
2Right: 3+0, 2+3, 1+5,

fold_right_last()

Just as fold_left() has a variation that allows us to select the initial value from the input range, so too does fold_right().

With right folding, it’s more common that we want the rightmost (ie, last) value of our input to be selected as the initial value. So, the algorithm is implemented as fold_right_last():

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int Op(int x, int y){
6  std::cout << x << " - " << y << " = "
7    << x - y << ", ";
8  return x - y;
9}
10
11int main(){
12  std::vector Numbers{1, 2, 3};
13
14  // 1 - (2 - 3)
15  std::optional Result{
16    std::ranges::fold_right_last(Numbers, Op)};
17
18  if (Result.has_value()) {
19    std::cout << "\nResult: " << Result.value();
20  }
21}

12 - 3 = -1, 1 - -1 = 2,
2Result: 2

Summary

This lesson introduced the fold algorithms added in C++23, demonstrating their utility in simplifying collections into a single value through various examples and custom operations.

Main Points Learned

• The introduction of 6 new fold algorithms in C++23 as alternatives to std::reduce() and std::accumulate().
• How to use std::ranges::fold_left() to combine elements of a collection using a binary operation and an initial value.
• The ability to use custom operators and lambda expressions with fold algorithms for customized behavior.
• The introduction of fold_left_with_iter() and fold_left_first_with_iter() for working with ranges and sentinels.
• Understanding the distinction between left and right folding and its impact on the result of fold operations.
• Learning about fold_right() and fold_right_last() for bidirectional ranges, and how fold direction affects operation outcomes.
• How some fold algorithms use std::optional to handle empty ranges.

Next Lesson

Internal and External Linkage

A deeper look at the C++ linker and how it interacts with our variables and functions. We also cover how we can change those interactions, using the extern and inline keywords

ContinueView Course