随笔-10  评论-1  文章-0  trackbacks-0

C++ Templates Tutorial

C++ Library  
 

Table of Contents

Introduction

Class Templates

Function Templates

Template Instantiation

Class Template Specialization

Template Function Specialization

Template Parameters

Static Members and Variables

Templates and Friends


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.

Class Templates

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".

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
}

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 ;
}

Program 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!

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.

Implementing Template Functions

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 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 ;
}

Program Output

max(10, 15) = 15
max('k', 's') = s
max(10.1, 15.2) = 15.2

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 ;
    }
    
    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.

     

  7. If an instantiation of a class template is required, and the template declared but not defined, the program is ill-formed. VC5.0 compiler generates error C2079.
    template <class T> class X ;
    
    int main()
    {
    	X<int> xi ; //error C2079: 'xi' uses undefined class 'X<int>'
    	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.

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 ;
}

Program 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.

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> 
{
} ; //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.

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 ;
}

Program 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 ;
}

Program Output

max(10, 15) = 15
max('k', 's') = s
max(10.1, 15.2) = 15.2
max("Aladdin", "Jasmine") = Jasmine

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
    {
    } ;
    
    //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 ;
    }
    

     

  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 ; //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.

     

  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()
    	{
    		//error C2105: '++' needs l-value             
                 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') ; //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 ;
    }
    
  7. A non-type template parameter cannot be of floating type. For example,
    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 ;
    }
    

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 it's 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 it's 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*.

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>.


© 1997 Microsoft Corporation. All rights reserved. Terms of Use.
posted on 2010-12-12 00:10 Mr.Johnson 阅读(1124) 评论(0)  编辑 收藏 引用 所属分类: C++

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理