The tutorial will cover the following topics.

- Function pointers

- Anonymous/lambda functions

- Partial function application

- Higher order functions

- Higher order functions in the STL

- Templating our functions

- Creating new loop constructs

- Variadic template functions

All code snippets have have been compiled with g++ 4.6.1 (g++ -std=c++0x file) and should be valid c++11. The fully working example programs are at the bottom.

**1) Function pointers.**

Function pointers have been a part of C++ since the beginning, in fact they have been a part of C from the beginning. But their interface has always been cumbersome.

An example of a classic C function pointer, feel free to skip to the new:

The old:

int foo(double) {} int (*foo_ptr)(double) = &foo;

Now you can call the function through the pointer like this foo_ptr(5.0);

Member functions makes things much worse:

class A { public: int foo(double) {} }; int (A::*mem_foo_ptr)(double) = &A::foo;

And you would call it like this: ((a).*(mem_foo_ptr))(5.0);, if a is an object of type A. In fact people usually use a macro to make it a little less painful. From c++ faq lite:

#define CALL_MEMBER_FN(object, ptrToMember) ((object).*(ptrToMember))

The function call is now: CALL_MEMBER_FN(a, mem_foo_ptr)(3.14);

The new:

With c++11 we have a new way to deal with function and member function pointers under the functional header, the std::function wrapper.

int foo(double) {} std::function<int(double)> call_foo1 = &foo;

Now you can call foo through the function object like this: call_foo(5.0);.

class A { public: int foo(double) {} }; std::function<int (A&, double)> call_foo1 = &A::foo; std::function<int (A*, double)> call_foo_on_ptr1 = &A::foo;

And now you call foo like this: call_foo1(a, 5.0) or call_foo_on_ptr1(&a, 5.0), if a is an object of type A.

Not only is the interface more convenient, but you can assign anything to a std::function object that can be called like a function, including function objects/bind object.

C++11 introduces tools to let the the compiler automatically deduct the type of a variable from the expression. For regular functions we can do:

auto call_foo = &foo; decltype(&foo) call_foo2 = &foo; std::function<decltype(foo)> call_foo3 = &foo; call_foo(5.0); call_foo2(5.0); call_foo3(5.0);

This represents 3 ways to to create a function pointer without knowing anything about it's type. The first one is the simplest and the result the same as the second one. The third one explicitly wraps it in a std::function wrapper.

For member functions it is a little more difficult. &A::foo is actually the old function pointer type with it's incredibly weird call syntax. We can however convert it to a regular function that takes it's object as a first argument like this:

A a; auto call_foo2 = std::mem_fn(&A::foo); call_foo(a, 5.0);

a may also be an A*.

Or use bind as explained in Partial function application.

I make use of the auto keyword extensively throughout the tutorial. And when I call something a function in this tutorial it can have many different types. Including but not limited to a function pointers, std::function objects, bind objects (see partial function application) or functors you defined yourself.

Don't confuse using auto as not using strong typing. The compiler knows exactly what type auto is at compile time.

**2) Anonymous/lambda functions**

Anonymous functions, also called lambda functions are a new c++11 functions with no name that can be created everywhere. For example:

int main() { auto double_n = [](double x) {return x * 2;}; std::cout << double_n(50) << std::endl; //100 }

Double_n is a function pointer pointing to a an anonymous function. For auto you could use std::function<double(double)>, but it's usually much easier to keep it auto.

If we want to, we can also make some or all variables from the local scope available to the function.

For example:

int main() { int sum = 0; auto running_sum = [&sum](double x) {sum += x;}; running_sum(1); running_sum(2); running_sum(3); //sum is now 6 (1+2+3) }

Notice the [&sum], this means that we make the sum variable available to the lambda function by reference. We can also make any combination of variables available to the the lambda function. This table summarizes how it would work.

[]: no variables defined. Attempting to use any external variables in the lambda is an error. [x, &y]: x is captured by value, y is captured by reference [&]: any external variable is implicitly captured by reference if used [=]: any external variable is implicitly captured by value if used [&, x]: x is explicitly captured by value. Other variables will be captured by reference [=, &z]: z is explicitly captured by reference. Other variables will be captured by value

This is a powerful tool, for example, want the sum of the variables in an array or any other container or just print it.

int arr[] = {1,2,3,4,5,6,7}; int sum = 0; std::for_each(std::begin(arr), std::end(arr), [&sum] (int x) {sum += x;}); std::for_each(std::begin(arr), std::end(arr), [] (int x) {std::cout << x << ' ';});

Can you see what is happening, for_each will call a function for every element, we pass it a lambda function that has access to the sum variable and increments it. Can you guess the line that will multiply all the elements ?

You can also call a lambda recursively but it does require a little trick. Take the following factorial function as an example (fact(n) = n! = n * (n-1) * (n-2) * ... * 1).

int main() { std::function<int(int)> fact = [&fact] (int n) { return (n==0) ? 1 : n * fact(n-1); }; }

See how we make the fact function we are defining available to the lambda function. Note that this is one of the cases where declaring the type of the function as auto will not work.

**3) Partial function application**

Partial function application is converting functions that take parameters to create new functions, with some of the parameters already matched. It is also referred to as parameter binding.

int foo(double x, std::string y) {}

Suppose we know already what the double parameter x is going to be and we want to make a new function with the x already filled in, bind allows us to do this.

std::function<int(std::string)> foo_str = std::bind(&foo, 5.0, std::placeholders::_1); foo_str("just a message");

We can also use an argument more than once. For example suppose we have a sum function?.

int sum(int x, int y) {return x + y;}

But what we really want is a double function, then we could do:

using namespace std::placeholders; auto dbl_func = std::bind(&sum, _1, _1);

Did you see that one coming ?

Bind, by default, always copies arguments by value even if the function takes references. But you can override this behavior by wrapping your arguments with std::ref or std::cref (constant reference). Beware however that if you do so, that you make the free functions dependent on the variables you pass by reference, this can hurt you silently when the variable goes out of scope before the bind object. The same is true when you use pointers, but bind does work excellently in combination with smart pointers.

example:

double dbl = 5.0; std::function<int()> parameter_free_foo = std::bind(&foo, std::ref(dbl)); //bind dbl by reference

A special form of binding is binding a member function to an object to create a free function. Remember our example:

class A { public: int foo(double) {} };

Suppose we already have an object of type A and want a free function, then.

A a; auto free_foo = std::bind(&A::foo, a, std::placeholders::_1);

The next concept is transforming a function called on an object to a function that takes the object it would have been called on as a parameter. This can be very useful. Suppose you have a vector of Objects of type A. And A has a member function foo.

std::vector<A> vector_of_A;

Now I want to call foo on every object in the vector with for_each but I have a problem. For_each takes a function that takes an object of type A, but A::foo doesn't take an object of type A it is called on an object of type A. We can solve this with std::bind or the mem_fn wrappers we have seen already.

using namespace std::placeholders; std::vector<A> a_vect; std::for_each(a_vect.begin(), a_vect.end(), std::mem_fn(&A::foo)); std::for_each(a_vect.begin(), a_vect.end(), std::bind(&A::foo, _1));

The syntax would be the same if a_vect was a std::vector<A*>

These 2 statements transform a function that is called on an object to a function that takes the object it is supposed to be called on as a parameter.

**4) Higher order function**

Higher order functions is just a term used for functions that take other functions as a parameter and/or return a function. If you are familiar with the stl, then you've probably already used them. The for_each/find_if/sort_by,... they all take a function as a parameter. So let's make our own.

Suppose we want to make a sum, sum_of_square, sum_of_cubes function, but we are lazy. We have this sum function:

double suma(std::vector<double>::iterator begin, std::vector<double>::iterator end) { double sum = 0: for (; begin != end; ++begin) { sum += *begin; } return sum; }

And we'd like to use it for all 3 use cases.

One way to approach this is to pass a function to sum function to be applied before the (*it) is summated. This is not so hard as you might think. This will work fine:

double suma(std::vector<double>::iterator begin, std::vector<double>::iterator end, std::function<double(double)> f) { double sum = 0; for (; begin != end; ++begin) { sum += f(*begin); } return sum; }

Now we can pass the square/cube function to the sum function to calculate the sum of squares/cubes. Combining this with the pow function and the power of lambda functions:

std::vector<double> vect = {1,2,3,4,5,6}; double sums = suma(vect.begin(), vect.end(), [] (double x) {return x;}); //pass identity function double sum_of_squares = suma(vect.begin(), vect.end(), [] (double x) {return pow(x,2);}); //pass ^2 function double sum_of_cubes = suma(vect.begin(), vect.end(), [] (double x) {return pow(x,3);}); //pass ^3 function

