Fold Expression
An introduction to C++17 fold expressions, which allow us to work more efficiently with parameter packs
C++17 introduced fold expressions, which provide a shortened syntax to implement simple recursive algorithms that act on a parameter pack. A fold expression looks like this:
(Args + ...)
It has four components:
- A set of parenthesis,
(
and)
- An expression involving a parameter pack. In this example, we've assumed our parameter pack is called
Args
- An operator - in this example, we've used
+
- A set of ellipses -
...
We'll delve into the specific behavior of parameter packs throughout this lesson.
Using Fold Expressions
When using a fold expression, we can imagine it inserting the operator between every object in the parameter pack and returning the result of that expression.
In the following example, we use a parameter pack containing the integers 5
, 10
, and 20
. Our fold expression uses the +
operator, so our expression unpacks to something equivalent to 5 + 10 + 20
.
#include <iostream>
template <typename... Types>
auto Fold(Types... Args){
return (Args + ...);
}
int main(){
std::cout << "Result: " << Fold(5, 10, 20);
}
Our result is the sum of everything in the parameter pack:
Result: 35
The operand we use in a fold expression can be any expression involving the parameter pack. Simply using Args
in isolation is the most obvious example of such an expression, but we can get more complex.
In this example, our fold expression uses the square of each value in the parameter pack, resulting in an expression equivalent to (1*1) + (2*2) + (3*3)
:
#include <iostream>
template <typename... Types>
auto Fold(Types... Args){
return ((Args * Args) + ...);
}
int main(){
std::cout << "Result: " << Fold(1, 2, 3);
}
Result: 14
Below, we send every value of our parameter pack into a function and use the function's return value in our fold expression. In this case, our function just logs the value, and then returns it unmodified:
#include <iostream>
int Log(int Arg){
std::cout << "Arg: " << Arg << '\n';
return Arg;
}
template <typename... Types>
auto Fold(Types... Args){
return (Log(Args) + ...);
}
int main(){
int Result{Fold(5, 10, 20)};
std::cout << "Result: " << Result;
}
Arg: 5
Arg: 10
Arg: 20
Result: 35
Folding Over the Comma Operator
Often, we will simply want to iterate over every parameter in our container - we may not care what the fold expression returns. For this, we can fold over the comma operator ,
The following example is similar to the previous, except instead of logging and summing our parameters, we only want to log them. As such, we can replace the +
operator with ,
and change our return types to void
:
#include <iostream>
template <typename T>
void Log(T Object){
std::cout << Object << ' ';
}
template <typename... Types>
void Fold(Types... Args){
(Log(Args), ...);
}
int main(){
Fold("Hello", "World");
}
In this case, we can imagine the expression (Log(Args), ...);
expanding to Log("Hello"), Log("World");
to generate the output:
Hello World
Using Lambdas
We can replace our Log()
function from the previous example with a lambda, which we pass Args
to:
#include <iostream>
template <typename... Types>
void Fold(Types... Args){
(
[](auto& Arg){
std::cout << Arg << ' ';
}(Args),
...
);
}
int main(){
Fold("Hello", "World");
}
Hello World
In this case, the Args
we pass to the lambda is the same as the Args
parameter of the outer Fold()
function:
template <typename... Types>
void Fold(Types... Args){
(
[](auto& Arg){
std::cout << Arg << ' ';
}(Args),
...
);
}
As such, this example can be simplified by having the lambda capture Args
directly from the outer function's scope using [&Args]
or simply [&]
as the capture group:
[&](auto& Arg){
std::cout << Args << ' ';
}(Args)
This allows us to remove both the parameter list from our lambda, and the argument when we invoke it:
[&]{
std::cout << Args << ' ';
}()
Let's put everything together:
#include <iostream>
template <typename... Types>
void Fold(Types... Args){
(
[&]{ std::cout << Args << ' '; }(),
...
);
}
int main(){
Fold("Hello", "World");
}
Hello World
Left Folds and Right Folds
There are two ways a fold operation can be implemented - these are generally called left folds and right folds. The difference is the order in which the parameters in the parameter pack are combined to generate the return value.
We control the direction of the fold by reordering the components of the fold expression:
template <typename... Types>
auto LeftFold(Types... Args){
return (... + Args);
}
template <typename... Types>
auto RightFold(Types... Args){
return (Args + ...);
}
For some operators, the fold direction doesn't matter. For example, addition is associative - that is, given a list of numbers, their sum will be the same regardless of the order in which the numbers are added.
But that is not always the case. For example, subtraction is not associative. The following example shows a left fold and right fold in that context:
#include <iostream>
template <typename... Types>
auto LeftFold(Types... Args){
return (... - Args);
}
template <typename... Types>
auto RightFold(Types... Args){
return (Args - ...);
}
int main(){
std::cout << "(5 - 10) - 20 = ";
std::cout << LeftFold(5, 10, 20);
std::cout << "\n5 - (10 - 20) = ";
std::cout << RightFold(5, 10, 20);
}
Even though the parameter pack is the same in each case, each fold type composes the operations in a different order, thereby generating different return values. LeftFold()
returns -25
, whilst RightFold()
returns 15
:
(5 - 10) - 20 = -25
5 - (10 - 20) = 15
Binary Folds
We have the option of adding a second operand to a fold expression, thereby creating a binary fold. This additional operand is sometimes referred to as the "initial value". Below, we demonstrate the syntax using 0
as the initial value:
template <typename... Types>
int BinaryFold(Types... Args){
return (0 + ... + Args);
}
Like unary folds, binary folds have two variants - commonly called right and left, which we can control by reordering the components of our fold expression:
#include <iostream>
template <typename... Types>
int BinaryLeftFold(Types... Args){
return (0 - ... - Args);
}
template <typename... Types>
int BinaryRightFold(Types... Args){
return (Args - ... - 0);
}
int main(){
std::cout << "((0 - 5) - 10) - 20 = ";
std::cout << BinaryLeftFold(5, 10, 20);
std::cout << "\n5 - (10 - (20 - 0)) = ";
std::cout << BinaryRightFold(5, 10, 20);
}
((0 - 5) - 10) - 20 = -35
5 - (10 - (20 - 0)) = 15
Binary folds have two main uses. First, they allow us to handle empty parameter packs without causing compilation errors.
In the following example, the binary fold function will return 0
when called with no arguments, whilst the unary fold function will cause a compilation error:
template <typename... Types>
int BinaryFold(Types... Args){
return (0 + ... + Args);
}
template <typename... Types>
int UnaryFold(Types... Args){
return (... + Args);
}
int main(){
BinaryFold(); // Returns 0
UnaryFold(); // Compilation error
}
error: a unary fold expression over '+' must have a non-empty expansion
see reference to function template instantiation 'int UnaryFold<>(void)'
Secondly, fold expressions are not limited to arithmetic operations. We can fold over any operator, and binary fold expressions provide additional flexibility in this regard.
The following example logs everything in a parameter pack, using <<
as the operator, and std::cout
as the initial operand:
#include <iostream>
template <typename... Types>
void Fold(Types... Args){
(std::cout << ... << Args);
}
int main(){
Fold("Hello ", "World");
}
Hello World
The previous example works because the initial expression will be std::cout << "Hello "
. As we've seen in all our previous examples of terminal logging, this expression returns a reference to the std::cout
object, allowing us to chain more values to the terminal.
The previous fold expression is effectively equivalent to:
(std::cout << "Hello ") << "World";
If our parameter pack had a third value, like the string "!!!"
, our fold expression would be:
((std::cout << "Hello ") << "World") << "!!!";
This pattern continues for any number of parameters.
Summary
In this lesson, we explored fold expressions, a C++17 feature that can make working with parameter packs easier. The key points to remember include:
- C++17 fold expressions combine a parameter pack and an operator, separated by the
...
syntax. - Fold expressions can be either unary (using one operand - the parameter pack) or binary (using two operands - the parameter pack and an initial value).
- Using fold expressions with arithmetic operations to perform calculations on parameter packs.
- The concept of left folds and right folds and their significance in operation ordering.
- How to use the comma operator in fold expressions for iterating over parameter packs and executing side effects.
- Addressing the potential issue of overloaded comma operators in fold expressions.
- The utility of binary folds in handling empty parameter packs and their application beyond arithmetic operations, including logging with
std::cout
.
Perfect Forwarding and std::forward
An introduction to problems that can arise when our functions forward their parameters to other functions, and how we can solve those problems with std::forward