Overload Resolution and SFINAE

The previous lesson showed how to look at a type and select a branch: the decision was made inside an if constexpr. One step earlier there is another question. When several functions share a name, which one does the compiler call, and what happens to a template that does not fit in the candidate list? This lesson measures how a call is chosen and how a template is eliminated without an error when it meets the wrong type. The selection ends at compile time, and the cost is again in the compile kind.

Candidate, Viable Candidate, Best Candidate

For a function call, the compiler goes through three stages. First it collects every function and function template visible under the called name as a candidate. Then it moves the ones whose argument count and conversions fit into the list of viable candidates. Finally, the one that best fits the arguments among the viable candidates is chosen as the best candidate. If two candidates remain equally good and no tie-breaking rule favors one of them, the call is ambiguous and compilation stops.

If a template and a non-template function compete on equal terms, the non-template function wins. But if the template matches the argument type exactly while the non-template function needs a conversion, the template wins, because an exact match is better than a conversion.

// overload.cpp — template and non-template candidates
#include <cstdio>
#include <string>

const char* pick(int) { return "int"; }
const char* pick(double) { return "double"; }

template <typename T>
const char* pick(T) { return "template"; }

int main() {
    std::printf("pick(1)      %s\n", pick(1));
    std::printf("pick(1.5)    %s\n", pick(1.5));
    std::printf("pick('a')    %s\n", pick('a'));
    std::printf("pick(2.5f)   %s\n", pick(2.5f));
    std::printf("pick(string) %s\n", pick(std::string("x")));
    return 0;
}

pick(1)      int
pick(1.5)    double
pick('a')    template
pick(2.5f)   template
pick(string) template

For pick(1) and pick(1.5), the non-template function is an exact match and wins the tie. 'a' is a char; the int candidate needs an integral promotion, while the template matches exactly with T = char, so the template wins. The same holds for float. For string, only the template is a viable candidate.

SFINAE: Substitution Failure Is Not an Error

After the template argument is deduced, the compiler puts the deduced type into the template’s declaration. If this substitution produces an invalid type or expression, that template silently drops out of the candidate list and compilation raises no error. The principle is known as SFINAE: substitution failure is not an error. An error is raised only if no candidate remains.

The classic way to use SFINAE on purpose is std::enable_if_t<condition, type>: if the condition is true it is equal to type, and if it is false the substitution fails and the template is eliminated. It is usually placed in the type of a non-type template parameter, and that parameter is given a default value such as = 0.

// enable-if.cpp — candidate elimination with enable_if_t
#include <cstdio>
#include <type_traits>

template <typename T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
const char* category(T) { return "integer"; }

template <typename T, std::enable_if_t<std::is_floating_point_v<T>, int> = 0>
const char* category(T) { return "floating"; }

int main() {
    std::printf("category(7)   %s\n", category(7));
    std::printf("category(2.5) %s\n", category(2.5));
    return 0;
}

category(7)   integer
category(2.5) floating

MT26. For category(7), the declaration of the second template becomes enable_if_t<false, int>, the substitution fails, and the second candidate is eliminated; integer remains. For category(2.5) it is the reverse. The signatures of the two templates look the same, but the types of their template parameters depend on different conditions, so the signatures differ and there is no clash. The selection is made at compile time and leaves no query at run time.

Conversion Ranking

What “best” means among viable candidates depends on the conversion that binds the argument to each candidate. Conversions rank from best to worst as follows: exact match, integral or floating-point promotion, standard conversion, user-defined conversion, and last the ellipsis parameter. A candidate is best if it is not worse than the others on any argument and is better on at least one. If two candidates cannot beat each other, the call is ambiguous and compilation stops; I describe this error in prose, because code that does not compile is not written as a block.

// ranking.cpp — conversion ranking
#include <cstdio>

const char* h(int) { return "int"; }
const char* h(long) { return "long"; }
const char* h(double) { return "double"; }

const char* g(long) { return "long"; }
const char* g(...) { return "ellipsis"; }

int main() {
    short s = 1;
    std::printf("h('a')  %s\n", h('a'));
    std::printf("h(s)    %s\n", h(s));
    std::printf("h(1.5f) %s\n", h(1.5f));
    std::printf("h(2L)   %s\n", h(2L));
    std::printf("g(1)    %s\n", g(1));
    std::printf("g(1.5)  %s\n", g(1.5));
    return 0;
}

h('a')  int
h(s)    int
h(1.5f) double
h(2L)   long
g(1)    long
g(1.5)  long

