Templates in C++

Unit 4 Templates Structure 4.1 Introduction 4.2 Class templates 4.2.1 Implementing a class template 4.2.2 Implementing class template member functions 4.2.3 Using a class template Self Assessment Questions 4.3 Function templates 4.3.1 Implementing function templates 4.3.2 Using template functions Self Assessment Questions 4.4 Template instantiation Self Assessment Questions 4.5 Class template specialization 4.5.1 Template class partial specialization Self Assessment Questions 4.6 Template function specialization Self Assessment Questions 4.7 Template parameters Self Assessment Questions 4.8 Static members and variables Self Assessment Questions 4.9 Templates and friends 4.10 Templates and multiple-file projects 4.11 Summary 4.12 Terminal Questions References and Further Reading 4.1 Introduction Many C++ programs use common data structures like stacks, queues and lists. A program may require a queue of customers and a queue of messages. One could easily implement a queue of customers, then take the existing code and implement a queue of messages. The program grows, and now there is a need for a queue of orders. So just take the queue of messages and convert that to a queue of orders (Copy, paste, find, replace?). Need to make some changes to the queue implementation? Not a very easy task, since the code has been duplicated in many places. Re-inventing source code is not an intelligent approach in an object oriented environment which encourages re-usability. It seems to make more sense to implement a queue that can contain any arbitrary type rather than duplicating code. How does one do that? The answer is to use type parameterization, more commonly referred to as templates. C++ templates allow one to implement a generic Queue<T> template that has a type parameter T. T can be replaced with actual types, for example, Queue<Customers>, and C++ will generate the class Queue<Customers>. Changing the implementation of the Queue becomes relatively simple. Once the changes are implemented in the template Queue<T>, they are immediately reflected in the classes Queue<Customers>, Queue<Messages>, and Queue<Orders>. Templates are very useful when implementing generic constructs like vectors, stacks, lists, queues which can be used with any arbitrary type. C++ templates provide a way to re-use source code as opposed to inheritance and composition which provide a way to re-use object code. C++ provides two kinds of templates: class templates and function templates. Use function templates to write generic functions that can be used with arbitrary types. For example, one can write searching and sorting routines which can be used with any arbitrary type. The Standard Template Library generic algorithms have been implemented as function templates, and the containers have been implemented as class templates. Objectives After going through this unit and understanding the specifics of templates you will be able to: · Define templates, and the types of templates available in C++. · Describe how templates are dealt with by the C++ compiler. · Outline the scenarios in which templates are useful and the way they have to be declared. · Understand in detail the in-depths of template programming, i.e., partial specialization, template parameters, template friendship and more. · Write advanced C++ programs using templates. 4.2 Class Templates 4.2.1 Implementing a Class Template A class template definition looks like a regular class definition, except it is prefixed by the keyword template. For example, here is the definition of a class template for a Stack. template <class T> class Stack {     public:         Stack(int = 10);         ~Stack() { delete [] stackPtr ; }         int push(const T&);         int pop(T&);         int isEmpty()const { return top == -1; }         int isFull() const { return top == size - 1; }     private:         int size;  // number of elements on Stack.         int top;         T* stackPtr; }; T is a type parameter and it can be any type. For example, Stack<Token>, where Token is a user defined class. T does not have to be a class type as implied by the keyword class. For example, Stack<int> and Stack<Message*> are valid instantiations, even though int and Message* are not "classes". 4.2.2 Implementing Class Template Member Functions Implementing template member functions is somewhat different compared to the regular class member functions. The declarations and definitions of the class template member functions should all be in the same header file. The declarations and definitions need to be in the same header file. Consider the following: //B.H template <class t> class b {     public:         b();         ~b(); }; //B.CPP #include "B.H" template <class t> b<t>::b() { } template <class t> b<t>::~b() { } //MAIN.CPP #include "B.H" void main() {     b<int> bi;     b <float> bf; } When compiling B.cpp, the compiler has both the declarations and the definitions available. At this point the compiler does not need to generate any definitions for template classes, since there are no instantiations. When the compiler compiles main.cpp, there are two instantiations: template class B<int> and B<float>. At this point the compiler has the declarations but no definitions. While implementing class template member functions, the definitions are prefixed by the keyword template. Here is the complete implementation of class template Stack: //stack.h #pragma once template <class T> class Stack {     public:         Stack(int = 10);         ~Stack() { delete [] stackPtr; }         int push(const T&);         int pop(T&); // pop an element off the stack         int isEmpty()const { return top == -1; }         int isFull() const { return top == size - 1; }     private:         int size; // Number of elements on Stack         int top;         T* stackPtr; }; //constructor with the default size 10 template <class T> Stack<T>::Stack(int s) {     size = s > 0 && s < 1000 ? s : 10;     top = -1; // initialize stack     stackPtr = new T[size]; } // push an element onto the Stack template <class T> int Stack<T>::push(const T& item) {     if (!isFull())     {         stackPtr[++top] = item;         return 1; // push successful     }     return 0; // push unsuccessful } // pop an element off the Stack template <class T> int Stack<T>::pop(T& popValue) {     if (!isEmpty())     {         popValue = stackPtr[top--];         return 1; // pop successful     }     return 0; // pop unsuccessful } 4.2.3 Using a class template Using a class template is easy. Create the required classes by plugging in the actual type for the type parameters. This process is commonly known as "Instantiating a class". Here is a sample driver class that uses the Stack class template. #include <iostream> #include "stack.h" using namespace std; void main() {     typedef Stack<float> FloatStack;     typedef Stack<int> IntStack;     FloatStack fs(5);     float f = 1.1;     cout << "Pushing elements onto fs" << endl;     while (fs.push(f))     {         cout << f << ' ';         f += 1.1;     }     cout << endl << "Stack Full." << endl     << endl << "Popping elements from fs" << endl;     while (fs.pop(f))         cout << f << ' ';     cout << endl << "Stack Empty" << endl;     cout << endl;     IntStack is;     int i = 1.1;     cout << "Pushing elements onto is" << endl;     while (is.push(i))     {         cout << i << ' ';         i += 1;     }     cout << endl << "Stack Full" << endl     << endl << "Popping elements from is" << endl;     while (is.pop(i))         cout << i << ' ';     cout << endl << "Stack Empty" << endl; } Output: Pushing elements onto fs 1.1 2.2 3.3 4.4 5.5 Stack Full. Popping elements from fs 5.5 4.4 3.3 2.2 1.1 Stack Empty Pushing elements onto is 1 2 3 4 5 6 7 8 9 10 Stack Full Popping elements from is 10 9 8 7 6 5 4 3 2 1 Stack Empty In the above example we defined a class template Stack. In the driver program we instantiated a Stack of float (FloatStack) and a Stack of int(IntStack). Once the template classes are instantiated you can instantiate objects of that type (for example, fs and is.) A good programming practice is using typedef while instantiating template classes. Then throughout the program, one can use the typedef name. There are two advantages: · typedef's are very useful when "templates of templates" come into usage. For example, when instantiating an STL vector of int's, you could use:                     typedef vector<int, allocator<int> > INTVECTOR; · If the template definition changes, simply change the typedef definition. For example, currently the definition of template class vector requires a second parameter.                     typedef vector<int, allocator<int> > INTVECTOR;                     INTVECTOR vi1; In a future version, the second parameter may not be required, for example,                     typedef vector<int> INTVECTOR;                     INTVECTOR vi1; Imagine how many changes would be required if there was no typedef! Self Assessment Questions 1. How does a class template definition differ from a normal class definition? 2. Why is it considered a good programming practice to use typedef while instantiating templates? 4.3 Function Templates To perform identical operations for each type of data compactly and conveniently, use function templates. You can write a single function template definition. Based on the argument types provided in calls to the function, the compiler automatically instantiates separate object code functions to handle each type of call appropriately. The STL algorithms are implemented as function templates. 4.3.1 Implementing Function Templates Function templates are implemented like regular functions, except they are prefixed with the keyword template. Here is a sample with a function template. #include <iostream> using namespace std; //max returns the maximum of the two elements template <class T> T max(T a, T b) {     return a > b ? a : b; } 4.3.2 Using Template Functions Using function templates is very easy: just use them like regular functions. When the compiler sees an instantiation of the function template, for example: the call max(10, 15) in function main, the compiler generates a function max(int, int). Similarly the compiler generates definitions for max(char, char) and max(float, float) in this case. #include <iostream> using namespace std; //max returns the maximum of the two elements template <class T> T max(T a, T b) {     return a > b ? a : b; } void main() {     cout << "max(10, 15) = " << max(10, 15) << endl;     cout << "max('k', 's') = " << max('k', 's') << endl;     cout << "max(10.1, 15.2) = " << max(10.1, 15.2) << endl; } Output: max(10, 15) = 15 max('k', 's') = s max(10.1, 15.2) = 15.2 Self Assessment Questions 1.       When is it considered appropriate to use function templates? 2.       Using the working example given in this section as your guide, write a program so as to add numbers of different data types using function templates. 4.4 Template Instantiation When the compiler generates a class, function or static data members from a template, it is referred to as template instantiation. · A class generated from a class template is called a generated class. · A function generated from a function template is called a generated function. · A static data member generated from a static data member template is called a generated static data member. The compiler generates a class, function or static data members from a template when it sees an implicit instantiation or an explicit instantiation of the template. 1. Consider the following sample. This is an example of implicit instantiation of a class template. template <class T> class Z {     public:         Z() {};         ~Z() {};         void f(){};         void g(){}; }; int main() {     Z<int> zi;   //implicit instantiation generates class Z<int>     Z<float> zf; //implicit instantiation generates class Z<float>     return 0; } 2. Consider the following sample. This sample uses the template class members Z<T>::f() and Z<T>::g(). template <class T> class Z {     public:         Z() {};         ~Z() {};         void f(){};         void g(){}; }; int main() {     Z<int> zi; //implicit instantiation generates class Z<int>     zi.f();    //and generates function Z<int>::f()     Z<float> zf; //implicit instantiation generates class Z<float>     zf.g();      //and generates function Z<float>::g()     return 0; } This time in addition to the generating classes Z<int> and Z<float>, with constructors and destructors, the compiler also generates definitions for Z<int>::f() and Z<float>::g(). The compiler does not generate definitions for functions, nonvirtual member functions, class or member class that does not require instantiation. In this example, the compiler did not generate any definitions for Z<int>::g() and Z<float>::f(), since they were not required. 3. Consider the following sample. This is an example of explicit instantiation of a class template. template <class T> class Z { public:     Z() {};     ~Z() {};     void f(){};     void g(){}; }; int main() {     template class Z<int>; //explicit instantiation of class Z<int>     template class Z<float>; //explicit instantiation of class Z<float>     return 0; } 4. Consider the following sample. Will the compiler generate any classes in this case? The answer is NO. template <class T> class Z {     public:         Z() {};         ~Z() {};         void f(){};         void g(){}; }; int main() {     Z<int>* p_zi; //instantiation of class Z<int> not required     Z<float>* p_zf; //instantiation of class Z<float> not required     return 0; } This time the compiler does not generate any definitions! There is no need for any definitions. It is similar to declaring a pointer to an undefined class or struct. 5. Consider the following sample. This is an example of implicit instantiation of a function template. //max returns the maximum of the two elements template <class T> T max(T a, T b) {     return a > b ? a : b; } void main() {     int I;     I = max(10, 15); //implicit instantiation of max(int, int)     char c;     c = max('k', 's'); //implicit instantiation of max(char, char) } In this case the compiler generates functions max(int, int) and max(char, char). The compiler generates definitions using the template function max. 6. Consider the following sample. This is an example of explicit instantiation of a function template. template <class T> void Test(T r_t) { } int main() {     //explicit instantiation of Test(int)     template void Test<int>(int);     return 0; } In this case the compiler would generate function Test(int). The compiler generates the definition using the template function Test. 7. If an instantiation of a class template is required, and the template declared but not defined, the program is ill-formed. template <class T> class X ; int main() {     X<int> xi;     return 0; } 8. Instantiating virtual member functions of a class template that does not require instantiation is implementation defined. For example, in the following sample, virtual function X<T>::Test() is not required, VC5.0 generates a definition for X<T>::Test. template <class T> class X {     public:         virtual void Test() {} }; int main() {     X<int> xi; //implicit instantiation of X<int>     return 0; } In this case the compiler generates a definition for X<int>::Test, even if it is not required. Self Assessment Questions 1. What is meant by template instantiation? 2. What is meant by a generated class and a generated function? 4.5 Class Template Specialization In some cases it is possible to override the template-generated code by providing special definitions for specific types. This is called template specialization. The following example defines a template class specialization for template class stream. #include <iostream> using namespace std; template <class T> class stream {     public:         void f() { cout << "stream<T>::f()"<< endl; } }; template <> class stream<char> {     public:         void f() { cout << "stream<char>::f()"<< endl; } }; int main() {     stream<int> si;     stream<char> sc;     si.f();     sc.f();     return 0; } Output: stream<T>::f() stream<char>::f() In the above example, stream<char> is used as the definition of streams of chars; other streams will be handled by the template class generated from the class template. 4.5.1 Template Class Partial Specialization You may want to generate a specialization of the class for just one parameter, for example //base template class template<typename T1, typename T2> class X { }; //partial specialization template<typename T1> class X<T1, int> { }; int main() {     // generates an instantiation from the base template     X<char, char> xcc ;     //generates an instantiation from the partial specialization     X<char, int> xii ;      return 0 ; } A partial specialization matches a given actual template argument list if the template arguments of the partial specialization can be deduced from the actual template argument list. Self Assessment Questions 1. What is template specialization? 2. Describe a scenario in which template class partial specialization is considered appropriate. 4.6 Template Function Specialization In some cases it is possible to override the template-generated code by providing special definitions for specific types. This is called template specialization. The following example demonstrates a situation where overriding the template generated code would be necessary: #include <iostream> using namespace std; //max returns the maximum of the two elements of type T, //where T is a class or data type for which operator> is defined. template <class T> T max(T a, T b) {     return a > b ? a : b; } int main() {        cout << "max(10, 15) = " << max(10, 15) << endl ;     cout << "max('k', 's') = " << max('k', 's') << endl ;     cout << "max(10.1, 15.2) = " << max(10.1, 15.2) << endl ;     cout << "max("Aladdin", "Jasmine") = " << max("Aladdin", "Jasmine") << endl ;     return 0 ; } Output: max(10, 15) = 15 max('k', 's') = s max(10.1, 15.2) = 15.2 max("Aladdin", "Jasmine") = Aladdin Not quite the expected results! Why did that happen? The function call max("Aladdin", "Jasmine") causes the compiler to generate code for max(char*, char*), which compares the addresses of the strings! To correct special cases like these or to provide more efficient implementations for certain types, one can use template specializations. The above example can be rewritten with specialization as follows: #include <iostream> #include <cstring> using namespace std; //max returns the maximum of the two elements template <class T> T max(T a, T b) {     return a > b ? a : b ; } // Specialization of max for char* template <> char* max(char* a, char* b) {     return strcmp(a, b) > 0 ? a : b ; } int main() {     cout << "max(10, 15) = " << max(10, 15) << endl ;     cout << "max('k', 's') = " << max('k', 's') << endl ;     cout << "max(10.1, 15.2) = " << max(10.1, 15.2) << endl ;     cout << "max("Aladdin", "Jasmine") = " << max("Aladdin", "Jasmine") << endl ;     return 0 ; } Output: max(10, 15) = 15 max('k', 's') = s max(10.1, 15.2) = 15.2 max("Aladdin", "Jasmine") = Jasmine Self Assessment Questions 1. What is template function specialization? 2. Implement the examples given in session and understand the outputs. 4.7 Template Parameters 1. C++ templates allow one to implement a generic Queue<T> template that has a type parameter T. T can be replaced with actual types, for example, Queue<Customers>, and C++ will generate the class Queue<Customers>. For example, template <class T> class Stack{ }; Here T is a template parameter, also referred to as type-parameter. 2. C++ allows you to specify a default template parameter, so the definition could now look like:                     template <class T = float, int elements = 100> Stack { ....}; Then a declaration such as                     Stack<> mostRecentSalesFigures; would instantiate (at compile time) a 100 element Stack template class named mostRecentSalesFigures of float values; this template class would be of type Stack<float, 100>. Note, C++ also allows non-type template parameters. In this case, template class Stack has an int as a non-type parameter. If you specify a default template parameter for any formal parameter, the rules are the same as for functions and default parameters. Once a default parameter is declared all subsequent parameters must have defaults. 3. Default arguments cannot be specified in a declaration or a definition of a specialization. For example, template <class T, int size> class Stack { }; //defined as a non-template class template <class T, int size = 10> class Stack<int, 10> { }; int main() {     Stack<float,10> si;               return 0; } 4. A type-parameter defines its identifier to be a type-name in the scope of the template declaration, and canot be re-declared within its scope (including nested scopes). For example, template <class T, int size> class Stack {     int T;     void f()     {         char T; //error type-parameter re-defined.     } }; class A {}; int main() {     Stack<A,10> si;     return 0; } 5. The value of a non-type-parameter cannot be assigned to or have its value changed. For example, template <class T, int size> class Stack {     void f()     {         size++ ; //error change of template argument value     } }; int main() {     Stack<double,10> si ;     return 0 ; } 6. A template-parameter that could be interpreted as either a parameter-declaration or a type-parameter, is taken as a type-parameter. For example, class T {}; int i; template <class T, T i> void f(T t) {     T t1 = i; //template arguments T and i     ::T t2 = ::i; //globals T and i } int main() {     f('s');     return 0 ; } Self Assessment Questions 1. Write an example to show how default template parameters may be described. 2. Is the statement, “Once a default parameter has been specified all subsequent parameters must have defaults specified,” true or false? 4.8 Static Members and Variables 1. Each template class or function generated from a template has its own copies of any static variables or members. 2. Each instantiation of a function template has its own copy of any static variables defined within the scope of the function. For example, template <class T> class X {     public:         static T s; }; int main() {     X<int> xi ;     X<char*> xc ; } Here X<int> has a static data member s of type int and X<char*> has a static data member s of type char*. 3. Static members are defined as follows: #include <iostream> using namespace std; template <class T> class X {     public:         static T s; }; template <class T> T X<T>::s = 0 ; template <> int X<int>::s = 3 ; template <> char* X<char*>::s = "Hello" ; int main() {     X<int> xi ;     cout << "xi.s = " << xi.s << endl ;     X<char*> xc ;     cout << "xc.s = " << xc.s << endl ;     return 0 ; } Program Output: xi.s = 10 xc.s = Hello 4. Each instantiation of a function template has its own copy of the static variable. For example, #include <iostream> using namespace std; template <class T> void f(T t) {     static T s  = 0;     s = t;     cout << "s = " << s << endl; } int main() {     f(10);     f("Hello");     return 0; } Program Output: s = 10 s = Hello Here f<int>(int) has a static variable s of type int, and f<char*>(char*) has a static variable s of type char*. Self Assessment Questions 1. “Each instantiation of a function template has its own copy of any static variables declared within the scope of the function.” State if the previous statement was true or false. 2. Implement all the examples given in this section by making minor changes to them, and observe the results. 4.9 Templates and Friends Friendship can be established between a class template and a global function, a member function of another class (possibly a template class), or even an entire class (possible template class). The table below lists the results of declaring different kinds of friends of a class. Class Template friend declaration in class template X Results of giving friendship template class <T> class X friend void f1(); makes f1() a friend of all instantiations of template X. For example, f1() is a friend of X<int>, X<A>, and X<Y>. template class <T> class X friend void f2(X<T>&); For a particular type T for example, float, makes f2(X<float>&) a friend of class X<float> only. f2(x<float>&) cannot be a friend of class X<A>. template class <T> class X friend A::f4(); // A is a user defined class with a member function f4(); makes A::f4() a friend of all instantiations of template X. For example, A::f4() is a friend of X<int>, X<A>, and X<Y>. template class <T> class X friend C<T>::f5(X<T>&); // C is a class template with a member function f5 For a particular type T for example, float, makes C<float>::f5(X<float>&) a friend of class X<float> only. C<float>::f5(x<float>&) cannot be a friend of class X<A>. template class <T> class X friend class Y; makes every member function of class Y a friend of every template class produced from the class template X. template class <T> class X friend class Z<T>; when a template class is instantiated with a particular type T, such as a float, all members of class Z<float> become friends of template class X<float>. 4.10 Templates and Multiple-file Projects From the point of view of the compiler, templates are not normal functions or classes. They are compiled on demand, meaning that the code of a template function is not compiled until an instantiation with specific template arguments is required. At that moment, when an instantiation is required, the compiler generates a function specifically for those arguments from the template. When projects grow it is usual to split the code of a program in different source code files. In these cases, the interface and implementation are generally separated. Taking a library of functions as example, the interface generally consists of declarations of the prototypes of all the functions that can be called. These are generally declared in a "header file" with a .h extension, and the implementation (the definition of these functions) is in an independent file with c++ code. Because templates are compiled when required, this forces a restriction for multi-file projects: the implementation (definition) of a template class or function must be in the same file as its declaration. That means that we cannot separate the interface in a separate header file, and that we must include both interface and implementation in any file that uses the templates. Since no code is generated until a template is instantiated when required, compilers are prepared to allow the inclusion more than once of the same template file with both declarations and definitions in a project without generating linkage errors. 4.11 Summary Templates are a fairly new addition to the C++ language, and were only recently standardized on. They are also one of the more useful features of C++. They allow you to create classes that are more dynamic in terms of the types of data they can handle. A class template is a class that is implemented with one or more type parameters left open. To use a class template, you pass the open types as template arguments. The class template is then instantiated (and compiled) for these types. For class templates, only those member functions that are called are instantiated. You can specialize class templates for certain types. You can partially specialize class templates for certain types. You can define default values for class template parameters. These may refer to previous template parameters. Template functions define a family of functions for different template arguments. When you pass template arguments, function templates are instantiated for these argument types. You can explicitly qualify the template parameters. You can overload function templates. When you overload function templates, limit your changes to specifying template parameters explicitly. Make sure you see all overloaded versions of function templates before you call them. 4.12 Terminal Questions 1. Mention the scenarios where using templates is beneficial. 2. How do function templates make programming easy? 3. How does the compiler deal with function templates? 4. How does using typedef help when template definition changes? 5. Write a note on template parameters. 6. How are static members declared within a template class? Explain with an example. 7. Describe the various types of template friendships. 8. Explain the sentence, “Templates are not normal functions or classes.”