Note that our suma function looks very much like the stl functions for_each, find_if, etc in the algorithm header, if you ever wondered how it's done, this is how. The stl versions will work with any type though, not just a vector of doubles, we will deal with this in "6) Templating our functions".

Ok we can now calculate those sums, but I want to make functions to calculate those sums, no problem:

using namespace std::placeholders; auto sum_f = std::bind(&suma, _1, _2, [] (double x) {return x;}); auto sum_of_squares_f = std::bind(&suma, _1, _2, [] (double x) {return pow(x,2);}); auto sum_of_cubes_f = std::bind(&suma, _1, _2, [] (double x) {return pow(x,3);}); double sum = sum_f(vect.begin(), vect.end()); double sum_of_squares = sum_of_squares_f(vect.begin(), vect.end()); double sum_of_cubes = sum_of_cubes_f(vect.begin(), vect.end());

You didn't forget about bind again did you ?

Let's do something even more interesting. We want a function that combines 2 functions f and g, such that the result is a new function that combines the two like this f(g()).

std::function<double(double)> combine_functions(std::function<double(double)> f, std::function<double(double)> g) { return [=](double x){return g(f(x));}; }

We cannot just return g(f()) as it is not immediately obvious to the compiler that the types match. But what we can do is return a new lambda function that applies the functions the way we want them to. See the [=], this gives the lambda function access to the functions f,g.

An alternative would be to use the bind statement

std::function<double(double)> combine_functions(std::function<double(double)> f, std::function<double(double)> g) { //f after g, so g(f(x)) return std::bind(g, std::bind(f, std::placeholders::_1)); }

Yes we can bind functions to other functions with a nested bind.

So how can we use this ?

Suppose we have a double function, but what we really want is a quadrupal function:

auto dbl = [](double x){return x*2;}; auto quadrupal = combine_functions(dbl, dbl);

There we have just combined 2 functions to create a new function. quadrupal, with the same effect as dbl(dbl(x)).

**5) Higher order functions in the stl**

The stl (standard template library) has really embraced this idea of higher order functions. Especially when it comes to containers such as vector/list/map/set and many others.

In the algorithm header there are a lot of really powerful higher order functions (functions that take or can take a function as a parameter), to be specific:

in algorithm header:

for_each, find_if, count_if, transform, replace_copy_if, remove_if, remove_copy_if, , partition, stable_partition, sort, stable_sort, partial_sort, partial_sort_copy, lower_bound, upper_bound, equal_range, binary_search, merge, inplace_merge, set_union, set_intersection, set_difference, set_symmetric_difference, push_heap, pop_heap, make_heap, sort_heap, min, max, min_element, max_element, lexicographical_compare, next_permutation, prev_permutation.

in numeric header:

accumulate, adjacent_difference, inner_product, partial_sum.

Also containers like map/set/multimap/multiset take a function as a template type parameter and optional parameter. Many containers also have higher order member functions not mentioned here.

These in combination with the convenience of lambda functions can be powerful tools to make your code shorter, faster and more to the point. See the programs at the bottom to see an example of the stl at work.

**6) Templating our functions**

You probably noticed that the functions in the algorithm header seem to work with any type, container or function you throw at it and you are wondering if your functions can do the same. Well let's find out. Let's create our own for_each function. Looking back at the sum example, you should be able to make one that works for just ints for example, it's a good exercise to try for yourself.

Anyway, it should look something like this:

void for_each2(std::vector<int>::iterator begin, std::vector<int>::iterator end, std::function<void(int)> f) { for (; begin != end; ++begin) { f(*begin); } }

We use the begin pointer as the current pointer, as it already is a copy and an additional copy would be wasteful.

If we wanted a for_each function for vectors of doubles, we would have to write a function that is exactly the same except int would be double. If we used a std::list, then that wouldn't change anything either, just replace all std::vector with std::list and it will work. For this C++ offers templates.

So let's try to make it container agnostic first. To do this we replace std::vector<int>::iterator with a template parameter:

template<class InputIterator> void for_each2(InputIterator begin, InputIterator end, std::function<void(int)> f) { for (begin != end; ++begin) { f(*begin); } }

When we compile, the compiler will just fill in the right type instead of InputIterator. Try it with: list/map/set,...:

std::list<int> l = {1,2,3,4,5} ; std::for_each2<std::list<int>::iterator>(l.begin(), l.end(), [] (int x) {std::cout << x << ' ';}); std::for_each2(l.begin(), l.end(), [] (int x) {std::cout << x << ' ';});

The second one will only work if the compiler can deduct from your parameter, which type it has to substitute. In this case it can.

But we still can't use a data type other than int because we still need to pass a function that takes an int (std::function<void(int)>). Let's make that a template parameter too:

template<class InputIterator, class Function> void for_each2(InputIterator begin, InputIterator end, Function f) { for (; begin != end; ++begin) { f(*begin); } }

We don't care which type the function is, as long as f(*begin) works.

This is exactly the same function declaration as for_each, defined in the c++ standard. You have written a small part of the stl.

**7) Creating new loop constructs**

You are now more than familiar with for_each. Now combining for_each and lambda's we can create a sort of loop, that iterates over the elements of a container:

std::vector<int> vect = {1,2,3,4,5,6,7,8,9,10} std::for_each(vect.begin(), vect.end(), [&](int& x) { //x will loop over all members of vect });

This behaves almost the same like any ordinary for loop. The same variables external variables are available (see [&]), And the current element in the container will be accessible through x. It is almost equivalent to:

for(auto it = vect.begin(), it != vect.end(), ++it) { int& x = *it; }

And the very similar to the new c++11 for each loop construct:

for (int& x: vect) { //x will loop over all members of vect }

I say almost and very similar because control statements like continue and break are not available. A return statement in the lambda function will function as a continue but there is no break.

This looping using a lambda function however has far reaching consequences because we can easily make our own for_each like functions and thus create new kinds of loops.

For example, we want a loop that loops over every odd member of any container. Then we could write something like this:

template<class InputIterator, class Function> void for_each_odd(InputIterator begin, InputIterator end, Function f) { for (; begin != end; ++begin) { if (*begin%2 != 0) { f(*begin); } } }

We can call our new loop like this:

for_each_odd(vect.begin(), vect.end(), [&](int& x) { //x will loop over all odd members of vect });

Now lets make this more flexible:

template<class InputIterator, class Predicate, class Function> void for_each_if(InputIterator begin, InputIterator end, Predicate pred, Function f) { for (begin != end; ++begin) { if (pred(*begin)) { f(*begin); } } }

auto larger_than_5 = [](int x){return x > 5;}; for_each_if(vect.begin(), vect.end(), larger_than_5, [&](int x) { //loop over all elements of vect > 5 });

It doesn't even have to loop over anything. It can be used to create a sort of generator. Take the following example:

template<class Function> void generate_primes(Function f) { for (int i = 2; ; i++) { bool prime = true; int max_j = sqrt(double(i)) + 1; for (int j = 2; j < max_j; j++) { if (i%j == 0) { prime = false; break; } } if (prime) { if (!f(i)) return; } } }

It is a not particularly efficient function to generate consecutive primes. But what is interesting is that we can use it like this.

generate_primes([&](int prime) { if (prime > 100) return false; //break //loop over primes < 100 return true; //continue });

So what are the return true/false and the strange if (!f(i)) return; in the generate_primes doing there. Well we need a way to exit the loop, traditional control statements like break and continue don't work because we are not technically in a loop. The solution I've used here is to make the function passed to generate prime a boolean function where true means continue and false means stop.

Alternatively we could pass an additional predicate function to generate_primes like we did in for_each_if.

Try to implement every looping construct let's say ruby supports, I'm sure it can be done.

I'll give you 3 more I quite like

template<class T> void times(T times, std::function<void(void)> f) { for (T i = 0; i < times; i++) { f(); } } ... times(5, []() { std::cout << "*"; });

For those times, you just want to do something 5 times, and:

template<class T, class Function> void step(T begin, T step_size, T end, Function f) { for (; i <= end; begin+=step_size) { f(begin); } } ... //step function with begin, step_size, end step(0.0, 0.1, 1.0, [](double i) { std::cout << i << " "; }); std::cout << std::endl;

A simple step function, works with integers but also floats/doubles as shown above.

And we've written a for_each_if, but I also found that sometimes you want to do something with a container while a certain condition remains true, so:

//Assumes the data set is partitioned by predicate template <class Iterator, class Predicate, class Function> void for_each_while(Iterator begin, Iterator end, Predicate p, Function f) { //the find first is actually more efficient than checking the predicate //as you go along, because the predicate only needs to be checked for //worst case log(n) elements and can be ignored after that. Iterator real_end = std::partition_point(begin, end, p); for_each(begin, real_end, f); }

**8) Variadic template functions**

Variadic templates allow functions to take any number of variables as a variable/type pack. This is perhaps best explained through an example.

So let's create a simple sum function, that takes any number of parameters, so we want to be able to call it like this:

sum(1, 2, 3, 4) sum(1, 3)

And any other number of parameters.

We can create a function declaration that can take any number of parameters like this

template <class... Nrs> double sum(Nrs... nrs);

The problem is that we cannot simply iterate over the nrs (not directly, see later). We can however send it to another function, but then we would have the same problem there. What we can do is slightly change the declaration so we get one parameter separately.

template <class Head, class... Tail> double sum(Head head, Tail... tail);

Now we have a variable head that is a plain variable and tail, which we can send to another function. So how could we use this to calculate the sum like this:

template <class Head, class... Tail> double sum(Head head, Tail... tail) { return head + sum(tail...); }

This is a recursive definition of a sum, the sum of all elements is the first element + the sum of the remaining elements. This almost works, but when we try to compile it we get an error that no definition for sum() exists. What happens is that this recursion continues until the last element, after that the tail is empty and it tries to call sum with no parameters. So the solution, create a function sum with no parameters.

double sum() { return 0; } template <class Head, class... Tail> double sum(Head head, Tail... tail) { return head + sum(tail...); }

Can you create a function that multiplies any number of elements ?

If you want to know how many variables are in a pack, you can use the new sizeof...(tail).

To help with variadic templates, the stl now also comes with std::tuple. It is a sort of a generalization of std::pair.

#include <tuple> std::tuple<int, double, std::string> entry = {1 , 2.0, "Hello"};

Or if you want the compiler to figure out the type.

#include <tuple> auto entry = std::make_tuple(1 , 2.0, "Hello");

Obviously make_tuple can take any combination of parameters, I'm sure you can see that it is a variadic function. But how can it help us:

#include <tuple> template <class... Variables> double foo(Variables... variables) { auto variables_tuple = std::make_tuple(variables...); //extract data from the tuple here }

A std::tuple is a strange beast though, lacking for example a looping construct. But it can be helpful to extract a particular element with std::get<i>(tuple) for example.

To iterate over variadic parameters, you can create a container with them.

template <class... Params> void f(Params... params) { std::array<int, sizeof...(params)> list = {params...}; }

So we could write our sum function like this:

template <class... Params> double sum(Params... params) { std::array<double, sizeof...(params)> l = {params...}; return std::accumulate(l.begin(), l.end(), 0.0); }

This however only works if all parameters are of the same type or atleast implicitly convertible to one type. If you have a heterogeneous parameter pack, you will have to use recursion.

Going to tuples again.

Regularly people ask if you can return multiple values from a function. A tuple is yet another way to do this. and std::tie has made it somewhat easier.

#include <tuple> std::tuple<int, int> foo() { return std::make_tuple(1,2); } main() { int a, b; std::tie(a,b) = foo(); }

std::tie ties references together, so they can be assigned to by a tuple.

Std::tie also takes a std::placeholder if you are not interested in a particular result.

This concludes the fun with functions tutorial, now try to have some fun with functions yourself.

Appendix, Example programs:

1.1: Function pointers

Spoiler

1.2: Member function pointers

Spoiler

2: Anonymous functions

Spoiler

3: Partial function application

Spoiler

4: Higher order functions

Spoiler

5: Higher order functions in the stl

Spoiler

6: Templating our functions

Spoiler

7: Creating new loop constructs

Spoiler

8: Variadic template functions

Spoiler

**Changes**

- Added times and step function to "Creating new loop constructs"
- Added iterating over variadic parameter packs
- Replaced mem_fun/mem_fun_ref which are deprecated by mem_fn as suggested by Ricky65
- Replaced some algorithms by others that incur one less copy on the iterator as suggested by Ricky65
- Added for_each_while
- Pointed out that in order for std::array<type, sizeof...(params)> = {params...}; to work, the params need to have an homogeneous type.

This post has been edited by **Karel-Lodewijk**: 19 February 2012 - 07:16 AM