Using fold expressions to simplify variadic function templates

In this chapter, we are discussing folding several times; this is an operation that applies a binary function to a range of values to produce a single value. We have seen this when we discussed variadic function templates, and will see it again with higher-order functions. It turns out there is a significant number of cases where the expansion of a parameter pack in variadic function templates is basically a folding operation. To simplify writing such variadic function templates, C++17 introduced fold expressions, which fold an expansion of a parameter pack over a binary operator. In this recipe, we will learn how to use fold expressions to simplify writing variadic function templates.

Getting ready

The examples in this recipe are based on the variadic function template add (), which we wrote in the previous recipe, Writing a function template with a variable number of arguments. That implementation is a left-folding operation. For simplicity, we'll present the function again:

template <typename T>
T add(T value)
{
  return value;
}
template <typename T, typename... Ts>
T add(T head, Ts... rest)
{
  return head + add(rest...);
}

In the next section, we will learn how this particular implementation can be simplified, as well as other examples of using fold expressions.

How to do it...

To fold a parameter pack over a binary operator, use one of the following forms:

• Left folding with a unary form (... op pack):

  template <typename... Ts>
  auto add(Ts... args)
  {
    return (... + args);
  }
  

• Left folding with a binary form (init op ... op pack):

  template <typename... Ts>
  auto add_to_one(Ts... args)
  {
    return (1 + ... + args);
  }
  

• Right folding with a unary form (pack op ...):

  template <typename... Ts>
  auto add(Ts... args)
  {
    return (args + ...);
  }
  

• Right folding with a binary form (pack op ... op init):

  template <typename... Ts>
  auto add_to_one(Ts... args)
  {
    return (args + ... + 1);
  }
  

How it works...

When the compiler encounters a fold expression, it expands it in one of the following expressions:

When the binary form is used, the operator on both the left-hand and right-hand sides of the ellipses must be the same, and the initialization value must not contain an unexpanded parameter pack.

The following binary operators are supported with fold expressions:

When using the unary form, only operators such as *, +, &, |, &&, ||, and , (comma) are allowed with an empty parameter pack. In this case, the value of the empty pack is as follows:

Now that we have the function templates we implemented earlier (let's consider the left-folding version), we can write the following code:

auto sum = add(1, 2, 3, 4, 5);         // sum = 15
auto sum1 = add_to_one(1, 2, 3, 4, 5); // sum = 16

Considering the add(1, 2, 3, 4, 5) call, it will produce the following function:

int add(int arg1, int arg2, int arg3, int arg4, int arg5)
{
  return ((((arg1 + arg2) + arg3) + arg4) + arg5);
}

It's worth mentioning that due to the aggressive ways modern compilers do optimizations, this function can be inlined and, eventually, we may end up with an expression such as auto sum = 1 + 2 + 3 + 4 + 5.

There's more...

Fold expressions work with all overloads for the supported binary operators, but do not work with arbitrary binary functions. It is possible to implement a workaround for that by providing a wrapper type that will hold a value and an overloaded operator for that wrapper type:

template <typename T>
struct wrapper
{
  T const & value;
};
template <typename T>
constexpr auto operator<(wrapper<T> const & lhs,
                         wrapper<T> const & rhs)
{
  return wrapper<T> {
    lhs.value < rhs.value ? lhs.value : rhs.value};
}

In the preceding code, wrapper is a simple class template that holds a constant reference to a value of type T. An overloaded operator< is provided for this class template; this overload does not return a Boolean to indicate that the first argument is less than the second, but actually an instance of the wrapper class type to hold the minimum value of the two arguments. The variadic function template min (), shown here, uses this overloaded operator< to fold the pack of arguments expanded to instances of the wrapper class template:

template <typename... Ts>
constexpr auto min(Ts&&... args)
{
  return (wrapper<Ts>{args} < ...).value;
}
auto m = min(3, 1, 2); // m = 1

This min() function is expanded by the compiler to something that could look like the following:

template<>
inline constexpr int min<int, int, int>(int && __args0,
                                        int && __args1,
                                        int && __args2)
{
  return
    operator<(wrapper_min<int>{__args0},
      operator<(wrapper_min<int>{__args1},
                wrapper_min<int>{__args2})).value;
}

What we can see here is cascading calls to the binary operator < that return a Wrapper<int> value. Without this, an implementation of the min() function using fold expressions would not be possible. The following implementation does not work:

template <typename... Ts>
constexpr auto minimum(Ts&&... args)
{
  return (args < ...);
}

The compiler would transform this, based on the call min(3, 1, 2), to something such as the following:

template<>
inline constexpr bool minimum<int, int, int>(int && __args0,
                                             int && __args1,
                                             int && __args2)
{
  return __args0 < (static_cast<int>(__args1 < __args2));
}

The result is a function that returns a Boolean, and not the actual integer value, which is the minimum between the supplied arguments.

See also

• Implementing higher-order functions map and fold to learn about higher-order functions in functional programming and how to implement the widely used map and fold (or reduce) functions