模板与泛型编程

1、6.1 模板的概念 6.2 函数模板 6.3 类模板 6.4 编程示例:栈模板 6.5 泛型编程,第 6 章 模板,6.1 模板的概念,6.1.1 什么是模板 在编程中程序员经常会遇到这样的情况，对于不同数据类型的参数虽然需要实现相似的函数功能，例如编写求两个整型数据中最大值的函数与求两个实型数据最大值的函数，它们的程序逻辑相同，程序代码也相同，只是它们的参数类型与返回值类型不同。对这样的情况，在C语言中程序员不得不定义两个函数，然后将程序代码重复书写一遍。同样有时也会遇到具有类似功能的类，例如一个整型数据集合的类与实型数据集合的类，它们实现的功能相同，但存储的数据类型不同。,对于上面的情况，

2、C+语言中可以使用模板来避免在程序中多次书写相同的代码。模板是一种描述函数或类的特性的蓝图。可以从一个函数模板生成多个函数或从一个类模板生成多个类。建立一个模板后，编译器将根据需要从模板生成多份代码。,6.1.2 模板的基本语法 C+语言中使用关键字template开始一个模板的声明，模板声明的一般形式为： template说明体 模板参数表可以包含一个或多个模板参数声明，如果有多个模板参数，参数与参数之间以逗号隔开。例如带有一个参数的模板可以以下述形式开头： template class表示参数T是一个数据类型。在使用该模板时，T可以用用户定义的数据类型，也可以用C+语言固有的数据类型，如i

3、nt、float等替换。这里的class与类定义中的class没有关系。 参数标识符T也可以用其它的任何标识符来表示，例如：,template 通常的习惯是，表示数据类型的参数用T打头，后跟表示该参数的含义的英文单词，T表示英文Type。 多个参数的模板声明的格式为： template 类模板参数除了可以是数据类型外，还可以是其它类型的数据，例如整型数据： template 参数的具体使用方法将在下面两节中详细介绍。,6.2 函 数 模 板,6.2.1 函数模板的定义 不管它们的性质如何，所有的函数模板都具有同样的基本格式：,template 函数头 函数体 例如，下面是一个单参数的模板的声明

4、： template void f(T param) /此处为函数体 ,template关键字和尖括号中的class T一起开始了模板的构造。下面的函数头函数体中的T在使用时将被指定的类型标识符替代。模板中的每个参数在函数参数表中必须至少使用一次。下面的声明是不允许的： template void f(T1 param) /.函数体 这个函数模板声明了两个参数T1和T2，但是函数本身却只使用了T1来定义param。正确的声明应该是在函数参数表中至少使用T1和T2各一次：,template void f(T1 param1,T2 param2) /.函数体 下面是一个模板声明的程序源文件，读者可

5、以将它输入命名为minmax.h，以便在需要时使用。通常的习惯是，将模板放在头文件中声明，以便不同的程序文件可以共享。目前的编译器一般不支持将函数模板的声明与函数模板的函数体部分分别存放，生成独立的函数库文件，然后使用（普通函数可以在头文件中声明原型，函数实现放在独立的源文件中，编译生成函数库，在使用时只需要头文件中函数原型声明，而不需要函数实现的源代码）。,#ifndef MINMAX_H #define MINMAX_H/避免重复包含本文件 template T max(T a, T b) return (ab)?a:b; ,template T min(T a,T b) return (

6、a int inrange(T a,T b,T c) return (b=a) #endif,该程序中声明并实现了三个函数模板，每个模板都以下面的声明开始： template 在这个声明中，T是对象的类型，该对象由函数对其进行操作。下面的程序使用了上面定义的模板，从中可以看出如何使用函数模板： #include #include “minmax.h” int main( ) int a=123, b=456; coutmin(123,456)=min(a,b)n;,coutmax(123,456)=max(a,b)n; double c=3.14159, d=9.87654; coutmin(

