第八章 多态性和虚函数 胡昊 南京大学计算机系软件所

重要内容 类属（泛型）的基本概念 函数模板 类模板 模板的复用 C++标准模板库简介

类属（泛型）程序设计 在程序设计中经常需要用到一些功能完全相同的程序实体，但它们所涉及的数据的类型不同。 例如，对不同元素类型的数组进行排序的函数： void int_sort(int x[],int num); void double_sort(double x[],int num); void A_sort(A x[],int num); 这三个函数的实现基本是一样的。

再例如，元素类型不同的栈类 class AStack class IntStack { A buf[100]; public: bool push(A); bool pop(A&); }; class IntStack { int buf[100]; public: bool push(int); bool pop(int&); }; class DoubleStack { double buf[100]; public: bool push(double); bool pop(double&); }; 这三个类的实现基本也是一样的。

类属（泛型）程序设计（续） 对于前面的三个排序函数和三个类，如果能分别只用一个函数和一个类来描述它们将会大大简化程序设计的工作。 在程序设计中，一个程序实体能对多种类型的数据进行操作或描述的特性称为类属性。 基于具有类属性的程序实体进行程序设计的技术称为：类属程序设计（或泛型程序设计，Generic Programming）。 具有类属性的程序实体通常有： 类属函数 类属类

类属函数 类属函数是指一个函数能对不同类型的参数完成相同的操作。 C++提供了下面两种实现类属函数的机制： 通过指针类型参数的函数 通过函数模板

