C++ Templates Tutorial |
C++ Library |
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.
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".
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
}
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 ;
}
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 vector<int, allocator<int> > INTVECTOR ;
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!
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.
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 ;
}
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 ;
}
max(10, 15) = 15
max('k', 's') = s
max(10.1, 15.2) = 15.2
When the compiler generates a class, function or static data members from a template, it is referred to as template instantiation.
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.
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 ;
}
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.
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 ;
}
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.
//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.
template <class T>
void Test(T r_t)
{
}
int main()
{
//explicit instantiation of Test(int)
template void Test<int>(int) ;
return 0 ;
}
NOTE: Visual C++ 5.0 does not support this syntax currently. The above sample causes compiler error C1001.
In this case the compiler would generate function Test(int). The compiler generates the definition using the template function Test.
template <class T> class X ;
int main()
{
X<int> xi ; //error C2079: 'xi' uses undefined class 'X<int>'
return 0 ;
}
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.
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 ;
}
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.
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>
{
} ; //C2989 here
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.
NOTE: Visual C++ 5.0 does not support template class partial specialization. The above sample causes compiler error C2989: template class has already been defined as a non-template class.
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 ;
}
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 ;
}
max(10, 15) = 15
max('k', 's') = s
max(10.1, 15.2) = 15.2
max("Aladdin", "Jasmine") = Jasmine
template <class T>
class Stack
{
} ;
Here T is a template parameter, also referred to as type-parameter.
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.
template <class T, int size>
class Stack
{
} ;
//error C2989: 'Stack<int,10>' : template class has already been
//defined as a non-template class
template <class T, int size = 10>
class Stack<int, 10>
{
} ;
int main()
{
Stack<float,10> si ;
return 0 ;
}
template <class T, int size>
class Stack
{
int T ; //error type-parameter re-defined.
void f()
{
char T ; //error type-parameter re-defined.
}
} ;
class A {} ;
int main()
{
Stack<A,10> si ;
return 0 ;
}
NOTE: VC++ 5.0 or SP1 compiles this sample without any errors. It does not flag the re-definition of type-parameter as an error.
template <class T, int size>
class Stack
{
void f()
{
//error C2105: '++' needs l-value
size++ ; //error change of template argument value
}
} ;
int main()
{
Stack<double,10> si ;
return 0 ;
}
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') ; //C2783 here
return 0 ;
}
NOTE: Compiling the above sample using VC++ 5.0 and SP1 causes compiler error C2783: could not deduce template argument for 'i'. To workaround the problem, replace the call to f('s') with f<char, 's'>('s').
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<char, 's'>('s') ; //workaround
return 0 ;
}
template <double d> class X ; //error C2079: 'xd' uses
//undefined class 'X<1.e66>'
//template <double* pd> class X ; //ok
//template <double& rd> class X ; //ok
int main()
{
X<1.0> xd ;
return 0 ;
}
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*.
#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 ;
}
xi.s = 10 xc.s = Hello
#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 ;
}
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*.
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>. |