Tag dispatch versus concept overloading

In Bjarne Stroustrup’s paper P0557R1 “Concepts: The Future of Generic Programming” (January 2017), section 6 is titled “Concept Overloading,” which Stroustrup distinguishes from the traditional approach “using helper functions and tag dispatch.” More subtly, Stroustrup seems to distinguish between true “overloading” (asking the compiler to resolve among multiple viable overloads) and other means of giving-two-things-the-same-name:

Where we cannot overload, we need to use workarounds (e.g., traits,

`enable_if`

, or helper functions).

I’ll present two problems, each with two solutions (one in C++11 and one in C++20), which I think illustrate something interesting about “concept overloading” versus… other things.

## 1. Absolute value for signed and unsigned

Let’s write a function template that returns the absolute value
of its integral input. If the type of the input is signed, we
compute `(x < 0) ? -x : x`

. If it’s unsigned, we simply return `x`

.

### Tag-dispatch solution

```
// A
template<class T>
T abs_impl(T x, std::false_type) {
return (x < 0) ? -x : x;
}
template<class T>
T abs_impl(T x, std::true_type) {
return x;
}
template<class T>
T abs_value(T x) {
return abs_impl(x, std::is_unsigned<T>{});
}
int main() {
assert(abs_value(-42) == 42);
assert(abs_value(42u) == 42u);
}
```

### C++20 Concepts solution

```
// B
template<std::signed_integral T>
T abs_value(T x) {
return (x < 0) ? -x : x;
}
template<std::unsigned_integral T>
T abs_value(T x) {
return x;
}
int main() {
assert(abs_value(-42) == 42);
assert(abs_value(42u) == 42u);
}
```

Notice that no type can satisfy both
`signed_integral`

and
`unsigned_integral`

at the same time, so this Concepts-based solution is equivalent to the C++14 `enable_if`

approach denigrated by Stroustrup as a “workaround”:

```
// C
template<class T, std::enable_if_t<std::is_signed<T>::value, int> = 0>
T abs_value(T x) {
return (x < 0) ? -x : x;
}
template<class T, std::enable_if_t<std::is_unsigned<T>::value, int> = 0>
T abs_value(T x) {
return x;
}
int main() {
assert(abs_value(-42) == 42);
assert(abs_value(42u) == 42u);
}
```

In this kind of overload set, all the constraints are mutually exclusive, such that no more than one viable candidate is ever present. Overload resolution never has to choose the “best” overload from among a candidate set. As I understand it, this is not what we mean by “concept overloading.”

## 2. Advance for forward and random-access iterators

Let’s write a function template that returns its iterator argument
advanced by two positions.
For the general case of a forward iterator, we compute `++it`

twice.
But if the input is additionally a random-access iterator, we can simply return `it + 2`

.

### Tag-dispatch solution

```
// D
template<class It>
It plus2_impl(It it, std::forward_iterator_tag) {
++it; ++it;
return it;
}
template<class It>
It plus2_impl(It it, std::random_access_iterator_tag) {
return it + 2;
}
template<class It>
It plus2(It it) {
using Tag = typename std::iterator_traits<It>::iterator_category;
return plus2_impl(it, Tag{});
}
```

The term “tag dispatch” is used to refer both to snippet `D`

and to snippet `A`

above. But notice the difference (not reflected
in our terminology): In `A`

, our `abs_impl`

helpers were designed so
that only one of them would be viable. In `D`

, our `plus2_impl`

helpers
are designed so that the first overload is always viable, and then
the second overload is sometimes *also* viable; when it is, it’s the
better match (over.ics.rank/4.4.4).

### C++20 Concepts solution (concept overloading)

```
// E
template<std::forward_iterator It>
It plus2(It it) {
++it; ++it;
return it;
}
template<std::random_access_iterator It>
It plus2(It it) {
return it + 2;
}
```

In this overload set, the constraints are not mutually exclusive.
Like `D`

, snippet `E`

