模板和泛型编程

1、面向对象程序设计与C+,第十章 模板与泛型编程,教 师： 王 涛 电 话: 51688243 办公室: 九教北525 E-mail: twang,1. 普通函数的缺陷,求两个数最大值的函数, 可以重载多个函数： int max(int a, int b) return (a b) ? a : b; char max(char a char b) return (a b) ? a : b; float max(float a, float b) return (a b) ? a : b; double max(double a, double b) return (a b) ? a : b; 以

2、上函数的实现方式完全一样，是否可以用一个通用函数完成？,普通类的缺陷,分别有整数链表及浮点数链表： struct inode struct fnode int val; float val; inode *next; fnode* next; ; class ilist class flist inode* head; fnode* head; public: public: ilist(); flist(); ilist(); flist(); void clear(); void clear(); void insert(int); void insert(float); void app

3、end(int); void append(float); bool remove(int); bool remove(float); bool contains(int); bool contains(float); int length(); int length(); ; ;,对于一些结构及操作相同,只是成员数据类型不同的抽象数据结构,若是用普通类class进行封装,需要将不同的数据类型封装成不同的类,造成代码重复及使用不便. 解决的方法之一：利用class封装较为通用的数据类型,使用的时候再进行数据类型转换. 解决的方法之二：使用模板,普通类的缺陷,2.模板,对于结构和操作相同,但成员

4、数据类型不同的抽象类型，可以通过模板实现。 模板有两种形式： 模板函数(函数模板) 模板类(类模板) 模板声明格式为： template ,函数模板,对于功能和操作基本相同,只是参数或返回值类型不同的若干函数，可以通过函数模板实现. int max(int x, int y) / 求两个整数的最大值 return (x y)? x : y; float max(float x, float y) / 求两个浮点数的最大值 return (x y)? x : y; char max(char x, char y) / 求两个字符的最大值 return (x y)? x : y; ,templat

5、e T max( T x, T y) return (x y)? x : y; void main() int x1 = 10, y1 = 8; float x2 = 20.3, y2 = 33.5; char x3 = k, y3 = n; cout “max(x1,y1) = “ max(x1, y1) endl; cout “max(x2,y2) = “ max(x2, y2) endl; cout “max(x3,y3) = “ max(x3, y3) y)? x : y; / 模板函数 char* max(char* x, char* y) / 非模板函数 return (strcm

6、p(x, y) = 0)? x: y; void main() char ch16 = “abc”; char ch26 = “def”; cout “max(ch1,ch2) = “ max(ch1, ch2) = 0)? x: y; const char* max(char* x, const char* y) / 函数3 return (strcmp(x, y) = 0)? x: y; void main() char ch16 = “abc”; char ch26 = “def”; cout “max(ch1,ch2) = “ max(ch1, ch2) endl; ,重载模板函数,函

7、数匹配顺序：函数2函数1函数3,模板类,模板类允许用户为类定义一种模式，使得类中某些数据成员,成员函数的参数以及返回值，能取任意类型(包括标准类型及自定义类型). template / 模板声明 class array T* data; int size; public: array(int size); T,在类定义体外定义成员函数时，需进行模板声明，并在类名后缀“”. template / 模板声明 array:array(int size) / template / 模板声明 T for(int i = 0; i 5; i+) xi = i; for( i = 0; i 5; i+) c

8、out xi endl; 示例程序:10_01,3. STL的使用,STL(standard template library)是C+提供的一套模板库，包含: list 链表 vector 集合(动态数组) stack 栈 queue 队列 map 图 其它几种,list模板,STL中的list模板封装了链表操作: begin() 指向链表头(节点) end() 指向链表结束(不是指向表尾节点) push_front(), push_back() 添加头/尾节点 pop_front(), pop_back() 取出头/尾节点 erase() 删除链表中一节点 insert() 插入节点到链表中

9、 clear() 清空链表 size() 返回链表大小 其它操作 示例程序:10_02,vector模板,STL的vector模板封装了动态数组的操作: begin() 指向数组头(节点) end() 指向数组结束(不是指向数组尾元素) push_back() 添加头/尾节点 pop_back() 取出头/尾节点 erase() 删除链表中一节点 insert() 插入节点到链表中 clear() 清空链表 size() 返回链表大小 operator 下标操作 其它操作,迭代器iterator,在链表等结构中,一般都有prev,next等指针,通过指针迭代来遍历链表. 大多数模板中，都有迭代

10、器类型iterator,通过迭代器来实现遍历. list intList; /* 此处省略加入数据操作 */ list:iterator it = intList.begin(); / 指向头元素 while(it != intList.end() ) / 直到链表最后 cout *it “ “; it+; / 迭代指向下一元素 示例程序：10_03,泛型算法,为了方便程序员开发，STL中不仅封装了多种模板，还提供了很多泛型算法(函数). 泛型算法指独立于具体模板的算法: min(), max() 求最大值最小值 sort() 排序 find() 查找 remove() 删除 accumula

11、te() 算数计数 更多的算法请教材或C+ Primer相关章节及附录.,所有泛型算法前两个实参都是一对iterator,通常被称为first和last. 泛型算法正确工作的要求： 能遍历模板中元素集合：从first通过反复递增操作能到达last. 模板种元素能进行比较：关联的底层类型支持等于操作符. 需要一个公共类型来表示元素在容器中的位置，以及没有找到时使用的无位置(no position). 使用泛型算法需要包含和头文件.,泛型算法,因为STL中list不像vector一样支持随即访问,所以remove,sort等泛型算法不能用于list，但list模板本身封装了这些算法： list:sort() 排序 list:merge() 合并两个有序序列 list:reverse() 元素方向排列 list:remove() 删除等于某个值的元素 ,泛型算法,泛型算法示例,从屏幕(或文件)输入一段文字，利用泛型函数(算法)实现： 按字母顺序排列单词 去掉所有重复的单词 去掉没有意义的中性词(如and,if,or,but等) 统计超过6个字母的单词的个数. 示例程序10_04.,仿照示例程序10_01编写模板类matrix，支持任意数据类型