Cpp Notes

ch11.fold_expressions

C++17 - The complete guide, Ch 11:　Fold Expressions

  • Since C++17, there is a feature to compute the result of using a binary operator over all the arguments of a parameter pack.
  • For example, the following function returns the sum of all passed arguments:
template <typename... T>
auto foldSum(T... args) {
  return (... + args);  // ((arg1 + arg2) + arg3) ...
}
  • Note that the parentheses around the return expression are part of the fold expression and cannot be omitted.
  • Calling the function with foldSum(47, 11, val, -1); instantiates the template to perform: return 47 + 11 + val + -1;
  • Calling it for foldSum(std::string("hello"), "world", "!"); instantiates the template for: return std::string("hello") + "world" + "!";
  • Also note that the order of fold expression arguments can differ and is important (and might look a bit counter-intuitive):
    • (... + args) results in ((arg1 + arg2) + arg3) ... which means that the fold expression repeatedly “post-adds” things.
    • (args + ...) which repeatedly “pre-adds” things, so that the resulting expression is: (arg1 + (arg2 + arg3)) ...
  • (Personal notes: think of ... as what has been calculated.)

11.1 Motivation for Fold Expressions

  • Fold expressions avoid the need to recursively instantiate templates to perform an operation on all parameters of a parameter pack. Before C++17, you had to implement:
template <typename T>
auto foldSumRec(T arg) {
  return arg;
}

template <typename T1, typename... Ts>
auto foldSumRec(T1 arg1, Ts... otherArgs) {
  return arg1 + foldSumRec(otherArgs...);
}
  • Such an implementation is not only cumbersome to write, it also stresses C++ compilers.

🆚 With this, the effort reduces significantly for both the programmer and the compiler.

template <typename... T>
auto foldSum(T... args) {
  return (... + args);  // arg1 + arg2 + arg3 ...
}

11.2 Using Fold Expressions

Given a parameter args and an operator op, C++17 allows us to write

  • Either a unary left fold ( ... op args )

    • which expands to: ((arg1 op arg2) op arg3) op ...

  • Or a unary right fold ( args op ... )

    • which expands to: arg1 op (arg2 op ... (argN-1 op argN))

  • The parentheses are required. However, the parentheses and the ellipsis (...) do not have to be separated by white spaces.

  • The difference between left and right fold is important more often than expected.

    • For example, there might be different effects even when you use operator +. With the left fold expression:
template <typename... T>
auto foldSumL(T... args) {
  return (... + args);  // ((arg1 + arg2) + arg3) ...
}
  • the call foldSumL(1, 2, 3) evaluates to: ((1 + 2) + 3) This also means that the following example compiles:
std::cout << foldSumL(std::string("hello"), "world", "!") << '\n'; // OK
  • Remember that operator + is defined for standard strings provided at least one operand is a std::string. Because the left fold is used, the call first evaluates std::string("hello") + "world" which returns a std::string, so that adding the string literal "!" is then also valid.

🆚 However, a call such as

  • std::cout << foldSumL("hello", "world", std::string("!")) << '\n'; // ERROR will not compile because it evaluates to ("hello" + "world") + std::string("!") and adding two string literals is not allowed.

🆚 However, if we change the implementation to:

template <typename... T>
auto foldSumR(T... args) {
  return (args + ...);  // (arg1 + (arg2 + arg3)) ...
}
  • the call foldSumR(1, 2, 3) evaluates to: (1 + (2 + 3)) which means that the following example no longer compiles:
std::cout << foldSumR(std::string("hello"), "world", "!") << '\n'; // ERROR

🆚 while the following call does now compile:

std::cout << foldSumR("hello", "world", std::string("!")) << '\n'; // OK

In almost all cases, evaluation from left to right is the intention. Therefore, the left fold syntax with the parameter pack at the end should usually be preferred: (... + args); // preferred syntax for fold expressions

11.2.1 Dealing with Empty Parameter Packs

