Pure C++
Generic Programming: Template Specialization
Stanley B. Lippman
Contents
Partial Template Specialization
Function Template Specialization
Overload Function Resolution
As I discussed in my last column, a param-eterized type that does more than simple storage and retrieval is constrained as to the acceptable types that may be safely bound to it (see Pure C++: CLR Generics Versus C++ Templates. Using generics, these constraints are made explicit through the where clause. In the C++/CLI template facility, you can often work around these constraints by specializing a function or class template—either individual member functions or an entire class. For the sake of illustration, let's add a min function to my tStack class from the previous column. Ordinarily, I would use the generic min algorithm, but that would only help me as a programmer, not as author of an article on template specialization. For your convenience, the tStack class template definition is reproduced in Figure 1.
Figure 1 tStack Declaration
// c++\cli template stack declaration
template <class elemType>
public ref class tStack
{
vector<elemType> ^m_stack;
int top;
public:
tStack();
tStack( int size );
elemType pop();
void push( elemType et );
// our new function to implement
elemType tStack<elemType>::min();
};
Figure 2 shows one possible implementation of min. I define min_val, a local variable, to hold the minimum element, and I initialize it to the first element of the container. I then define two iterators, and compare each element against min_val, reassigning it if the value happens to be smaller. Can you identify the implicit constraint? Yep, you got it:
if ( *it < min_val )
Figure 2 min Implementation
template <class elemType>
elemType tStack<elemType>::min()
{
// note: iterators are value classes...
vector<elemType>::iterator it = m_stack->begin();
vector<elemType>::iterator end_it = m_stack->end();
if ( it == end_it )
throw gcnew Exception;
elemType min_val = *it++;
for ( ; it != end_it; ++it )
if ( *it < min_val )
min_val = *it;
return min_val;
}
The only valid types that can be bound to elemType in terms of the min function, in general, are those that are able to use the built-in less-than operator or that provide their own operator<() instance. If operator<() is not defined for such a type, and an attempt is made to call min on a tStack of items of this type, a compile-time error is issued at the point where the invalid comparison operator is used in min. The System::String class, as it happens, does not have a less-than operator (it uses the CompareTo method of IComparable). If I attempt to invoke min on a tStack instantiated with String, therefore, it breaks down at compile time because the comparison operation fails.
One possible solution that I won't pursue is to define a global operator operator<() that uses CompareTo to compare two values of type String. These global operators are then invoked automatically by tStack<String^>::min():
bool operator<( String^ s1, String^ s2 ) {
return ( s1->CompareTo( s2 ) < 0 ) ? true : false;
}
The goal, remember, is to prevent the tStack::min member function definition to be instantiated if the user-specified type argument is String. Instead, you want to define your own tStack<String^>::min instance that uses the CompareTo method. You do this by providing a specialized definition for a member of a class template instantiation using an explicit specialization definition. This definition indicates the template name, the template arguments for which the template is specialized, the function parameter list, and the function body. The keyword template is followed by the less than (<) and greater than (>) tokens, followed by the definition of the specialization for the class member (see Figure 3).
Figure 3 Explicit Specialization Definitions
// explicit specialization definitions
template<> String^
tStack<String^>::min( )
{
vector<String^>::iterator it = m_stack->begin();
vector<String^>::iterator end_it = m_stack->end();
if ( it == end_it )
throw gcnew Exception;
String^ min_val = *it++;
for ( ; it != end_it; ++it )
if ( it->CompareTo( min_val ) < 0 )
min_val = *it;
return min_val;
}
Even though the class type tStack<String^> is instantiated from the general class template definition (that is, a String-specific instance is internally generated by the compiler in which each occurrence of the elemType placeholder is replaced with the String type), each object of type tStack<String^> invokes your specialization of the member function min. The tStack::min member function definition is neither expanded nor used for a tStack<String^>.
In some cases the entire class template definition may be inappropriate for use with a particular type. In this case the programmer can provide a definition to specialize the entire class template. The programmer may provide a definition of tStack<String^>:
template <class elemType>
ref class tStack;
// class template specialization
template<> ref class tStack<String^> {
public:
tStack();
String^ pop();
void push( Stack^ et );
// ...
};
An explicit specialization for a class template can be defined only after the general class template has been declared. If you provide a full class template specialization, you must define each member function or static data member associated with this specialization. The generic member definitions of the class template are never used (nor are they cross-checked) to create the definitions for the members of an explicit specialization. This is because the class template specialization may have a completely different set of class members from the generic template.
When defining a member of a fully specialized class template, such as tStack<String^>, you do not precede its definition with the special template<> marking. Rather, you indicate the specialization by explicitly listing the actual type, as in the following:
// defines the member function min()
// of a class template specialization
String^ tStack<String^>::min() { ... }
Partial Template Specialization
If a class template has more than one template parameter, you can specialize the class template for one or a set of particular parameterized values or types. That is, you might want to provide a template that matches a general template except that some of the template parameters have been replaced by actual types or values. This is possible using partial template specialization. For example, imagine the following Buffer class template:
template <class elemType, int size>
ref class Buffer { ... };
Here is how you might use partial specialization on Buffer to optimally handle buffers with a size of 1KB:
// partial specialization of class template Buffer
template <class elemType>
ref class Buffer<elemType,1024> {
// Uses special algorithms for 1KB size ...
};
The partial specialization for Buffer only has one type parameter, named elemType, because the value for size is fixed at 1024. The parameter list for a partial template specialization only lists the parameters for which the template arguments are still unknown. However, when you define an instance of the template, you must specify both parameters (unlike the use of a default value for a parameter). In the following example, the class template partial specialization is instantiated with a type argument for elemType that is String:
Buffer<String^,1024> mumble;
However, if you instead write the following line of code, the compiler generates an error flagging the declaration as missing the second parameter:
Buffer<String^> mumble; // error
Why? What would happen if a developer later introduced a set of specialized Buffers, such as:
template <class elemType>
ref class Buffer<elemType,4096> {};
template <class elemType>
ref class Buffer<elemType,512> {};
Were the second parameter not required in the declaration of mumble in the earlier example, the compiler would have no way to distinguish between the several specializations!
The partial specialization has the same name as the full general template to which it corresponds—Buffer in the example. This raises an interesting question. Notice that the instantiation for Buffer<String^,1024> could be instantiated from the class template definition as well as from the partial specialization. Why is it then that the partial specialization is chosen to instantiate the template? The general rule is that when class template partial specializations are declared, the compiler chooses the template definition that is the most specialized for the instantiation. When no partial specialization can be used, the generic template definition is used.
For example, when Buffer<String^,2048> must be instantiated, this instantiation does not match any of the partial template specializations, so the general template definition is selected.
The definition of a partial specialization is completely disjointed from the definition of the general template. The partial specialization may have a completely different set of members from the generic class template. A class template partial specialization must have its own definitions for its member functions, static data members, and nested types, the same as for a class template specialization. The generic definitions for the members of a class template are never used to instantiate the members of the class template partial specialization.
Partial template specialization of class templates forms the basis of some very sophisticated design idioms within modern C++ usage. If you're interested, you can read more on this usage in Modern C++ Design: Generic Programming and Design Patterns Applied by Andrei Alexandrescu (Addison-Wesley, 2001).
Function Template Specialization
Non-member function templates can also be specialized. Again, in some cases, you may be able to take advantage of some specific knowledge about a type to write a more efficient function than the one that is instantiated from the template. At other times, the general template definition is simply wrong for a type. For example, suppose you have this definition of the function template max:
template <class T>
T max( T t1, T t2 ) {
return ( t1 > t2 ? t1 : t2 );
}
If the function template is instantiated with a template argument of type System::String, the generated instance fails to compile because, as you saw earlier, the String class does not support either the less-than or greater-than operators. The code in Figure 4 shows how you specialize a function template (again, the general function template must have been declared before you can provide your specialization).
Figure 4 Specializing a Function Template
using namespace System;
// String explicit specialization:
// overrides instantiation from general template definition
// declaration ...
template<> String^ max<String^>( String^ s1, String^ s2 );
// definition ...
template<> String^ max<String^>( String^ s1, String^ s2 )
{
return ( s1->CompareTo( s2 ) > 0 ? s1 : s2 );
}
The qualification of the function template name with its actual type parameter, max<String^>, can be omitted from the explicit specialization declaration if the template arguments can be deduced from the function parameters. For example, the compiler can deduce that T binds to String in the following specialization of max, and so in this case the language allows the following shorthand notation as a convenience:
// ok: T as String is deduced from parameter types
template<> String^ max( String^, String^ );
Once this explicit specialization is introduced, an invocation such as the following resolves to this specialized instance:
void foo( String^ s1, String^ s2 ) {
String^ maxString = max( s1, s2 );
// ...
}
The general function template is not expanded for two arguments of type String. This is the exact behavior that is required.
Whenever you provide an explicit function template specialization, you must always specify both template<> and the function parameter list. For example, the following two declarations of max are illegal and flagged at compile time as such:
// error: invalid specialization declarations
// missing template<>
String^ max<String^>( String^, String^ );
// missing function parameter list
template<> String^ max<String^>;
That said, there is one case in which omitting the template<> portion of a function template specialization is not an error. This is when you declare an ordinary function with a return type and a parameter list that match those of a template instantiation:
// general template definition
template <class T>
T max( T t1, T t2 ) { /* ... */ }
// ok: an ordinary function declaration!
String^ max( String^, String^ );
No doubt a number of you are shaking your heads and thinking, gosh, C++ is really confusing. And you may be wondering why on earth anyone would want to declare an ordinary function that matches a template instantiation instead of declaring an explicit specialization. Well, consider the following example in which things don't quite work the way you would like:
void foo( String^ s1, String^ s2 ) {
// is the specialized instance resolved?
String^ maxString = max( "muffy", s2 );
// ...
}
Under C++/CLI, for overload resolution, the type of a string literal is both const char[n], where n is the length of the literal plus one for the terminating null, and System::String. This means, for example, that, given the set of functions
void f( System::String^ ); // (1)
void f( const char* ); // (2)
void f( std::string ); // (3)
a call such as this one
// resolves to (1) under C++/CLI
f( "bud, not buddy" );
exactly matches (1), whereas under ISO-C++, the resolution would be (2). So, the question is, for the type deduction of a function template, is a string literal also treated as a System::String? And the short answer is, no. (The long answer will be the topic of my next column, which will cover function templates in detail.) The specialized String instance of max therefore is not chosen, and the following call to max
String^ maxString = max( "muffy", s2 ); // error
fails at compile time because the definition of max requires both arguments to be of the same type, T:
template <class T> T max( T t1, T t2 );
What can you do? Turning the template to a two-parameter instance, as in the following redeclaration
template <class T1,class T2> ??? max( T1 t1, T2 t2 );
allows us to compile the invocation of max with muffy and s2, but then breaks down over the greater-than operator, and specifying which parameter type to return.
What I would like is to always force the conversion of a string literal to type String, and this is where the ordinary function declaration comes to the rescue.
Only a limited set of type conversions are applied to convert an argument of a function template instantiation to the type of the corresponding function parameter if the argument participates in the deduction of a template argument. This is also the case if the function template is explicitly specialized. And, as you've seen, a string literal to System::String conversion is not part of that set.
In the case of the pernicious string literal, explicit specializations do not help you bypass the restrictions on type conversions. If you want to allow more than just the set of limited type conversions, you must define an ordinary function instead of a function template specialization. And this is why C++ allows a non-template and template function to be overloaded.
I'm almost finished, but there is one last item to clarify. What does it mean to create the set of max functions that you see in Figure 5? You know that the call
max( 10, 20 );
always resolves to the general template definition, with T deduced to be int. Similarly, you now know that the calls
max( "muffy", s2 );
max( s2, "muffy" );
always resolve to the ordinary function instance in which the literal string is converted to System::String, but then there is the question of which instance the call
max( s2, s2 );
is resolved to in the set of three max functions? To answer this, let's step through the process of resolving an overloaded function.
Figure 5 max Functions
// general template definition
template <class T>
T max( T t1, T t2 ) { /* ... */ }
// our first specialization – fine for two Strings
// but not String, string literal
template<> String^ max<String^>( String^ s1, String^ s2 );
// our ordinary function declaration to support
// a mixture of String, string literal
String^ max( String^, String^ );
Overload Function Resolution
The first step in overload function resolution is just to build the set of candidate functions. The candidate function 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 is the non-template instance. I 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 my example, the function argument is s2, which is of type String. Template argument deduction binds String to T, and the template instantiation max(String^,String^) is added to the set of candidate functions.
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, as in my case? 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.
There are, therefore, two candidate functions for the call: the specialized template instantiation and the non-template instance.
// candidate functions
// specialized template ...
template<> String^ max<String^>( String^ s1, String^ s2 );
// non-template instance
String^ max( String^, String^ );
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 consists of ranking the type conversions applied to the arguments to select the best viable function. For the example, both functions appear equally good. 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 max is invoked because it's given precedence over the template instantiation. The reasoning behind this is that an explicitly implemented function is in a sense more real than an instance created from a general blueprint.
Surprisingly, in solving the case of the pernicious string literal, I've eliminated any chance of my earlier String specialization from ever being invoked, so I can eliminate it. I only need the general template declaration and the overloaded non-template instance:
// our final overloaded set to support String
template <class T>
T max( T t1, T t2 ) { /* ... */ }
String^ max( String^, String^ );
That may or may not seem complicated, but it sure is powerful—far beyond the scope of what the common language runtime (CLR) generic facility can support in terms of both language integration and flexibility.
Template specialization is a fundamental aspect of C++ template design. It allows for optimal performance, overcoming constraints on individual or families of class types, and for flexible design patterns that have proven invaluable in real-world code. In my next column, I will drill down into C++/CLI support for both template and generic functions.
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.