How to Use Overloaded Functions With The STL

The latest challenge on Fluent C++ wasn’t an easy one. It consisted in finding the best way to use overloaded functions with the STL – or with any other context that accepts functions as parameters, for that matter.

You guys submitted solutions that took very different approaches, and this is awesome. Let’s see in details the concrete case, our winner and his solution, and then let’s mix good ideas coming from other solutions with it.

The missing link between the STL and function overloading

Here is the problem we’re trying to solve.

The STL is a fantastic tool to make your code more expressive and more robust. If you’re a C++ developer and want to become proficient at it, it is essential that you learn the STL.

But there is one case where we can’t apply STL algorithms right out of the box: when the function passed has overloads.

Here is an example to illustrate. Let’s consider this function f that takes an int by reference and adds 1 to it:

void f(int& i)
{
    ++i;
}

Now we use this function in the simplest algorithm, std::for_each, to increment every element of a container of numbers:

std::vector<int> numbers = {1, 2, 3, 4, 5};
std::for_each(begin(numbers), end(numbers), f);

So far, so good. But if we just add a new function, that is also called f but that takes a std::string. In other terms, an overload of f:

void f(std::string& s);

I’m not even defining this overload, a mere declaration is enough to… cause a compilation error!

Overloads are perfectly legal in C++ in general, but here the new overload prevents the call to the algorithm from compiling. Indeed, the compiler can’t decide which one the algorithm should use.

That’s from a compiler’s point of view. From a human point of view the situation is obvious: there is one overload that takes ints, one that takes strings, and the collection contains ints. It’s a no-brainer, we should use the first overload of f, the one that takes ints.

The challenge was to find a way to make the compiler use the right overload in an expressive way, without resorting to a static_cast of f at call site to resolve overloading manually.

The winner

Our winner today is… Vittorio Romeo!

Vittorio is a modern C++ enthusiast who loves to share his knowledge by creating video tutorials and participating to conferences. You can find Vittorio on his website vittorioromeo.info or on Twitter @supahvee1234.

Now let’s see Vittorio’s solution. Here is his challenge submission, and the essence of his solution is this:

// C++ requires you to type out the same function body three times to obtain SFINAE-friendliness and 
// noexcept-correctness. That's unacceptable.
#define RETURNS(...) noexcept(noexcept(__VA_ARGS__)) -> decltype(__VA_ARGS__){ return __VA_ARGS__; }

// The name of overload sets can be legally used as part of a function call - we can use a macro to
// create a lambda for us that "lifts" the overload set into a function object.
#define LIFT(f) [](auto&&... xs) RETURNS(f(::std::forward<decltype(xs)>(xs)...))

With a call site looking like this:

std::for_each(begin(numbers), end(numbers), LIFT(f));

The idea here is to wrap the call of f into a lambda, that accepts a template value (auto&&... xs) that it passes on to f. This way, the algorithm instantiates the lambda with the type of the elements in the range, and the compiler is informed of the type of the argument passed to f. Then it has no problem resolving the overload.

Said differently, the initial problem was that no argument is passed to f when we invoke the algorithm, we just pass f as a function. And the compiler needs to see what arguments are passed to a function to pick the right overload. Vittorio’s solution adds a level of indirection (the lambda) that creates an expression where f takes an argument.

Now the devil is in the details, and this is where Vittorio’s solution made it out of the pack. Indeed all submitted solution did the job (there were a series of unit tests to pass). Some of you even submitted solutions that used a lambda in the same idea. But this solution is probably the most reusable because it deals with all the details.

First, let’s look at value categories. The lambda accept forwarding references:

auto&&... xs

and forwards them to f:

f(::std::forward<decltype(xs)>(xs)...)

This keeps the l- or r- value reference nature of the arguments. All about this topic in Item 24 of Effective Modern C++. A practical implication of this is that if the lambda had auto parameters instead of auto&&, then it would make a copy of its argument each time it is called.

Second, this solution maintains the noexcept quality of each overload of f, be it true or false:

noexcept(noexcept(__VA_ARGS__))

This way, the wrapper around f doesn’t add a specific behaviour. It behaves very much like it was just f we called, except that it takes care of the overloading resolution. Which was exactly the purpose of the challenge.

Finally, using decltype(__VA_ARGS__) instead of just decltype(auto) helps compile-time evaluations like std::is_invocable figure out the type of what the function could be returning, depending on its arguments. Indeed such contexts don’t instantiate the body of the template function to determine what decltype(auto) resolves to. This is useful in SFINAE contexts for example.

For more examples on those technical aspects, you can watch Vittorio’s 5 minutes lightning talk at CppNow that describes this technique.

Your solution, collectively

Even if Vittorio won the challenge, that doesn’t mean the other solutions weren’t good. Quite the contrary, in fact.

For this reason I want to show you the solutions of some other contestants too, specifically Filipe Verri and Paul Dreik.

Filipe went on a similar idea as Vittorio’s:

#define resolve(f) [] (auto&&... args) -> decltype(auto) { \
    return f(std::forward<decltype(args)>(args)...); \
}

What I want you to focus on here is the name of this function: resolve. This name shows what the function is doing (resolving an overload) rather than how it does it (creating a function object). And showing the what rather than the how makes for a clearer call site. You may want to consider a more specific name like resolve_overload for instance, since macro don’t have scopes nor namespaces.

All the above solutions use macros, and you may prefer not to. For this reason Paul Dreik went to the point by creating a very simple lambda. It’s not as generic as the the previous solution, but it does all that is necessary for simple cases:

// this is the only line I added
const auto call_f=[](auto x) { return f(x); };

and for all the call sites of the challenge:

std::for_each(begin(as), end(as), call_f); // <-- f replaced with call_f

So in a particular case you just don’t care about copies (in collections of primitive types for example), values category and the underlying function isn’t noexcept and won’t be, then this alternative does the same as the generic macro but… without a macro.

And if you care about not making copies you can just use auto&& instead of auto. And we can also get rid of the return keyword here.

So, here is a solution that mixes all this.

In the general case you can use:

#define RETURNS(...) noexcept(noexcept(__VA_ARGS__)) -> decltype(__VA_ARGS__){ return __VA_ARGS__; }

#define resolve_overload(f) [](auto&&... xs) RETURNS(f(::std::forward<decltype(xs)>(xs)...))


std::for_each(begin(as), end(as), resolve_overload(f));

And if you refuse to use macros and your case doesn’t involve precise value categories and noexcept specifications:

std::for_each(begin(as), end(as), [](auto&& x){f(x);});

Thanks to all that tried the challenge! It’s thrilling to see that, together, we can improve our usage of C++, and make our code ever more expressive.

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