Jonathan Boccara's blog

Various Ways of Applying a Function to the Elements of a Collection in C++

Published February 7, 2020 - 0 Comments

Applying a function to each element of a collection of object is a basic use case of manipulating collections, in C++ or anywhere else for that matter.

For this, the STL algorithms library offers std::transform. However, std::transform can lead to verbose code, in particular if we have to call it several times. To illustrate, consider this class Point on which we have a function that computes the norm:

struct Point
{
    double x;
    double y;
};

double norm(Point const& point)
{
    return sqrt(point.x * point.x + point.y * point.y);
}

If we’d like to check if the norms of a collections of points are equal to some reference values, we can use std::transform:

auto const myPoints = std::vector<Point>{ {3,4}, {6,8}, {9,12} };

auto myNorms = std::vector<double>{};
std::transform(begin(myPoints), end(myPoints), back_inserter(myNorms), norm);
auto const areNormsCorrect = myNorms == std::vector<double>{5, 10, 15};

3 lines of code to check if the norms of the points are equal to reference values is quite a lot of code. In particular when we need to repeat it for several applications in the same piece of code.

To fix this problem we can use ranges::view::transform, a range adaptor from the range v3 library, that leads to more concise code:

auto const areNormsCorrect = (myPoints | ranges::view::transform(norm) | ranges::to_vector) == std::vector<double>{5, 10, 15};

or even:

auto const areNormsCorrect = ranges::equal(myPoints | ranges::view::transform(norm), {5, 10, 15});

But to use it, you need to have access to the range v3 library (and to a compiler that supports it), which is not the case for everyone.

If none of those solutions seems satisfactory, here is another alternative. As in How to Write Simple Code to Accomplish Complex Tasks, we will first design an interface, and then think about how to implement it.

The interface of project

We will design a simple solution so that you can implement it in your code, regardless of which libraries you have access to. The point is not to design a library that covers every possible use case. Rather, we will focus on one common use case: applying a function to the elements of a collection, and retrieving a std::vector containing the results.

To achieve this, let’s design project, that takes a function that can accept one element of the collection, and returns a function that accepts a whole collection and applies the unitary function to each element and returns a std::vector with the results.

The name project comes from the fact that applying a function to each element can be seen as a “projection” (in particular if this function returns a member of the object).

Here is how project would be used:

auto norms = project(norm);

As a reminder, norm is a function that can be applied to each element of the collection of Points:

double norm(Point const& point)
{
    return sqrt(point.x * point.x + point.y * point.y);
}

Then we would use norms, the result of applying project on norm, this way:

auto const myPoints = std::vector<Point>{ {3,4}, {6,8}, {9,12} };

auto const areNormsCorrect = norms(myPoints) == std::vector<double>{5, 10, 15};

Let’s now see how to implement project.

Implementation of project

Here is a possible implementation of project. We will go through it line by line afterwards.

template<typename Function>
auto project(Function function)
{
    return [function](auto const& inputs)
    {
        using value_type = decltype(inputs.front());
        using function_return_type = std::result_of_t<Function(value_type)>;
        auto results = std::vector<std::decay_t<function_return_type>>{};
        results.reserve(inputs.size());
        for (auto const& input : inputs)
        {
            results.push_back(std::invoke(function, input));
        }
        return results;
    };
}

project is a function that takes a function (e.g. norm) and returns a function (e.g. norms). Since functions can take many types (including the unspecified types of lambdas), a simple way to take a function as input parameter is to use a template type.

To return a function with expressive code, we can return a lambda and have auto as a returned type:

template<typename Function>
auto project(Function function)
{

What we return is a lambda that takes a collection (e.g. myPoints):

    return [function](auto const& inputs)
    {

In the implementation of this lambda, we need to create the container in which to output the results of applying the function to the elements of inputs. This container is an std::vector, but of what? Of the return type of the function. But what is this type?

To work out the result type of the function, we can use std::result_of, that takes a template parameter containing the type of the function (Function) and the type of the function’s input. We don’t have the type of the function’s input, but that’s what is in the inputs collection.

We can deduce the type of the elements in the inputs collection by identifying the type returned when accessing an element of the function:

        using value_type = decltype(inputs.front());

We could also have used the value_type alias inside of the input collection, if that collection follows the conventions of the STL.

We can now use std::result_of (or rather its C++14 counterpart std::result_of_t that directly returns the desired type, instead of accessing it with ::type):

        using function_return_type = std::result_of_t<Function(value_type)>;

In the case where the function returns a reference, we need to remove the reference, because there is no such thing as a vector of references. For this we can use std::decay_t (the C++14 counterpart of C++11’s std::decay):

        auto results = std::vector<std::decay_t<function_return_type>>{};

Since we know the final size of that vector (it’s the same size as inputs), we might as well use it to allocate the necessary memory for results only once:

        results.reserve(inputs.size());

With the inputs data and the results structure at our disposal, we can apply function to each element. We could use std::transform to apply free functions and function objects. But in the case where function is a class method or even a class data member (e.g. &Point::x), std::transform cannot apply it. We will go for a more generic C++ component: C++17’s std::invoke:

        for (auto const& input : inputs)
        {
            results.push_back(std::invoke(function, input));
        }

If you don’t have C++17 you can resort to using std::transform and limit project to free functions and function objects. note that returning lambdas from a function requires C++14. If you don’t have C++14 you can resort to returning a std::function as explained at the end of Making code expressive with lambdas. This requires C++11 only.

We finally return the results from the lambda:

        return results;
    };
}

A trade-off

project allows to write more concise code than using std::transform or a for loop, has very simple code, but is nowhere as complete as the ranges library. If you don’t have access to range v3, do you think project would be relevant in your code?

By the way, if you think project should have a better name, or if you have any other piece of feedback, please let me know in the comments section!

You will also like

Don't want to miss out ? Follow:   twitterlinkedinrss
Share this post!Facebooktwitterlinkedin