指针参数实现类属函数 void sort(void *base, //需排序的数据首地址 unsigned int count, //数据元素的个数 unsigned int element_size, //数据元素的尺寸 int (*cmp)(const void *, const void *) ) //比较两个元素的函数 { /* 不论采用何种排序算法，一般都需要对数组进行以下操作： 1、取第i个元素 (char *)base+i*element_size 2、比较第i个和第j个元素的大小 (*cmp)((char *)base+i*element_size, (char *)base+j*element_size) 3、交换第i个和第j个元素 char *p1=(char *)base+i*element_size, *p2=(char *)base+j*element_size; for (int k=0; k<element_size; k++) { char temp=p1[k]; p1[k] = p2[k]; p2[k] = temp; } */ }

int int_compare(const void *p1, const void *p2) { if (*(int *)p1 < *(int *)p2) return –1; else if (*(int *)p1 > *(int *)p2) return 1; else return 0; } int double_compare(const void *p1, const void *p2) //比较double类型元素大小。 { if (*(double *)p1 < *(double *)p2) else if (*(double *)p1 > *(double *)p2)

int A_compare(const void *p1, const void *p2) { if (*(A *)p1 < *(A *)p2) //类A需重载操作符：< return –1; else if (*(A *)p1 > *(A *)p2) //类A需重载操作符：> return 1; else return 0; } ...... int a[100]; sort(a,100,sizeof(int),int_compare); double b[200]; sort(b,200,sizeof(double),double_compare); A c[300]; sort(c,300,sizeof(A),A_compare);

冒泡排序算法 输入n个数给a[1]到a[n] for j=1 to n-1 for i=1 to n-j a[i] > a[i+1] 真 假 a[i]  a[i+1] 输出a[1]到a[n]

冒泡排序程序 #include <iostream.h> void main() { int a[11]; int i, j, t; cout<<“input 10 numbers:”<<endl; for(i=1; i<11; i++) cin>>a[i]; cout<<endl; for(j=1; j<=9; j++) for(i=1; i<=10-i; i++) if(a[i]>a[i+1]) { t=a[i]; a[i]=a[i+1]; a[i+1]=t; } cout<<“The sorted numbers”<<endl; cout<<a[i]; }

函数模板 在C++中，实现类属函数的另外一种办法是用函数模板。函数模板是指带有类型参数的函数定义，其格式如下： template <class T1, class T2, ...> <返回值类型> <函数名>(<参数表>) { ...... } 其中， T1、T2等是函数模板的类型参数 <参数表>中的参数类型以及函数体中的局部变量的类型可以是：T1、T2等 使用函数模板定义的函数时需要提供与T1、T2相对应的具体类型。

例如： template <class T> void sort(T elements[], unsigned int count) { /* 1、取第i个元素 elements[i] 2、比较第i个和第j个元素的大小 elements[i] < elements [j] 3、交换第i个和第j个元素 T temp=elements [i]; elements[i] = elements [j]; elements[j] = temp; */ }

除了类型参数外，函数模板也可以带有非类型参数。 例如： template <class T, int size> //size为一个int型的普通参数。 void f(T a) { T temp[size]; ...... }

函数模板的使用 函数模板定义了一系列重载的函数。要使用函数模板所定义的函数（称为模板函数），首先必须要对函数模板进行实例化（生成具体的函数）。函数模板的实例化通常是隐式的，由编译程序根据实参的类型自动地把函数模板实例化为具体的函数，这种确定函数模板实例的过程叫做模板实参推演（template argument deduction）。 例如： int a[100]; sort(a,100); //调用void sort(int elements[], unsigned int count) double b[200]; sort(b,200); //调用void sort(double elements[], unsigned int count) A c[300]; //类A中需重载操作符：<，需要时还应自定义拷贝构造函数和=。 sort(c,300); //调用void sort(A elements[], unsigned int count)

有时，编译程序无法根据调用时的实参类型来确定所调用的模板函数，这时，需要在程序中显式地实例化函数模板。显式实例化时，在调用模板函数时需要向函数模板提供实参。 例如： template <class T, int size> void f(T a) { T temp[size]; ...... } int main() { f<int,10>(1); //调用模板函数f(int a)，该函数体中的size为10

函数模板和函数重载的配合使用 问题：max(x,m) 调用哪一个模板函数？ template <class T> T max(T a, T b) { return a>b?a:b; } ...... int x,y,z; double l,m,n; z = max(x,y); //调用模板函数：int max(int a,int b) l = max(m,n); //调用模板函数：double max(double a,double b) 问题：max(x,m) 调用哪一个模板函数？

解决办法： 显式实例化 max<double>(x,m); 或 max<int>(x,m); 再定义一个max的重载函数 double max(int a,double b) { return a>b?a:b; }

类模板 其中，T1、T2等为类模板的类型参数，在类成员的说明中可以用T1、T2等来说明它们的类型。 如果一个类的成员的类型可变，则该类称为类属类。类属类一般用类模板实现，其格式为： template <class T1,class T2,...> class <类名> { <类成员说明> } 其中，T1、T2等为类模板的类型参数，在类成员的说明中可以用T1、T2等来说明它们的类型。

例如：定义一个可表示各种类型元素的栈类。 template <class T> class Stack { T buffer[100]; int top; public: Stack() { top = -1; } bool push(const T &x); bool pop(T &x); }; bool Stack <T>::push(const T &x) { ...... } bool Stack <T>::pop(T &x) { ...... }

除了类型参数外，类模板也可以包括非类型参数。 例如： template <class T, int size> class Stack { T buffer[size]; int top; public: Stack() { top = -1; } bool push(const T &x); bool pop(T &x); }; template <class T,int size> bool Stack <T,size>::push(const T &x) { ...... } bool Stack <T,size>::pop(T &x) { ...... }

Stack类 #include <iostream.h> using namespace std; const int STACK_SIZE=100; class Stack { int top; int buffer[STACK_SIZE]; public: Stack() {top=-1;} bool push(int i) { if(top==STACK_SIZE-1) {…… } else{ top++; buffer[top]=i; return true;} } bool pop(int &i) { if(top== -1) {……} else { i=buffer[top]; top--; return true; } };

类模板的使用 类模板定义了若干个类，在使用这些类之前，编译程序将会对类模板进行实例化。类模板的实例化需要在程序中显式地指出。例如： Stack<int> st1; //创建一个元素为int型的栈对象。 int x; st1.push(10); st1.pop(x); Stack<double> st2; //创建一个元素为double型的栈对象。 double y; st2.push(1.2); st2.pop(y); Stack<A> st3; //创建一个元素为A类型的栈对象（A为定义的一个类）。 A a,b; st3.push(a); st3.pop(b);

类模板中的静态成员仅属于实例化后的类（模板类），不同类模板实例之间不共享类模板中的静态成员。例如： template <class T> class A { static int x; T y; ...... }; template <class T> int A<T>::x=0; A<int> a1,a2; //a1和a2共享一个x。 A<double> a3,a4; //a3和a4共享另一个x。

模板的复用 一个模板可以有很多的实例。是否实例化模板的某个实例要由使用情况来决定。 例如： // file1.cpp #include "file2.h" int main() { S<float> s1; //实例化“S<float>”并创建该类的一个对象s1。 s1.f(); //调用void S<float>::f() S<int> s2; //实例化“S<int>”并创建该类的一个对象s2。 s2.f(); //Error，连接程序将指出：“void S<int>::f()”不存在。 sub(); return 0; }

// file2.h template <class T> class S //类模板s的定义 { T a; public: void f(); }; extern void sub(); // file2.cpp #include "file2.h" void S<T>::f() //类模板s的实现 { ...... } void sub() { S<float> x; //实例化“S<float>”并创建该类的一个对象x。 x.f(); //实例化：void S<float>::f()并调用之。

解决上述问题的通常做法是把模板的定义和实现都放在头文件中。 // file2.h template <class T> class S //类模板s的定义 { T a; public: void f(); }; void S<T>::f() //类模板s的实现 { ...... } extern void sub();

// file1.cpp #include "file2.h" int main() { S<float> s1; //实例化“S<float>”并创建该类的一个对象s1。 s1.f(); //实例化：void S<float>::f()并调用之。 S<int> s2; //实例化“S<int>”并创建该类的一个对象s2。 s2.f(); //实例化：void S<int>::f()并调用之。 sub(); return 0; } // file2.cpp void sub() { S<float> x; //实例化“S<float>”并创建该类的一个对象x。 x.f(); //实例化：void S<float>::f()并调用之。

C++标准模板库（STL） 在C++标准库中，除了从C标准库保留下来的一些功能外，所提供的功能大都以模板形式给出，这些模板构成了C++的标准模板库（Standard Template Library，简称STL）。 STL主要包含： 常用的算法（函数）模板（如：排序函数模板、查找函数模板等） 容器类模板（如：集合类模板、栈类模板等） 迭代器类模板，实现了抽象的指针功能，用于对容器中的数据元素进行遍历和访问。