Implementing handy helper functions with fold expressions

Since C++11, there are variadic template parameter packs, which enable implementing functions that accept arbitrarily many parameters. Sometimes, these parameters are all combined into one expression in order to derive the function result from that. This task became really easy with C++17, as it comes with fold expressions.

How to do it...

Let's implement a function that takes arbitrarily many parameters and returns their sum:

1. At first, we define its signature:

      template <typename ... Ts>
      auto sum(Ts ... ts);

2. So, we have a parameter pack ts now, and the function should expand all the parameters and sum them together using a fold expression. If we use any operator (+, in this example) together with ... in order to apply it to all the values of a parameter pack, we need to surround the expression with parentheses:

      template <typename ... Ts>
      auto sum(Ts ... ts)
      {
          return (ts + ...);
      }

3. We can now call it this way:

      int the_sum {sum(1, 2, 3, 4, 5)}; // Value: 15

4. It does not only work with int types; we can call it with any type that just implements the + operator, such as std::string:

      std::string a {"Hello "};
      std::string b {"World"};
      
      std::cout << sum(a, b) << '\n'; // Output: Hello World

How it works...

What we just did was a simple recursive application of a binary operator (+) to its parameters. This is generally called folding. C++17 comes with fold expressions, which help expressing the same idea with less code.

This kind of expression is called unary fold. C++17 supports folding parameter packs with the following binary operators: +, -, *, /, %, ^, &, |, =, <, >, <<, >>, +=, -=, *=, /=, %=, ^=, &=, |=, <<=, >>=, ==, !=, <=, >=, &&, ||, ,, .*, ->*.

By the way, in our example code, it does not matter if we write (ts + …) or (… + ts); both work. However, there is a difference that may be relevant in other cases--if the … dots are on the right-hand side of the operator, the fold is called a right fold. If they are on the left-hand side, it is a left fold.

In our sum example, a unary left fold expands to 1 + (2 + (3 + (4 + 5))), while a unary right fold will expand to (((1 + 2) + 3) + 4) + 5. Depending on the operator in use, this can make a difference. When adding numbers, it does not.

There's more...

In case someone calls sum() with no arguments, the variadic parameter pack contains no values that could be folded. For most operators, this is an error (for some, it is not; we will see this in a minute). We then need to decide if this should stay an error or if an empty sum should result in a specific value. The obvious idea is that the sum of nothing is 0.

This is how it’s done:

template <typename ... Ts>
auto sum(Ts ... ts)
{
    return (ts + ... + 0);
}

This way, sum() evaluates to 0, and sum(1, 2, 3) evaluates to (1 + (2 + (3 + 0))). Such folds with an initial value are called binary folds.

Again, it works if we write (ts + ... + 0), or (0 + ... + ts), but this makes the binary fold a binary right fold or a binary left fold again. Check out the following diagram:

When using binary folds in order to implement the no-argument case, the notion of an identity element is often important--in this case, adding a 0 to any number changes nothing, which makes 0 an identity element. Because of this property, we can add a 0 to any fold expression with the operators + or -, which leads to the result 0 in case there are no parameters in the parameter pack. From a mathematical point of view, this is correct. From an implementation view, we need to define what is correct, depending on what we need.

The same principle applies to multiplication. Here, the identity element is 1:

template <typename ... Ts>
auto product(Ts ... ts)
{
    return (ts * ... * 1);
}

The result of product(2, 3) is 6, and the result of product() without parameters is 1.

The logical and (&&) and or (||) operators come with built-in identity elements. Folding an empty parameter pack with && results in true, and folding an empty parameter pack with || results in false.

Another operator that defaults to a certain expression when applied on empty parameter packs is the comma operator (,), which then defaults to void().

In order to ignite some inspiration, let's have a look at some more little helpers that we can implement using this feature.

Match ranges against individual items

How about a function that tells whether some range contains at least one of the values we provide as variadic parameters:

template <typename R, typename ... Ts>
auto matches(const R& range, Ts ... ts)
{
    return (std::count(std::begin(range), std::end(range), ts) + ...);
}

