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 8 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>
2

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}
12

1Result: 15
2

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}
13

1Result: 9
2

Ranges and Sentinels

A practical guide to defining ranges using sentinel values, and why we sometimes need to

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}
14

1Result: 15
2

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}
14

1Result: 15.5
2

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

• 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}
27

1Count: 5
2Sum: 15
3

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}
26

1Result: 15
2

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 in order 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)
6

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 8 Lines
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}
36

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

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}
10

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,

Optional Values, std::optional and Monadic Operations

A guide to handling optional data in C++ using the std::optional container

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}
16

1Result: 15
2

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}
16

1Result is empty
2

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:

• Returns a ranges::in_value_result, similar to fold_left_iter()
• Uses an initial value from the input range, similar to fold_left_first()

Below is an example of it being used:

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

fold_right()

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

The main implication is the way in which operations are grouped. Left folding combines objects at the start of our input first, whilst right folding operations on the later elements first.

This means that, depending on our operation, the fold direction can change the return value:

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 Result: " << 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 Result: " <<
23    RightResult;
24}
25

1Left Result: -6
2Right Result: 2
3

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 Result: " << LeftResult;
14
15  int RightResult{
16    std::ranges::fold_right(Numbers, 10,
17                            std::minus{})};
18
19  // 1-10 = -9
20  std::cout << "\nRight Result: " <<
21    RightResult;
22}
23

1Left Result: 9
2Right Result: -9
3

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}
19

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

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. 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.
20      value_or(0);
21  }
22}
23

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