MT27. The char and short arguments bind to int by promotion, and a promotion is better than a standard conversion to long; so both choose the int candidate. float binds to double by promotion. For 2L, long is an exact match. For g(1), a standard conversion to long competes with the ellipsis: the conversion wins. For g(1.5) there is also a standard conversion from double to long, and it is better than the ellipsis. The standard determines this ranking; the output only confirms it.

Ordering Candidates with a Priority Tag

If more than one of the candidates eliminated with enable_if is viable at the same time, the call becomes ambiguous. An old method for establishing priority is to build a derivation chain of tag types. priority<2> derives from priority<1>, and that from priority<0>. Each candidate takes a different tag as its last parameter, and the call is made with the highest tag: the exact match is the highest tag, the eliminated ones drop out of the list, and among the rest the one with the shortest derivation distance is chosen.

// priority.cpp — candidate order by tag
#include <cstdio>
#include <string>
#include <type_traits>
#include <utility>

template <int N>
struct priority : priority<N - 1> {};
template <>
struct priority<0> {};

template <typename T>
auto classify(const T& x, priority<2>) -> decltype(x.size(), "sized") {
    return "sized";
}

template <typename T, std::enable_if_t<std::is_pointer_v<T>, int> = 0>
const char* classify(const T&, priority<1>) { return "pointer"; }

template <typename T>
const char* classify(const T&, priority<0>) { return "generic"; }

template <typename T>
const char* classify(const T& x) { return classify(x, priority<2>{}); }

int main() {
    int n = 3;
    std::printf("string  %s\n", classify(std::string("ab")));
    std::printf("pointer %s\n", classify(&n));
    std::printf("int     %s\n", classify(n));
    return 0;
}

string  sized
pointer pointer
int     generic

MT28. For std::string, two candidates are viable, because the pointer candidate is eliminated by enable_if; priority<2> is the highest tag and needs no derivation step, so sized wins. For int*, the size() query fails in the declaration, the first candidate is eliminated, and the priority<1> candidate is chosen. For int, both are eliminated and generic remains. C++17 if constexpr and C++20 concepts replace this chain; but the tag method is still common in old code, so it has to be readable.

Detection with void_t

enable_if writes a condition out explicitly. Sometimes the question is whether an expression is valid for a type. std::void_t<...> ties this question to SFINAE: whatever its arguments are, it becomes void, but if one of the arguments is invalid, the substitution fails. The primary template derives from false_type; the partial specialization tries the expression inside void_t.

// divisible.cpp — detection with void_t
#include <cstdio>
#include <string>
#include <type_traits>
#include <utility>

template <typename T, typename = void>
struct divisible : std::false_type {};

template <typename T>
struct divisible<T, std::void_t<decltype(std::declval<T>() / 2)>> : std::true_type {};

int main() {
    std::printf("divisible<int>         %s\n", divisible<int>::value ? "yes" : "no");
    std::printf("divisible<double>      %s\n", divisible<double>::value ? "yes" : "no");
    std::printf("divisible<std::string> %s\n", divisible<std::string>::value ? "yes" : "no");
    return 0;
}

divisible<int>         yes
divisible<double>      yes
divisible<std::string> no

The expression std::declval<T>() / 2 is valid for int and invalid for std::string. If it is invalid, the partial specialization is eliminated and the primary template remains. This is the answer to the question asked at the start of the lesson: a candidate that does not fit raises no error; it drops out of the candidate list.

C++20: Concepts and requires

enable_if and void_t do the job but are hard to read. C++20 brought concepts and the requires expression to write the same constraint directly. If a constraint is not satisfied, the template is not a candidate, and in the error message compilers usually show the unsatisfied constraint instead of a long substitution dump.

// concept.cpp — constraint with requires
#include <cstdio>
#include <string>

template <typename T>
concept Divisible = requires(T x) { x / 2; };

template <Divisible T>
const char* half(T) { return "divisible"; }

const char* half(...) { return "indivisible"; }

int main() {
    std::printf("half(8)   %s\n", half(8));
    std::printf("half(str) %s\n", half(std::string("x")));
    return 0;
}

half(8)   divisible
half(str) indivisible

The constrained template is a viable candidate for int, and it wins because the ellipsis candidate is less good. For std::string, the constraint is not satisfied, the template is eliminated, and the ellipsis candidate remains. A concept names a query; the selection still ends at compile time.

The Body of an Eliminated Candidate Is Not Written

A count shows where the cost of SFINAE lies. If a candidate is eliminated, its body is never instantiated. Below, the bodies of two candidates are recorded with a local static; a body that is not called leaves no record.

