南京大学计算机科学与技术系：《程序设计（C++）》课程教学资源（PPT讲稿，高级篇）05 泛型（类属）程序设计－模板

泛型（类属）程序设计 一一模板

泛型（类属）程序设计 －－模板

主要内容 ■泛型（类属）的基本概念 ■函数模板 ■类模板 ■模板的复用问题 基于C++标准模板库(STL)的编程

主要内容 ◼ 泛型（类属）的基本概念 ◼ 函数模板 ◼ 类模板 ◼ 模板的复用问题 ◼ 基于C++标准模板库(STL)的编程

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

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

再例如，元素类型不同的栈类 class IntStack class AStack { int buf[100]; { Abuf[100]; public: public: void push(int); void push(A); void pop(int&); void pop(A&); }i class DoubleStack { double buf[100]; public: void push(double); void pop(double&); } 这三个类的实现也是一样的（用数组表示元素）

class IntStack { int buf[100]; public: void push(int); void pop(int&); }; class DoubleStack { double buf[100]; public: void push(double); void pop(double&); }; class AStack { A buf[100]; public: void push(A); void pop(A&); }; ▪ 再例如，元素类型不同的栈类 这三个类的实现也是一样的（用数组表示元素）

对于前面的三个排序函数和三个栈类，如 果能分别只用一个函数和一个类来描述它 们，这将会大大简化程序设计的工作！

◼ 对于前面的三个排序函数和三个栈类，如 果能分别只用一个函数和一个类来描述它 们，这将会大大简化程序设计的工作！

泛型（类属）程序设计 一个程序实体能对多种类型的数据进行操作或描述 的特性称为类属性。具有类属性的程序实体通常有 ·类属函数 ·。类属类 基于具有类属性的程序实体进行程序设计的技术称 为：泛型程序设计（或类属程序设计，Generic Programming) 类属也是一种多态，称为参数化多态，即， 段以类型作为参数的代码，给参数提供不同的类型就 能得到多个不同的代码

泛型（类属）程序设计 ◼ 一个程序实体能对多种类型的数据进行操作或描述 的特性称为类属性。具有类属性的程序实体通常有： • 类属函数 • 类属类 ◼ 基于具有类属性的程序实体进行程序设计的技术称 为：泛型程序设计（或类属程序设计，Generic Programming）。 ◼ 类属也是一种多态，称为参数化多态，即， • 一段以类型作为参数的代码，给参数提供不同的类型就 能得到多个不同的代码

类属函数 ■类属函数是指一个函数能对不同类型的参数完 成相同的操作 C++提供了两种实现类属函数的机制： 采用通用指针类型的参数(C语言的做法) 函数模板

类属函数 ◼ 类属函数是指一个函数能对不同类型的参数完 成相同的操作。 ◼ C++提供了两种实现类属函数的机制： • 采用通用指针类型的参数（C语言的做法） • 函数模板

用通用指针参数实现类属非序函数 ■函数定义： void sort(void*base,/需排序的数据（数组）首地址 unsigned int count,/数据元素的个数 unsigned int element_size,/一个数据元素所需的空间大小 int(*cmp)(const void*,const void*))/比较两个元素的函数 /不论采用何种排序算法，一般都需要对数组进行以下操作： /取第i个元素 (char *)base+i*element_size /比较第i个和第j个元素的大小（利用调用者提供的回调函数cmp实现 (*cmp)((char *)base+i*element_size, (char *)base+j*element_size) /交换第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; }/上面的char用byte替代更好！typedef unsigned char byte;

用通用指针参数实现类属排序函数 ◼ 函数定义： void sort(void *base, //需排序的数据（数组）首地址 unsigned int count, //数据元素的个数 unsigned int element_size, //一个数据元素所需的空间大小 int (*cmp)(const void *, const void *) ) //比较两个元素的函数 { //不论采用何种排序算法，一般都需要对数组进行以下操作： //取第i个元素 (char *)base+i*element_size //比较第i个和第j个元素的大小 （利用调用者提供的回调函数cmp实现） (*cmp)((char *)base+i*element_size, (char *)base+j*element_size) //交换第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; } } //上面的char用byte替代更好！typedef unsigned char byte;

■调用者需要提供： int int_compare(const void *p1,const void *p2) /比较int类型元素大小。 { 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) return -1; else if (*(double *)p1 *(double *)p2) return 1; else return O;

◼ 调用者需要提供： int int_compare(const void *p1, const void *p2) //比较int类型元素大小。 { 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) return 1; else return 0; }

int A_compare(const void *p1,const void *p2) /比较A类元素大小。 {if(*(A*)p1*(A*)p2)/类A需重载操作符：> return 1; else return 0 } /类属排序函数的使用 inta[100]; sort(a,100,sizeof(int),int_compare); double b[200]; sort(b,200,sizeof(double),double_compare); Ac[300];... sort(c,300,sizeof(A),A_compare); 用通用指针实现类属函数比较麻烦，也容易出错！

int A_compare(const void *p1, const void *p2) //比较A类元素大小。 { 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); ◼ 用通用指针实现类属函数比较麻烦，也容易出错！