relies on overload resolution to choose the
“best” overload from among a candidate set. Rather than rely on
the best-match rules regarding inheritance, `E`

relies on the fact
that the second overload’s constraint *subsumes* the first overload’s
constraint, and thus
(over.match.best.general/2.6)
the second overload is the best match whenever it is viable at all.

My understanding is that *this* is what Stroustrup refers to as
“concept overloading.”

## Final thoughts

UPDATE, 2021-06-08: I’ve changed my snippets

`F`

,`G`

, and`H`

to relax the`signed_integral`

constraint into`integral`

; originally, I’d relaxed the`unsigned_integral`

constraint. Reddit commenter “Quincunx271” rightly pointed out that that way was strictly worse. Our new version of`F`

has one generic overload that works correctly for all integral types, plus a faster overload for unsigned types. (This is the same overall pattern as`D`

and`E`

.) My original post’s`F`

had a generic overload that worked correctly for unsigned types butincorrectlyfor signed types, and then an overload “rescuing” the correct behavior for signed types. That was unnecessarily silly of me.Reddit commenter “sphere991” observes that in real life we could use

`if constexpr`

. I absolutely agree; I prefer`if constexpr`

over any multi-function approach. But this post wasn’t about`if constexpr`

; it was about “concept overloading.” :)

It seems to be the current wisdom that if you’re writing an
overload set with C++20 Concepts, you needn’t go out of your way
to make your constraints mutually exclusive. I claim that all of my
examples are reasonable C++20; but I do have the impression that some
commentators would go so far as to remove the constraint from one
or the other of the overloads in snippet `B`

, or relax it until
it was no longer mutually exclusive. Thus:

```
// F
template<std::integral T> // note: NOT signed_integral
T abs_value(T x) {
return (x < 0) ? -x : x;
}
template<std::unsigned_integral T>
T abs_value(T x) {
return x;
}
```

The tag-dispatch equivalent would be to replace `false_type`

with an ellipsis:

```
// G
template<class T>
T abs_impl(T x, ...) {
return (x < 0) ? -x : x;
}
template<class T>
T abs_impl(T x, std::true_type) {
return x;
}
template<class T>
T abs_value(T x) {
return abs_impl(x, std::is_unsigned<T>{});
}
```

or use a template of two parameters:

```
// H
template<class T, class U>
T abs_impl(T x, U) {
return (x < 0) ? -x : x;
}
```

Personally, I would vastly prefer to read snippet `A`

than
to read either `G`

or `H`

.

I have used

`H`

in situations dispatching on multiple bools at a time — where we want to do one thing if`b1`

and`b2`

are both true, a different thing if`b1`

is true and`b2`

is false, and a third thing if`b1`

is false regardless of`b2`

.)

For me *personally, so far,* my attitude carries over into C++20 Concepts:
I find snippet `B`

strictly more understandable at a glance than
snippet `F`

, because you can understand each candidate’s purpose
in isolation, without even knowing that the other candidate exists.
However, in cases where the overloads express a *natural* hierarchy
(by which I mean “a hierarchy that the educated reader ought to know
to be on the lookout for”), concept overloading could be the simplest
approach. For example, I find snippet `E`

reasonably understandable.
I would not be tempted to rewrite it merely to introduce
mutually exclusive constraints:

```
// J
template<std::forward_iterator It>
requires (!std::random_access_iterator<It>)
It plus2(It it) {
++it; ++it;
return it;
}
template<std::forward_iterator It>
requires std::random_access_iterator<It>
It plus2(It it) {
return it + 2;
}
```

Although honestly, if I saw that a coworker had already written snippet `J`

,
I would not be tempted to change it back to snippet `E`

!

Concept overloading allows you to increase the number of viable candidates
in your overload sets, without introducing artificial inheritance hierarchies
of tag types á là `std::forward_iterator_tag`

or
`priority_tag`

.
But ultimately it is just another tool in the C++ toolbox; you can be
*allowed* to use it, without feeling *obliged* to use it.