// body-count.cpp — body of an eliminated candidate
#include <cstdio>
#include <type_traits>

inline int integer_bodies = 0;
inline int floating_bodies = 0;

template <typename T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
int twice(T x) {
    static const bool record = (++integer_bodies, true);
    (void)record;
    return static_cast<int>(x) * 2;
}

template <typename T, std::enable_if_t<std::is_floating_point_v<T>, int> = 0>
int twice(T x) {
    static const bool record = (++floating_bodies, true);
    (void)record;
    return static_cast<int>(x * 2);
}

int main() {
    twice(7);
    twice(8);
    twice(9L);
    std::printf("integer=%d floating=%d\n", integer_bodies, floating_bodies);
    twice(2.5);
    std::printf("integer=%d floating=%d\n", integer_bodies, floating_bodies);
    return 0;
}

integer=2 floating=0
integer=2 floating=1

MT29. After three integer calls, only integer bodies exist: one for int and one for long, so two bodies; the floating body count is zero. Then a double call makes the floating body count one. The eliminated candidate has dropped out of the list and its body was never written; for this reason the cost of SFINAE is only the elimination itself. The numbers are a product count, not a duration.

Ordering with Concepts: Subsumption

C++20 resolution with concepts chooses the more constrained one if two constrained versions of the same candidate are viable. If one concept includes another (std::signed_integral subsumes std::integral), the subsuming concept is more specialized. This rule replaces the tag chain: the order comes from the structure of the concepts themselves.

// constraint-order.cpp — concept subsumption
#include <concepts>
#include <cstdio>

template <typename T>
const char* grade(T) { return "general"; }

template <std::integral T>
const char* grade(T) { return "integer"; }

template <std::signed_integral T>
const char* grade(T) { return "signed"; }

int main() {
    std::printf("grade(1)   %s\n", grade(1));
    std::printf("grade(1u)  %s\n", grade(1u));
    std::printf("grade(1.5) %s\n", grade(1.5));
    return 0;
}

grade(1)   signed
grade(1u)  integer
grade(1.5) general

MT30. int is both integral and signed_integral; the more constrained one, signed, is chosen. unsigned is only integral, so integer remains. double satisfies neither, so general remains. This selection is again made at compile time and leaves no query at the call site. The cost is in the compile kind; only the collecting of candidates and the checking of constraints are added to the compiler’s work.

The Bounding Measurement

SFINAE covers only substitution errors in the immediate context of the declaration: errors that arise directly while the return type, the parameter types, and the template parameters are written. If another template has to be instantiated in the meantime and the error arises inside it, there is no elimination and compilation stops. The body of a function is instantiated after the candidate is chosen. An error in the body no longer eliminates from the candidate list; it stops compilation. For example, if a template that writes the call x.size() in its body is called with int, the compiler counts that template as a viable candidate, chooses it, raises an error while instantiating the body, and compilation stops.

When the same call is moved into the declaration, it turns into elimination. The version below makes the size() query in the return type.

// declaration.cpp — query in the declaration, body without error
#include <cstdio>
#include <string>

template <typename T>
auto size_of(const T& x) -> decltype(x.size(), long()) {
    return static_cast<long>(x.size());
}

long size_of(...) { return -1; }

int main() {
    std::printf("string %ld\n", size_of(std::string("abcd")));
    std::printf("int    %ld\n", size_of(7));
    return 0;
}

string 4
int    -1

MT31. For std::string, the return type is valid and the template is chosen. For int, x.size() is invalid, the substitution fails, and the ellipsis candidate remains. Had the same query been in the body, compilation would have stopped. For this reason the number is the evidence of the elimination event; the answer to the measurement question is the stage at which this elimination takes place: compile.

Summary

• The mechanism measured in this lesson moves the cost to the compile kind: collecting candidates, eliminating the viable ones, and choosing the best candidate end at compile time, and no query is left at run time.
• Candidate, viable candidate, and best candidate are collected, eliminated, and chosen in that order; on a tie the non-template function wins, and an exact match beats a conversion.
• In SFINAE, substitution failure is not an error: with enable_if_t, category(7) selects integer and category(2.5) selects floating.
• void_t detects the validity of an expression: divisible<int> yes, divisible<std::string> no.
• C++20 concept and requires write the same constraint readably; SFINAE covers only the declaration, and an error in the body stops compilation.

Next Step

In this lesson candidate elimination ended at compile time and left no query at run time. The next lesson applies this idea to a class hierarchy: if a template is used instead of a virtual function, dispatch moves to compile time, but a separate body is written for every type. What is the measure of this trade?