How does partial ordering of function templates work?

Question

The section [temp.func.order] describes a complicated process by which it is determined whether one function template is more specialized than another. I am having trouble visualizing, and understanding how this process actually works.

Could you explain which sections in the standard apply in this simple example?

template <typename T, int N>
struct array { T data[N]; };

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

template <typename T, int N>
void foo(array<T, N>); // #2

template <typename T>
void foo(array<T, 1>); // #3


// call: foo(array<int, 1>{})

It's intuitively obvious #3 is more specialized than #2, which is more specialized than #1, but how is this really determined in the standard?

Answer 1

The basic idea behind partial ordering is not very complicated. First, let's rename some of the T's:

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

template <typename U, int N>
void foo(array<U, N>); // #2

template <typename V>
void foo(array<V, 1>); // #3

The idea is that every array<U, N> is a T, but not every T is an array<U, N>. That makes #2 more specialized than #1.

And every array<V, 1> is an array<U, N>, but not every array<U, N> is an array<V, 1> (since N might not be 1). That makes #3 more specialized than #2.

In order to check whether every array<U, N> is a T, we replace U with a "unique type" and N with a "unique value". Call these UniqT1 and uniqv1. Then, we get the type array<UniqT1, uniqv1> and we attempt to deduce T from this. That's easy: it's just T = array<UniqT1, uniqv1>. Then we also try the same thing the other way around: is every T an array<U, N>? To determine this, we replace T with UniqT2 and attempt to deduce U and N in array<U, N>. Since the type UniqT2 is "unique", there is no way to make array<U, N> the same type as UniqT2 no matter what U and N are.

Similarly when you replace V in #3 with a unique type, you can deduce U and N in #2, but you can't do it the other way around: replace U and N with a unique type and unique value in #2, and then you can't deduce V in #3, because N, being a unique value, isn't equal to 1. That implies that #3 is more specialized than #2.

Now as for the standard wording:

The "synthesize a unique type/value" rule is [temp.func.order]/3.

Then [temp.func.order]/4 tells you to perform deduction after substituting the unique types/values.

[temp.deduct.partial]/10 tells you how to interpret the result: if deduction only succeeds in one of the two directions, then whichever template's arguments are the ones that could be deduced, that one is the less specialized one.

In the context of a call, I should additionally mention that according to [temp.deduct.partial]/3.1 any parameter types for which no actual argument was provided in the call are ignored.

The details of the rules are of course enormously complicated, so my summary of "every X is a Y but not vice versa" does not come close to explaining the whole thing. The additional rules cover situations like parameters of reference type, comparing non-static member functions with static member functions, and variadic templates.

Answer 2

The basic idea of partial ordering is that one tries deducing the template arguments for template 1 from the parameter types of template 2. If deduction succeeds, template 2 is at least as specialized as template 1.

Deduction trivially succeeds for #1 from anything since its declared parameter type is just T. #2 similarly succeeds from #3 since we can deduce T₂=T₃ and N₂=0. The other directions do not succeed, so the obvious total order emerges in this particular case.