Clever overloading

This post is intended to be a light introduction to certain C++ guru tricks. I want to introduce a couple of concepts that typically put normal people off. If you are an expert you will probably not learn anything new, except maybe for how to talk about such things to ordinary programmers. If you are an “ordinary programmer” with a happy family life, note that you really do not have to know these tricks to be a good, successful developer.

We are going to see a rather unusual problem connected to function overloading and explore the techniques of solving it.

The problem

Here is a suggestion from Vladimir Batov for extending library Optional. Both Optional from Library Fundamentals TS as well as Optional in Boost 1.56 have a member function value_or. This enables you an interesting way of accessing the potentially absent contained value: “either give me the value or give me the default”:

optional<int> convert(std::string s);

int i = convert(t).value_or(0);
// if conversion fails: i = 0; 

Function value_or() is declared more less like this:

template <typename T>
class optional
{
  // ...

  template <typename U>
  T value_or(U const& v) const
  {
    if (*this)              // initialized?
      return this->value(); // get contained value
    else
      return v;             // get v converted to T
  }
};

So, value_or() takes any argument of any type U implicitly convertible to T, not necessarily a T. It performs the conversion only when it is required, so that in the following code:

optional<std::string> get_text();
std::string s = get_text().value_or("n/a");

No std::string will be constructed from "n/a" when the returned optional contains a value.

It works pretty good. Now, here is an idea for a clever extension. Extend function value_or() so that it accepts any U that is either convertible to T or is callable (a functor or a function) with no arguments and a return type convertible to T:

int log_and_continue()
{
  clog << "conversion failed; using -1 instead" << endl;
  return -1;
}

int i = convert(t).value_or(&log_and_continue);
// if conversion fails: i = -1 and log; 

Can this be implemented? Consider the naïve case:

// WILL NOT WORK

template <typename U>
T value_or(U const& v) const
{
  if (*this)
    return this->value();
  else if (std::is_convertible<U, T>::value)
    return v;
  else
    return v();
}

This expression, std::is_convertible<U, T>::value is called a type trait, it is a sort of (meta)function that returns a compile-time boolean constant saying if U is convertible to T. It may not be obvious that this is a ‘function’ at first, given these angle brackets and colons, but it might be easier to think of it as a function if we wrapped it into a macro:

#define IS_CONVERTIBLE(U, T) std::is_convertible<U, T>::value

int main()
{
  assert (IS_CONVERTIBLE(int, double));
  assert (!IS_CONVERTIBLE(int, std::string));
}

Nonetheless, function value_or as defined above doesn’t work. In order for this function (any function instantiated from this template) to compile both instructions return v; and return v(); need to be valid; even if it can be proven at compile-time that the condition is always true (or false). This is how compilation rules in C++ work. The above code could be made to work in C++17 with constexpr if, but since C++17 is not official at the point of writing this post, we will only leave it as a bonus material at an end.

We could solve the problem by splitting this function into two overloads:

// WILL NOT WORK

template <typename U>
T value_or(U const& v) const
{
  if (*this)
    return this->value();
  else
    return v;
}

template <typename F>
T value_or(F const& f) const
{
  if (*this)
    return this->value();
  else
    return f();
}

Now each function contains only one required expression. It looks like it might work, but when we make a call like this:

int i = convert(t).value_or(def);

How is the compiler supposed to know which of the two overloads to pick? Compiler is good at picking the best function out of a number of competing overloads but here neither can be considered best. The two overloads match equally well: just some object passed by reference. This ambiguity results in a compiler error. So, is there a way to instruct the compiler which overload it should prefer and when?

Ideal solution: Concepts Lite

There is no direct way of doing it cleanly as of today. This is the problem that Concepts Lite aim at fixing. With Concepts Lite, this problem is solved like this:

// Concepts Lite, not C++ yet

template <typename U>
T value_or(U const& v) const
  requires is_convertible<U, T>::value
{
  if (*this)
    return this->value();
  else
    return v;
}

template <typename F>
T value_or(F const& f) const
{
  if (*this)
    return this->value();
  else
    return f();
}

This requires is a keyword and means “prefer this overload if is_convertible<U, T>::value is true.” If is_convertible<U, T>::value is false the first overload is not even considered, so the compiler can pick the second one. Concepts Lite are about far more than just solving our overload resolution problem, but this is another story, not in the scope of our post.

Working solution: tag dispatching

But we can solve our problem with some clever tricks. There are at least two ways of doing it. Here is one. We will add a second special function parameter to each function. This will be a “tag” that will make the functions look different. We will also change the name of the function slightly. You will see why in a second:

#include <type_traits>

template <typename U>
T value_or_(U const& v, std::true_type) const
{
  if (*this)
    return this->value();
  else
    return v;
}

template <typename F>
T value_or_(F const& f, std::false_type) const
{
  if (*this)
    return this->value();
  else
    return f();
}

These std::true_type and std::false_type are ‘tags’ defined in the Standard Library. A tag is an empty class. It contains no member and has no state: its purpose is to control (or “mess with”, if you will) the overload selection algorithm. You can use our functions like this:

int i = convert(t).value_or_(def, true_type{});

Are you familiar with brace-initialization syntax? While true_type is a type, true_type{} is an object. But this solution is silly. It is no better than having two different function names instead of two overloads. True; so let’s make it better:

template <typename U>
T value_or(U const& v) const
{
  return value_or_(v, std::is_convertible<U, T>{});
}

And that’s it. Let’s see what is going on here. You already know type trait std::is_convertible, but this time we are using it without referring to its static member value. This is how type traits work in the Standard Library. If the condition they represent for the given types (U being convertible to T in our case) holds, the trait is derived from true_type; if not, it is derived from false_type. This makes true_type and false_type represent boolean values — however, the values are not encoded as different bit patterns stored in memory, but as different types.

Thus, based on the value of std::is_convertible<U, T>{}, we dispatch the call to either of the two overloads. Everything works fine now:

int i = convert(t).value_or(def);
// picks the right overload

You can see the full working example here.

Working solution: enable_if

Tag dispatching is not the only clever solution to our problem. Let’s explore another possibility: enable_if. Our overloaded functions return T. We will change the return type a bit. Don’t get scared off. We will explain everything step by step.

#include <type_traits>

template <typename U>
typename std::enable_if<is_convertible<U, T>::value, T>::type
value_or_(U const& v) const
{
  if (*this)
    return this->value();
  else
    return v;
}

template <typename F>
typename std::enable_if<!is_convertible<F, T>::value, T>::type
value_or_(F const& f) const
{
  if (*this)
    return this->value();
  else
    return f();
}

Let’s focus on the first overload for now. Its return type is of the form:

typename std::enable_if<_ARGUMENTS_>::type

This is how in C++03 type meta-functions work. You pass some arguments into the class template, and get a type in return. Do you know why we need to type this typename? If you do not, just believe me that you have to type it. This is how templates work in C++: in certain cases you need to hint the compiler that type is a type rather than a static data member.

So, what are the two arguments that meta-function enable_if takes? The first one is a compile-time constant of type bool. Just some compile-time value. It represents a condition. The second argument is a type (rather than value). If the condition is true, the nested type type is same as this second template parameter. If the condition is false the nested type type is not defined. For example, the following construct:

typename std::enable_if<true, T>::type

really means “type T”. But the following one:

typename std::enable_if<false, T>::type

is just ill-formed: we are trying to access a type that doesn’t exist. But what is it good for? Let’s get back to our function signature:

template <typename U>
typename std::enable_if<is_convertible<U, T>::value, T>::type
value_or_(U const& v) const;

When the overload resolution mechanism tries to consider this function if it is a good match: when U is convertible to T, this signature is really equivalent to:

template <typename U>
T
value_or_(U const& v) const;

But when U is not convertible to T, the declaration is simply malformed. However, this is a special case of malformed-ness that happens during overload resolution for which special rules in the language apply. The gurus call it SFINAE. In our case it means that the compiler will pretend this overload just isn’t there and try to look for other ones. It will find the other overload, and because the other overload uses the opposite condition (note the usage of operator!), the compiler will have a good unambiguous match. Thus based on the result of the meta-function is_convertible compiler will always see only one overload: either the first or the second, and will never have an ambiguity. For a full example see here.

There is also another way to solve our problem with enable_if without having to spoil the return type. But while the two solutions described so far will work back in C++03 if you use Boost.TypeTraits and Boost.EnableIf instead of C++11 header <type_traits>, the third way will only work in C++11. You can see the example here. Even more, in C++11 we can do it without a single enable_if in our class, as suggested by Paweł Turkowski: see here. There is no room to discuss it in detail in this post.

Is this a valid goal?

Ok, so we explored a couple of clever tricks; now let’s get back to our original problem statement. An ‘intelligent’ function value_or that (upon the attempt to access a missing value) first tries to convert the argument to T, and if it doesn’t work it tries to check if the argument can be called as a function and use its result. Is is a good idea to have an intelligent function like this that tries to figure out what your intentions were? After all, you can have two functions that do these two different things:

int i = convert(t).value_or(0);
int j = convert(t).value_or_eval(&log_and_continue);

So far, I have avoided an important problem with how our task is formulated. There exist types U which are both convertible to T and callable with zero arguments — which way should our intelligent function pick then? Also, there are types that are neither callable nor convertible to T. What do we want to do for these? Fail with an error message, I guess, but what message? “U not convertible to T”? “U is not a funcction”? “U is neither convertible to T, nor is it a function”? “no function value_or found for this U”? Depending on what your answer to these two questions is, you might want a different design for your function overloads. If you are using tag dispatching, you will need a four-state tag or two boolean tags. If you are using enable_if, you may need to add more complicated conditions, like:

std::is_convertible<U, T>::value && !is_generator<U, T>::value

I use the name Generator after SGI’s STL Programmer’s Guide. It represents a zero-argument function returning a value of type T. But it is not even defined in the Standard Library. We would have to write it ourselves.

Tag dispatching vs enable_if

Our example above is rather controversial. But it served my goal well: to compare how the two techniques solve the same problem. Typically, however, the two techniques solve different kinds of problems.

Tags need not be true-or-false; they can form a hierarchy (in OO sense); this enables the rules of overloading similar to these when we pick between the derived and base class. STL uses this for overloading (e.g. function std::advance) based on iterator categories. Iterator categories are represented by tags:

struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag: input_iterator_tag{};
struct bidirectional_iterator_tag: forward_iterator_tag{};
struct random_access_iterator_tag: bidirectional_iterator_tag{};

These tags are embedded in the iterator traits. And now, if we implement two overloads for tags input_iterator_tag and random_access_iterator_tag, all iterators in between like BidirectionalIterator will be dispatched to the overload with input_iterator_tag tag. And in the case of STL algorithms, they are overloaded not in order to do different things (like in our task), but to do the very same thing more efficiently. For more details on this see here.

The enable_if technique is good when you want to disable some overload in certain cases and enable nothing instead. For instance, we used it to fix the “too perfect forwarding” problem.

Beware of your dark nature!

If you have read this far, it seams I got you interested in these techniques. Let me warn you then. I only showed you that such techniques exist. I really do not recommend employing them in your code (unless there is some really good reason to do so). I spent quite a while figuring out why one of the enable_if examples in this post didn’t compile. I solved the problem with value_or in Boost.Optional by adding a function with a different name: value_or_eval. Even if you accept the complexity you intend to add, consider your colleagues. You will put a burden of complicated, magical code not only on yourself, but also on everyone that ever has to read or fix your code. Have mercy. The noble goal of programming is to make the programs simple — not complicated.

A C++17 solution

As C++17 is drawing nigh, we can see how it can solve our problem. Here is the code:

template <typename U>
T value_or(U const& v) const
{
  if (*this)
    return this->value();
    
  if constexpr (std::is_convertible<U, T>::value)
    return v;
  else
    return v();
}

The additional constexpr means that the code under condition is only instantiated when the compile-time condition is evaluated to true.

Further reading

1. Jaakko Järvi, Jeremiah Willcock, Andrew Lumsdaine, Matt Calabrese, Boost.EnableIf.
2. John Maddock, Steve Cleary, et al, Boost.TypeTraits.
3. David Abrahams, “Ceneric Programming Techniques”.
4. David Abrahams, Douglas Gregor, “Generic Programming in C++: Techniques”.
5. John Maddock, Steve Cleary, “C++ Type Traits”.
6. Jaakko Järvi, Jeremiah Willcock, Howard Hinnant, Andrew Lumsdaine, “Function Overloading Based on Arbitrary Properties of Types”.
7. Andrew Sutton, Bjarne Stroustrup, Gabriel Dos Reis, “Concepts Lite: Constraining Templates with Predicates”.
8. Bjarne Stroustrup, Gabriel Dos Reis, Andrew Sutton, “«Static If» Considered”
9. Andrew Sutton, Bjarne Stroustrup, Gabriel Dos Reis, “Concepts Lite”.
10. Andrew Sutton, “Working Draft, C++ Extensions for Concepts”.
11. R. Martinho Fernandes, “Remastered enable_if”.
12. R. Martinho Fernandes, “To SFINAE or not to SFINAE”.
13. Xeo, “Beating overload resolution into submission”.
14. Andrzej Krzemieński, “Meta-functions in C++11”.