The helper function uses the std::count function from the STL. This function takes three parameters: the first two parameters are the begin and end iterators of some iterable range, and as the third parameter, it takes a value which will be compared to all the items of the range. The std::count method then returns the number of all the elements within the range that are equal to the third parameter.

In our fold expression, we always feed the begin and end iterators of the same parameter range into the std::count function. However, as the third parameter, each time we put one other parameter from the parameter pack into it. In the end, the function sums up all the results and returns it to the caller.

We can use it like this:

std::vector<int> v {1, 2, 3, 4, 5};

matches(v,         2, 5);          // returns 2
matches(v,         100, 200);      // returns 0
matches("abcdefg", 'x', 'y', 'z'); // returns 0
matches("abcdefg", 'a', 'd', 'f'); // returns 3

As we can see, the matches helper function is quite versatile--it can be called on vectors or even on strings directly. It would also work on initializer lists, on instances of std::list, std::array, std::set, and so on!

Check if multiple insertions into a set are successful

Let's write a helper that inserts an arbitrary number of variadic parameters into an std::set and returns if all the insertions are successful:

template <typename T, typename ... Ts>
bool insert_all(T &set, Ts ... ts)
{
    return (set.insert(ts).second && ...);
}

So, how does this work? The insert function of std::set has the following signature:

std::pair<iterator, bool> insert(const value_type& value);

The documentation says that when we try to insert an item, the insert function will return an iterator and a bool variable in a pair. The bool value is true if the insertion is successful. If it is successful, the iterator points to the new element in the set. Otherwise, the iterator points to the existing item, which would collide with the item to be inserted.

Our helper function accesses the .second field after insertion, which is just the bool variable that reflects success or fail. If all the insertions lead to true in all the return pairs, then all the insertions were successful. The fold expression combines all the insertion results with the && operator and returns the result.

We can use it like this:

std::set<int> my_set {1, 2, 3};

insert_all(my_set, 4, 5, 6); // Returns true
insert_all(my_set, 7, 8, 2); // Returns false, because the 2 collides

Note that if we try to insert, for example, three elements, but the second element can already not be inserted, the && ... fold will short-circuit and stop inserting all the other elements:

std::set<int> my_set {1, 2, 3};

insert_all(my_set, 4, 2, 5); // Returns false
// set contains {1, 2, 3, 4} now, without the 5!

 

Check if all the parameters are within a certain range

If we can check if one variable is within some specific range, we can also do the same thing with multiple variables using fold expressions:

template <typename T, typename ... Ts>
bool within(T min, T max, Ts ...ts)
{
    return ((min <= ts && ts <= max) && ...);
}

The expression, (min <= ts && ts <= max), does tell for every value of the parameter pack if it is between min and max (including min and max). We choose the && operator to reduce all the Boolean results to a single one, which is only true if all the individual results are true.

This is how it looks in action:

within( 10,  20,  1, 15, 30);    // --> false
within( 10,  20,  11, 12, 13);   // --> true
within(5.0, 5.5,  5.1, 5.2, 5.3) // --> true

Interestingly, this function is very versatile because the only requirement it imposes on the types we use is that they are comparable with the <= operator. And this requirement is also fulfilled by std::string, for example:

std::string aaa {"aaa"};
std::string bcd {"bcd"};
std::string def {"def"};
std::string zzz {"zzz"};

within(aaa, zzz,  bcd, def); // --> true
within(aaa, def,  bcd, zzz); // --> false

 

Pushing multiple items into a vector

It's also possible to write a helper that does not reduce any results but processes multiple actions of the same kind. Like inserting items into an std::vector, which does not return any results (std::vector::insert() signalizes error by throwing exceptions):

template <typename T, typename ... Ts>
void insert_all(std::vector<T> &vec, Ts ... ts)
{
    (vec.push_back(ts), ...);
}

int main()
{
    std::vector<int> v {1, 2, 3};
    insert_all(v, 4, 5, 6);
}

Note that we use the comma (,) operator in order to expand the parameter pack into individual vec.push_back(...) calls without folding the actual result. This function also works nicely with an empty parameter pack because the comma operator has an implicit identity element, void(), which translates to do nothing.