If a fold expression is used with an empty parameter pack, the following rules apply:

  • If operator && is used, the value is true.
  • If operator || is used, the value is false.
  • If the comma operator is used, the value is void().
  • For all other operators, the call is ill-formed.

For all other cases (and in general), you can add an initial value: given a parameter pack args, an initial value value, and an operator op, C++17 also allows us to write

  • Either a binary left fold ( value op ... op args ) which expands to: (((value op arg1) op arg2) op arg3) op ...
  • Or a binary right fold ( args op ... op value ) which expands to: arg1 op (arg2 op ... (argN op value)))
  • The operator op has to be the same on both sides of the ellipsis.

For example, the following definition allows you to pass an empty parameter pack when adding values:

template <typename... T>
auto foldSum(T... s) {
  return (0 + ... + s);  // even works if sizeof...(s)==0
}
  • From a concept perspective, whether we add 0 as the first or last operand should be irrelevant:
template<typename... T>
auto foldSum (T... s){
  return (s + ... + 0); // even works if sizeof...(s)==0
}
  • However, as for unary fold expressions, the different evaluation order is important more often than expected and the binary left fold should be preferred:
(val + ... + args); // preferred syntax for binary fold expressions

Also, the first operand might be special, such as in this example:

template<typename... T>
void print (const T&... args)
{
  (std::cout << ... << args) << '\n';
}
  • Here, it is important that the first call is the output of the first passed argument to print(), which returns the stream to perform the other output calls.

🆚 Other implementations might not compile or might even do something unexpected. For example, with

std::cout << (args << ... << '\n');

  • a call like print(1) will compile but print the value 1 left shifted by the value of ’\n’, which is usually 10, so that the resulting output is 1024.

  • Note that in this print() example, no whitespace separates all the elements of the parameter pack from each other. A call such as print("hello", 42, "world") will print: hello42world To separate the passed elements with spaces, you need a helper that ensures that the output of any but the first argument is extended by a leading space.

  • This can be done, for example, with a helper function template spaceBefore():

template <typename T>
const T& spaceBefore(const T& arg) {
  std::cout << ' ';
  return arg;
}

template <typename First, typename... Args>
void print(const First& first_arg, const Args&... args) {
  std::cout << first_arg;
  (std::cout << ... << spaceBefore(args)) << '\n';
}

Here, (std::cout << ... << spaceBefore(args)) is a fold expression that expands to:

std::cout << spaceBefore(arg1) << spaceBefore(arg2) << ...

  • Thus, for each element in the parameter pack args, the expression calls a helper function, that prints out a space character before returning the passed argument, writing it to std::cout.

  • To ensure that this does not apply to the first argument, we add an additional first parameter that does not use spaceBefore().

  • Note that the evaluation of the output of the parameter pack requires that all output on the left is done before spaceBefore() is called for the actual element. Thanks to the defined evaluation order of operator << and function calls, this is guaranteed to work since C++17.

  • We can also use a lambda to define spaceBefore() inside print():

template <typename First, typename... Args>
void print(const First& firstarg, const Args&... args) {
  std::cout << firstarg;
  auto spaceBefore = [](const auto& arg) {
    std::cout << ' ';
    return arg;
  };
  (std::cout << ... << spaceBefore(args)) << '\n';
}

However, note that by default, lambdas return objects by value, which means that this would create an unnecessary copy of the passed argument.

  • The way to avoid that is to explicitly declare the return type of the lambda to be const auto& or decltype(auto):
template <typename First, typename... Args>
void print(const First& firstarg, const Args&... args) {
  std::cout << firstarg;
  auto spaceBefore = [](const auto& arg) -> const auto& {
    std::cout << ' ';
    return arg;
  };
  (std::cout << ... << spaceBefore(args)) << '\n';
}
  • C++ would not be C++ if you were not able to combine this all in one statement:
