Pure C++
Invoking Generic or Function Templates
Stanley B. Lippman
Contents
As I promised last time, in this month's column I'll walk through the process of defining and invoking a generic or template function under C++\CLI. A function template or a generic function begins with the template or generic keyword followed by its parameter list. Unlike a template function, a generic function may then optionally specify a constraint clause. This is followed with either the prototype declaration or full definition of the function. These functions can either be independent functions, such as those shown in Figure 1, or member functions either of a nonparameterized or parameterized reference, value, or interface class, as shown in Figure 2.
Figure 2 Member Functions
public value class SmallInt {
public:
generic <class elemType>
elemType convertTo();
// ...
};
template <class T>
ref class myContainer {
public:
myContainer( int size );
myContainer( int size, T initValue );
template <class Iter>
myContainer( Iter first, Iter last, T val );
// ...
};
Figure 1 Independent Functions
template <class elemType>
interior_ptr<elemType>
find( array<elemType> ^ta, elemType value );
generic <class elemType>
where elemType: IComparable<elemType>
elemType
max( elemType t1, elemType t2 )
{
return t1->CompareTo( t2 ) >= 0 ? t1 : t2;
}
The type parameters can be used within the return type, signature, and body of the function. If the function is a member of a parameterized class, it can also refer to the type parameters of its containing class—as does the third parameter of the three-argument myContainer template constructor in Figure 2.
The type parameters are not required to be used within the function signature; however, only those occurring in the function signature can be deduced. (Type deduction is discussed in the following section.)
As with ordinary functions, if a second or subsequent function having the same name differs in either the number or type of its parameters, it is treated as an overloaded instance. This set of overloaded functions can be a mix of both generic and template definitions, as shown in this example:
// ok: overloaded function set based on signature
template <class elemType>
elemType min( elemType t1, elemType t2 );
generic <class elemType>
where elemType: IComparable<elemType>
elemType min( array<elemType>^ t1 );
However, if the name and signature of two functions are the same, differences in either the return type or the associated constraint clauses between the two functions are flagged as declaration errors. The return type (except in the case of conversion operators) and constraint clauses do not contribute to the overloading of a function, as happens here:
// error: functions are not overloadable by either
// return type or constraint clause differences
generic <class T>
where T : IComparable
int min( T t1, T t2 );
generic <class U>
where U : IComparable<U>
double min( U t1, U t2 );
Unlike an ordinary function, however, a set of parameterized functions with the same signature can be overloaded based on unique parameter lists, as shown here:
// ok: overloaded function set based on parameter list
generic <class elemType>
where elemType : IComparable<elemType>
elemType min( elemType, elemType );
generic <class elemType, class elemType2>
where elemType : IComparable<elemType>
elemType min( elemType, elemType2 );
An interesting question is, how can an invocation such as this
possibly be resolved between these two instances? In fact, it turns out this is not at all ambiguous, and the reason for that has to do with "partial ordering," which I'll discuss shortly.
Function Instantiation
When each of the type parameters occurs within the function signature, an invocation of the function is usually sufficient for the compiler to deduce the associated type arguments for the call. Here's an example:
// ok: compiler deduces that elemType => int
int ival = min( 10, 20 );
However, if the two values passed to the function differ by type in the call to min, the compiler is unable to deduce the type argument, and the invocation is flagged as an error, as happens here:
// error: is elemType int or double?
int ival = min( 10, 2.0 );
When the compiler sees a call of min, the following steps take place. First, the compiler recognizes that min is a non-overloaded parameterized function—it doesn't matter at this point if it is a template function or a generic function. Next the compiler discovers that there is a single formal parameter, and it must deduce the type of the parameter from the actual argument(s) being passed. The first argument is the literal constant, 10. This is of type int, and so the compiler tentatively binds elemType to int. It then looks at the second argument, either 20 or 2.0, and compares its type to that of the tentative resolution of elemType. If the type of the two arguments are the same (which is the case with the integer literal constant 20), the compiler has deduced elemType to be of type int. If they are not of the same type (which is the case with the double literal constant 2.0), the compiler must generate an error since there is no way for it to prefer binding one type over the other. In this case, you must help the compiler out.
In the case where the compiler cannot deduce a parameter type, you must provide an explicit parameter list following the name of the function, like so:
// ok: we explicitly bind the type
int ival = max<double>( 10, 2.0 );
What happens in this invocation is that elemType binds to double. The integer literal 10 is promoted to double before it is passed to min. The invocation is no longer illegal.
The return type is not considered while the compiler is deducing the type argument—only the actual arguments passed to the call are considered (again, this is true except in the case of user-defined conversion operators). If you define a method in which the only use of a type parameter is to declare the return type,
generic <class elemType>
elemType Convert( String^ );
the compiler—in some cases—cannot deduce the argument type, as happens in the following:
// error: unable to deduce type argument
Convert( myString );
Therefore, you must qualify all invocations with the explicit type argument, as in:
// ok: explicit list the type argument
Convert<int>( myString );
This is true even if the target type is specified by an initialization or assignment. Take a look at this example:
// still requires an explicit listing of the type argument
int sval = Convert<int>( myString );
Similarly, when a type parameter is not present in the signature, the compiler is not able to deduce the type argument, as shown in the following example:
// can't deduce the second parameter
// since it is not present in signature
generic <class elemType, class elemType2>
where elemType : IComparable<elemType>
elemType min( elemType, elemType );
It is interesting to note that in the original pre-ISO template definition, there was no ability to explicitly list the intended type parameters for a function. Type deduction was required in all cases, but could not be carried out for all cases. This was corrected in the ISO standard.
Partial Ordering Rules
In some situations, even if two different parameterized functions can be instantiated, the function call might still be unambiguous. Given the following two template definitions for sum, for example, there exists a situation in which the first template definition is preferred even if an instantiation can be generated from either of these function templates:
template < class Type > Type sum( Type*, int ); // 1
template < class Type > Type sum( Type, int ); // 2
int ia[1024];
// which instance is selected [ // 1 or // 2 ] ?
int ival1 = sum( ia, 1024 );
Look at the two declarations and see if you can reason out which one is preferred over the other and why that is the case. The template instance selected is number 1—the one taking a Type* rather than Type. It is considered to be the most specialized of the template definitions. The deduced template argument for Type is therefore int and not int*.
For one template to be more specialized than another, both templates must have the same name and the same number of parameters (except in the special case of a function taking a variable number of arguments, in which case the partial ordering stops pairwise comparison at that point). For the corresponding function parameters with different types, such as T* and T, one of the parameters must be able to accept a subset of the arguments that the corresponding parameter in the other template can accept.
For example, for the template sum(Type*,int), the first function parameter can match arguments only of pointer type. For the template sum(Type,int), the first function parameter can match arguments of pointer type as well as arguments of any other type. The second template accepts a superset of the types accepted by the first template. The template that accepts the more limited set of arguments is said to be more specialized—this is what the partial ordering rule resolves. In the example, the template sum(Type*,int) is more specialized and is the template that is instantiated for the function call.
Similarly, in the original example (see Figure 3), generic 1 is instantiated because it is the more specialized. If you don't see that, step back a moment. While this may seem nonintuitive at first, the rule is simple: generic 1 accepts the more limited set of arguments—all single parameters—while generic 2 accepts all single parameters as well as all two parameters. So, generic 1 is always chosen whenever the two parameters to min are of the same type.
Figure 3 Partial Ordering
// ok: overloaded function set based on parameter list
generic <class elemType> //1
where elemType : IComparable<elemType>
elemType min( elemType, elemType );
generic <class elemType, class elemType2> //2
where elemType : IComparable<elemType>
elemType min( elemType, elemType2 );
// the invocation
int minVal = min(10,20);
Should every programmer using C++ be able to distinguish the partial ordering of an overloaded set of template or generic functions? No. But someone working on the project needs to understand these issues and articulate them at design and code reviews. Otherwise, the possible unexpected invocation of a function in rare cases can prove to be frustrating.
Overload Function Resolution
I looked at overload function resolution in the
previous column. I hope I don't exhaust your patience by making a second pass on it. I promise this will be the last I write on the subject. So here goes.
A parameterized function can be overloaded. It can also have the same name as a nonparameterized function, as shown here:
template <class Type> Type sum( Type, int );
double sum( double, double );
When a program invokes sum, the call can be resolved either to an instantiation of the function template or to the non-template function. Which one the call resolves to depends on which of these functions best matches the types of the function arguments. The function overload resolution process is used in order to determine which function best matches the arguments on the function call, as shown in this example:
void calc( int ii, double dd )
{
// does it call a template instantiation
// or the ordinary function?
sum( dd, ii );
}
Does sum(dd,ii) call a function instantiated from the template, or does it call the non-template function? To answer this, let's step through the process of resolving an overloaded function. The first step is just to identify the set of candidate functions. You should recall that this set consists of the functions that have the same name as the called function and for which a declaration is visible at the point of the call.
The first visible function, of course, is the non-template instance. You need to add that to the candidate list. What about the function template?
When a function template is visible, an instantiation of that template is treated as a candidate function if a function can be instantiated using the function call arguments. In the example you just saw, the function argument is dd, which is of type double. Template argument deduction binds double to Type, and the template instantiation sum<double,int>(double,int) is added to the set of candidate functions.
The next step of function overload resolution selects the set of viable functions from the set of candidate functions. For a candidate function to qualify as a viable function, type conversions must exist to convert each actual argument type to the type of the corresponding formal parameter. In the example, both candidate functions are viable.
The last step of resolving an overloaded function involves ranking the type conversions applied to the arguments to select the best viable function. For my example, the ranking is as follows. For the function template instantiation sum(double,int):
- For the first argument, both the argument and the parameter have type double, and the conversion is an exact match.
- For the second argument, both the argument and the parameter have type int, and the conversion is also an exact match.
For the non-template function sum(double,double):
- For the first argument, both the argument and the parameter have type double, and the conversion is an exact match.
- For the second argument, the argument has type int and the parameter has type double; the conversion applied is a floating-integral standard conversion.
Both functions are equally good when the first argument is considered. However, the function template instantiation is better for the second argument. Therefore, the function selected as the best viable function for the call is the instantiation sum<double,int>(double,int).
A function template instantiation is entered in the set of candidate functions only if template argument deduction succeeds. However, it is not an error if template argument deduction fails; it just means that no function instantiation is added to the set of candidate functions.
What if template argument deduction succeeds but the template is explicitly specialized for the template arguments deduced? Then it is the explicit specialization that is entered in the set of candidate functions in the place of the function that would be instantiated from the generic template definition.
Consider the following pair of declarations:
// function template declaration
template <class T>
T min( T, T );
// non-template function min( int, int )
int min( int, int );
An invocation such as
int f( int ix, int iy ) { return min( ix, iy ); }
matches equally both the template instantiation of min in which T is bound to int, and the non-template min. Should this, therefore, be treated as an ambiguous call since both are equally viable?
The answer is that the call is not ambiguous. The non-template min is invoked because it is given precedence over the template instantiation. The reasoning applied here is that an explicitly implemented function is in a sense more real than an instance created from a general blueprint.
Finally, what if the programmer really wanted to have the template instance of min invoked? Not a problem. You can force the compiler to choose the template instance by using the <> notation on the call, as follows:
// forces compiler to choose template instance
int f( int ix, int iy ) { return min<>( ix, iy ); }
Wrap-Up
It may initially seem that there are just too many rules regarding templates. You've seen some of them now—the partial ordering rules and the rules governing the interoperability of an overloaded set of template and non-template functions. The rules are meant to adjudicate every possible combination not because these combinations are either desirable or common, but because they do occasionally occur. In 90 percent of the cases, these issues don't arise. But if a case should occur, these rules allow the developer community to determine exactly what should occur, and judge whether the design or the compiler is in error.
In the original template definition, prior to standardization, none of these rules existed, and the template facility appeared much simpler. Implementing and programming the original spec led to an enumeration of these many rules. So what is it about templates that make these rules necessary?
Template design exists at a higher level of abstraction than non-template design and, I believe, we programmers don't currently have a great deal of experience thinking at the scale of combinatorics that parameterized types makes possible. There may be more rules than are necessary for elegance, but for completeness they carry the day. I hope I have been able to convey to you some sense of their importance.
Send your questions and comments for Stanley to purecpp@microsoft.com.
Stanley B. Lippman is an Architect with the Visual C++ team at Microsoft. He began working on C++ with its inventor, Bjarne Stroustrup, in 1984 at Bell Laboratories. In between, he worked in feature animation at Disney and DreamWorks, was a Distinguished Consultant with JPL, and was a Software Technical Director on Fantasia 2000.