What is the partial ordering procedure in template deduction

Question

Reading the C++11 standard I can't fully understand the meaning of the following statement. Example are very welcome.

Two sets of types are used to determine the partial ordering. For each of the templates involved there is the original function type and the transformed function type. [Note: The creation of the transformed type is described in 14.5.6.2. — end note ] The deduction process uses the transformed type as the argument template and the original type of the other template as the parameter template. This process is done twice for each type involved in the partial ordering comparison: once using the transformed template-1 as the argument template and template-2 as the parameter template and again using the transformed template-2 as the argument template and template-1 as the parameter template
-- N3242 14.8.2.4.2

Perri

Did you already watch Stephan T. Lavavej's lectures on Core C++? In particular, lectures 2 and 3 on argument deduction and overload resolution might be helpful. – Anthelmintic

Partial ordering basically checks in the parameters of two templates, if the parameter of one is more restrictive than the corresponding parameter of the other. If you have f(T) and f(bar<T>) (with T as a template parameter), then the first overload can take all possible arguments of the second overload, but the second overload can't take all possible arguments from the first overload - only those of the bar<T> form. – Liverwurst

Answer 1

While Xeo gave a pretty good description in the comments, I will try to give a step-by-step explanation with a working example.

First of all, the first sentence from the paragraph you quoted says:

For each of the templates involved there is the original function type and the transformed function type. [...]

Hold on, what is this "transformed function type"? Paragraph 14.5.6.2/3 explains that:

To produce the transformed template, for each type, non-type, or template template parameter (including template parameter packs (14.5.3) thereof) synthesize a unique type, value, or class template respectively and substitute it for each occurrence of that parameter in the function type of the template [...]

This formal description may sound obscure, but it is actually very simple in practice. Let's take this function template as an example:

template<typename T, typename U>
void foo(T, U) // #1

Now since T and U are type parameters, the above paragraph is asking us to pick a corresponding type argument for T (whatever) and substitute it everywhere in the function signature where T appears, then to do the same for U.

Now "synthesizing a unique type" means that you have to pick a fictitious type you haven't used anywhere else, and we could call that P1 (and then pick a P2 for U), but that would make our discussion uselessly formal.

Let's just simplify things and pick int for T and bool for U - we're not using those types anywhere else, so for our purposes, they are just as good as P1 and P2.

So after the transformation, we have:

void foo(int, bool) // #1b

This is the transformed function type for our original foo() function template.

So let's continue interpreting the paragraph you quoted. The second sentence says:

The deduction process uses the transformed type as the argument template and the original type of the other template as the parameter template. [...]

Wait, what "other template"? We only have one overload of foo() so far. Right, but for the purpose of establishing an ordering between function templates, we need at least two of them, so we'd better create a second one. Let's use:

template<typename T>
void foo(T const*, X<T>) // #2

Where X is some class template of ours.

Now what with this second function template? Ah, yes, we need to do the same we previously did for the first overload of foo() and transform it: so again, let's pick some type argument for T and replace T everywhere. I'll pick char this time (we aren't using it anywhere else in this example, so that's as good as some fictitious P3):

void foo(char const*, X<char>) #2b

Great, now he have two function templates and the corresponding transformed function types. So how to determine whether #1 is more specialized than #2 or vice versa?

What we know from the above sentence is that the original templates and their transformed function types must be matched somehow. But how? That's what the third sentence explains:

This process is done twice for each type involved in the partial ordering comparison: once using the transformed template-1 as the argument template and template-2 as the parameter template and again using the transformed template-2 as the argument template and template-1 as the parameter template

So basically the transformed function type of the first template (#1b) is to be matched against the function type of the original second template (#2). And of course the other way round, the transformed function type of the second second template (#2b) is to be matched against the function type of the original first template (#1).

If matching will succeed in one direction but not in the other, then we will know that one of the templates is more specialized than the other. Otherwise, neither is more specialized.

Let's start. First of all, we will have to match:

void foo(int, bool) // #1b

Against:

template<typename T>
void foo(T const*, X<T>) // #2

Is there a way we can perform type deduction on T so that T const* becomes exactly int and X<T> becomes exactly bool? (actually, an exact match is not necessary, but there are really few exceptions to this rule and they are not relevant for the purpose of illustrating the partial ordering mechanism, so we'll ignore them).

Hardly. So let's try matching the other way round. We should match:

void foo(char const*, X<char>) // #2b

Against:

template<typename T, typename U>
void foo(T, U) // #1

Can we deduce T and U here to produce an exact match for char const* and X<char>, respectively? Sure! It's trivial. We just pick T = char const* and U = X<char>.

So we found out that the transformed function type of our first overload of foo() (#1b) cannot be matched against the original function template of our second overload of foo() (#2); on the other hand, the transformed function type of the second overload (#2b) can be matched against the original function template of the first overload (#1).

Conclusion? The second overload of foo() is more specialized than the first one.

To pick a counter-example, consider these two function templates:

template<typename T, typename U>
void bar(X<T>, U)

template<typename T, typename U>
void bar(U, T const*)

Which overload is more specialized than the other? I won't go through the whole procedure again, but you can do it, and that should convince you that a match cannot be produced in either direction, since the first overload is more specialized than the second one for what concerns the first parameter, but the second one is more specialized than the first one for what concerns the second parameter.

Conclusion? Neither function template is more specialized than the other.

Now in this explanation I have ignored a lot of details, exceptions to the rules, and cryptic passages in the Standard, but the mechanism outlined in the paragraph you quoted is indeed this one.

Also notice, that the same mechanism outlined above is used to establish a "more-specialized-than" ordering between partial specializations of a class template by first creating an associated, fictitious function template for each specialization, and then ordering those function templates through the algorithm described in this answer.

This is specified by paragraph 14.5.5.2/1 of the C++11 Standard:

For two class template partial specializations, the first is at least as specialized as the second if, given the following rewrite to two function templates, the first function template is at least as specialized as the second according to the ordering rules for function templates (14.5.6.2):

— the first function template has the same template parameters as the first partial specialization and has a single function parameter whose type is a class template specialization with the template arguments of the first partial specialization, and

— the second function template has the same template parameters as the second partial specialization and has a single function parameter whose type is a class template specialization with the template arguments of the second partial specialization.

Hope this helped.

Kaseykasha

+1 but this whole argument deduction game comes after name lookup and only applies to function overloads / class specializations, i.e. they all have the same name? so foo(T, U) and foo(T, X<T>) would be played against each other, correct? – Anthelmintic

@TemplateRex: Ouch, you are right. I will edit the answer to make this clear. Thank you for mentioning :) – Kaseykasha

I'd also mention that argument matching for specializations of a class template are resolved by constructing a set of unique overloads of a function template and then proceeding to apply the "mutual substitution game". I.e. class specialization pattern matching is identical to argument deduction for function templates. – Anthelmintic

This is a great answer, BTW, too bad the stuff is just too complicated for most C++ programmers to generate more traffic, compared to e.g. vector::resize() questions :-) – Anthelmintic

@TemplateRex: :) Yes, that is a common pattern on SO. But it is also a matter of timing. The question on resize() was answered within minutes, while this one had to wait for 7 hours. Perhaps that also explains why there is not a lot of traffic around this one anymore. – Kaseykasha