An introduction to the 6 new folding algorithms added in C++23, providing alternatives to

`std::reduce`

and `std::accumulate`

Posted

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:

```
#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:

- A range of elements
- An initial value to â€śfoldâ€ť the elements into
- 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:

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

```
Result: 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:

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

```
Result: 9
```

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:

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

```
Result: 15
```

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`

:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main(){
std::vector Numbers{1, 2, 3, 4, 5};
std::cout << "Result: "
<< std::ranges::fold_left(
Numbers,
0.5f,
std::plus{});
}
```

```
Result: 15.5
```

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:

```
#include <algorithm>
#include <iostream>
#include <vector>
struct Accumulator {
Accumulator operator+(int n){
return Accumulator{sum + n, ++count};
}
void Log(){
std::cout << "Count: " << count
<< "\nSum: " << sum;
}
int sum;
int count;
};
int main(){
std::vector Numbers{1, 2, 3, 4, 5};
std::ranges::fold_left(
Numbers.begin(), Numbers.end(),
Accumulator{},
std::plus{}).Log();
}
```

```
Count: 5
Sum: 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`

:

```
#include <algorithm>
#include <iostream>
#include <vector>
template <typename T>
struct ZeroSentinel {
bool operator==(T Iter) const{
return Iter == ContainerEnd || *Iter == 0;
}
T ContainerEnd;
};
int main(){
std::vector Numbers{1, 3, 5, 0, 10};
int Result{
std::ranges::fold_left(
Numbers.begin(),
ZeroSentinel{Numbers.end()},
1, std::multiplies{}
)};
std::cout << "Result: " << Result;
}
```

```
Result: 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 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()`

:

```
std::ranges::fold_left_with_iter(
Numbers.begin(),
ZeroSentinel{Numbers.end()},
1, std::multiplies{}
)
```

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:

```
#include <algorithm>
#include <iostream>
#include <vector>
struct ZeroSentinel {/*...*/};
int main(){
std::vector Numbers{1, 3, 5, 0, 10};
auto [Iter, Result]{
std::ranges::fold_left_with_iter(
Numbers.begin(),
ZeroSentinel{Numbers.end()}, 1,
std::multiplies{})};
std::cout << "Result: " << Result << '\n';
if (Iter != Numbers.end()) {
std::cout << "The input had a zero";
}
std::cout << "\nNumber before sentinel: "
<< *(Iter - 1);
std::cout << "\nSize of range: "
<< Iter - Numbers.begin();
}
```

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

`fold_left_first()`

The `fold_left_first()`

variation of the algorithm does not require us to provide an initialÂ value:

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

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`

,

In most cases, the `optional`

will have aÂ value:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main(){
std::vector Numbers{1, 2, 3, 4, 5};
std::optional Result{
std::ranges::fold_left_first(
Numbers, std::plus{})};
if (Result.has_value()) {
std::cout << "Result: " << Result.value();
}
}
```

```
Result: 15
```

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

```
#include <algorithm>
#include <iostream>
#include <vector>
int main(){
std::vector<int> Numbers{};
std::optional Result{
std::ranges::fold_left_first(
Numbers, std::plus{})};
if (!Result.has_value()) {
std::cout << "Result is empty";
}
}
```

```
Result 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:

- 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:

```
#include <algorithm>
#include <iostream>
#include <vector>
struct ZeroSentinel {/*...*/};
int main(){
std::vector Numbers{1, 3, 5, 0, 10};
auto [Iter, Result]{
std::ranges::fold_left_first_with_iter(
Numbers.begin(),
ZeroSentinel{Numbers.end()},
std::multiplies{})};
if (Result.has_value()) {
std::cout << "Result: " << Result.value() <<
'\n';
}
if (Iter != Numbers.end()) {
std::cout << "The input had a zero";
}
std::cout << "\nNumber before sentinel: " << *
(Iter - 1);
std::cout << "\nSize of range: " << Iter -
Numbers.begin();
}
```

`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:

```
#include <algorithm>
#include <iostream>
#include <vector>
int main(){
std::vector Numbers{1, 2, 3};
// ((0-1)-2)-3 = -6
int LeftResult{
std::ranges::fold_left(
Numbers,
0,
std::minus{})};
std::cout << "Left Result: " << LeftResult;
int RightResult{
std::ranges::fold_right(Numbers, 0,
std::minus{})};
// 1-(2-(3-0)) = 1-(-1) = 2
std::cout << "\nRight Result: " <<
RightResult;
}
```

```
Left Result: -6
Right Result: 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

```
#include <algorithm>
#include <iostream>
#include <vector>
int main(){
std::vector Numbers{1};
// 10-1 = 9
int LeftResult{
std::ranges::fold_left(Numbers, 10,
std::minus{})};
std::cout << "Left Result: " << LeftResult;
int RightResult{
std::ranges::fold_right(Numbers, 10,
std::minus{})};
// 1-10 = -9
std::cout << "\nRight Result: " <<
RightResult;
}
```

```
Left Result: 9
Right Result: -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:

```
#include <algorithm>
#include <iostream>
#include <vector>
int Op(int x, int y){
std::cout << x << "+" << y << ", ";
return x + y;
}
int main(){
std::vector Numbers{1, 2, 3};
std::cout << "Left: ";
std::ranges::fold_left(Numbers, 0, Op);
std::cout << "\nRight: ";
std::ranges::fold_right(Numbers, 0, Op);
}
```

```
Left: 0+1, 1+2, 3+3,
Right: 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. So, the algorithm is implemented as `fold_right_last()`

:

```
#include <algorithm>
#include <iostream>
#include <vector>
int Op(int x, int y){
std::cout << x << " - " << y << " = "
<< x - y << ", ";
return x - y;
}
int main(){
std::vector Numbers{1, 2, 3};
// 1 - (2 - 3)
std::optional Result{
std::ranges::fold_right_last(Numbers, Op)};
if (Result.has_value()) {
std::cout << "\nResult: " << Result.
value_or(0);
}
}
```

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

â€” First Published

Posted

This lesson is part of theÂ course:### Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.