7、3.14159, 9.87654)=min(c,d)n; coutmax(3.14159, 9.87654)=max(c,d)n; short s1=10, low=5, high=15; couts1=s1n; if(inrange(s1, low, high),coutlow=s1=highn; else couts1 is not within range lowtohighn; return 0; 从程序中可以看出，函数模板在使用时并没有显式地指明其参数，程序中有两处用到min模板，编译器根据参数的数据类型进行匹配。第一次使用min模板，其参数为整型数据，编译器从模板生成下面形式的函数

8、：,int min(int, int); 第二次使用参数为双精度型数据，编译器从模板生成下面形式的函数： double min(double,double); 这里编译器使用了函数的重载机制生成两个同名的函数，它们的参数形式不同，因此无须显式声明在套用模板时如何给定模板的参数。,*6.2.2 重设模板函数 前面的例子演示了如何定义一个函数模板以及如何使用，但有时可能需要替换已定义的模板，请看下面的例子：,#include minmax.h #include void main( ) char * first=first; char * second=second; coutmax(first,

9、second); ,根据已定义的模板，编译器将从模板生成下面的函数： char * max(char * a, char * b) return (ab)?a:b; 程序在执行的过程中将比较两个指针参数的值，而不是比较指针所指向的字符串，对char*类型的参数不能套用函数模板。C+语言允许在定义了一个模板后以特定的函数来替换模板，为修复上面程序的缺陷，可重新编写一个字符串求最大值的函数来代替含模板生成的函数。下面是修改后的程序代码：,#include minmax.h #include #include char * max(char * a,char * b) return strcmp(a

10、,b)0?a:b; void main( ) char * first=first; char * second=second; coutmax(first, second); ,现在编译器在编译表达式max(first,second)时，不再从max模板生成函数，而直接使用程序中定义的求字符串类型数据最大值的函数。 如果模板所产生的函数版本不能达到预期的结果，那么就可以使用上面的技术来替换模板。,*6.2.3 显式和隐式的模板函数 前面的例子中，编译器在由函数模板生成函数时根据程序中函数调用的参数类型进行匹配，生成的函数原型完全由编译器决定，无须在程序中显式声明。这种隐式生成的模板函数编译器

11、对参数类型进行精确匹配，不进行任何隐含的类型转换。看下面的程序片断：,template T max(T a, T b) return (ab)?a:b; void f(int i,char c) ,max(i, i);/调用max(int, int) max(c, c);/调用max(char, char) max(i, c);/没有匹配的max(int, char) max(c, i);/没有匹配的max(char, int) 这段代码在编译时将会产生以下的错误信息： Could not find a match for max(int, char) in function f(int, c

12、har) Could not find a match for max(char, int) in function f(int, char),int max(int, int); /显式声明max(int, int) void f(int i, char c) max(i, i); /调用max(int, int) max(c, c); /调用max(char, char) max(i, c); /调用max(int, int) max(c, i); /调用max(int, int) 通过显式声明模板函数，编译器对不能从模板进行精确匹配的调用试图以显式声明的函数原型进行匹配，这里将函数调用表

13、达式max(i,c)和max(c,i)中的c隐含转换为整型数据后传递给max。,如果用通常的方法定义一个原型为int max(int, int)的函数，语句max(i, c)和max(c, i)将可以正常编译，变量c被隐含地转换为整型数据后传递给max函数。 对于上面的这种情况，可以通过显式地声明从模板生成的函数原型来解决： template T max(T a, T b) return (ab)?a:b; ,*6.3 类 模 板,6.3.1 类模板的定义与使用 类模板定义了类的模式。例如前面提到的整型数据元素集合和实型数据元素集合的例子，它们实现的功能相同，不同的只是其存储的数据类型不同。将

14、其定义为类模板，模板的参数为该数据类型，可以由它来生成整型集合类和实型集合类。下面通过一个简单的例子来介绍如何定义和使用类模板。 #include template class Vector,T *data; int size; public: Vector(int); Vector( )delete data; T ,int main( ) Vector x(5); for(int i=0;i5;i+) xi=i; for(int i=0;i5;i+) coutxi ; coutn; return 0; ,这个例子中定义了一个类模板Vector，它有一个类型参数T，类定义的模板声明由temp

15、late开始，下面的类声明部分与普通类声明的方法相同，只是在部分地方用参数T表示数据类型。 模板类的每一个非内置函数的定义是一个独立的模板，同样以template开始，函数头中的类名由模板类名加模板参数构成，如例子中的Vector。 模板类在使用时与函数模板不同，函数模板无须显式指明使用模板时的参数（使用了函数重载机制），模板类在使用时必须指明参数，形式为：模板类名。例子中的Vector即是如此，编译器根据参数int生成一个int的Vector类，理解程序时可以将Vector看成是一个完整的类名。在使用时Vector不能单独出现，它总是和尖括号中的参数表一起出现。,6.3.2 类模板参数 上面

