A template is a mold from which the compiler generates a family of classes or functions. C++ programming styles and concepts have changed considerably since the first implementation of templates back in 1991 (in cfront 2.0). Initially, templates were viewed as a support for generic container classes such as Array and List. In recent years, the experience of using templates has shown that this feature is most useful in designing and implementing general-purpose libraries such as the Standard Template Library. Templatized libraries and frameworks are both efficient and portable. With the widespread usage of templates, C++ has added more sophisticated constructs to control their behavior and performance, including partial specializations, explicit specializations, template members, exported templates, default type arguments, and more.
This chapter discusses various aspects of designing and implementing templates. First, class templates are explained. Function templates come next. Finally, template issues of special concern -- such as pointers to members, virtual member functions within a template class, inheritance relations, and explicit instantiations -- are discussed.
Many algorithms and data structures can be defined independently of the concrete data type that they manipulate. Often, the reliance on a hardwired data type is merely a programming artifact. The concept of a complex number, for instance, is not exclusively limited to the fundamental type double. Rather, it is applicable to every floating-point type. Designing a type-independent class that abstracts the concept of a complex number has many advantages because it enables users to choose the desired level of precision for a specific application without having to reduplicate code manually. In addition, type-independent classes are more portable among different platforms and locales.
A class template is declared using the keyword template, followed by a template parameter list that is enclosed in angular brackets and a declaration or a definition of the class. For example
template <class T> class Vector; //declaration
template <class T> class Vector //definition
{
private:
size_t sz;
T * buff;
public:
explicit Vector<T>(size_t s = 100);
Vector<T> (const Vector <T> & v); //copy constructor
Vector<T>& operator= (const Vector<T>& v); //assignment operator
~Vector<T>(); //destrcutor
//other member functions
T& operator [] (unsigned int index);
const T& operator [] (unsigned int index) const;
size_t size() const;
};
Member functions of a class template can be defined outside the class body. In this case, they have to be explicitly declared as member functions of their class template. For example
//definitions of Vector's member functions
//follow the class declaration
template <class T> Vector<T>::Vector<T> (size_t s) //constructor definition
: sz(s),
buff (new T[s])
{}
template <class T> Vector<T>::Vector<T> (const Vector <T> & v) //copy ctor
{
sz = 0;
buff = 0;
*this = v; //use overloaded assignment operator
}
template <class T> Vector<T>& Vector<T>::operator= // assignment operator
(const Vector <T> & v)
{
if (this == &v)
return *this;
this->Vector<T>::~Vector<T>(); //call destructor
buff = new T[v.size()]; //allocate sufficient storage
for (size_t i =0; i < v.size(); i++)
buff[i] = v[i]; //memberwise copy
sz = v.size();
return *this;
}
template <class T> Vector<T>::~Vector<T> () //destructor
{
delete [] buff;
}
template <class T> inline T& Vector<T>::operator [] (unsigned int i)
{
return buff[i];
}
template <class T> inline const T& Vector<T>::operator [] //const version
(unsigned int i) const
{
return buff[i];
}
template <class T> inline size_t Vector<T>::size () const
{
return sz;
}
//Vector.hpp
The prefix template <class T> indicates that T is a template parameter, which is a placeholder for a yet unspecified type. The keyword class is of particular interest because the corresponding argument for the parameter T is not necessarily a user-defined type; it can also be a fundamental type, such as char or int. If you prefer a more neutral term, you can use the typename keyword instead (typename also has other uses, though, as you will see next):
template <typename T> class Vector //typename instead of class
//no semantic difference between the two forms
{
//...
};
template <typename T> Vector<T>::Vector<T> (size_t s)
: sz(s), buff (new T[s]) {}
Within the scope of Vector, qualification with the parameter T is redundant, so the member functions can be declared and defined without it. The constructor, for example, can be declared as follows:
template <class T> class Vector
{
public:
Vector (size_t s = 100); // equivalent to Vector <T>(size_t s = 100);
};
Similarly, the constructor's definition can omit the redundant parameter:
// equivalent to template <class T> Vector<T>::Vector<T>(size_t s)
template <class T> Vector<T>::Vector (size_t s) :
buff (new T[s]), sz(s)
{}
A class template is not a class. The process of instantiating a class from a class template and a type argument is called template instantiation. A template id, that is, a template name followed by a list of arguments in angular brackets (for example, Vector<int>), is called a specialization. A specialization of a class template can be used exactly like any other class. Consider the following examples:
void func (Vector <float> &); //function parameter
size_t n = sizeof( Vector <char>); //sizeof expression
class myStringVector: private Vector<std::string> //base class
{/*...*/};
#include <iostream>
#include <typeinfo>
#include <string>
using namespace std;
cout<<typeid(Vector< string>).name(); //typeid expression
Vector<int> vi; // creating an object
The compiler instantiates only the necessary member functions of a given specialization. In the following example, points of member instantiation are numbered:
#include <iostream>
#include "Vector.hpp"
using namespace std;
int main()
{
Vector<int> vi(5); // 1
for (int i = 0; i<5; i++)
{
vi[i] = i; //fill vi // 2
cout<<vi[i]<<endl;
}
return 0; // 3
}
The compiler generates code only for the following Vector member functions, which are used either explicitly or implicitly in the program:
Vector<int>::Vector<int> (size_t s) //1: constructor
: sz(s), buff (new int[s]) {}
inline int& Vector<int>::operator [] (unsigned int idx) //2: operator []
{
return buff[idx];
}
Vector<int>::~Vector<int> () //3: destructor
{
delete [] buff;
}
In contrast, code for the member function size_t Vector<int>::size() const is not generated by the compiler because it is not required. For some compilers, it might be simpler to instantiate all the class members at once whether they are needed or not. However, the "generate on demand" policy is a Standard requirement, and has two functions:
Efficiency -- It is not uncommon for certain class templates to define hundreds of member functions (STL containers, for example); normally, however, fewer than a dozen of these are actually used in a program. Generating the code for unused member functions times the number of specializations used in the program can easily bloat the size of the executable -- and it might unnecessarily increase compilation and linkage time.
Flexibility -- In some cases, not every type supports all the operations that are defined in a class template. For example, a container class can use ostream's operator << to display members of fundamental types such as char and int and user-defined types for which an overloaded version of << is defined. However, a POD (plain old data) struct for which no overloaded version of << exists can still be stored in such a container as long as the << is not invoked.
A template can take type parameters, that is, symbols that represent an as yet unspecified type. For example
template <class T > class Vector {/*...*/};
A template can also take ordinary types such as int and long as parameters:
template <class T, int n> class Array
{
private:
T a[n];
int size;
public:
Array() : size (n){}
T& operator [] (int idx) { return a[idx]; }
};
Note, however, that when an ordinary type is used as a parameter, the template argument must be a constant or a constant expression of an integral type. For example
void array_user()
{
const int cn = 5;
int num = 10;
Array<char, 5> ac; // OK, 5 is a const
Array<float, cn> af; // OK, cn is const
Array<unsigned char, sizeof(float)> auc; // OK, constant expression used
Array<bool, num> ab; // error, num is not a constant
}
Besides constant expressions, other arguments that are allowed are a non-overloaded pointer to member and the address of an object or a function with external linkage. This also implies that a string literal cannot be used as a template argument because it has internal linkage. For example:
template <class T, const char *> class A
{/*...*/};
void array_user()
{
const char * p ="illegal";
A<int, "invalid"> aa; // error, string literal used as a template argument
A<int, p> ab; // also an error, p doesn't have external linkage
}
A template can take a template as an argument. For example
int send(const Vector<char*>& );
int main()
{
Vector <Vector<char*> > msg_que(10); //a template used as an argument
//...fill msg_que
for (int i =0; i < 10; i++) //transmit messages
send(msg_que[i]);
return 0;
}
Note that when a template is used as an argument, the space between the left two angular brackets is mandatory:
Vector <Vector<char*> > msg_que(10);
Otherwise, the >> sequence is parsed as the right shift operator.
A typedef can be used to avert this mishap and improve readability, both for the compiler and for the human reader:
typedef Vector<char *> msg; Vector<msg> msg_que;
Class templates can have default type arguments.
As with default argument values of a function, the default type of a template gives the programmer more flexibility in choosing the optimal type for a particular application. For instance, the Vector template can be optimized for special memory management tasks. Instead of using the hard-coded size_t type for storing the size of a Vector, it can have a size type as a parameter. For most purposes, the default type size_t is used. However, for managing extremely large memory buffers on the one hand -- or very small ones on the other hand -- the programmer is free to choose other suitable data types instead. For example
template <class T, class S = size_t > class Vector
{
private:
S sz;
T * buff;
public:
explicit Vector(S s = 100): sz(s), buff(new T[s]){}
~Vector();
//other member functions
S size() const;
};
template <class T, class S> Vector<T,S>::~Vector<T,S>()//destructor definition
{
delete [] buff;
}
template <class T, class S> S Vector<T,S>::size() const
{
return sz;
}
int main()
{
Vector <int> ordinary;
Vector <int, unsigned char> tiny(5);
return 0;
}
An additional advantage of a default size type is the capability to support implementation-dependent types. On a machine that supports 64-bit integers, for instance, programmers can use Vector to easily manipulate very large memory buffers:
Vector <int, unsigned __int64> very_huge;
The fact that the programmer does not have to make any changes to the definition of Vector to get the appropriate specialization cannot be overemphasized. Without templates, such a high level of automation is very difficult to achieve.
Templates can have static data members. For example
template<class T> class C
{
public:
static T stat;
};
template<class T> T C<T>::stat = 5; //definition
A static data member can be accessed as follows:
void f()
{
int n = C<int>::stat;
}
A friend of a class template can be a function template or class template, a specialization of a function template or class template, or an ordinary (nontemplate) function or class. The following sections discuss the various types of friendship that a class template can have.
Nontemplate friend declarations of a class template look quite similar to friend declarations of a nontemplate class. In the following example, the class template Vector declares the ordinary function f() and class Thing as its friends:
class Thing;
template <class T> class Vector
{
public:
//...
friend void f ();
friend class Thing;
};
Each specialization of Vector has the function f() and class Thing as friends.
You can declare a specialization as a friend of a class template. In the following example, the class template Vector declares the specialization C<void*> as its friend:
template <class T> class C{/*...*/};
template <class T> class Vector
{
public:
//...
friend class C<void*>; //other specializations are not friends of Vector
};
A friend of a class template can be a template by itself. For instance, you can declare a class template as a friend of another class template:
template <class U> class D{/*...*/};
template <class T> class Vector
{
public:
//...
template <class U> friend class D;
};
Every specialization of D is a friend of every specialization of Vector. You can also declare a function template as a friend (function templates will be discussed in further detail shortly). For instance, you might add an overloaded operator == function template to test the equality of two Vector objects. Consequently, for every specialization of Vector, the implementation will generate a corresponding specialization of the overloaded operator ==. In order to declare a friend template function, you first have to forward declare the class template and the friend function template as follows:
template <class T> class Vector; // class template forward declaration // forward declaration of the function template to be used as a friend template <class T> bool operator== (const Vector<T>& v1, const Vector<T>& v2);
Next, the friend function template is declared inside the class body:
template <class T> class Vector
{
public:
//...
friend bool operator==<T> (const Vector<T>& v1, const Vector<T>& v2);
};
Finally, the friend function template is defined as follows:
template <class T> bool operator== (const Vector<T>& v1, const Vector<T>& v2)
{
// two Vectors are equal if and only if:
// 1) they have the same number of elements;
// 2) every element in one Vector is identical to the
// corresponding element in the second one
if (v1.size() != v2.size())
return false;
for (size_t i = 0; i<v1.size(); i++)
{
if(v1[i] != v2[i])
return false;
}
return true;
}
It is possible to define a partial specialization of a class template. A partial specialization provides an alternative definition of the primary template. It is used instead of the primary definition when the arguments in any specialization match those that are given in the partial specialization. For instance, a partial specialization of Vector can handle pointer types exclusively. Thus, for specializations of fundamental types and user-defined types, the primary Vector class is used. For pointers, the partial specialization is used instead of the primary class template. A pointer partial specialization can optimize the manipulation of pointers in several ways.
In addition, some operations that manipulate pointers involve dereferencing and the use of operator ->, neither of which is used with non-pointer types.
A partial specialization is defined as follows:
//filename: Vector.hpp
template <class T> class Vector <T*> //partial specialization of Vector <T>
{
private:
size_t size;
void * p;
public:
Vector();
~Vector();
//...member functions
size_t size() const;
};
//Vector.hpp
A partial specialization is indicated by the parameter list that immediately follows the class template name (remember that the primary template is declared without the list after its name). Compare these two forms:
template <class T> class Vector //primary template
{};
template <class T> class Vector <T*> //partial specialization
{};
Partial specializations of a class template that has several parameters are declared as follows:
template<class T, class U, int i> class A { }; // primary
template<class T, int i> class A<T, T*, i> { }; // partial specialization
template<class T> class A<int, T*, 8> { }; // another partial specialization
Partial specializations must appear after the primary declaration of a class template, and its parameter cannot contain default types.
An explicit specialization of a class template provides an alternative definition of the primary template. It is used instead of the primary definition if the arguments in a particular specialization match those that are given in the explicit specialization. When is it useful? Consider the Vector template: The code that is generated by the compiler for the specialization Vector<bool> is very inefficient. Instead of storing every Boolean value in a single bit, it occupies at least an entire byte. When you are manipulating large amounts of bits, for example in logical operations or digital signal processing, this is unacceptable. In addition, bit-oriented operations can be performed more efficiently using the bitwise operators. Obviously, there are significant advantages to defining a Vector template that is specifically adjusted to manipulate bits. Following is an example of an explicit specialization Vector<bool> that manipulates bits rather than bytes:
template <> class Vector <bool> //explicit specialization
{
private:
size_t sz;
unsigned char * buff;
public:
explicit Vector(size_t s = 1) : sz(s),
buff (new unsigned char [(sz+7U)/8U] ) {}
Vector<bool> (const Vector <bool> & v);
Vector<bool>& operator= (const Vector<bool>& v);
~Vector<bool>();
//other member functions
bool& operator [] (unsigned int index);
const bool& operator [] (unsigned int index) const;
size_t size() const;
};
void bitmanip()
{
Vector< bool> bits(8);
bits[0] = true; //assign
bool seventh = bits[7]; //retrieve
}
The template<> prefix indicates an explicit specialization of a primary template. The template arguments for a specialization are specified in the angular brackets that immediately follow the class name. The specialization hierarchy of Vector that has been defined thus far is as follows:
template <class T> class Vector //primary template
{};
template <class T> class Vector <T*> //partial specialization
{};
template <> class Vector <bool> //explicit specialization
{};
Fortunately, the Standard Template Library already defines a specialization of std::vector<bool> for manipulating bits optimally, as you will read in the next chapter, "STL and Generic Programming."
The overloaded operator == of class Vector performs a plausible comparison between two Vector objects when their elements are either fundamental types or objects that overload operator ==. However, a comparison of two objects that store C strings is likely to yield the wrong result. For example
#include "Vector.hpp"
extern const char msg1[] = "hello";
extern const char msg2[] = "hello";
int main()
{
Vector<const char *> v1(1), v2(1); //the same number of elements
v1[0] = msg1;
v2[0] = msg2;
bool equal = (v1 == v2); //false, strings are equal but pointers aren't
return 0;
}
NOTE: Whether identical string literals are treated as distinct objects is implementation-dependent. Some implementations might store the constants msg1 and msg2 at the same memory address (on such implementations, the expression bool equal = (v1 == v2); yields true). However, the discussion here assumes that msg1 and msg2 are stored in two distinct memory addresses.
Although v1 and v2 have the same number of elements and their elements hold the same string value, operator == returns false because it compares the addresses of the strings rather than the strings themselves. You can alter this behavior by defining a specialized version of operator == for type const char * exclusively, which compares the strings rather than their addresses. The compiler picks the specialized version only when objects of type Vector<const char *> are compared. Otherwise, it uses the primary version of operator ==. It is not necessary to add the declaration of the specialized friend operator == in the declaration of the template class Vector. However, it is still recommended that you do so in order to document the existence of a specialized operator ==. For example
template <class T> class Vector;
template <class T> bool operator== (const Vector<T>& v1, const Vector<T>& v2);
template <class T> class Vector
{
//...
public:
friend bool operator==<T> (const Vector<T>& v1,
const Vector<T>& v2); // primary
friend bool operator== ( //specialized version
const Vector<const char *>& v1,
const Vector<const char *>& v2);
};
The definition of the specialized function must appear after the generic version. Therefore, you place it at the same header file, right after the generic version. Following is the specialized version:
//appended to vector.hpp
#include <cstring> //needed for strcmp
using namespace std;
template <> bool operator== (
const Vector<const char *>& v1,
const Vector<const char *>& v2 )
{
if (v1.size() != v2.size()) //as before
return false;
for (size_t i = 0; i<v1.size(); i++)
{
if (strcmp(v1[i], v2[i]) != 0) //compare string values
return false;
}
return true;
}
Here again, the empty angular brackets that follow the keyword template indicate a specialized version that overrides a previously defined generic version. The compiler now uses the specialized form of operator == to compare v1 and v2; as expected, the result is now true.
Specialized functions operate in a way that resembles the behavior of virtual member functions in a derived class. In both cases, the actual function that is being called depends on the type. However, the virtual dispatch mechanism relies on the dynamic type of the object, whereas template function specializations are resolved statically.
Many algorithms perform a sequence of identical operations, regardless of the data type they manipulate. min and max, array sort, and swap are examples of such type-independent algorithms. In the pre-template era, programmers had to use alternative techniques to implement generic algorithms:-- macros, void pointers, and a common root base -- all of which incurred significant drawbacks. This section exemplifies the drawbacks of these techniques and then demonstrates how function templates are used in implementing generic algorithms.
Function-like macros were the predominant form of implementing generic algorithms in C. For example
#define min(x,y) ((x)<(y))?(x):(y)
void f()
{
double dlower = min(5.5, 5.4);
int ilower = min(sizeof(double), sizeof(int));
char clower = min('a', 'b');
}
The C Standard library defines various function-like macros. To some extent, they can be used effectively because they avoid the overhead that is associated with a full-blown function call. However, macros have significant drawbacks as well. The preprocessor macro expansion is a simple text substitution, with very limited awareness of scope rules and type-checking. Furthermore, macros are notoriously hard to debug because the compiler scans a source file that might look very different from the original file. For this reason, compiler diagnostics can refer to code that the original source file does not contain. Macros can easily bloat the size of a program because every macro call is expanded inline. When large macros are called repeatedly, the result can be a dramatic increase in the size of the program. In spite of the syntactic similarity, macros are semantically very different from functions -- they have no linkage, address, or storage type. For these reasons, use macros sparingly -- if at all.
An alternative approach to macros is the use of a generic pointer, void *, which can hold the address of any data type. The C standard library defined two generic functions that rely on this feature: qsort and bsearch. qsort is declared in the header <stdlib.h> as follows:
void qsort( void *,
size_t,
size_t,
int (*) (const void *, const void *)
);
The type-unawareness of these generic functions is achieved by using void pointers and an abstract, user-defined comparison function. Still, there are noticeable limitations to this technique. void pointers are not type-safe, and the repeated function callbacks impose runtime overhead that, in most cases, cannot be avoided by inlining.
In some other object-oriented languages, every object is ultimately derived from a common base class (this design approach and its deficiencies in C++ are described in further detail in Chapter 5, "Object-Oriented Programming and Design"). Generic algorithms can rely on this feature. For example
// pseudo C++ code
class Object // a common root class
{
public:
virtual bool operator < (const Object&) const; //polymorphic behavior
//..other members
};
const Object& min(const Object &x, const Object& y)
{
return x.operator<(y) ? x : y; //x and y can be objects of any class type
}
Imitating this approach in C++ is not as useful as it is in other languages, though. C++ does not force a common root class. Therefore, it is the programmer's -- not the implementation's -- responsibility to ensure that every class is derived from a common base. Worse yet, the common root class is not standardized. Thus, such algorithms are not portable. In addition, these algorithms cannot handle fundamental types because they are limited to class objects exclusively. Finally, the extensive use of runtime type checking imposes an unacceptable performance on general-purpose algorithms.
Function templates are free from all these drawbacks. They are type-safe, they can be inlined by the compiler to boost performance, and -- most importantly -- they are applicable to fundamental types and user-defined types alike.
A function template declaration contains the keyword template, followed by a list of template parameters and a function declaration. As opposed to ordinary functions, which are usually declared in one translation unit and defined in another, the definition of a function template follows its declaration. For example
template <class T> T max( T t1, T t2)
{
return (t1 > t2) ? t1 : t2;
}
Unlike class templates, function template parameters are implicitly deduced from the type of their arguments.
In the following example, the compiler instantiates three distinct specializations of swap, according to the type of arguments used in each invocation:
#include <string>
using namespace std;
int main()
{
int i = 0, j = 8;
char c = 'a', d = 'z';
string s1 = "first", s2 = "second";
int nmax = max(i, j); // int max (int, int);
char cmax = max(c, d); // char max (char, char);
string smax = max(s1, s2); // string max (string, string);
return 0;
}
It is possible to define several function templates with the same name (that is, to overload it) or to combine ordinary functions with function templates that have the same name. For example
template <class T> T max( T t1, T t2)
{
return (t1 > t2) ? t1 : t2;
}
int max (int i, int j)
{
return (i > j) ? i : j;
}
The compiler does not generate an int version of max(). Instead, it invokes the function int max (int, int) when max() is called with arguments of type int.
C++ provides several facilities for controlling the instantiation of templates, including explicit instantiation of templates and exported templates. The following sections demonstrate how to use these features, as well as other techniques to enhance performance.
Two templates are equivalent (that is, they refer to the same template id) when all the following conditions hold:
Name equivalence -- The names of the templates are identical and they refer to the same template.
Argument Equivalence -- The type arguments of the templates are the same.
Identical non-Type Arguments -- The non-type arguments of integral or enumeration type of both templates have identical values, and their non-type arguments of pointer or reference type refer to the same external object or function.
Template-template Arguments -- The template-template arguments of both templates refer to the same template.
Following are some examples:
template<class T, long size> class Array
{ /* ... */ };
void func()
{
Array<char, 2*512> a;
Array<char, 1024> b;
}
The compiler evaluates constant expressions such as 2*512, so templates a and b are of the same type. Following is another example:
template<class T, int(*error_code_fct)()> class Buffer
{ /* ... */ };
int error_handler();
int another_error_handler();
void func()
{
Buffer<int, &error_handler> b1;
Buffer<int, &another_error_handler> b2;
Buffer<int, &another_error_handler> b3;
Buffer<unsigned int, &another_error_handler> b4;
}
b2 and b3 are of the same type because they are instances of the same template and they take the same type and non-type arguments. Conversely, b1 and b4 are of distinct types.
The function func() instantiated three distinct specializations from the same class template: one for b1, a second for b2 and b3, and a third for b4. Unlike ordinary function overloading, the compiler generates a distinct class from the template for every unique type. On machines that have the same underlying representation for long and int types, the following code still results in the instantiation of two distinct templates:
void too_prolific()
{
Buffer<int, &error_handler> buff1;
Buffer<long, &error_handler> buff2;
}
Similarly, char and unsigned char are distinct types, even on machines that treat char as unsigned by default. Programmers who are accustomed to the lenient matching rules of ordinary function overloading are not always aware of the potential code bloat that can result from using templates with very similar yet distinct types.
In the following example, three distinct copies of the template min are generated -- one for each type that is used:
template < class T > T min(T f, T s)
{
return f < s? f: s;
}
void use_min()
{
int n = 5, m= 10;
int j = min(n,m); //min<int> instantiated
char c = 'a', d = 'b';
char k = min(c,d); //min<char> instantiated
short int u = 5, v = 10;
short int w = min(u,v); // min<short int> instantiated
}
On the other hand, an ordinary function avoids the automatic generation of redundant specializations:
int min(int f, int s)
{
return f < s? f: s;
}
void use_min()
{
// all three invocation of min
// use int min (int, int);
int n = 5, m= 10;
int j = min(n,m);
char c = 'a', d = 'b';
char k = min(c,d);
short int u = 5, v = 10;
short int w = min(u,v);
}
Still, the template version of min has a clear advantage over the function: It can handle pointers and any other user-defined types. You want the benefits of a template while avoiding the unnecessary generation of specializations. How can these be avoided? A simple solution is to safely cast the arguments into one common type before invoking the function template. For example:
void no_proliferation()
{
short n = 5, m= 10;
int j = min( static_cast<int> (n),
static_cast<int> (m) ); //min<int> instantiated
char c = 'a', d = 'b';
char k = static_cast<char> (min( static_cast<int> ,
static_cast<int> ) ); //min<int> used
}
This technique can also be applied to pointers: First, they have to be cast to void *, and then they must be cast back to their original type. When you are using pointers to polymorphic objects, pointers to derived objects are cast to pointers to a base class.
For very small templates such as min, casting the arguments into a common denominator type is not worth the trouble. Nonetheless, when nontrivial templates that contain hundreds of code lines are used, you might consider doing so.
As was previously noted, templates are instantiated only if they are used in the program. Generally, compilers generate the necessary code for a specialization when they encounter its use in the source file. When large applications that consist of hundreds of source files have to be compiled, this can cause a significant increase in compilation time because the compiler's processing is repeatedly interrupted when it has to generate code for sporadic specializations. The recurrent interruption can occur in almost every source file because they use -- almost without exception -- template classes of the Standard Library. Consider a simple project that consists of only three source files:
//filename func1.cpp
#include <string>
#include <iostream>
using namespace std;
void func1()
{
string s; //generate default constructor and destructor
s = "hello"; //generate assignment operator for const char *
string s2;
s2 = s; // generate operator = const string&, string&
cout<<s2.size(); // generate string::size, ostream& operator <<(int)
}
//func1.cpp
//filename func2.cpp
#include <string>
#include <iostream>
using namespace std;
void func2()
{
string s; //generate default constructor and destructor
cout<<"enter a string: "<<endl; //generate ostream& operator<<(const char *)
cin>>s //generate istream& operator>>(string&)
}
//func2.cpp
//filename main.cpp
int main()
{
func1();
func2();
retrun 0;
}
// main.cpp
The compilation time can be reduced if all the necessary template code is instantiated all at once, thereby avoiding the repeated interruption of the compiler's processing. For this purpose, you can use an explicit instantiation. An explicit instantiation is indicated by the keyword template (without the <>), followed by a template declaration. Here are a few examples of explicit template instantiations:
template <class T> class A{/*..*/};
template<class T> void func(T&) { }
//filename instantiations.hpp
template class Vector<short>; //explicit instantiation of a class template
template A<int>::A<int>(); //explicit instantiation of a member function
template class
std::basic_string<char>; //explicit instantiation of a namespace member
template void func<int>(int&); //explicit instantiation of a function template
The Standard Library defines several specializations of class templates. One example is the class template basic_string<>. Two specialized versions of this class are std::string and std::wstring, which are typedefs of the specializations basic_string<char> and basic_string<wchar_t>, respectively. Usually, there is no need to instantiate any of these explicitly because the header <string> already instantiates these specializations:
#include <string> //definitions of std::string and std::wstring
using namespace std;
bool TranslateToKorean(const string& origin,
wstring& target ); //English / Korean dictionary
int main()
{
string EnglishMsg = "This program has performed an illegal operation";
wstring KoreanMsg;
TranslateToKorean(EnglishMsg, KoreanMsg);
}
NOTE: Exported templates are relatively new in C++; therefore, not all compilers support this feature yet. Please consult your user's manual to check whether your compiler supports it.
A template definition can be #included in several translation units; consequently, it can be compiled several times. As you have observed, this can considerably increase compilation and linkage time. Instead of #including a complete definition of the template, it is possible to compile the template definition only once, and use only the template's declaration in other translation units. This is very similar to the compilation of external functions and classes, in which the definition is compiled only once and then only the declarations are required.
To compile a template separately and then use its declaration, the template has to be exported. This is done by preceding the template's definition with the keyword export:
//filename min.cpp
export template < class T > T min (const T& a, const T& b)
{
return a > b ? b : a;
}
Now only the declaration of the template is required when it is used in other translation units. For example
//file min.c
template < class T > T min (const T & a, const T & b); //declaration only
int main()
{
int j=0, k=1;
in smaller = min(j,k);
return 0;
}
Inline function templates cannot be exported. If an inline template function is declared both export and inline, the export declaration has no effect and the template is only inline. Declaring a class template exported is equivalent to declaring all its non-inline member functions, static data members, and member classes exported. Templates in an unnamed namespace are not to be exported.
The interaction of templates with other language features can sometimes yield surprising results. The following sections discuss various aspects of interaction between templates and other language features, including ambiguous interpretation of qualified template names, inheritance, and virtual member functions.
Using qualified names in a template can cause ambiguity between a type and a non-type. For example
int N;
template < class T > T func()
{
T::A * N; // ambiguous: multiplication or a pointer declaration?
//
}
If T::A is a typename, the definition of func() N creates a pointer. If, on the other hand, T::A is a non-type (for example, if A is data member of type int), T::A * N is an expression statement that consists of the multiplication of the qualified member T::A by a global int N. By default, the compiler assumes that an expression such as T::A refers to a non-type. The typename keyword instructs the compiler to supersede this default interpretation and resolve the ambiguity in favor of a type name rather than a non-type. In other words, the preceding (seemingly ambiguous) statement is actually resolved as a multiplication expression, the result of which is discarded. In order to declare a pointer, the typename keyword is required:
int N;
template < class T > T func()
{
typename T::A * N; // N is a now pointer since T::A is a typename
//...
};
A common mistake is to assume that a container of pointers or references to objects of a derived class is a container of pointers or references to a base class. For example
#include<vector>
using namespace std;
class Base
{
public: virtual void f() {}
};
class Derived : public Base
{
public: void f() {}
};
void func( vector<Base*>& vb);
int main()
{
Derived d;
vector<Derived*> vd;
vd.push_back(&d);
func(vd); //error, vector<Derived*>& is not a vector<Base*>
}
Although the is-a relationship exists between the classes Derived and Base, there is no such relationship between specializations of the same class template that contain pointers or references to related objects.
A member function template should not be virtual. However, ordinary member functions in a class template can be virtual. For example
template <class T> class A
{
public:
template <class S> virtual void f(S); //error
virtual int g(); // OK
};
A specialization of a member function template does not override a virtual function that is defined in a base class. For example
class Base
{
public:
virtual void f(char);
};
class Derived : public Base
{
public:
template <class T> void f(T); //does not override B::f(int)
};
Pointers to class members can take the address of a specialized member function of a class template. As with ordinary classes, pointers to members cannot take the address of a static member function. In the following example, the specialization std::vector<int> is used:
#include<vector>
using namespace std;
// a typedef is used to hide the unwieldy syntax
typedef void (vector< int >::*pmv) (size_t);
void func()
{
pmv reserve_ptr = &vector< int >::reserve;
//...use reserve_ptr
}
Templates simplify and streamline the implementation of generic containers and functions. The benefits of templates have allured software vendors, who are now migrating from plain object-oriented frameworks to object-oriented generic frameworks. However, parameterized types are not unique to C++. Back in 1983, Ada introduced generic packages, which were roughly equivalent to class templates. Other languages implemented similar mechanisms of automated code generation from a skeletal user-written code.
The two main template categories in C++ are class templates and function templates. A class template encapsulates parameterized data members and function members. Function templates are a means of implementing generic algorithms. The traditional methods of implementing generic algorithms in pre-template C++ were rather limited, unsafe, and inefficient compared to templates. An important aspect of templates is the support of object semantics.
C++ enables programmers to control the instantiation of templates by explicitly instantiating them. It is possible to instantiate an entire class, a certain member function of a class, or a particular specialization of a function template. An explicit instantiation of a template is indicated by the keyword template, without angular brackets that are followed by the template declaration. Explicit specializations of a class template are always required. For function templates, the compiler usually deduces the specialization from the type of the arguments. It is possible to define partial specialization of a class template that overrides the primary class template for a set of types. This feature is most useful for modifying the behavior of a class template that manipulates pointers. A partial specialization is indicated by a secondary list of parameters following the name of the template. An explicit specialization enables the programmer to override the automatic instantiation of a class template for a certain type. An explicit specialization is indicated by the keyword template, followed by empty angular brackets and a list of type arguments after the template's name.
Templates and operator overloading are the building blocks of generic programming. The Standard Template Library is an exemplary framework of generic programming, as you will see in the next chapter.
© Copyright 1999, Macmillan Computer Publishing. All rights reserved.