Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

3 Exploring Functions

Functions are a fundamental concept in programming; regardless of the topic we discuss, we end up writing functions. Trying to cover functions in a single chapter is not only hard but also not very rational. Being a fundamental element of the language, functions are encountered in every recipe of this book. This chapter, however, covers modern language features related to functions and callable objects, with a focus on lambda expressions, concepts from functional languages such as higher-order functions, and type-safe functions with a variable number of arguments.

The recipes included in this chapter are as follows:

Defaulted and deleted functions
Using lambdas with standard algorithms
Using generic and template lambdas
Writing a recursive lambda
Writing a function template with a variable number of arguments
Using fold expressions to simplify variadic function templates
Implementing the higher-order functions map and fold
Composing functions into a higher-order function
Uniformly invoking anything callable

We will start this chapter by learning about a feature that makes it easier for us to provide special class member functions or prevent any function (member or non-member) from being invoked.

Defaulted and deleted functions

In C++, classes have special members (constructors, destructors, and assignment operators) that may be either implemented by default by the compiler or supplied by the developer. However, the rules for what can be default implemented are a bit complicated and can lead to problems. On the other hand, developers sometimes want to prevent objects from being copied, moved, or constructed in a particular way. This is possible by implementing different tricks using these special members. The C++11 standard has simplified many of these by allowing functions to be deleted or defaulted in the manner we will see in the next section.

Getting started

For this recipe, you need to be familiar with the following concepts:

Special member functions (default constructor, destructor, copy constructor, move constructor, copy assignment operator, move assignment operator)
The copyable concept (a class features a copy constructor and copy assignment operator making it possible to create copies)
The moveable concept (a class features a move constructor and a move assignment operator making it possible to move objects)

With this in mind, let's learn how to define default and deleted special functions.

How to do it...

Use the following syntax to specify how functions should be handled:

To default a function, use =default instead of the function body. Only special class member functions that have defaults can be defaulted:
```
struct foo
{
  foo() = default;
};
```
To delete a function, use =delete instead of the function body. Any function, including non-member functions, can be deleted:
```
struct foo
{
  foo(foo const &) = delete;
};
void func(int) = delete;
```

Use defaulted and deleted functions to achieve various design goals, such as the following examples:

To implement a class that is not copyable, and implicitly not movable, declare the copy constructor and the copy assignment operator as deleted:

class foo_not_copyable
{
public:
  foo_not_copyable() = default;
  foo_not_copyable(foo_not_copyable const &) = delete;
  foo_not_copyable& operator=(foo_not_copyable const&) = delete;
};

To implement a class that is not copyable, but is movable, declare the copy operations as deleted and explicitly implement the move operations (and provide any additional constructors that are needed):

class data_wrapper
{
  Data* data;
public:
  data_wrapper(Data* d = nullptr) : data(d) {}
  ~data_wrapper() { delete data; }
  data_wrapper(data_wrapper const&) = delete;
  data_wrapper& operator=(data_wrapper const &) = delete;
  data_wrapper(data_wrapper&& other) :data(std::move(other.data))
  {
    other.data = nullptr;
  }
  data_wrapper& operator=(data_wrapper&& other)
  {
    if (this != std::addressof(other))
    {
      delete data;
      data = std::move(other.data);
      other.data = nullptr;
    }
    return *this;
  }
};

To ensure a function is called only with objects of a specific type, and perhaps prevent type promotion, provide deleted overloads for the function (the following example with free functions can also be applied to any class member functions):
```
template <typename T>
void run(T val) = delete;
void run(long val) {} // can only be called with long integers
```

How it works...

A class has several special members that can be implemented, by default, by the compiler. These are the default constructor, copy constructor, move constructor, copy assignment, move assignment, and destructor (for a discussion on move semantics, refer to the Implementing move semantics recipe in Chapter 9, Robustness and Performance). If you don't implement them, then the compiler does it so that instances of a class can be created, moved, copied, and destructed. However, if you explicitly provide one or more of these special methods, then the compiler will not generate the others according to the following rules:

If a user-defined constructor exists, the default constructor is not generated by default.
If a user-defined virtual destructor exists, the default constructor is not generated by default.
If a user-defined move constructor or move assignment operator exists, then the copy constructor and copy assignment operator are not generated by default.
If a user-defined copy constructor, move constructor, copy assignment operator, move assignment operator, or destructor exists, then the move constructor and move assignment operator are not generated by default.
If a user-defined copy constructor or destructor exists, then the copy assignment operator is generated by default.
If a user-defined copy assignment operator or destructor exists, then the copy constructor is generated by default.

Note that the last two rules in the preceding list are deprecated rules and may no longer be supported by your compiler.

Sometimes, developers need to provide empty implementations of these special members or hide them in order to prevent the instances of the class from being constructed in a specific manner. A typical example is a class that is not supposed to be copyable. The classical pattern for this is to provide a default constructor and hide the copy constructor and copy assignment operators. While this works, the explicitly defined default constructor ensures the class is no longer considered trivial and, therefore, a POD type. The modern alternative to this is using a deleted function, as shown in the preceding section.

When the compiler encounters =default in the definition of a function, it will provide the default implementation. The rules for special member functions mentioned earlier still apply. Functions can be declared =default outside the body of a class if and only if they are inlined:

class foo
{
public:
  foo() = default;
  inline foo& operator=(foo const &);
};
inline foo& foo::operator=(foo const &) = default;

The defaulted implementations have several benefits, including the following:

Can be more efficient than the explicit ones.
Non-defaulted implementations, even if they are empty, are considered non-trivial, and that affects the semantics of the type, which becomes non-trivial (and, therefore, non-POD).
Helps the user not write explicit default implementations. For instance, if a user-defined move constructor is present, then the copy constructor and the copy assignment operator are not provided by default by the compiler. However, you can still default explicitly and ask the compiler to provide them so that you don't have to do it manually.

When the compiler encounters the =delete in the definition of a function, it will prevent the calling of the function. However, the function is still considered during overload resolution, and only if the deleted function is the best match does the compiler generate an error. For example, by giving the previously defined overloads for the run() function, only calls with long integers are possible. Calls with arguments of any other type, including int, for which an automatic type promotion to long exists, will determine a deleted overload to be considered the best match and therefore the compiler will generate an error:

run(42);  // error, matches a deleted overload
run(42L); // OK, long integer arguments are allowed

Note that previously declared functions cannot be deleted as the =delete definition must be the first declaration in a translation unit:

void forward_declared_function();
// ...
void forward_declared_function() = delete; // error

The rule of thumb, also known as The Rule of Five, for class special member functions is that if you explicitly define any copy constructor, move constructor, copy assignment operator, move assignment operator, or destructor, then you must either explicitly define or default all of them.

The user-defined destructor, copy-constructor, and copy assignment operator are necessary because objects are constructed from copies in various situations (like passing parameters to functions). If they are not user-defined, they are provided by the compiler, but their default implementation may be wrong. If the class manages resources, then the default implementation does a shallow copy, meaning that it copies the value of the handle of the resource (such as a pointer to an object) and not the resource itself. In such cases, a user-defined implementation must do a deep copy that copies the resource, not the handle to it. The presence of the move constructor and move assignment operator are desirable in this case because they represent a performance improvement. Lacking these two is not an error but a missed optimization opportunity.

