Why are these templates ambiguous?

Question

The book C++ Templates : The Complete Guide has an example on page 275 that I'm having trouble wrapping my head around.

Quoting excerpts from the book...

template <typename T>
class Promotion<T,T> {
  public:
    typdef T ResultT;
};

template<typename T1, typename T2>
class Promotion<Array<T1>, Array<T2> > {
  public:
    typedef Array<typename Promotion<T1,T2>::ResultT> ResultT;
};

template<typename T>
class Promotion<Array<T>, Array<T> > {
  public:
    typedef Array<typename Promotion<T,T>::ResultT> ResultT;
};

Unfortunately, the partial specialization Promotion<Array<T1>, Array<T2> > is neither more nor less specialized than the partial specialization Promotion<T,T>. To avoid template selection ambiguity, the last partial specialization was added. It is more specialized than either of the previous two partial specializations.

Why are the first two templates ambiguous, and why does the last template solve the ambiguity issue? When I try to apply the rules I either can't figure out how it comes up with an ambiguity, or if I think I have a way for it to happen I don't know why the last template solves the problem.

Answer 1

Maybe your confusion stems from how the relation "is more specialised than" works. It's a partial order, not a total order -- that means that given 2 template specialisations, it's not always the case that one is more specialised than the other.

Anon's comment is right: Suppose that 3rd specialisation didn't exist, and later in your code you had:

Promotion<Array<double>, Array<double> > foo;

(Of course you probably wouldn't actually create a variable of this empty struct type, but this is just the simplest way to force its instantiation.)

Given this declaration of foo, which of the 1st 2 specialisations would be picked?

• Specialisation 1 applies, with T = Array<double>.
• Specialisation 2 applies, with T1 = double, T2 = double.

Both specialisations are applicable, so we need to determine which "is more specialised than" the other, and pick that one. How? We will say that X is more specialised than Y if it is at least as specialised as Y, but Y is not at least as specialised as X. Although it seems like this is just dancing around the problem, there is a clever rule that we can use to answer this new question:

X is at least as specialised as Y if, regardless of what types we assign to the template parameters of X, the resulting type could always be matched by Y.

Note that we forget about the particular types involved in the current instantiation (in this case, double) -- the "is at least as specialised as" relation is a property of the partial specialisations themselves, and doesn't depend on particular instantiations.

Can specialisation 1 always be matched by specialisation 2? The process is a bit like algebra. We require that for any type T, we can find types T1 and T2 such that:

Promotion<Array<T1>, Array<T2> > = Promotion<T, T>

This implies:

Array<T1> = T
Array<T2> = T

So the answer is no. Looking at just the first implied result, given any type T, in general it's not possible to find a type T1 such that Array<T1> is the same type as T. (It would work if T happened to be Array<long>, but not if T is int or char* or most other types.)

What about the other way around? Can specialisation 2 always be matched by specialisation 1? We require that for any types T1 and T2, we can find a type T such that:

Promotion<T, T> = Promotion<Array<T1>, Array<T2> >

Implying:

T = Array<T1>
T = Array<T2>

So the answer is again no. Given any type T1, it's always possible to find a type T such that T is the same type as Array<T1> -- just literally set T = Array<T1>. But in general the other type T2 is not constrained to be the same as T1, and if it's not (e.g. if T1 = bool but T2 = float) then it will not be possible to find a type T that is the same as both Array<T1> and Array<T2>. So in general, it's not possible to find such a type T.

In this case, not only is neither specialisation more specialised than the other, neither is even as specialised as the other. As a result, if the need arises to instantiate this template class and both specialisations match -- as it does in the example Anon gave -- there is no way to choose a "best" one.