Templates provide direct support for generic programming, that is, programming using types as parameters. The C++ template mechanism allows a type to be a parameter in the definition of a class or a function. A template depends only on the properties that it actually uses from its parameter types and does not require different types used as arguments to be explicitly related. In particular, the argument types used for a template need not be from a single inheritance hierarchy.
Main tings to know about templates are
• The basic mechanisms for defining and using class templates
• Function templates, function overloading, and type deduction
• Template parameters used to specify policies for generic algorithms
• Multiple definitions providing alternative implementations for a template
• Derivation and templates (runtime and compile time polymorphism)
• Source code organization
A Simple String Template
template class String {}
The templateprefix specifies that a template is being declared and that a type argument C will be used in the declaration. After its introduction, C is used exactly like other type names. The scope of C extends to the end of the declaration prefixed by template . Note that template says that C is a type name; it need not be the name of a class.
The name of a class template followed by a type bracketed by <> is the name of a class (as defined by the template) and can be used exactly like other class names.
String cs;
Except for the special syntax of its name, String works exactly as if it had been defined using the definition of class std::String.
In general, typedefs are useful for shortening the long names of classes generated from templates. Also, we often prefer not to know the details of how a type is defined, and a typedef allows us to hide the fact that a type is generated from a template.
Defining a Template
A class generated from a class template is a perfectly ordinary class. Thus, use of a template does not imply any runtime mechanisms beyond what is used for an equivalent ‘‘handwritten’’ class. Nor does it necessarily imply any reduction in the amount of code generated.
It is usually a good idea to debug a particular class, such as String, before turning it into a template such as String. By doing so, we handle many design problems and most of the code errors in the context of a concrete example. Later, we can deal with any problems that might arise from generalization without being distracted by more conventional errors.
Members of a template class are declared and defined exactly as they would have been for a non template class. A template member need not be defined within the template class itself. In that case, its definition must be provided somewhere else, as for non template class members. Members of a template class are themselves templates parameterized by the parameters of their template class. When such a member is defined outside its class, it must explicitly be declared a template.
template struct String: :Srep {
C* s; / / pointer to elements
int sz; / / number of elements
int n; / / reference count
/ / ...
};
templateC String: :read(int i) const
{
return rep->s[i] ;
}
template String: :String()
{
p = new Srep(0,C()) ;
}
Template parameters, such as C, are parameters rather than names of types defined externally to the template. However, that doesn’t affect the way we write the template code using them. Within the scope of String, qualification with is redundant for the name of the template itself, so String::String is the name for the constructor. If you prefer, you can be explicit:
template String: :String()
{
p = new Srep(0,C()) ;
}
Just as there can be only one function defining a class member function in a program, there can be only one function template defining a class template member function in a program. However, overloading is a possibility for functions only, while specialization enables us to provide alternative implementations for a template.
It is not possible to overload a class template name, so if a class template is declared in a scope, no other entity can be declared there with the same name.
Template Instantiation
The process of generating a class declaration from a template class and a template argument is often called template instantiation. Similarly, a function is generated (‘‘instantiated’’) from a template function plus a template argument. A version of a template for a particular template argument is called a specialization.
In general, it is the implementation’s job – not the programmer’s – to ensure that versions of a template function are generated for each set of template arguments used
Obviously, templates provide a powerful way of generating code from relatively short definitions. Consequently, a certain amount of caution is in order to avoid flooding memory with almost identical function definitions.
Template Parameters
A template can take type parameters, parameters of ordinary types such as ints, and template parameters. Naturally, a template can take several parameters. For example:
template class Cont{ /* ... */ };
As shown, a template parameter can be used in the definition of subsequent template parameters. Integer arguments come in handy for supplying sizes and limits. For example:
template class Buffer {
T v[i] ;
int sz;
public:
Buffer() : sz(i) {}
/ / ...
};
Buffer cbuf;
Buffer rbuf;
A template argument can be a constant expression, the address of an object or function with external linkage, or a non overloaded pointer to member. A pointer used as a template argument must be of the form &of, where of is the name of an object or a function, or of the form f, where f is the name of a function. A pointer to member must be of the form &X::of where of is the name of an member. In particular, a string literal is not acceptable as a template argument.
An integer template argument must be a constant:
void f(int i)
{
Buffer bx; / / error: constant expression expected
}
Conversely, a non type template parameter is a constant within the template so that an attempt to change the value of a parameter is an error.
Type Equivalence
Given a template, we can generate types by supplying template arguments.
String s1;
String s2;
String s3;
When using the same set of template arguments for a template, we always refer to the same generated type. However, what does ‘‘the same’’ mean in this context? As usual, typedefs do not introduce new types, so String is the same type as String. But char and unsigned char are different types.
Type Checking
A template is defined and then later used in combination with a set of template arguments. When the template is defined, the definition is checked for syntax errors and possibly also for other errors that can be detected in isolation from a particular set of template arguments.
A compiler can catch simple semantic errors at the point of definition or later at the point of use. Users generally prefer early detection, but not all ‘‘simple’’ errors are easy to detect. like a pointer T* cannot be initialized by the integer 7.
Errors that relate to the use of template parameters cannot be detected until the template is used.
The earliest that errors relating to a template parameter can be detected is at the first point of use of the template for a particular template argument. That point is usually called the first point of instantiation, or simply the point of instantiation. The implementation is allowed to postpone this checking until the program is linked.
Function Templates
For most people, the first and most obvious use of templates is to define and use container classes.
When a template function is called, the types of the function arguments determine which version of the template is used; that is, the template arguments are deduced from the function arguments.
Function Template Arguments
Function templates are essential for writing generic algorithms to be applied to a wide variety of container types. The ability to deduce the template arguments for a call from the function arguments is crucial. A compiler can deduce type and non type arguments from a call, provided the function argument list uniquely identifies the set of template arguments.
Note that class template parameters are never deduced. The reason is that the flexibility provided by several constructors for a class would make such deduction impossible in many cases and obscure in many more. Specialization provides a mechanism for implicitly choosing between different implementations of a class . If we need to create an object of a deduced type, we can often do that by calling a function to do the creation;
If a template argument cannot be deduced from the template function arguments, we must specify it explicitly. This is done in the same way template arguments are explicitly specified for a template class. For example:
i n t * p = c r e a t e < i n t >(); // function, template argument ‘int’
One common use of explicit specification is to provide a return type for a template function:
t e m p l a t eT i m p l i c i t c a s t (U u ) { r e t u r n u ; }
v o i d g (i n t i )
{
i m p l i c i t c a s t (i ); // error: can’t deduce T
i m p l i c i t c a s t(i ); // T is double; U is int
i m p l i c i t c a s t(i ); // T is char; U is double
i m p l i c i t c a s t(i ); // T is char*; U is int; error: cannot convert int to char*
}
As with default function arguments, only trailing arguments can be left out of a list of explicit template arguments.
Function Template Overloading
One can declare several function templates with the same name and even declare a combination of function templates and ordinary functions with the same name. When an overloaded function is called, overload resolution is necessary to find the right function or template function to invoke. For example:
t e m p l a t eT s q r t (T );
t e m p l a t ec o m p l e x s q r t (c o m p l e x );
d o u b l e s q r t (d o u b l e );
v o i d f (c o m p l e xz )
{
s q r t (2 ); // sqrtint(int)
sqrt(2.0) ; / / sqrt(double)
sqrt(z) ; / / sqrtdouble(complexdouble)
}
In the same way that a template function is a generalization of the notion of a function, the rules for resolution in the presence of function templates are generalizations of the function overload resolution rules. Basically, for each template we find the specialization that is best for the set of function arguments. Then, we apply the usual function overload resolution rules to these specializations and all ordinary functions:
[1] Find the set of function template specializations that will take part in overload resolution. Do this by considering each function template and deciding which template arguments, if any, would be used if no other function templates or functions of the same name were in scope. For the call s q r t (z ), this makes
s q r t(c o m p l e x ) and
s q r t < c o m p l e x>(c o m p l e x ) candidates.
[2] If two template functions can be called and one is more specialized than the other, consider only the most specialized template function in the following steps. For the call
s q r t (z ), this means that s q r t(c o m p l e x ) is preferred over s q r t < c o m p l e x >(c o m p l e x ): any call that matches s q r t (c o m p l e x )
also matches s q r t(T ).
[3] Do overload resolution for this set of functions, plus any ordinary functions as for ordinary functions. If a template function argument has been determined by template argument deduction, that argument cannot also have promotions, standard conversions, or user defined conversions applied. For s q r t (2 ), s q r t < i n t >(i n t ) is an exact match, so it is preferred over s q r t (d o u b l e ).
[4] If a function and a specialization are equally good matches, the function is preferred. Consequently,
s q r t (d o u b l e ) is preferred over s q r t(d o u b l e ) for s q r t (2 .0 ).
[5] If no match is found, the call is an error. If we end up with two or more equally good matches, the call is ambiguous and is an error.
Specialization
By default, a template gives a single definition to be used for every template argument (or combination of template arguments) that a user can think of. This doesn’t always make sense for someone writing a template. I might want to say, ‘‘if the template argument is a pointer, use this implementation; if it is not, use that implementation’’ or ‘‘give an error unless the template argument is a pointer derived from class
M y b a s e .’’ Many such design concerns can be addressed by providing alternative definitions of the template and having the compiler choose between them based on the template arguments provided where they are used. Such alternative definitions of a template are called user defined specializations, or simply, user specializations.
Consider likely uses of a V e c t o r template:
t e m p l a t ec l a s s V e c t o r { // general vector type
T * v ;
i n t s z ;
p u b l i c :
V e c t o r ();
V e c t o r (i n t );
T & e l e m (i n t i ) { r e t u r n v [i ]; }
T & o p e r a t o r [](i n t i );
v o i d s w a p (V e c t o r &);
/ / ...
};
V e c t o r < i n t > v i ;
V e c t o r < S h a p e *> v p s ;
V e c t o r < s t r i n g > v s ;
V e c t o r < c h a r *> v p c ;
V e c t o r < N o d e *> v p n ;
Most V e c t o r s will be V e c t o r s of some pointer type. There are several reasons for this, but the primary reason is that to preserve runtime polymorphic behavior, we must use pointers. That is, anyone who practices object oriented programming and also uses typesafe containers (such as the standard library containers) will end up with a lot of containers of pointers.
The default behavior of most C++ implementations is to replicate the code for template functions. This is good for runtime performance, but unless care is taken it leads to code bloat in critical cases such as the
V e c t o r example.
Fortunately, there is an obvious solution. Containers of pointers can share a single implementation. This can be expressed through specialization. First, we define a version (a specialization) of V e c t o r for pointers to v o i d :
t e m p l a t e <> c l a s s V e c t o r{
v o i d ** p ;
/ / ...
v o i d *& o p e r a t o r [](i n t i );
};
This specialization can then be used as the common implementation for all V e c t o r s of pointers.
The t e m p l a t e <> prefix says that this is a specialization that can be specified without a template parameter. The template arguments for which the specialization is to be used are specified in <> brackets after the name. That is, thesays that this definition is to be used as the implementation of every V e c t o r for which T is void* .
The V e c t o ris a complete specialization. That is, there is no template parameter to specify or deduce when we use the specialization; V e c t o r is used for V e c t o r s declared like this:
V e c t o rv p v ;
The general template must be declared before any specialization. For example:
t e m p l a t ec l a s s L i s t { /* ... */ };
t e m p l a t ec l a s s L i s t { /* ... */ }; // error: general template after specialization
Order of Specializations
One specialization is more specialized than another if every argument list that matches its specialization pattern also matches the other, but not vice versa. For example:
t e m p l a t ec l a s s V e c t o r ; // general
t e m p l a t ec l a s s V e c t o r ; // specialized for any pointer
t e m p l a t e <> c l a s s V e c t o r; // specialized for void*
Every type can be used as a template argument for the most general V e c t o r , but only pointers can be used for V e c t o rand only v o i d *s can be used for V e c t o r . The most specialized version will be preferred over the others in declarations of objects, pointers, etc., and in overload resolution.
A specialization pattern can be specified in terms of types composed using the constructs allowed for template parameter deduction.
Template Function Specialization
Naturally, specialization is also useful for template functions.
T e m p l a t eb o o l l e s s (T a , T b ) { r e t u r n a < b ; } can be specialized as t e m p l a t e <> b o o l l e s s (c o n s t c h a r * a , c o n s t c h a r * b )
{
r e t u r n s t r c m p (a ,b )<0 ; } Because the template argument can be deduced from the function argument list, we need not specify it explicitly. So, we could simplify the definition of the specialization: t e m p l a t e <> b o o l l e s s <>(c o n s t c h a r * a , c o n s t c h a r * b )
{
r e t u r n s t r c m p (a ,b )<0 ; } Given the t e m p l a t e <> prefix, the second empty <> is redundant, so we would typically simply write:
t e m p l a t e <> b o o l l e s s (c o n s t c h a r * a , c o n s t c h a r * b )
{
r e t u r n s t r c m p (a ,b )<0 ; } Derivation and Templates Templates and derivation are mechanisms for building new types out of existing ones, and generally for writing useful code that exploits various forms of commonality. Combinations of the two mechanisms are the basis for many useful techniques. Deriving a template class from a non template class is a way of providing a common implementation for a set of templates. Another way of looking at such examples is that a template is used to provide an elegant and type safe interface to an otherwise unsafe and inconvenient to use facility. Naturally, it is often useful to derive one template class from another. One use of a base class is as a building block in the implementation of further classes. If the data or operations in such a base class depend on a template parameter of a derived class, the base itself must be parameterized; t e m p l a t ec l a s s v e c t o r { /* ... */ };
t e m p l a t ec l a s s V e c : p u b l i c v e c t o r { /* ... */ };
The overload resolution rules for template functions ensure that functions work ‘‘correctly’’ for such derived types.
Having the same template parameter for the base and derived class is the most common case, but it is not a requirement. Interesting, although less frequently used, techniques rely on passing the derived type itself to the base class.
t e m p l a t ec l a s s B a s i c o p s { // basic operators on containers
b o o l o p e r a t o r ==(c o n s t C &) c o n s t ; // compare all elements
b o o l o p e r a t o r !=(c o n s t C &) c o n s t ;
/ / ...
};
t e m p l a t ec l a s s M a t h c o n t a i n e r : p u b l i c B a s i c o p s < M a t h c o n t a i n e r > {
p u b l i c :
s i z e t s i z e () c o n s t ;
T & o p e r a t o r [](s i z e t );
/ / ...
};
This allows the definition of the basic operations on containers to be separate from the definition of the containers themselves and defined once only. However, the definition of operations such as == and != must be expressed in terms of both the container and its elements, so the base class needs to be passed to the container template.
A class generated from a class template is a perfectly ordinary class. Consequently, it can have f r i e n d functions. In this case, I used f r i e n d s to achieve the conventional symmetric argument style for == and !=. One might also consider passing a template rather than a container as the C argument in such cases.
Parameterization and Inheritance
A template parameterizes the definition of a type or a function with another type. Code implementing the template is identical for all parameter types, as is most code using the template. An abstract class defines an interface. Much code for different implementations of the abstract class can be shared in class hierarchies, and most code using the abstract class doesn’t depend on its implementation. From a design perspective, the two approaches are so close that they deserve a common name. Since both allow an algorithm to be expressed once and applied to a variety of types, people sometimes refer to both as p o l y m o r p h i c . To distinguish them, what virtual functions provide is called runtime polymorphism, and what templates offer is called compile time polymorphism or parametric polymorphism.
So when do we choose to use a template and when do we rely on an abstract class? In either case, we manipulate objects that share a common set of operations. If no hierarchical relationship is required between these objects, they are best used as template arguments. If the actual types of these objects cannot be known at compile time, they are best represented as classes derived from a common abstract class. If runtime efficiency is at a premium, that is, if inlining of operations is essential, a template should be used.
Member Templates
A class or a class template can have members that are themselves templates.
A member template cannot be v i r t u a l .
This must be illegal. If it were allowed, the traditional virtual function table technique for implementing virtual functions could not be used. The linker would have to add a new entry to the virtual table for class Shape each time someone called i n t e r s e c t () with a new argument type.
Inheritance Relationships
A class template is usefully understood as a specification of how particular types are to be created. In other words, the template implementation is a mechanism that generates types when needed based on the user’s specification. Consequently, a class template is sometimes called a type generator.
As far as the C++ language rules are concerned, there is no relationship between two classes generated from a single class template so implicit conversions fromto is not possible.
Template Conversions
The example in the previous section demonstrates that there cannot be any default relationship between classes generated from the same templates. However, for some templates we would like to express such a relationship. For example, when we define a pointer template, we would like to reflect inheritance relationships among the objects pointed to. Member templates allow us to specify many such relationships where desired. Consider:
t e m p l a t ec l a s s P t r { // pointer to T
T * p ;
p u b l i c :
P t r (T *);
t e m p l a t eo p e r a t o r P t r (); // convert PtrTto PtrT2
/ / ...
};
Be careful to define logically meaningful conversions only.
Note that the template parameter lists of a template and its template member cannot be combined.
For example:
t e m p l a t e// error
P t r:: o p e r a t o r P t r () { r e t u r n P t r (p ); }
Advice
[1] Use templates to express algorithms that apply to many argument types.
[2] Use templates to express containers.
[3] Provide specializations for containers of pointers to minimize code size.
[4] Always declare the general form of a template before specializations.
[5] Declare a specialization before its use.
[6] Minimize a template definition’s dependence on its instantiation contexts.
[7] Define every specialization you declare.
[8] Consider if a template needs specializations for Cstyle strings and arrays.
[9] Parameterize with a policy object.
[10] Use specialization and overloading to provide a single interface to implementations of the same concept for different types.
[11] Provide a simple interface for simple cases and use overloading and default arguments to express less common cases.
[12] Debug concrete examples before generalizing to a template.
[13] Remember to e x p o r t template definitions that need to be accessible from other translation units.
[14] Separately compile large templates and templates with nontrivial context dependencies.
[15] Use templates to express conversions but define those conversions very carefully.
[16] Where necessary, constrain template arguments using a c o n s t r a i n t () member function.
[17] Use explicit instantiation to minimize compile time and link time.
[18] Prefer a template over derived classes when runtime efficiency is at a premium.
[19] Prefer derived classes over a template if adding new variants without recompilation is important.
[20] Prefer a template over derived classes when no common base can be defined.
[21] Prefer a template over derived classes when built in types and structures with compatibility constraints
Main tings to know about templates are
• The basic mechanisms for defining and using class templates
• Function templates, function overloading, and type deduction
• Template parameters used to specify policies for generic algorithms
• Multiple definitions providing alternative implementations for a template
• Derivation and templates (runtime and compile time polymorphism)
• Source code organization
A Simple String Template
template
The template
The name of a class template followed by a type bracketed by <> is the name of a class (as defined by the template) and can be used exactly like other class names.
String
Except for the special syntax of its name, String
In general, typedefs are useful for shortening the long names of classes generated from templates. Also, we often prefer not to know the details of how a type is defined, and a typedef allows us to hide the fact that a type is generated from a template.
Defining a Template
A class generated from a class template is a perfectly ordinary class. Thus, use of a template does not imply any runtime mechanisms beyond what is used for an equivalent ‘‘handwritten’’ class. Nor does it necessarily imply any reduction in the amount of code generated.
It is usually a good idea to debug a particular class, such as String, before turning it into a template such as String
Members of a template class are declared and defined exactly as they would have been for a non template class. A template member need not be defined within the template class itself. In that case, its definition must be provided somewhere else, as for non template class members. Members of a template class are themselves templates parameterized by the parameters of their template class. When such a member is defined outside its class, it must explicitly be declared a template.
template
C* s; / / pointer to elements
int sz; / / number of elements
int n; / / reference count
/ / ...
};
template
{
return rep->s[i] ;
}
template
{
p = new Srep(0,C()) ;
}
Template parameters, such as C, are parameters rather than names of types defined externally to the template. However, that doesn’t affect the way we write the template code using them. Within the scope of String
template
{
p = new Srep(0,C()) ;
}
Just as there can be only one function defining a class member function in a program, there can be only one function template defining a class template member function in a program. However, overloading is a possibility for functions only, while specialization enables us to provide alternative implementations for a template.
It is not possible to overload a class template name, so if a class template is declared in a scope, no other entity can be declared there with the same name.
Template Instantiation
The process of generating a class declaration from a template class and a template argument is often called template instantiation. Similarly, a function is generated (‘‘instantiated’’) from a template function plus a template argument. A version of a template for a particular template argument is called a specialization.
In general, it is the implementation’s job – not the programmer’s – to ensure that versions of a template function are generated for each set of template arguments used
Obviously, templates provide a powerful way of generating code from relatively short definitions. Consequently, a certain amount of caution is in order to avoid flooding memory with almost identical function definitions.
Template Parameters
A template can take type parameters, parameters of ordinary types such as ints, and template parameters. Naturally, a template can take several parameters. For example:
template
As shown, a template parameter can be used in the definition of subsequent template parameters. Integer arguments come in handy for supplying sizes and limits. For example:
template
T v[i] ;
int sz;
public:
Buffer() : sz(i) {}
/ / ...
};
Buffer
Buffer
A template argument can be a constant expression, the address of an object or function with external linkage, or a non overloaded pointer to member. A pointer used as a template argument must be of the form &of, where of is the name of an object or a function, or of the form f, where f is the name of a function. A pointer to member must be of the form &X::of where of is the name of an member. In particular, a string literal is not acceptable as a template argument.
An integer template argument must be a constant:
void f(int i)
{
Buffer
}
Conversely, a non type template parameter is a constant within the template so that an attempt to change the value of a parameter is an error.
Type Equivalence
Given a template, we can generate types by supplying template arguments.
String
String
String
When using the same set of template arguments for a template, we always refer to the same generated type. However, what does ‘‘the same’’ mean in this context? As usual, typedefs do not introduce new types, so String
Type Checking
A template is defined and then later used in combination with a set of template arguments. When the template is defined, the definition is checked for syntax errors and possibly also for other errors that can be detected in isolation from a particular set of template arguments.
A compiler can catch simple semantic errors at the point of definition or later at the point of use. Users generally prefer early detection, but not all ‘‘simple’’ errors are easy to detect. like a pointer T* cannot be initialized by the integer 7.
Errors that relate to the use of template parameters cannot be detected until the template is used.
The earliest that errors relating to a template parameter can be detected is at the first point of use of the template for a particular template argument. That point is usually called the first point of instantiation, or simply the point of instantiation. The implementation is allowed to postpone this checking until the program is linked.
Function Templates
For most people, the first and most obvious use of templates is to define and use container classes.
When a template function is called, the types of the function arguments determine which version of the template is used; that is, the template arguments are deduced from the function arguments.
Function Template Arguments
Function templates are essential for writing generic algorithms to be applied to a wide variety of container types. The ability to deduce the template arguments for a call from the function arguments is crucial. A compiler can deduce type and non type arguments from a call, provided the function argument list uniquely identifies the set of template arguments.
Note that class template parameters are never deduced. The reason is that the flexibility provided by several constructors for a class would make such deduction impossible in many cases and obscure in many more. Specialization provides a mechanism for implicitly choosing between different implementations of a class . If we need to create an object of a deduced type, we can often do that by calling a function to do the creation;
If a template argument cannot be deduced from the template function arguments, we must specify it explicitly. This is done in the same way template arguments are explicitly specified for a template class. For example:
i n t * p = c r e a t e < i n t >(); // function, template argument ‘int’
One common use of explicit specification is to provide a return type for a template function:
t e m p l a t e
v o i d g (i n t i )
{
i m p l i c i t c a s t (i ); // error: can’t deduce T
i m p l i c i t c a s t
i m p l i c i t c a s t
i m p l i c i t c a s t
}
As with default function arguments, only trailing arguments can be left out of a list of explicit template arguments.
Function Template Overloading
One can declare several function templates with the same name and even declare a combination of function templates and ordinary functions with the same name. When an overloaded function is called, overload resolution is necessary to find the right function or template function to invoke. For example:
t e m p l a t e
t e m p l a t e
d o u b l e s q r t (d o u b l e );
v o i d f (c o m p l e x
{
s q r t (2 ); // sqrtint(int)
sqrt(2.0) ; / / sqrt(double)
sqrt(z) ; / / sqrtdouble(complexdouble)
}
In the same way that a template function is a generalization of the notion of a function, the rules for resolution in the presence of function templates are generalizations of the function overload resolution rules. Basically, for each template we find the specialization that is best for the set of function arguments. Then, we apply the usual function overload resolution rules to these specializations and all ordinary functions:
[1] Find the set of function template specializations that will take part in overload resolution. Do this by considering each function template and deciding which template arguments, if any, would be used if no other function templates or functions of the same name were in scope. For the call s q r t (z ), this makes
s q r t
s q r t < c o m p l e x
[2] If two template functions can be called and one is more specialized than the other, consider only the most specialized template function in the following steps. For the call
s q r t (z ), this means that s q r t
also matches s q r t
[3] Do overload resolution for this set of functions, plus any ordinary functions as for ordinary functions. If a template function argument has been determined by template argument deduction, that argument cannot also have promotions, standard conversions, or user defined conversions applied. For s q r t (2 ), s q r t < i n t >(i n t ) is an exact match, so it is preferred over s q r t (d o u b l e ).
[4] If a function and a specialization are equally good matches, the function is preferred. Consequently,
s q r t (d o u b l e ) is preferred over s q r t
[5] If no match is found, the call is an error. If we end up with two or more equally good matches, the call is ambiguous and is an error.
Specialization
By default, a template gives a single definition to be used for every template argument (or combination of template arguments) that a user can think of. This doesn’t always make sense for someone writing a template. I might want to say, ‘‘if the template argument is a pointer, use this implementation; if it is not, use that implementation’’ or ‘‘give an error unless the template argument is a pointer derived from class
M y b a s e .’’ Many such design concerns can be addressed by providing alternative definitions of the template and having the compiler choose between them based on the template arguments provided where they are used. Such alternative definitions of a template are called user defined specializations, or simply, user specializations.
Consider likely uses of a V e c t o r template:
t e m p l a t e
T * v ;
i n t s z ;
p u b l i c :
V e c t o r ();
V e c t o r (i n t );
T & e l e m (i n t i ) { r e t u r n v [i ]; }
T & o p e r a t o r [](i n t i );
v o i d s w a p (V e c t o r &);
/ / ...
};
V e c t o r < i n t > v i ;
V e c t o r < S h a p e *> v p s ;
V e c t o r < s t r i n g > v s ;
V e c t o r < c h a r *> v p c ;
V e c t o r < N o d e *> v p n ;
Most V e c t o r s will be V e c t o r s of some pointer type. There are several reasons for this, but the primary reason is that to preserve runtime polymorphic behavior, we must use pointers. That is, anyone who practices object oriented programming and also uses typesafe containers (such as the standard library containers) will end up with a lot of containers of pointers.
The default behavior of most C++ implementations is to replicate the code for template functions. This is good for runtime performance, but unless care is taken it leads to code bloat in critical cases such as the
V e c t o r example.
Fortunately, there is an obvious solution. Containers of pointers can share a single implementation. This can be expressed through specialization. First, we define a version (a specialization) of V e c t o r for pointers to v o i d :
t e m p l a t e <> c l a s s V e c t o r
v o i d ** p ;
/ / ...
v o i d *& o p e r a t o r [](i n t i );
};
This specialization can then be used as the common implementation for all V e c t o r s of pointers.
The t e m p l a t e <> prefix says that this is a specialization that can be specified without a template parameter. The template arguments for which the specialization is to be used are specified in <> brackets after the name. That is, the
The V e c t o r
V e c t o r
The general template must be declared before any specialization. For example:
t e m p l a t e
t e m p l a t e
Order of Specializations
One specialization is more specialized than another if every argument list that matches its specialization pattern also matches the other, but not vice versa. For example:
t e m p l a t e
t e m p l a t e
t e m p l a t e <> c l a s s V e c t o r
Every type can be used as a template argument for the most general V e c t o r , but only pointers can be used for V e c t o r
A specialization pattern can be specified in terms of types composed using the constructs allowed for template parameter deduction.
Template Function Specialization
Naturally, specialization is also useful for template functions.
T e m p l a t e
{
r e t u r n s t r c m p (a ,b )<0 ; } Because the template argument can be deduced from the function argument list, we need not specify it explicitly. So, we could simplify the definition of the specialization: t e m p l a t e <> b o o l l e s s <>(c o n s t c h a r * a , c o n s t c h a r * b )
{
r e t u r n s t r c m p (a ,b )<0 ; } Given the t e m p l a t e <> prefix, the second empty <> is redundant, so we would typically simply write:
t e m p l a t e <> b o o l l e s s (c o n s t c h a r * a , c o n s t c h a r * b )
{
r e t u r n s t r c m p (a ,b )<0 ; } Derivation and Templates Templates and derivation are mechanisms for building new types out of existing ones, and generally for writing useful code that exploits various forms of commonality. Combinations of the two mechanisms are the basis for many useful techniques. Deriving a template class from a non template class is a way of providing a common implementation for a set of templates. Another way of looking at such examples is that a template is used to provide an elegant and type safe interface to an otherwise unsafe and inconvenient to use facility. Naturally, it is often useful to derive one template class from another. One use of a base class is as a building block in the implementation of further classes. If the data or operations in such a base class depend on a template parameter of a derived class, the base itself must be parameterized; t e m p l a t e
t e m p l a t e
The overload resolution rules for template functions ensure that functions work ‘‘correctly’’ for such derived types.
Having the same template parameter for the base and derived class is the most common case, but it is not a requirement. Interesting, although less frequently used, techniques rely on passing the derived type itself to the base class.
t e m p l a t e
b o o l o p e r a t o r ==(c o n s t C &) c o n s t ; // compare all elements
b o o l o p e r a t o r !=(c o n s t C &) c o n s t ;
/ / ...
};
t e m p l a t e
p u b l i c :
s i z e t s i z e () c o n s t ;
T & o p e r a t o r [](s i z e t );
/ / ...
};
This allows the definition of the basic operations on containers to be separate from the definition of the containers themselves and defined once only. However, the definition of operations such as == and != must be expressed in terms of both the container and its elements, so the base class needs to be passed to the container template.
A class generated from a class template is a perfectly ordinary class. Consequently, it can have f r i e n d functions. In this case, I used f r i e n d s to achieve the conventional symmetric argument style for == and !=. One might also consider passing a template rather than a container as the C argument in such cases.
Parameterization and Inheritance
A template parameterizes the definition of a type or a function with another type. Code implementing the template is identical for all parameter types, as is most code using the template. An abstract class defines an interface. Much code for different implementations of the abstract class can be shared in class hierarchies, and most code using the abstract class doesn’t depend on its implementation. From a design perspective, the two approaches are so close that they deserve a common name. Since both allow an algorithm to be expressed once and applied to a variety of types, people sometimes refer to both as p o l y m o r p h i c . To distinguish them, what virtual functions provide is called runtime polymorphism, and what templates offer is called compile time polymorphism or parametric polymorphism.
So when do we choose to use a template and when do we rely on an abstract class? In either case, we manipulate objects that share a common set of operations. If no hierarchical relationship is required between these objects, they are best used as template arguments. If the actual types of these objects cannot be known at compile time, they are best represented as classes derived from a common abstract class. If runtime efficiency is at a premium, that is, if inlining of operations is essential, a template should be used.
Member Templates
A class or a class template can have members that are themselves templates.
A member template cannot be v i r t u a l .
This must be illegal. If it were allowed, the traditional virtual function table technique for implementing virtual functions could not be used. The linker would have to add a new entry to the virtual table for class Shape each time someone called i n t e r s e c t () with a new argument type.
Inheritance Relationships
A class template is usefully understood as a specification of how particular types are to be created. In other words, the template implementation is a mechanism that generates types when needed based on the user’s specification. Consequently, a class template is sometimes called a type generator.
As far as the C++ language rules are concerned, there is no relationship between two classes generated from a single class template so implicit conversions from
Template Conversions
The example in the previous section demonstrates that there cannot be any default relationship between classes generated from the same templates. However, for some templates we would like to express such a relationship. For example, when we define a pointer template, we would like to reflect inheritance relationships among the objects pointed to. Member templates allow us to specify many such relationships where desired. Consider:
t e m p l a t e
T * p ;
p u b l i c :
P t r (T *);
t e m p l a t e
/ / ...
};
Be careful to define logically meaningful conversions only.
Note that the template parameter lists of a template and its template member cannot be combined.
For example:
t e m p l a t e
P t r
Advice
[1] Use templates to express algorithms that apply to many argument types.
[2] Use templates to express containers.
[3] Provide specializations for containers of pointers to minimize code size.
[4] Always declare the general form of a template before specializations.
[5] Declare a specialization before its use.
[6] Minimize a template definition’s dependence on its instantiation contexts.
[7] Define every specialization you declare.
[8] Consider if a template needs specializations for Cstyle strings and arrays.
[9] Parameterize with a policy object.
[10] Use specialization and overloading to provide a single interface to implementations of the same concept for different types.
[11] Provide a simple interface for simple cases and use overloading and default arguments to express less common cases.
[12] Debug concrete examples before generalizing to a template.
[13] Remember to e x p o r t template definitions that need to be accessible from other translation units.
[14] Separately compile large templates and templates with nontrivial context dependencies.
[15] Use templates to express conversions but define those conversions very carefully.
[16] Where necessary, constrain template arguments using a c o n s t r a i n t () member function.
[17] Use explicit instantiation to minimize compile time and link time.
[18] Prefer a template over derived classes when runtime efficiency is at a premium.
[19] Prefer derived classes over a template if adding new variants without recompilation is important.
[20] Prefer a template over derived classes when no common base can be defined.
[21] Prefer a template over derived classes when built in types and structures with compatibility constraints
No comments:
Post a Comment