16、的例子中模板只有一个表示数据类型的参数，多个参数以及其它类型的参数也是允许的。请看下面的例子： template class Set T elemssize; /存储元素的数组 int card;/集合中元素的个数 public:,void EmptySet( )card=0; Bool Member(T); ErrCode AddElem(T); void RmvElem(T); void Copy(Set *); Bool Equal(Set *); void Print( ); void Intersect(Set *,Set *); ErrCode Union(Set *,Set *)

17、; ;,这个模板声明了一个集合类模板，实现了整型集合的功能，它有两个参数，一个表示集合存储的数据元素的类型，另一个为集合所能存储的数据元素的最大个数。如果需要一个大集合，则在使用时传递一个较大的常数给size；如果集合较小，则可以从模板生成一个元素个数较小的集合类，而无须担心浪费存储空间。像函数的参数可以有缺省值一样，这里也使用了缺省值，如果在使用时不指明size的大小，则使用缺省的常数值maxCard。 下面是该模板类非内置函数AddElem和Copy的实现，其它的函数请读者自行补充完整。,template ErrCode Set:AddElem(T elem) if(Member(elem

18、) return noErr; if(cardsize) elemscard+=elem; return noErr; return overflow; ,template void Set:Copy(Set *set) for(int i=0;ielemsi=elemsi; set-card=card; 可以通过下面的语句来使用Set类模板： Set set;,定义一个整型集合对象，参数T由int类型替换，而参数size使用缺省值maxCard，也可以像下面这样指明size的大小： Set s; 定义一个浮点型的数据集合对象，集合的最大元素个数为10。要注意的是，传递给size的值只能用常量

19、表达式，而不能含有变量，因为模板的参数是在编译时处理的，而在编译阶段不可能计算变量表达式的值。,6.4 编程示例: 栈模板,#include enum Bool False, True; /抽象堆栈类模板定义 template class AbsStack protected: unsigned height;,public: bool IsEmpty( )return (height=0)?True:False; virtual void push(T ,/使用数组存储数据元素的堆栈类模板 template class ArrayStack:AbsStack Bool Error; T ve

20、cSize; public: ArrayStack()Empty(); virtual void push(T ,/压栈操作 template void ArrayStack:push(T ,/出栈操作 template void ArrayStack:pop(T ,/读取栈顶元素 template void ArrayStack:ReadTop(T ,/置堆栈为空 template void ArrayStack: Empty( ) height = 0; void main() ArrayStack s; int i=30;,s.push(i); int j; s.pop(j); s.po

21、p(j); coutjn; if(s.IsError() couterrorn; else coutno errorn; ,上面的程序首先定义了一个抽象的堆栈模板类AbsStack，该类模板只定义了堆栈类的接口，没有定义存储堆栈数据元素的内部数据结构，可以从其派生出使用不同数据结构存储堆栈数据元素的堆栈类。本例中使用了常见的存储方法数组存储数据元素，然后实现了堆栈的常见运算。,42,6.5 泛型程序设计C+标准模板库,泛型程序设计 与标准模板库有关的概念和术语 C+标准模板库中的容器 迭代器 标准C+库中的算法 函数对象,43,泛型程序设计,将程序写得尽可能通用 将算法从特定的数据结构中抽象出

22、来，成为通用的 C+的模板为泛型程序设计奠定了关键的基础 STL是泛型程序设计的一个范例 容器(container) 迭代器(iterator) 算法（algorithms） 函数对象（function object）,44,命名空间（Namespace）,一个命名空间将不同的标识符集合在一个命名作用域（named scope）内 为了解决命名冲突 例如，声明一个命名空间NS： namspace NS class File; void Fun (); 则引用标识符的方式如下， NS: File obj; NS: Fun (); 没有声明命名空间的标识符都处于无名的命名空间中,概念和术语,45,

23、命名空间（Namespace）,可以用using来指定命名空间 例如，经过以下声明：using NS:File;在当前作用域中就可以直接引用File using namespace std;命名空间std中所有标识符都可直接引用 在新的C+标准程序库中，所有标识符都声明在命名空间std中，头文件都不使用扩展名。,概念和术语,46,容器,容器类是容纳、包含一组元素或元素集合的对象。 异类容器类与同类容器类 顺序容器与关联容器 七种基本容器： 向量（vector）、双端队列（deque）、列表（list）、集合（set）、多重集合（multiset）、映射（map）和多重映射（multimap）,

24、概念和术语,47,容器的接口,通用容器运算符 =，!=，=，=，= 方法（函数）：能够修改容器的状态 迭代方法 begin()，end()，rbegin()，rend() 访问方法 size()，max_size()，swap()，empty(),48,适配器,适配器是一种接口类 为已有的类提供新的接口。 目的是简化、约束、使之安全、隐藏或者改变被修改类提供的服务集合。 三种类型的适配器： 容器适配器 用来扩展7种基本容器，它们和顺序容器相结合构成栈、队列和优先队列容器 迭代器适配器 函数对象适配器。,概念和术语,49,迭代器,迭代器是面向对象版本的指针，它们提供了访问容器、序列中每个元素的方

25、法。,概念和术语,50,算法,C+标准模板库中包括70多个算法 其中包括查找算法，排序算法，消除算法，记数算法，比较算法，变换算法，置换算法和容器管理等等。 这些算法的一个最重要的特性就是它们的统一性，并且可以广泛用于不同的对象和内置的数据类型。,概念和术语,51,顺序容器,顺序容器的接口 插入方法 push_front()，push_back()，insert()，运算符“=” 删除方法 pop() ，erase()，clear() 迭代访问方法 使用迭代器 其它顺序容器访问方法（不修改访问方法） front()，back()，下标运算符,容 器,52,顺序容器向量,向量属于顺序容器，用于容

26、纳不定长线性序列（即线性群体），提供对序列的快速随机访问（也称直接访问） 向量是动态结构，它的大小不固定，可以在程序运行时增加或减少。 例10-1 求范围2N中的质数，N在程序运行时由键盘输入。,容 器,/10_1.cpp #include #include #include /包含向量容器头文件 using namespace std ; void main(void) vector A(10); int n; int primecount = 0, i, j; cout=2 as upper limit: ; cin n; Aprimecount+ = 2;,53,for(i = 3; i

27、 i/2) Aprimecount+ = i; for (i = 0; iprimecount; i+)/输出质数 coutsetw(5)Ai; if (i+1) % 10 = 0) /每输出10个数换行一次 cout endl; coutendl; ,54,55,顺序容器双端队列,双端队列是一种放松了访问权限的队列。元素可以从队列的两端入队和出队，也支持通过下标操作符“”进行直接访问。 例10-2 使用双端队列容器保存双精度数值序列,容 器,56,顺序容器列表,列表主要用于存放双向链表，可以从任意一端开始遍历。列表还提供了拼接（splicing）操作，将一个序列中的元素从插入到另一个序列中。

28、 例10-3 改写例9-7 从键盘输入10个整数，用这些整数值作为结点数据，生成一个链表，按顺序输出链表中结点的数值。然后从键盘输入一个待查找整数，在链表中查找该整数，若找到则删除该整数所在的结点（如果出现多次，全部删除），然后输出删除结点以后的链表。在程序结束之前清空链表。,容 器,/10_3.cpp #include #include using namespace std ; void main(void) list Link;/构造一个列表用于存放整数链表 int i, key, item; for(i=0;i item; Link.push_front(item); coutList

29、: ; / 输出链表,57,list:iterator p=Link.begin(); while(p!=Link.end()/输出各节点数据，直到链表尾 cout key; Link.remove(key); cout List: ; / 输出链表 p=Link.begin();/ 使P重新指向表头 while(p!=Link.end() cout *p ; p+; / 使P指向下一个节点 cout endl; ,58,59,容器适配器,容器适配器是用来扩展7种基本容器的 栈容器 使用适配器与一种基础容器相结合来实现 例10-4：应用标准库中的deque顺序容器生成一个整数栈stack。 队列容器 使用适配器与一种基础容器相结合来实现的先进先出数据结构。 例10-5：应用标准库中的deque顺序容器生成一个整数标准队列Queue。,容 器,60,什么是迭代器,迭代器是面向对象版本的指针 指针可以指向内存中的一个地址 迭代器可以指向容器中的一个位置 S