Jonathan Boccara's blog

Tweet

Understand ranges better with the new Cartesian Product adaptor

Published April 14, 2017 - 3 Comments

A couple of days ago, the range-v3 library got a new component: the view::cartesian_product adaptor.

Understanding what this component does, and the thought process that went through its creation is easy and will let you have a better grasp of the range library. (Note that you could just as well understand all the following by looking at the zip adaptor. But cartesian_product is brand new, so let’s discover this one, in order to hit two birds with one stone.)

Oh maybe you’re wondering why you would need to understand the range library?

Like I explained in details on Arne Mertz’s blog Simplify C++!, ranges are the future of the STL. Essentially, the STL is a powerful tool for writing expressive code, and ranges are a very well designed library that takes it much farther. Ranges are expected to be included in the next C++ standard, hopefully C++20, and until then they are available to test on Eric Niebler’s github, its author. So in a nutshell, you want to learn ranges to understand where the craft of writing expressive C++ is heading to.

Motivation

The purpose of the cartesian_product adaptor is to iterater over all the possible combinations of the elements of several collections.

We will use toy examples in this articles to keep all the business specific aspects away, but an example of where this can be useful is where objects have versions. In such a case you may want to generate all possible objects for all possible dates for example.

But for our purpose we will use the following 3 collections. First a collection of numbers:

std::vector<int> numbers = {3, 5, 12, 2, 7};

then a collection of types of food that are typically served at a meetup, represented by strings:

std::vector<std::string> dishes = {"pizzas", "beers", "chips"};

and finally a collection of places, also represented by strings for simplicity:

std::vector<std::string> places = {"London", "Paris", "NYC", "Berlin"};

Now we want to do an action, like printing a sentence, with every possible combination of the elements of these 3 collections.

Putting the behaviour into an algorithm

Here was my first attempt at writing a generic function that could apply a function over all the possible combinations of several collections. I am purposefully taking away all the variadic aspects here, in order to keep the focus on the responsibilities of the algorithms:

template<typename Collection1, typename Collection2, typename Collection3, typename Function>
void cartesian_product(Collection1&& collection1, Collection2&& collection2, Collection3&& collection3, Function func)
{
    for (auto& element1 : collection1)
        for (auto& element2 : collection2)
            for (auto& element3 : collection3)
                func(element1, element2, element3);
}

And this does the job. Indeed, the following call:

cartesian_product(numbers, dishes, places,
    [](int number, std::string const& dish, std::string const& place)
    { std::cout << "I took " << number << ' ' << dish << " in " << place << ".\n";});

outputs this:

I took 3 pizzas in London.
I took 3 pizzas in Paris.
I took 3 pizzas in NYC.
I took 3 pizzas in Berlin.
I took 3 beers in London.
I took 3 beers in Paris.
I took 3 beers in NYC.
I took 3 beers in Berlin.
I took 3 chips in London.
I took 3 chips in Paris.
I took 3 chips in NYC.
I took 3 chips in Berlin.
I took 5 pizzas in London.
I took 5 pizzas in Paris.
I took 5 pizzas in NYC.
I took 5 pizzas in Berlin.
I took 5 beers in London.
I took 5 beers in Paris.
I took 5 beers in NYC.
I took 5 beers in Berlin.
I took 5 chips in London.
I took 5 chips in Paris.
I took 5 chips in NYC.
I took 5 chips in Berlin.

The limits of an algorithm

It looks ok, but the above code stops working if I slightly change the requirement. Say now that we no longer want a function to directly write to the console. To decouple the code from the IO, we want to output the various combinations into a container of strings.

And then we’re stuck with the above implementation, because it doesn’t return anything. (If it crossed your mind to store the output in the function by making it a function object, then you must be under an amount of stress which is higher than necessary. To relax, I suggest you read STL function objects: Stateless is Stressless).

In fact, the above algorithm is sort of the equivalent of std::for_each for all possible combinations, because it iterates over all of them and applies a function. And what we would need here is rather an equivalent of std::transform (more about this central algorithm here).

Are we to recode a new cartesian_product that takes an output collection and a function, like std::transform? It feels wrong, doesn’t it?. We’d rather take the iterating responsibility out of the algorithms. And this is exactly what the cartesian_product adaptor does for you.

The cartesian_product adaptor constructs a view over a set of collections, representing it as a range of tuples containing every possible combinations of the elements in the collections. Then the function has to take a tuple containing its arguments. Note that it would be preferable to keep taking the arguments directly instead of through a tuple, but more on this later.

Here is an example to satisfy the need of outputing the sentences into a string container:

std::string meetupRecap(std::tuple<int, std::string, std::string> const& args)
{
    int number = std::get<0>(args);
    std::string const& dish = std::get<1>(args);
    std::string const& place = std::get<2>(args);

    std::ostringstream result;
    result << "I took " << number << ' ' << dish << " in " << place << '.';
    return result.str();
}

std::vector<std::string> results;
transform(ranges::view::cartesian_product(numbers, dishes, places), std::back_inserter(results), meetupRecap);

And the same adaptor can also be used to perform the output to the console, without having to write a specific algorithm:

void meetupRecapToConsole(std::tuple<int, std::string, std::string> const& args)
{
    int number = std::get<0>(args);
    std::string const& dish = std::get<1>(args);
    std::string const& place = std::get<2>(args);

    
    std::cout << "I took " << number << ' ' << dish << " in " << place << ".\n";
}

for_each(ranges::view::cartesian_product(numbers, dishes, places), meetupRecapToConsole);

This adaptor effectively takes the responsability of generating all the possible combinations of elements, thus letting us reuse regular algorithms, such as for_each and transform.

The official cartesian_product range adaptor

A couple of months ago I came up with this adaptor and proposed it to Eric Niebler:

Eric responded positively and a few weeks later, Casey Carter implemented it inside the range-v3 library (thanks Casey!):

…which is how range-v3 got this new adaptor.

To me it’s a good addition, and I think that the interface using tuples can be further improved. There is a way to encapsulate the tuple machinery into another component – but we will get into this topic in another post, another time.

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


Comments are closed