template <typename First, typename... Args>
void print(const First& first_arg, const Args&... args) {
  std::cout << first_arg;
  //------------------------------------------------------
  (std::cout << ... << [](const auto& arg) -> decltype(auto) {
    std::cout << ' ';
    return arg;
  }(args))
      << '\n';
}

  • decltype(auto) essentially follows the same rules as auto for type deduction, and when you return arg, which you passed in as const reference, you are returning it as a const reference as well.

  • Nevertheless, a simpler way to implement print() is to use a lambda that prints both the space and the argument and then pass this to a unary fold:

template <typename First, typename... Args>
void print(First first, const Args&... args) {
  std::cout << first;
  auto outWithSpace = [](const auto& arg) { std::cout << ' ' << arg; };
  (..., outWithSpace(args));
  std::cout << '\n';
}
  • By using an additional template parameter declared with auto, we can make print() even more flexible so that it is parameterized for the separator to be a character, a string, or any other printable type.

11.2.2 Supported Operators

You can use all binary operators for fold expressions except ., ->, and [].

🛎️ Folded Function Calls

Fold expressions can also be used with the comma operator, combining multiple function calls into one statement.

  • That is, you can now simply implement below to call function foo() for all passed arguments.
template <typename... Types>
void callFoo(const Types&... args) {
  // ...
  (..., foo(args));  // calls foo(arg1), foo(arg2), foo(arg3), ...
}

Alternatively, if move semantics should be supported:

template <typename... Types>
void callFoo(Types&&... args) {
  // ...
  (..., foo(std::forward<Types>(args)));  // calls foo(arg1), foo(arg2), ...
}
  • To make this code safe in case the called function returns a value of a type with an overloaded comma operator, you should cast the return type to void:
template<typename... Types>
void callFoo(const Types&... args) {
  // ...
  (... , (void)foo(std::forward<Types>(args))); // calls foo(arg1), foo(arg2), ...
}

Note that due to the nature of the comma operator, whether we use the left or right fold operator is usually irrelevant.

  • The functions are always called from left to right. With (foo(args) , ...); the parentheses only group the calls so that the first foo() call is combined with the result of the next two foo() calls as follows: foo(arg1) , (foo(arg2) , foo(arg3));
  • However, because the evaluation order of the comma operator is usually from left to right, the first call still takes place before the group of two calls inside the parentheses, while within the parentheses, the middle call still takes place before the right call.
  • Nevertheless, as the left fold expression matches with the “native” evaluation order, again the use of left fold expressions is recommended if you use fold expressions for multiple function calls.

🛎️ Combining Hash Functions

Another example of using the comma operator for fold expressions is to combine hash values. This can be done as follows:

template <typename T>
void hashCombine(std::size_t& seed, const T& val) {
  seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

template <typename... Types>
std::size_t combinedHashValue(const Types&... args) {
  std::size_t seed = 0;            // initial seed
  (..., hashCombine(seed, args));  // chain of hashCombine() calls
  return seed;
}
  • By calling combinedHashValue ("Hi", "World", 42); the statement in the middle expands to:
hashCombine(seed,"Hi"), (hashCombine(seed,"World"), hashCombine(seed,42);
  • With these definitions, we can easily define a new hash function object for a type such as Customer to use it in an unordered set or as a key in an unordered map:
struct CustomerHash {
  std::size_t operator()(const Customer& c) const {
    return combinedHashValue(c.getFirstname(), c.getLastname(), c.getValue());
  }
};

std::unordered_set<Customer, CustomerHash> coll;
std::unordered_map<Customer, std::string, CustomerHash> map;

🛎️ Folded Function Calls for Base Classes

  • Folded function calls can even be used in more complex expressions. For example, you can fold the comma operator to perform function calls of member functions of a variadic number of base classes:
#include <iostream>
// template for variadic number of base classes
template <typename... Bases>
class MultiBase : private Bases... {
 public:
  void print() {
    // call print() of all base classes:
    (..., Bases::print());
  }
};
struct A {
  void print() { std::cout << "A::print()\n"; }
};
struct B {
  void print() { std::cout << "B::print()\n"; }
};
struct C {
  void print() { std::cout << "C::print()\n"; }
};
int main() {
  MultiBase<A, B, C> mb;
  mb.print();
}

Here, this allows us to initialize objects with a variadic number of base classes: MultiBase<A,B,C> mb;

template <typename... Bases>
class MultiBase : private Bases... {
  ...
};
  • Furthermore, with (... , Bases::print()); a fold expression is used to expand this to call print for each base class. That is, the statement with the fold expression expands to the following: (A::print() , B::print()) , C::print();

🛎️ Folded Path Traversals

  • You can also use a fold expression to traverse a path in a binary tree with operator ->*.
  • Consider the following recursive data structure:
struct Node {
  int value;
  Node* subLeft{nullptr};
  Node* subRight{nullptr};
  Node(int i = 0) : value{i} {}
  int getValue() const { return value; }

  //...

  // traverse helpers:
  static constexpr auto left = &Node::subLeft;
  static constexpr auto right = &Node::subRight;
  // traverse tree, using fold expression:
  // (Personal notes: not traversing the whole tree, just traverse as
  // the path that user specified - hence the result int next snippet)
  template <typename T, typename... TP>
  static Node* traverse(T np, TP... paths) {
    return (np->*...->*paths);  // np ->* paths1 ->* paths2 ...
  }
};

Here, (np ->* ... ->*paths) uses a fold expression to traverse the variadic elements of paths from np, which can be used as follows:

#include <iostream>

#include "foldtraverse.hpp"
int main() {
  // init binary tree structure:
  Node* root = new Node{0};
  root->subLeft = new Node{1};
  root->subLeft->subRight = new Node{2};
  //...

  // traverse binary tree:

  Node* node = Node::traverse(root, Node::left, Node::right);
  std::cout << node->getValue() << '\n';   // print 2

  node = root->*Node::left->*Node::right;
  std::cout << node->getValue() << '\n';   // also print 2

  node = root->subLeft->subRight;
  std::cout << node->getValue() << '\n';   // also print 2

  // E.g. all above 3s will print out value 2!! What traverse do is just
  // traversing the ordering that user gives!
  // E.g. Node::traverse(root, Node::left, Node::left) would have resulted
  // in a nullptr being returned!
}
  • When calling Node::traverse(root, Node::left, Node::right); the call of the fold expression expands to: root ->* Node::left ->* Node::right, which results in: root -> subLeft -> (sub's)subRight

11.2.3 Using Fold Expressions for Types

  • By using type traits, we can also use fold expressions to deal with template parameter packs (an arbitrary number of types passed as template parameters). For example, you can use a fold expression to find out whether a list of types is homogeneous:
#include <type_traits>

// unary right fold ( args op ... )
// which expands to: arg1 op (arg2 op ... (argN-1 op argN))


// check whether passed types are homogeneous:
template <typename T1, typename... TN>
struct IsHomogeneous {
  static constexpr bool value = (std::is_same_v<T1, TN> && ...);
};

// check whether passed arguments have the same type:
template <typename T1, typename... TN>
constexpr bool isHomogeneous(T1, TN...) {
  return (std::is_same_v<T1, TN> && ...);
}
  • The type trait IsHomogeneous<> can be used, for example, as follows:
IsHomogeneous<int, Size, decltype(42)>::value
  • In this case, the fold expression that initializes the member value expands to:
std::is_same_v<int, MyType> && std::is_same_v<int,decltype(42)>
  • The function template isHomogeneous<>() can be used, for example, as follows:
isHomogeneous(43, -1, "hello", nullptr)
  • In this case, the fold expression that initializes the member value expands to:
std::is_same_v<int, int> && std::is_same_v<int, const char*> && std::is_same_v<int, std::nullptr_t>
  • As usual, operator && short-circuits (aborts the evaluation after the first false).
  • The deduction guide for std::array<> uses this feature in the standard library.
Previous ch10.compile_time_if Next ch12.string_literals_as_template_parameters