Using lambdas with standard algorithms

One of the most important modern features of C++ is lambda expressions, also referred to as lambda functions or simply lambdas. Lambda expressions enable us to define anonymous function objects that can capture variables in the scope and be invoked or passed as arguments to functions. Lambdas are useful for many purposes, and in this recipe, we will learn how to use them with standard algorithms.

Getting ready

In this recipe, we'll discuss standard algorithms that take an argument that's a function or predicate that's applied to the elements it iterates through. You need to know what unary and binary functions are and what predicates and comparison functions are. You also need to be familiar with function objects because lambda expressions are syntactic sugar for function objects.

How to do it...

You should prefer to use lambda expressions to pass callbacks to standard algorithms instead of functions or function objects:

Define anonymous lambda expressions in the place of the call if you only need to use the lambda in a single place:

auto numbers =
  std::vector<int>{ 0, 2, -3, 5, -1, 6, 8, -4, 9 };
auto positives = std::count_if(
  std::begin(numbers), std::end(numbers),
  [](int const n) {return n > 0; });

Define a named lambda, that is, one assigned to a variable (usually with the auto specifier for the type), if you need to call the lambda in multiple places:
```
auto ispositive = [](int const n) {return n > 0; };
auto positives = std::count_if(
  std::begin(numbers), std::end(numbers), ispositive);
```
Use generic lambda expressions if you need lambdas that only differ in terms of their argument types (available since C++14):
```
auto positives = std::count_if(
  std::begin(numbers), std::end(numbers),
  [](auto const n) {return n > 0; });
```

How it works...

The non-generic lambda expression shown in the second bullet takes a constant integer and returns true if it is greater than 0, or false otherwise. The compiler defines an unnamed function object with the call operator, which has the signature of the lambda expression:

struct __lambda_name__
{
  bool operator()(int const n) const { return n > 0; }
};

The way the unnamed function object is defined by the compiler depends on the way we define the lambda expression that can capture variables, use the mutable specifier or exception specifications, or have a trailing return type. The __lambda_name__ function object shown earlier is actually a simplification of what the compiler generates because it also defines a default copy and move constructor, a default destructor, and a deleted assignment operator.

It must be well understood that the lambda expression is actually a class. In order to call it, the compiler needs to instantiate an object of the class. The object instantiated from a lambda expression is called a lambda closure.

In the following example, we want to count the number of elements in a range that are greater than or equal to 5 and less than or equal to 10. The lambda expression, in this case, will look like this:

auto numbers = std::vector<int>{ 0, 2, -3, 5, -1, 6, 8, -4, 9 };
auto minimum { 5 };
auto maximum { 10 };
auto inrange = std::count_if(
    std::begin(numbers), std::end(numbers),
    [minimum, maximum](int const n) {
      return minimum <= n && n <= maximum;});

This lambda captures two variables, minimum and maximum, by copy (that is, value). The resulting unnamed function object created by the compiler looks very much like the one we defined earlier. With the default and deleted special members mentioned earlier, the class looks like this:

class __lambda_name_2__
{
  int minimum_;
  int maximum_;
public:
  explicit __lambda_name_2__(int const minimum, int const maximum) :
  minimum_( minimum), maximum_( maximum)
  {}
  __lambda_name_2__(const __lambda_name_2__&) = default;
  __lambda_name_2__(__lambda_name_2__&&) = default;
  __lambda_name_2__& operator=(const __lambda_name_2__&)
    = delete;
  ~__lambda_name_2__() = default;
  bool operator() (int const n) const
  {
    return minimum_ <= n && n <= maximum_;
  }
};

The lambda expression can capture variables by copy (or value) or by reference, and different combinations of the two are possible. However, it is not possible to capture a variable multiple times and it is only possible to have & or = at the beginning of the capture list.

A lambda can only capture variables from an enclosing function scope. It cannot capture variables with static storage duration (that is, variables declared in a namespace scope or with the static or external specifier).

The following table shows various combinations for lambda captures semantics:

Lambda	Description
`[](){}`	Does not capture anything.
`[&](){}`	Captures everything by reference.
`[=](){}`	Captures everything by copy. Implicit capturing of the pointer `this` is deprecated in C++20.
`[&x](){}`	Capture only `x` by reference.
`[x](){}`	Capture only `x` by copy.
`[&x...](){}`	Capture pack extension `x` by reference.
`[x...](){}`	Capture pack extension `x` by copy.
`[&, x](){}`	Captures everything by reference except for `x` that is captured by copy.
`[=, &x](){}`	Captures everything by copy except for `x` that is captured by reference.
`[&, this](){}`	Captures everything by reference except for pointer `this` that is captured by copy (`this` is always captured by copy).
`[x, x](){}`	Error, `x` is captured twice.
`[&, &x](){}`	Error, everything is captured by reference, and we cannot specify again to capture `x` by reference.
`[=, =x](){}`	Error, everything is captured by copy, and we cannot specify again to capture `x` by copy.
`[&this](){}`	Error, the pointer `this` is always captured by copy.
`[&, =](){}`	Error, cannot capture everything both by copy and by reference.
`[x=expr](){}`	`x` is a data member of the lambda's closure initialized from the expression `expr`.
`[&x=expr](){}`	`x` is a reference data member of the lambda's closure initialized from the expression `expr`.

The general form of a lambda expression, as of C++17, looks like this:

[capture-list](params) mutable constexpr exception attr -> ret
{ body }

All parts shown in this syntax are actually optional except for the capture list, which can, however, be empty, and the body, which can also be empty. The parameter list can actually be omitted if no parameters are needed. The return type does not need to be specified as the compiler can infer it from the type of the returned expression. The mutable specifier (which tells the compiler the lambda can actually modify variables captured by copy), the constexpr specifier (which tells the compiler to generate a constexpr call operator), and the exception specifiers and attributes are all optional.

The simplest possible lambda expression is []{}, though it is often written as [](){}.

The latter two examples in the preceding table are forms of generalized lambda captures. These were introduced in C++14 to allow us to capture variables with move-only semantics, but they can also be used to define new arbitrary objects in the lambda. The following example shows how variables can be captured by move with generalized lambda captures:

auto ptr = std::make_unique<int>(42);
auto l = [lptr = std::move(ptr)](){return ++*lptr;};

Lambdas that are written in class methods and need to capture class data members can do so in several ways:

Capturing individual data members with the form [x=expr]:

struct foo
{
  int         id;
  std::string name;
  auto run()
  {
    return [i=id, n=name] { std::cout << i << ' ' << n << '
'; };
  }
};

Capturing the entire object with the form [=] (please notice that the implicit capture of pointer this via [=] is deprecated in C++20):

struct foo
{
  int         id;
  std::string name;
  auto run()
  {
    return [=] { std::cout << id << ' ' << name << '
'; };
  }
};

Capturing the entire object by capturing the this pointer. This is necessary if you need to invoke other methods of the class. This can be captured either as [this] when the pointer is captured by value, or [*this] when the object itself is captured by value. This can make a big difference if the object may go out of scope after the capture occurs but before the lambda is invoked:
```
struct foo
{
  int         id;
  std::string name;
  auto run()
  {
    return[this]{ std::cout << id << ' ' << name << '
'; };
  }
};
auto l = foo{ 42, "john" }.run();
l(); // does not print 42 john
```

In this latter case seen here, the correct capture should be [*this] so that object is copied by value. In this case, invoking the lambda will print 42 john, even though the temporary has gone out of scope.

The C++20 standard introduces several changes to capturing the pointer this:

It deprecates the implicit capturing of this when you use [=]. This will produce a deprecation warning to be issued by the compiler.
It introduces explicit capturing of the this pointer by value when you want to capture everything with [=, this]. You can still only capture the pointer this with a [this] capture.

There are cases where lambda expressions only differ in terms of their arguments. In this case, the lambdas can be written in a generic way, just like templates, but using the auto specifier for the type parameters (no template syntax is involved). This is addressed in the next recipe, as noted in the upcoming See also section.

Using generic and template lambdas

In the preceding recipe, we saw how to write lambda expressions and use them with standard algorithms. In C++, lambdas are basically syntactic sugar for unnamed function objects, which are classes that implement the call operator. However, just like any other function, this can be implemented generically with templates. C++14 takes advantage of this and introduces generic lambdas that do not need to specify actual types for their parameters and use the auto specifier instead. Though not referred to with this name, generic lambdas are basically lambda templates. They are useful in cases where we want to use the same lambda but with different types of parameter. Moreover, the C++20 standard takes this a step further and supports explicitly defining template lambdas. This helps with some scenarios where generic lambdas are cumbersome.

Getting started

It is recommended that you read the preceding recipe, Using lambdas with standard algorithms, before you continue with this one to familiarize yourself with the fundamentals of lambdas in C++.

How to do it...

In C++14, we can write generic lambdas:

By using the auto specifier instead of actual types for lambda expression parameters
When we need to use multiple lambdas that only differ by their parameter types

The following example shows a generic lambda used with the std::accumulate() algorithm, first with a vector of integers and then with a vector of strings:

auto numbers =
  std::vector<int>{0, 2, -3, 5, -1, 6, 8, -4, 9};
using namespace std::string_literals;
auto texts =
  std::vector<std::string>{"hello"s, " "s, "world"s, "!"s};
auto lsum = [](auto const s, auto const n) {return s + n;};
auto sum = std::accumulate(
  std::begin(numbers), std::end(numbers), 0, lsum);
  // sum = 22
auto text = std::accumulate(
  std::begin(texts), std::end(texts), ""s, lsum);
  // sum = "hello world!"s

In C++20, we can write template lambdas:

By using a template parameter list in angle brackets (such as <template T>) after the capture clause
When you want to:
- Restrict the use of a generic lambda with only some types, such as a container, or types that satisfy a concept.
- Make sure that two or more arguments of a generic lambda actually do have the same type.
- Retrieve the type of a generic parameter so that, for example, we can create instances of it, invoke static methods, or use its iterator types.
- Perform perfect forwarding in a generic lambda.

The following example shows a template lambda that can be invoked only using an std::vector:

std::vector<int> vi { 1, 1, 2, 3, 5, 8 };
auto tl = []<typename T>(std::vector<T> const& vec)
{
   std::cout << std::size(vec) << '
';
};
tl(vi); // OK, prints 6
tl(42); // error

How it works...

In the first example from the previous section, we defined a named lambda expression; that is, a lambda expression that has its closure assigned to a variable. This variable is then passed as an argument to the std::accumulate() function.

This general algorithm takes the begin and the end iterators, which define a range, an initial value to accumulate over, and a function that is supposed to accumulate each value in the range to the total. This function takes a first parameter representing the currently accumulated value and a second parameter representing the current value to accumulate to the total, and it returns the new accumulated value. Note that I did not use the term add because this can be used for other things than just adding. It can also be used for calculating a product, concatenating, or other operations that aggregate values together.

The two calls to std::accumulate() in this example are almost the same; only the types of the arguments are different:

In the first call, we pass iterators to a range of integers (from a vector<int>), 0 for the initial sum, and a lambda that adds two integers and returns their sum. This produces a sum of all integers in the range; for this example, it is 22.
In the second call, we pass iterators to a range of strings (from a vector<string>), an empty string for the initial value, and a lambda that concatenates two strings by adding them together and returning the result. This produces a string that contains all the strings in the range put together one after another; for this example, the result is hello world!.

Though generic lambdas can be defined anonymously in the place where they are called, it does not really make sense because the very purpose of a generic lambda (which is basically, as we mentioned earlier, a lambda expression template) is to be reused, as shown in the example from the How to do it... section.

When defining this lambda expression, when used with multiple calls to std::accumulate(), instead of specifying concrete types for the lambda parameters (such as int or std::string), we used the auto specifier and let the compiler deduce the type. When encountering a lambda expression that has the auto specifier for a parameter type, the compiler generates an unnamed function object that has a call operator template. For the generic lambda expression in this example, the function object would look like this:

struct __lambda_name__
{
  template<typename T1, typename T2>
  auto operator()(T1 const s, T2 const n) const { return s + n; }
  __lambda_name__(const __lambda_name__&) = default;
  __lambda_name__(__lambda_name__&&) = default;
  __lambda_name__& operator=(const __lambda_name__&) = delete;
  ~__lambda_name__() = default;
};

The call operator is a template with a type parameter for each parameter in the lambda that was specified with auto. The return type of the call operator is also auto, which means the compiler will deduce it from the type of the returned value. This operator template will be instantiated with the actual types the compiler will identify in the context where the generic lambda is used.

The C++20 template lambdas are an improvement of the C++14 generic lambdas, making some scenarios easier. A typical one was shown in the second example of the previous section, where the use of lambda was restricted with arguments of the type std::vector. Another example is when you want to make sure that two parameters of the lambda have the same type. Prior to C++20, this was difficult to do, but with template lambdas, it is very easy, as shown in the following example:

auto tl = []<typename T>(T x, T y)
{
  std::cout << x << ' ' << y << '
';
};
tl(10, 20);   // OK
tl(10, "20"); // error

Another scenario for template lambdas is when you need to know the type of a parameter so that you can create instances of that type or invoke static members of it. With generic lambdas, the solution is as follows:

struct foo
{
   static void f() { std::cout << "foo
"; }
};
auto tl = [](auto x)
{
  using T = std::decay_t<decltype(x)>;
  T other;
  T::f();
};
tl(foo{});

This solution requires the use of std::decay_t and decltype. However, in C++20, the same lambda can be written as follows:

auto tl = []<typename T>(T x)
{
  T other;
  T::f();
};

A similar situation occurs when we need to do perfect forwarding in a generic lambda, which requires the use of decltype to determine the types of the arguments:

template <typename ...T>
void foo(T&& ... args)
{ /* ... */ }
auto tl = [](auto&& ...args)
{
  return foo(std::forward<decltype(args)>(args)...);
};
tl(1, 42.99, "lambda");

With template lambda, we can rewrite it in a simpler way as follows:

auto tl = []<typename ...T>(T && ...args)
{
  return foo(std::forward<T>(args)...);
};

As seen in these examples, template lambdas are an improvement of generic lambdas, making it easier to handle the scenarios mentioned in this recipe.

Writing a recursive lambda

Lambdas are basically unnamed function objects, which means that it should be possible to call them recursively. Indeed, they can be called recursively; however, the mechanism for doing so is not obvious as it requires assigning the lambda to a function wrapper and capturing the wrapper by reference. Though it can be argued that a recursive lambda does not really make sense and that a function is probably a better design choice, in this recipe, we will look at how to write a recursive lambda.

Getting ready

To demonstrate how to write a recursive lambda, we will consider the well-known example of the Fibonacci function. This is usually implemented recursively in C++, as follows:

constexpr int fib(int const n)
{
  return n <= 2 ? 1 : fib(n - 1) + fib(n - 2);
}

Having this implementation as a starting point, let's see how we can rewrite it using a recursive lambda.

How to do it...

In order to write a recursive lambda function, you must do the following:

Define the lambda in a function scope
Assign the lambda to an std::function wrapper
Capture the std::function object by reference in the lambda in order to call it recursively

The following are examples of recursive lambdas:

A recursive Fibonacci lambda expression in the scope of a function that is invoked from the scope where it is defined:

void sample()
{
  std::function<int(int const)> lfib =
    [&lfib](int const n)
    {
      return n <= 2 ? 1 : lfib(n - 1) + lfib(n - 2);
    };
  auto f10 = lfib(10);
}

A recursive Fibonacci lambda expression returned by a function, which can be invoked from any scope:

std::function<int(int const)> fib_create()
{
  std::function<int(int const)> f = [](int const n)
  {
    std::function<int(int const)> lfib = [&lfib](int n)
    {
      return n <= 2 ? 1 : lfib(n - 1) + lfib(n - 2);
    };
    return lfib(n);
  };
  return f;
}
void sample()
{
  auto lfib = fib_create();
  auto f10 = lfib(10);
}

How it works...

The first thing you need to consider when writing a recursive lambda is that a lambda expression is a function object and that, in order to call it recursively from the lambda's body, the lambda must capture its closure (that is, the instantiation of the lambda). In other words, the lambda must capture itself, and this has several implications:

First of all, the lambda must have a name; an unnamed lambda cannot be captured so that it can be called again.
Secondly, the lambda can only be defined in a function scope. The reason for this is that a lambda can only capture variables from a function scope; it cannot capture any variable that has a static storage duration. Objects defined in a namespace scope or with the static or external specifiers have static storage duration. If the lambda was defined in a namespace scope, its closure would have static storage duration and therefore the lambda would not capture it.
The third implication is that the type of the lambda closure cannot remain unspecified; that is, it cannot be declared with the auto specifier. It is not possible for a variable declared with the auto type specifier to appear in its own initializer. This is because the type of the variable is not known when the initializer is being processed. Therefore, you must specify the type of the lambda closure. The way we can do this is by using the general-purpose function wrapper std::function.
Last, but not least, the lambda closure must be captured by reference. If we capture by copy (or value), then a copy of the function wrapper is made, but the wrapper is uninitialized when the capturing is done. We end up with an object that we are not able to call. Even though the compiler will not complain about capturing by value, when the closure is invoked, an std::bad_function_call is thrown.

In the first example from the How to do it... section, the recursive lambda is defined inside another function called sample(). The signature and the body of the lambda expression are the same as those of the regular recursive function fib (), which was defined in the introductory section. The lambda closure is assigned to a function wrapper called lfib that is then captured by reference by the lambda and called recursively from its body. Since the closure is captured by reference, it will be initialized at the time it has to be called from the lambda's body.

In the second example, we defined a function that returns the closure of a lambda expression that, in turn, defines and invokes a recursive lambda with the argument it was, in turn, invoked with. This is a pattern that must be implemented when a recursive lambda needs to be returned from a function. This is necessary because the lambda closure must still be available at the time the recursive lambda is called. If it is destroyed before that, we are left with a dangling reference, and calling it will cause the program to terminate abnormally. This erroneous situation is exemplified in the following example:

// this implementation of fib_create is faulty
std::function<int(int const)> fib_create()
{
  std::function<int(int const)> lfib = [&lfib](int const n)
  {
    return n <= 2 ? 1 : lfib(n - 1) + lfib(n - 2);
  };
  return lfib;
}
void sample()
{
  auto lfib = fib_create();
  auto f10 = lfib(10);       // crash
}

The solution for this is to create two nested lambda expressions, as shown in the How to do it... section. The fib_create() method returns a function wrapper that, when invoked, creates the recursive lambda that captures itself. This is slightly and subtly, yet fundamentally, different from the implementation shown in the preceding sample. The outer f lambda does not capture anything, especially by reference; therefore, we don't have this issue with dangling references. However, when invoked, it creates a closure of the nested lambda, which is the actual lambda we are interested in calling, and returns the result of applying that recursive lfib lambda to its parameter.

Writing a function template with a variable number of arguments

It is sometimes useful to write functions with a variable number of arguments or classes with a variable number of members. Typical examples include functions such as printf, which takes a format and a variable number of arguments, or classes such as tuple. Before C++11, the former was possible only with the use of variadic macros (which enable writing only type-unsafe functions) and the latter was not possible at all. C++11 introduced variadic templates, which are templates with a variable number of arguments that make it possible to write both type-safe function templates with a variable number of arguments, and also class templates with a variable number of members. In this recipe, we will look at writing function templates.

Getting ready

Functions with a variable number of arguments are called variadic functions. Function templates with a variable number of arguments are called variadic function templates. Knowledge of C++ variadic macros (va_start, va_end, va_arg and va_copy, va_list) is not necessary for learning how to write variadic function templates, but it represents a good starting point.

We have already used variadic templates in our previous recipes, but this one will provide detailed explanations.

How to do it...

In order to write variadic function templates, you must perform the following steps:

Define an overload with a fixed number of arguments to end compile-time recursion if the semantics of the variadic function template require it (refer to [1] in the following code).
Define a template parameter pack that is a template parameter that can hold any number of arguments, including zero; these arguments can be either types, non-types, or templates (refer to [2]).
Define a function parameter pack to hold any number of function arguments, including zero; the size of the template parameter pack and the corresponding function parameter pack is the same. This size can be determined with the sizeof... operator (refer to [3] and refer to the end of the How it works... section for information on this operator).
Expand the parameter pack in order to replace it with the actual arguments being supplied (refer to [4]).

The following example, which illustrates all the preceding points, is a variadic function template that adds a variable number of arguments using operator+:

template <typename T>                 // [1] overload with fixed
T add(T value)                        //     number of arguments
{
  return value;
}
template <typename T, typename... Ts> // [2] typename... Ts
T add(T head, Ts... rest)             // [3] Ts... rest
{
  return head + add(rest...);         // [4] rest...
}

How it works...

At first glance, the preceding implementation looks like recursion, because the function add() calls itself, and in a way it is, but it is a compile-time recursion that does not incur any sort of runtime recursion and overhead. The compiler actually generates several functions with a different number of arguments, based on the variadic function template's usage, so only function overloading is involved and not any sort of recursion. However, implementation is done as if parameters would be processed in a recursive manner with an end condition.

In the preceding code, we can identify the following key parts:

Typename... Ts is a template parameter pack that indicates a variable number of template type arguments.
Ts... rest is a function parameter pack that indicates a variable number of function arguments.
rest... is an expansion of the function parameter pack.

The position of the ellipsis is not syntactically relevant. typename... Ts, typename ... Ts, and typename ...Ts are all equivalent.

In the add(T head, Ts... rest) parameter, head is the first element of the list of arguments, while ...rest is a pack with the rest of the parameters in the list (this can be zero or more). In the body of the function, rest... is an expansion of the function parameter pack. This means the compiler replaces the parameter pack with its elements in their order. In the add() function, we basically add the first argument to the sum of the remaining arguments, which gives the impression of recursive processing. This recursion ends when there is a single argument left, in which case the first add() overload (with a single argument) is called and returns the value of its argument.

This implementation of the function template add() enables us to write code, as shown here:

auto s1 = add(1, 2, 3, 4, 5);
// s1 = 15
auto s2 = add("hello"s, " "s, "world"s, "!"s);
// s2 = "hello world!"

When the compiler encounters add(1, 2, 3, 4, 5), it generates the following functions (arg1, arg2, and so on are not the actual names the compiler generates), which show that this is actually only calls to overloaded functions and not recursion:

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

With GCC and Clang, you can use the __PRETTY_FUNCTION__ macro to print the name and the signature of the function.

By adding an std::cout << __PRETTY_FUNCTION__ << std::endl at the beginning of the two functions we wrote, we get the following when running the code:

T add(T, Ts ...) [with T = int; Ts = {int, int, int, int}]
T add(T, Ts ...) [with T = int; Ts = {int, int, int}]
T add(T, Ts ...) [with T = int; Ts = {int, int}]
T add(T, Ts ...) [with T = int; Ts = {int}]
T add(T) [with T = int]

Since this is a function template, it can be used with any type that supports operator+. The other example, add("hello"s, " "s, "world"s, "!"s), produces the hello world! string. However, the std::basic_string type has different overloads for operator+, including one that can concatenate a string into a character, so we should be able to also write the following:

auto s3 = add("hello"s, ' ', "world"s, '!');
// s3 = "hello world!"

However, that will generate compiler errors, as follows (note that I actually replaced std::basic_string<char, std::char_traits<char>, std::allocator<char> > with the string hello world! for simplicity):

In instantiation of 'T add(T, Ts ...) [with T = char; Ts = {string, char}]':
16:29:   required from 'T add(T, Ts ...) [with T = string; Ts = {char, string, char}]'
22:46:   required from here
16:29: error: cannot convert 'string' to 'char' in return
 In function 'T add(T, Ts ...) [with T = char; Ts = {string, char}]':
17:1: warning: control reaches end of non-void function [-Wreturn-type]

What happens is that the compiler generates the code shown here, where the return type is the same as the type of the first argument. However, the first argument is either an std::string or a char (again, std::basic_string<char, std::char_traits<char>, std::allocator<char> > was replaced with string for simplicity). In cases where char is the type of the first argument, the type of the return value head+add (...), which is an std::string, does not match the function return type and does not have an implicit conversion to it:

string add(string head, char arg1, string arg2, char arg3)
{return head + add(arg1, arg2, arg3);}
char add(char head, string arg1, char arg2)
{return head + add(arg1, arg2);}
string add(string head, char arg1)
{return head + add(arg1);}
char add(char value)
{return value;}

We can fix this by modifying the variadic function template so that it has auto for the return type instead of T. In this case, the return type is always inferred from the return expression, and in our example, it will be std::string in all cases:

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

It should be further added that a parameter pack can appear in a brace-initialization and that its size can be determined using the sizeof... operator. Also, variadic function templates do not necessarily imply compile-time recursion, as we have shown in this recipe. All these are shown in the following example:

template<typename... T>
auto make_even_tuple(T... a)
{
  static_assert(sizeof...(a) % 2 == 0,
                "expected an even number of arguments");
  std::tuple<T...> t { a... };
  return t;
}
auto t1 = make_even_tuple(1, 2, 3, 4); // OK
// error: expected an even number of arguments
auto t2 = make_even_tuple(1, 2, 3);

In the preceding snippet, we have defined a function that creates a tuple with an even number of members. We first use sizeof...(a) to make sure that we have an even number of arguments and assert by generating a compiler error otherwise. The sizeof... operator can be used with both template parameter packs and function parameter packs. sizeof...(a) and sizeof...(T) would produce the same value. Then, we create and return a tuple. The template parameter pack T is expanded (with T...) into the type arguments of the std::tuple class template, and the function parameter pack a is expanded (with a...) into the values for the tuple members using brace initialization.

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);
}

The parentheses shown here are part of the fold expression and cannot be omitted.

How it works...

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

Expression	Expansion
`(... op pack)`	`((pack$1 op pack$2) op ...) op pack$n`
`(init op ... op pack)`	`(((init op pack$1) op pack$2) op ...) op pack$n`
`(pack op ...)`	`pack$1 op (... op (pack$n-1 op pack$n))`
`(pack op ... op init)`	`pack$1 op (... op (pack$n-1 op (pack$n op init)))`

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:

`+`	`0`
`*`	`1`
`&`	`-1`
`\|`	`0`
`&&`	`true`
`\|\|`	`false`
`,`	`void()`

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.

Implementing the higher-order functions map and fold

Throughout the preceding recipes in this book, we have used the general-purpose algorithms std::transform() and std::accumulate() in several examples, such as for implementing string utilities to create uppercase or lowercase copies of a string or for summing the values of a range. These are basically implementations of higher-order functions, map and fold. A higher-order function is a function that takes one or more other functions as arguments and applies them to a range (a list, vector, map, tree, and so on), thus producing either a new range or a value. In this recipe, we will learn how to implement the map and fold functions so that they work with C++ standard containers.

Getting ready

Map is a higher-order function that applies a function to the elements of a range and returns a new range in the same order.

Fold is a higher-order function that applies a combining function to the elements of the range to produce a single result. Since the order of the processing can be important, there are usually two versions of this function. One is foldleft, which processes elements from left to right, while the other is foldright, which combines the elements from right to left.

Most descriptions of the function map indicate that it is applied to a list, but this is a general term that can indicate different sequential types, such as list, vector, and array, and also dictionaries (that is, maps), queues, and so on. For this reason, I prefer to use the term range when describing these higher-order functions.

As an example, the mapping operation could transform a range of strings into a range of integers representing the length of each string. The fold operation could then add these lengths to determine the combined length of all the strings.

How to do it...

To implement the map function, you should:

Use std::transform on containers that support iterating and assignment to the elements, such as std::vector or std::list:

template <typename F, typename R>
R mapf(F&& func, R range)
{
  std::transform(
    std::begin(range), std::end(range), std::begin(range),
    std::forward<F>(func));
  return range;
}

Use other means such as explicit iteration and insertion for containers that do not support assignment to the elements, such as std::map:

template<typename F, typename T, typename U>
std::map<T, U> mapf(F&& func, std::map<T, U> const & m)
{
  std::map<T, U> r;
  for (auto const kvp : m)
    r.insert(func(kvp));
  return r;
}
template<typename F, typename T>
std::queue<T> mapf(F&& func, std::queue<T> q)
{
  std::queue<T> r;
  while (!q.empty())
  {
    r.push(func(q.front()));
    q.pop();
  }
  return r;
}

To implement the fold function, you should:

Use std::accumulate() on containers that support iterating:

template <typename F, typename R, typename T>
constexpr T foldl(F&& func, R&& range, T init)
{
  return std::accumulate(
    std::begin(range), std::end(range),
    std::move(init),
    std::forward<F>(func));
}
template <typename F, typename R, typename T>
constexpr T foldr(F&& func, R&& range, T init)
{
  return std::accumulate(
    std::rbegin(range), std::rend(range),
    std::move(init),
    std::forward<F>(func));
}

Use other means to explicitly process containers that do not support iterating, such as std::queue:

template <typename F, typename T>
constexpr T foldl(F&& func, std::queue<T> q, T init)
{
  while (!q.empty())
  {
    init = func(init, q.front());
    q.pop();
  }
  return init;
}

How it works...

In the preceding examples, we implemented the map in a functional way, without side effects. This means it preserves the original range and returns a new one. The arguments of the function are the function to apply and the range. In order to avoid confusion with the std::map container, we have called this function mapf. There are several overloads for mapf, as shown earlier:

The first overload is for containers that support iterating and assignment to its elements; this includes std::vector, std::list, and std::array, but also C-like arrays. The function takes an rvalue reference to a function and a range for which std::begin() and std::end() are defined. The range is passed by value so that modifying the local copy does not affect the original range. The range is transformed by applying the given function to each element using the standard algorithm std::transform(); the transformed range is then returned.
The second overload is specialized for std::map, which does not support direct assignment to its elements (std::pair<T, U>). Therefore, this overload creates a new map, then iterates through its elements using a range-based for loop, and inserts the result of applying the input function to each element of the original map into the new map.
The third overload is specialized for std::queue, which is a container that does not support iterating. It can be argued that a queue is not a typical structure to map over, but for the sake of demonstrating different possible implementations, we are considering it. In order to iterate over the elements of a queue, the queue must be altered—you need to pop elements from the front until the list is empty. This is what the third overload does—it processes each element of the input queue (passed by value) and pushes the result of applying the given function to the front element of the remaining queue.

Now that we have these overloads implemented, we can apply them to a lot of containers, as shown in the following examples:

Retain absolute values from a vector. In this example, the vector contains both negative and positive values. After applying the mapping, the result is a new vector with only positive values:

auto vnums =
  std::vector<int>{0, 2, -3, 5, -1, 6, 8, -4, 9};
auto r = funclib::mapf([](int const i) {
  return std::abs(i); }, vnums);
// r = {0, 2, 3, 5, 1, 6, 8, 4, 9}

Square the numerical values of a list. In this example, the list contains integral values. After applying the mapping, the result is a list containing the squares of the initial values:
```
auto lnums = std::list<int>{1, 2, 3, 4, 5};
auto l = funclib::mapf([](int const i) {
  return i*i; }, lnums);
// l = {1, 4, 9, 16, 25}
```
Rounded amounts of floating points. For this example, we need to use std::round(); however, this has overloads for all floating-point types, which makes it impossible for the compiler to pick the right one. As a result, we either have to write a lambda that takes an argument of a specific floating-point type and returns the value of std::round() applied to that value, or create a function object template that wraps std::round() and enables its call operator only for floating point types. This technique is used in the following example:
```
template<class T = double>
struct fround
{
  typename std::enable_if_t<
    std::is_floating_point_v<T>, T>
  operator()(const T& value) const
  {
    return std::round(value);
  }
};
auto amounts =
  std::array<double, 5> {10.42, 2.50, 100.0, 23.75, 12.99};
auto a = funclib::mapf(fround<>(), amounts);
// a = {10.0, 3.0, 100.0, 24.0, 13.0}
```
Uppercase the string keys of a map of words (where the key is the word and the value is the number of appearances in the text). Note that creating an uppercase copy of a string is itself a mapping operation. Therefore, in this example, we use mapf to apply toupper() to the elements of the string representing the key in order to produce an uppercase copy:
```
auto words = std::map<std::string, int>{
  {"one", 1}, {"two", 2}, {"three", 3}
};
auto m = funclib::mapf(
  [](std::pair<std::string, int> const kvp) {
    return std::make_pair(
      funclib::mapf(toupper, kvp.first),
      kvp.second);
    },
    words);
// m = {{"ONE", 1}, {"TWO", 2}, {"THREE", 3}}
```

Normalize values from a queue of priorities; initially, the values are from 1 to 100, but we want to normalize them into two values, 1=high and 2=normal. All the initial priorities that have a value up to 30 get high priority; the others get normal priority:

auto priorities = std::queue<int>();
priorities.push(10);
priorities.push(20);
priorities.push(30);
priorities.push(40);
priorities.push(50);
auto p = funclib::mapf(
  [](int const i) { return i > 30 ? 2 : 1; },
  priorities);
// p = {1, 1, 1, 2, 2}

To implement fold, we actually have to consider the two possible types of folding; that is, from left to right and from right to left. Therefore, we have provided two functions called foldl (for left folding) and foldr (for right folding). The implementations shown in the previous section are very similar: they both take a function, a range, and an initial value and call std::algorithm() to fold the values of the range into a single value. However, foldl uses direct iterators, whereas foldr uses reverse iterators to traverse and process the range. The second overload is a specialization for the type std::queue, which does not have iterators.

Based on these implementations for folding, we can implement the following examples:

Adding the values of a vector of integers. In this case, both left and right folding will produce the same result. In the following examples, we pass either a lambda that takes a sum and a number and returns a new sum or the function object std::plus<> from the standard library, which applies operator+ to two operands of the same type (basically similar to the closure of the lambda):

auto vnums =
  std::vector<int>{0, 2, -3, 5, -1, 6, 8, -4, 9};
auto s1 = funclib::foldl(
  [](const int s, const int n) {return s + n; },
  vnums, 0);                // s1 = 22
auto s2 = funclib::foldl(
  std::plus<>(), vnums, 0); // s2 = 22
auto s3 = funclib::foldr(
  [](const int s, const int n) {return s + n; },
  vnums, 0);                // s3 = 22
auto s4 = funclib::foldr(
  std::plus<>(), vnums, 0); // s4 = 22

Concatenating strings from a vector into a single string:

auto texts =
  std::vector<std::string>{"hello"s, " "s, "world"s, "!"s};
auto txt1 = funclib::foldl(
  [](std::string const & s, std::string const & n) {
  return s + n;},
  texts, ""s);    // txt1 = "hello world!"
auto txt2 = funclib::foldr(
  [](std::string const & s, std::string const & n) {
  return s + n; },
  texts, ""s);    // txt2 = "!world hello"

Concatenating an array of characters into a string:

char chars[] = {'c','i','v','i','c'};
auto str1 = funclib::foldl(std::plus<>(), chars, ""s);
// str1 = "civic"
auto str2 = funclib::foldr(std::plus<>(), chars, ""s);
// str2 = "civic"

Counting the number of words in text based on their already computed appearances, available in a map<string, int>:

auto words = std::map<std::string, int>{
  {"one", 1}, {"two", 2}, {"three", 3} };
auto count = funclib::foldl(
  [](int const s, std::pair<std::string, int> const kvp) {
    return s + kvp.second; },
  words, 0); // count = 6

There's more...

These functions can be pipelined; that is, they can call one function with the result of another. The following example maps a range of integers into a range of positive integers by applying the std::abs() function to its elements. The result is then mapped into another range of squares. These are then summed together by applying a left fold on the range:

auto vnums = std::vector<int>{ 0, 2, -3, 5, -1, 6, 8, -4, 9 };
auto s = funclib::foldl(
  std::plus<>(),
  funclib::mapf(
    [](int const i) {return i*i; },
    funclib::mapf(
      [](int const i) {return std::abs(i); },
      vnums)),
  0); // s = 236

As an exercise, we could implement the fold function as a variadic function template, in the manner seen earlier. The function that performs the actual folding is provided as an argument:

template <typename F, typename T1, typename T2>
auto foldl(F&&f, T1 arg1, T2 arg2)
{
  return f(arg1, arg2);
}
template <typename F, typename T, typename... Ts>
auto foldl(F&& f, T head, Ts... rest)
{
  return f(head, foldl(std::forward<F>(f), rest...));
}

When we compare this with the add() function template that we wrote in the Writing a function template with a variable number of arguments recipe, we can notice several differences:

The first argument is a function, which is perfectly forwarded when calling foldl recursively.
The end case is a function that requires two arguments because the function we use for folding is a binary one (taking two arguments).
The return type of the two functions we wrote is declared as auto because it must match the return type of the supplied binary function f, which is not known until we call foldl.

The foldl() function can be used as follows:

auto s1 = foldl(std::plus<>(), 1, 2, 3, 4, 5);
// s1 = 15
auto s2 = foldl(std::plus<>(), "hello"s, ' ', "world"s, '!');
// s2 = "hello world!"
auto s3 = foldl(std::plus<>(), 1); // error, too few arguments

Notice that the last call produces a compiler error because the variadic function template foldl() requires at least two arguments to be passed, in order to invoke the supplied binary function.

Composing functions into a higher-order function

In the previous recipe, we implemented two higher-order functions, map and fold, and saw various examples of using them. At the end of the recipe, we saw how they can be pipelined to produce a final value after several transformations of the original data. Pipelining is a form of composition, which means creating one new function from two or more given functions. In the mentioned example, we didn't actually compose functions; we only called a function with the result produced by another, but in this recipe, we will learn how to actually compose functions together into a new function. For simplicity, we will only consider unary functions (functions that take only one argument).

Getting ready

Before you go forward, it is recommended that you read the previous recipe, Implementing higher-order functions map and fold. It is not mandatory for understanding this recipe, but we will refer to the map and fold functions we implemented there.

How to do it...

To compose unary functions into a higher-order function, you should:

For composing two functions, provide a function that takes two functions, f and g, as arguments and returns a new function (a lambda) that returns f(g(x)), where x is the argument of the composed function:

template <typename F, typename G>
auto compose(F&& f, G&& g)
{
  return [=](auto x) { return f(g(x)); };
}
auto v = compose(
  [](int const n) {return std::to_string(n); },
  [](int const n) {return n * n; })(-3); // v = "9"

For composing a variable number of functions, provide a variadic template overload of the function described previously:

template <typename F, typename... R>
auto compose(F&& f, R&&... r)
{
  return [=](auto x) { return f(compose(r...)(x)); };
}
auto n = compose(
  [](int const n) {return std::to_string(n); },
  [](int const n) {return n * n; },
  [](int const n) {return n + n; },
  [](int const n) {return std::abs(n); })(-3); // n = "36"

How it works...

Composing two unary functions into a new one is relatively trivial. Create a template function, which we called compose() in the earlier examples, with two arguments—f and g—that represent functions, and return a function that takes one argument, x, and returns f(g(x)). It is important that the type of the value returned by the g function is the same as the type of the argument of the f function. The returned value of the compose function is a closure; that is, it's an instantiation of a lambda.

In practice, it is useful to be able to combine more than just two functions. This can be achieved by writing a variadic template version of the compose() function. Variadic templates are explained in more detail in the Writing a function template with a variable number of arguments recipe.

Variadic templates imply compile-time recursion by expanding the parameter pack. This implementation is very similar to the first version of compose(), except for the following:

It takes a variable number of functions as arguments.
The returned closure calls compose() recursively with the expanded parameter pack; recursion ends when only two functions are left, in which case the previously implemented overload is called.

Even if the code looks like recursion is happening, this is not true recursion. It could be called compile-time recursion, but with every expansion, we get a call to another method with the same name but a different number of arguments, which does not represent recursion.

Now that we have these variadic template overloads implemented, we can rewrite the last example from the previous recipe, Implementing higher-order functions map and fold. Refer to the following snippet:

auto s = compose(
  [](std::vector<int> const & v) {
    return foldl(std::plus<>(), v, 0); },
  [](std::vector<int> const & v) {
    return mapf([](int const i) {return i + i; }, v); },
  [](std::vector<int> const & v) {
    return mapf([](int const i) {return std::abs(i); }, v); })(vnums);

Having an initial vector of integers, we map it to a new vector with only positive values by applying std::abs() to each element. The result is then mapped to a new vector by doubling the value of each element. Finally, the values in the resulting vector are folded together by adding them to the initial value, 0.

There's more...

Composition is usually represented by a dot (.) or asterisk (*), such as f . g or f * g. We can actually do something similar in C++ by overloading operator* (it would make little sense to try to overload the operator dot). Similar to the compose() function, operator* should work with any number of arguments; therefore, we will have two overloads, just like in the case of compose():

The first overload takes two arguments and calls compose() to return a new function.
The second overload is a variadic template function that, again, calls operator* by expanding the parameter pack.

Based on these considerations, we can implement operator* as follows:

template <typename F, typename G>
auto operator*(F&& f, G&& g)
{
  return compose(std::forward<F>(f), std::forward<G>(g));
}
template <typename F, typename... R>
auto operator*(F&& f, R&&... r)
{
  return operator*(std::forward<F>(f), r...);
}

We can now simplify the actual composition of functions by applying operator* instead of the more verbose call to compose():

auto n =
  ([](int const n) {return std::to_string(n); } *
   [](int const n) {return n * n; } *
   [](int const n) {return n + n; } *
   [](int const n) {return std::abs(n); })(-3); // n = "36"
auto c =
  [](std::vector<int> const & v) {
    return foldl(std::plus<>(), v, 0); } *
  [](std::vector<int> const & v) {
    return mapf([](int const i) {return i + i; }, v); } *
  [](std::vector<int> const & v) {
    return mapf([](int const i) {return std::abs(i); }, v); };
auto vnums = std::vector<int>{ 0, 2, -3, 5, -1, 6, 8, -4, 9 };
auto s = c(vnums); // s = 76

Although it may not be intuitive at first glance, the functions are applied in reverse order rather than the one shown in the text. For instance, in the first example, the absolute value of the argument is retained. Then, the result is doubled, and the result of that operation is then multiplied with itself. Finally, the result is converted to a string. For the supplied argument, -3, the final result is the string "36".

Uniformly invoking anything callable

Developers, and especially those who implement libraries, sometimes need to invoke a callable object in a uniform manner. This can be a function, a pointer to a function, a pointer to a member function, or a function object. Examples of such cases include std::bind, std::function, std::mem_fn, and std::thread::thread. C++17 defines a standard function called std::invoke() that can invoke any callable object with the provided arguments. This is not intended to replace direct calls to functions or function objects, but it is useful in template metaprogramming for implementing various library functions.

Getting ready

For this recipe, you should be familiar with how to define and use function pointers.

To exemplify how std::invoke() can be used in different contexts, we will use the following function and class:

int add(int const a, int const b)
{
  return a + b;
}
struct foo
{
  int x = 0;
  void increment_by(int const n) { x += n; }
};

In the next section, we'll explore the possible use cases for the std::invoke() function.

How to do it...

The std::invoke() function is a variadic function template that takes the callable object as the first argument and a variable list of arguments that are passed to the call. std::invoke() can be used to call the following:

Free functions:

auto a1 = std::invoke(add, 1, 2);   // a1 = 3

Free functions through pointer to function:

auto a2 = std::invoke(&add, 1, 2);  // a2 = 3
int(*fadd)(int const, int const) = &add;
auto a3 = std::invoke(fadd, 1, 2);  // a3 = 3

Member functions through pointer to member function:
```
foo f;
std::invoke(&foo::increment_by, f, 10);
```

Data members:

foo f;
auto x1 = std::invoke(&foo::x, f);  // x1 = 0

Function objects:

foo f;
auto x3 = std::invoke(std::plus<>(),
  std::invoke(&foo::x, f), 3); // x3 = 3

Lambda expressions:

auto l = [](auto a, auto b) {return a + b; };
auto a = std::invoke(l, 1, 2); // a = 3

In practice, std:invoke() should be used in template metaprogramming for invoking a function with an arbitrary number of arguments. To exemplify such a case, we'll present a possible implementation for our std::apply() function, and also a part of the standard library, as of C++17, that calls a function by unpacking the members of a tuple into the arguments of the function:

namespace details
{
  template <class F, class T, std::size_t... I>
  auto apply(F&& f, T&& t, std::index_sequence<I...>)
  {
    return std::invoke(
      std::forward<F>(f),
      std::get<I>(std::forward<T>(t))...);
  }
}
template <class F, class T>
auto apply(F&& f, T&& t)
{
  return details::apply(
    std::forward<F>(f),
    std::forward<T>(t),
    std::make_index_sequence<
      std::tuple_size_v<std::decay_t<T>>> {}); 
}

How it works...

Before we see how std::invoke() works, let's have a quick look at how different callable objects can be invoked. Given a function, obviously, the ubiquitous way of invoking it is by directly passing it the necessary parameters. However, we can also invoke the function using function pointers. The trouble with function pointers is that defining the type of the pointer can be cumbersome. Using auto can simplify things (as shown in the following code), but in practice, you usually need to define the type of the pointer to function first, and then define an object and initialize it with the correct function address. Here are several examples:

// direct call
auto a1 = add(1, 2);    // a1 = 3
// call through function pointer
int(*fadd)(int const, int const) = &add;
auto a2 = fadd(1, 2);   // a2 = 3
auto fadd2 = &add;
auto a3 = fadd2(1, 2);  // a3 = 3

Calling through a function pointer becomes more cumbersome when you need to invoke a class function through an object that is an instance of the class. The syntax for defining the pointer to a member function and invoking it is not simple:

foo f;
f.increment_by(3);
auto x1 = f.x;    // x1 = 3
void(foo::*finc)(int const) = &foo::increment_by;
(f.*finc)(3);
auto x2 = f.x;    // x2 = 6
auto finc2 = &foo::increment_by;
(f.*finc2)(3);
auto x3 = f.x;    // x3 = 9

Regardless of how cumbersome this kind of call may look, the actual problem is writing library components (functions or classes) that are able to call any of these types of callable objects, in a uniform manner. This is what benefits, in practice, from a standard function, such as std::invoke().

The implementation details of std::invoke() are complex, but the way it works can be explained in simple terms. Supposing the call has the form invoke(f, arg1, arg2, ..., argN), then consider the following:

If f is a pointer to a member function of a T class, then the call is equivalent to either:
- (arg1.*f)(arg2, ..., argN), if arg1 is an instance of T
- (arg1.get().*f)(arg2, ..., argN), if arg1 is a specialization of reference_wrapper
- ((*arg1).*f)(arg2, ..., argN), if it is otherwise
If f is a pointer to a data member of a T class and there is a single argument, in other words, the call has the form invoke(f, arg1), then the call is equivalent to either:
- arg1.*f if arg1 is an instance class T
- arg1.get().*f if arg1 is a specialization of reference_wrapper
- (*arg1).*f, if it is otherwise
If f is a function object, then the call is equivalent to f(arg1, arg2, ..., argN)

The standard library also provides a series of related type traits: std::is_invocable and std::is_nothrow_invocable on one hand, and std::is_invocable_r and std::is_nothrow_invocable_r on the other hand. The first set determines whether a function can be invocable with the supplied arguments, while the second determines whether it can be invocable with the supplied arguments and produce a result that can be implicitly converted to a specified type. The nothrow versions of these type traits verify that the call can be done without any exception being thrown.

Table of Contents for Exploring Functions

Create new playlist

Sign In

Sign Up

3

Exploring Functions

Defaulted and deleted functions

Getting started

How to do it...

How it works...

See also

Using lambdas with standard algorithms

Getting ready

How to do it...

How it works...

See also

Using generic and template lambdas

Getting started

How to do it...

How it works...

See also

Writing a recursive lambda

Getting ready

How to do it...

How it works...

See also

Writing a function template with a variable number of arguments

Getting ready

How to do it...

How it works...

See also

Using fold expressions to simplify variadic function templates

Getting ready

How to do it...

How it works...

There's more...

See also

Implementing the higher-order functions map and fold

Getting ready

How to do it...

How it works...

There's more...

See also

Composing functions into a higher-order function

Getting ready

How to do it...

How it works...

There's more...

See also

Uniformly invoking anything callable

Getting ready

How to do it...

How it works...

See also

Table of Contents for
Exploring Functions