C++ primer 6th Exercise 10.8

Question

You can describe a simple list as follows:

• The simple list can hold zero or more items of some particular type.
• You can create an empty list.
• You can add items to the list.
• You can determine whether the list is empty.
• You can determine whether the list is full.
• You can visit each item in the list and perform some action on it.

As you can see, this list really is simple; it doesn’t allow insertion or deletion, for example. Design a List class to represent this abstract type.You should provide a list.h header file with the class declaration and a list.cpp file with the class method implementations.You should also create a short program that utilizes your design.

The main reason for keeping the list specification simple is to simplify this programming exercise.You can implement the list as an array or, if you’re familiar with the data type, as a linked list. But the public interface should not depend on your choice.That is, the public interface should not have array indices, pointers to nodes, and so on. It should be expressed in the general concepts of creating a list, addingan item to the list, and so on.The usual way to handle visiting each item and performing an action is to use a function that takes a function pointer as an argument:

void visit(void (*pf)(Item &));

Here pf points to a function (not a member function) that takes a reference to Item argument, where Item is the type for items in the list.The visit() function applies this function to each item in the list.You can use the Stack class as a general guide.

---

What I want to know is why should I use pointer-to-functions? what's the difference between using usual member function and using the function that uses pointer-to-function as argument? (in this case, using void visit(void (*pf)(Item &)))?

Answer 1

Function Pointers

Imagine you have a function which takes a number and squares it and returns it. And you have a list whose each member you want squared. How do you do that?

1. You either write another function which accepts an array, loops through it and converts every element to its square.
2. You have a function which accepts an array and a function which can transform one single element. You apply the function to each element of the array.

Both perform the same task. You might think the previous case is easier to implement. You wont have to deal with function pointers after all.

However what if you have say 20 functions which can double, triple, cube, square, etc. a single parameter passed to them. If you follow the first route, you have to write 20 different functions (with probably different names). However now the latter makes sense. You just declare the individual functions. And call the transformer function by passing the array and any of the 20 functions via pointer to achieve your task.

An example is std::transform in the C++ STL.

Working stuff :

#include <iostream>
#include <vector>

typedef double (*function)(double);

void transformer(std::vector<double>& to_transform, function f)
{
    for(auto it = to_transform.begin(); it != to_transform.end(); ++it)
        *it = f(*it);
}

void print(const std::vector<double>& v)
{
    std::cout << "[ ";
    for(double val : v)
        std::cout << val << " ";
    std::cout << "]" ;
}

double f1(double a) { return a*2; }
double f2(double a) { return a*3; }
double f3(double a) { return a/2; }
double f4(double a) { return a*a*a; }

int main() {
    std::vector<double> array = { 2.3, 5.6, 4.5, 7.8, 2.3 };
    std::vector<function> function_ptrs = { &f1, &f2, &f3, &f4 };
    std::size_t val ;
    std::cout << "The original : " ;
    print(array);
    std::cout << "\nChoose a function (1-4) : ";
    std::cin >> val;
    std::cout << "The array after applying function " << val << " is : ";
    transformer(array, function_ptrs[(val - 1) % function_ptrs.size()]);
    print(array);
    return 0;
}

I am assuming you have a C++11 compliant compiler. The above code has 4 functions which take in a double and transform it somehow. The transformer function applies such a function to a vector of doubles. The function pointers are stored in a vector too - Yes an array of function pointers. The functions can be called as a normal element is accessed via indexing. On choosing an option, the appropriate function is called and executed by transformer element wise on the vector of doubles.

You can further improve it with templates (instead of fixed doubles) and using std::transform from STL.

C++11 Lambda Expressions

Also, with C++11, you should prefer lambdas and not function pointers. Lambdas are written as

[ ... capture list ... ] ( params ) -> return_type (optional) { body }

A solution with lambda would be something like this :

#include <iostream>
#include <algorithm>
#include <vector>

template <typename T>
void print(const std::vector<T>& v)
{
    std::cout << "[ ";
    for(T val : v)
        std::cout << val << " ";
    std::cout << "]" ;
}

int main() {
    std::vector<double> array = { 2.3, 5.6, 4.5, 7.8, 2.3 };
    std::cout << "The original : " ;
    print(array);
    std::cout << "\nThe array after transforming : " ;
    std::transform(array.begin(), array.end(), array.begin(), 
        [](double x) { return x * x; });
    print(array);
    return 0;
}

Function Objects

You can declare your own class which just overloads the () operator (which makes the object callable) and does an identical job as a function pointer (can be passed to a function and called) i.e. in this case the class would look like :

class double_the_value
{
    double operator()(double val) const { return val * 2.0 ; }
};

double_the_value f ;
std::cout << f(3.0) ; // outputs 6.0

An actual usage would be the std::unordered_map container where if you are using your own class types for keys, you will need to provide a key hasher - which can be a function object. This is demonstrated in detail by this answer.

Answer 2

When you're creating a true abstract list you have no idea what functions you will need to call on the objects, so your usual member functions won't be enough. You can't write all of them.

A common and easier alternative to this pattern is to return a copy of the full collection or expose iterators to the first and last element. But this can cause performance issues and can be risky - a copy can be expensive and is usually unnecessary, and if you use iterators they can become invalid if the collection changes beneath you. The visitor pattern hides all this by giving you better encapsulation and keeps the iteration loop within the class, where it usually belongs.

It's an additional layer of abstraction. If you have a collection of items, you usually want to do something to some (or all) of the items in that collection. The visitor pattern lets you inspect each item and then do something.