面向对象程序设计—第八章stl

1、西安交通大学1 第八章第八章 模模 板板2西安交通大学28.18.1模模 板板 模板的概念的引入 使用模板的原因 函数模板 类模板3西安交通大学38.18.1模板概念的引入模板概念的引入 一个程序的功能在对不同的数据类型进行相同处理过程时，可以将所处理的数据类型说明为参数，这样就产生了模板的概念。 例如： int abs(int value) /求整型的绝对值 return value0?value:-value; double abs (double value) /求double型的绝对值 return value0?value:-value; 4西安交通大学4这两个函数，功能几乎一样，只

2、是返回值和参数不一样。C+提供了函数模板的功能来简化我们对这种情况的表达： Template /使用函数模板来简化上面的情况 T abs(T value) return value0?value:-value; 其中T代表函数模板中要使用的通用类型，在函数的调用过程中，T被具体化。5西安交通大学5模板是实现代码重用机制的一种工具，它可以实现类型参数化，即把类型定义参数，从而实现了真正的代码可重用性。 模板分为函数模板和类模板。它们分别允许用户定义模板函数和模板类。下面的图显示了模板、模板函数和模板类和对象之间的关系。6西安交通大学6模板函数模板（函数模板和类模板）实例化模板类实例化对象实例化7

3、西安交通大学78.28.2使用模板的原因使用模板的原因先看下面的程序段: int max(int x, int y) /对整型数据操作 return (xy)? x:y; float max(float x, float y) /对浮点型数据操作return (xy)? x:y;double max(double x, double y) /对double型数据操作return (xy)? x:y;8西安交通大学8上面这组函数的功能都是相同的，都是在两个数中取较大的数进行输出，只是参数类型和函数的返回类型不同。但是我们发现，要想实现对任意类型的的两个数的大小进行比较，我们需要考虑到所有参数类型

4、和返回类型，同时，针对每种参数类型和返回类型我们都要定义相关的函数，这样做无论是在代码量还是在效率上都是相当繁琐的。 9西安交通大学98.38.3函数模板函数模板 函数模板的声明 函数模板与模板函数 函数模板的使用 模板函数重载的调用顺序10西安交通大学10函数模板的声明函数模板的声明函数模板的声明如下：template 返回类型 函数名（模板形参表） 函数体或者template返回类型 函数名（模板型参表） 函数体 11西安交通大学11其中template是声明模板的一个关键字，它表示声明一个模板。关键字class表明后面的是模板形参表，将模板形参实例化的参数称为模板实参，用模板实参实例化的

5、函数称为模板函数。函数模板的调用形式：函数名（实参数表）；12西安交通大学12我们先来看一个例子1. #include “iostream.h”2. template /声明一个函数模板3. T max(T x, T y)4. 5. return (xy)? x:y;6. 13西安交通大学137. void main()8.9.int a = 6, b = 8;10.float c = 8.5, d = 2.2;11.double e = 21.123, f = 145.987;12.char g = z, h = m;13.coutmax(a,b)endl; /函数模板的实例化14.cout

6、max(c,d)endl;15.coutmax(e,f)endl;16.coutmax(g,h)endl;17.14西安交通大学14程序输出结果为： 8 8.5 145.987 z主程序main()中利用函数模板一共生成了四个模板函数max(a,b), max(c,d), max(e,f), max(g,h)。max(a,b)用模板实参int将模板类型参数T进行了实例化；max(c,d)用实参float对T进行了实例化；max(e,f)用实参double对T进行了实例化；max(g,h)用实参char对T进行了实例化，也就是说，我们利用函数模板声明的函数，可以根据我们的需要对其进行实例化，尤其

7、对于参数类型不同但具体操作相同的函数尤为有用。 15西安交通大学15函数模板与模板函数函数模板与模板函数看一段主程序的代码:1.main() /主程序2.int i1=10, i2=56;3.float f1=12.5, f2=24.5;4.double d1=50.344, d2=4656.346;5.char c1=k, c2=n;6.cout”the max of i1,i2 is:”max(i1,i2)endl; 7. /根据传入的参数类型生成模板函数max(int,int)8.cout”the max of f1,f2 is:”max(f1,f2)endl; 9. /根据传入的参数类

8、型生成模板函数max(float,float)10.cout”the max of d1,d2 is:”max(d1,d2)endl; 11. /根据传入的参数类型生成模板函数max(double,double)12.cout”the max of c1,c2 is:”max(c1,c2)endl; 13. /根据传入的参数类型生成模板函数max(char,char)14.return 0;15. 16西安交通大学16上面例子中，函数模板max(x,y)根据传入的参数类型不同，生成了四个模板函数：17西安交通大学17函数模板和模板函数的区别：函数模板是模板的定义，定义中用到的是通用的参数类型，

9、它可以是任意类型T为参数和返回值。模板函数是实实在在的函数定义，它是由编译系统碰见具体函数调用时生成的，具有函数代码。函数模板代表了一类函数，模板函数表示某一具体的函数。18西安交通大学18函数模板的使用函数模板的使用 函数模板实现了函数参数的通用性，作为代码的重用机制，可以大幅度的提高程序设计的效率。关于函数模板有几点说明：(1)在函数模板中允许使用多个类型的参数，要注意template定义部分的每个模板参数前必须有关键字class。下面的例子建立了有两个模板形参的函数模板：#include /C+IO流头文件/定义两个参数的函数模板templatevoid myfunc(type1 x,

10、type2 y)coutx “ “ yendl;19西安交通大学19(2)在template语句与函数模板定义语句之间不允许有别的语句，比如：templateint i; /编译错误，不允许有别的语句T max(T x, T y) return (xy)?x:y;(3)函数可以带有模板参数表中未给出的、已存在的数据类型的参数。例如： template T func2(T arg1，int arg2) 20西安交通大学20void outdata(int i) couti;void outdata(double d) cout”d=”dendl;因为它们输出的内容和格式有所区别。(4)模板函数类

11、似于重载函数，只不过它更严格一点，函数被重载的时候，在每个函数体内部可以执行不同的动作，但是对于同一函数模板被实例化后的所有的模板函数都必须执行相同的动作。下面的情况就不能使用函数模板：21西安交通大学211.template2.T max(T x, T y)3.return (xy)?x:y; 4.void func(int i,char c)5.6. max(i, i); /正确 ,调用max(int,int)7. max(c, c); /正确 ,调用max(char,char)8. max(i, c); /错误 ,类型不匹配9. max(c, i); /错误 ,类型不匹配10. (5)函

12、数模板中的模板参数T可以实例化为各种类型，但是实例化T的各模板之间必须保持完全的一致，否则会发生错误。在这种情况下，函数模板中没有隐式的类型转换。例如：22西安交通大学22解决上面的问题有两种方法：(1)采用强制类型转换。 将max(i,c)；改写为max(i,int(c);(2)用非模板函数重载函数模板，这样下面重载有两种方式。23西安交通大学23声明一个非模板函数的原型：1.template2.T max(T x, T y)3.4.return (xy)?x:y;5.6.int max(int, int)；/只声明一个非模板函数的原型7.void func(int i,char c)8.9

13、. max(i, i); /正确 ,调用max(int,int)10. max(c, c); /正确 ,调用max(char,char)11. max(i, c); /正确 ,调用 max(int,int),使用隐式类型转换12. max(c, i); /正确 ,调用max(int,int),使用隐式类型转换13. 24西安交通大学24定义一个完整的非模板函数重载模板函数按照这种方式定义重载函数，所带的参数类型可以随意，就像一般的重载函数一样定义。比如：在上面程序的模板定义下面定义如下函数：char *max(char *x, char *y) return (strcmp(x,y)0)?x:

14、y;此函数重载了上述函数模板，当出现调用语句max(“abcd”,“efgh”)；时，执行的是这个重载的非模板函数。25西安交通大学25举例举例: :定义一个求幂函数的函数模板定义一个求幂函数的函数模板1. #include 2. template 3. T Power(T a, int exp)4. 5.T ans = a;6.while(-exp0) ans*=a;7.return ans;8. 9. / 测试用主函数10.int main()11.12.cout 35= Power(3, 5) endl;13.cout 1.12= Power(1.1, 2) endl;14.return

15、 0;15.运算结果:35=2431.12=1.2126西安交通大学26举例举例: :用函数模板实现顺序查找算法用函数模板实现顺序查找算法1. #include 2. template 3. int sequentialsearch(T a, const T& k, int n)4. int i=0;5.while(k!=ai&in-1)i=-1;7.return i;8. 9. int main() / 测试用主函数10. int i1 =3, 2, 5, 0, -1, 7;11.double d1 =3.3, 2.1, 0.3, 1.5, 10.6, 5.2;12.char *c1=xjt

16、u;13.cout sequentialsearch(i1, 15, 6) endl;14.cout sequentialsearch(d1, 3.3, 5) endl;15.cout sequentialsearch(c1, j, 4) endl;16.return 0;17. 运算结果:-10127西安交通大学27模板函数重载模板函数重载的调用顺序的调用顺序在C中，函数模板与同名的非模板函数重载时，调用的顺序遵循下述约定：l 寻找一个参数完全匹配的函数，如果找到就调用它。l 寻找一个函数模板，将其实例化，产生一个匹配的模板函数。若找到了，就调用它。l 若（1）和（2）都失败，再试一试低一级

17、的对函数的重载方法。例如通过类型转换可产生参数匹配等，若找到了，就调用它。若（1），（2），（3）均未找到匹配的函数，则是一个错误的调用。如果在第（1）步有多于一个的选择，那么这个调用是意义不明确的，是一个错误调用。28西安交通大学288.48.4类模板类模板类模板的定义：template class ClassName /具体内容;或template class ClassName /具体内容;29西安交通大学29调用形式： ClassName object；模板类是类模板对某一特定类型的实例。类模板代表了一类类，模板类表示某一具体的类。30西安交通大学30看下面一个例子:1.templat

18、e /声明一个类模板2.class stack /定义类模板3.4.private:5.T size20; /数组可取任意类型，即6. /模板参数类型T7.int p;8.public:9.void init()10.11.p = 0;12.31西安交通大学3112. void push(T obj)13.14.sizep = obj;15.p+;16.17.T pop();18.;19.template 20.T stack:pop()21.22.return sizep;23.p-;24.32西安交通大学32在类定义体外定义成员函数时，若此成员函数中有类型参数存在，则需要在函数体外进行模板

19、声明，并且在函数名前的类名后缀上“”。例如成员函数pop()。 33西安交通大学33类模板与模板类的关系 类模板不代表一个具体的实际的类，而代表了一系列的类。实际上，类模板的作用是将类模板实例化成一个具体的类。模板类是类 模 板 对 某 一 特 定 类 型 的 实 例 ， 比 如stack, stack, stack等，模板类表示某一具体的类。34西安交通大学3435西安交通大学35 关于类模板的几点说明：(1)在每个类模板定义之前，都需要在前面加上模板声明，如： template类模板在使用的时候，必须在名字后面缀上模板参数 ,例如stack。(2)模板类可以有多个模板参数，例如：36西安交

20、通大学361.#include2.template /定义两个模板参数的类模板3.class myclass4. T1 i;T2 j;5.public:6. myclass(T1 a, T2 b) i=a; j=b; 7. void show() cout”i=”i” j=“jendl; 8.; /定义结束37西安交通大学379./主程序10. main()11. 12. myclass ob1(12, 0.15); 13. /定义模板类myclass14. mycalssob2(x, “This is a test”); 15. /定义模板类myclass16. ob1.show();17.

21、 ob2.show();18. return 0;19. 上面的程序中声明了有两个模板参数的类模板。程序运行结果:i=12 j=0.15i=x j=This is a test38西安交通大学38举例举例: :栈类模板栈类模板在这个实例中实现了一个简单的栈（先进后出的数据结构）：1.#include 2.template /定义栈类3.class stack4.5.private:6.T stck100;/定义栈空间7.int tos;/定义栈顶位置8.public:9.stack()tos=0;/构造函数10.void push(T ch); /压栈11.T pop();/出栈12.39西安

22、交通大学3913. /压栈实现14. template 15. void stack :push(T ch)16. 17.if(tos=100-1)/合法性判断18.19.cout stack is fulln;20.return;21.22.stcktos=ch;/入栈操作23.tos+;/栈顶指针加124. 40西安交通大学4025./出栈实现26.template 27.T stack :pop()28.29.if(tos=0)/合法性判断30.31.cout stack is emptyn;32.return 0;33.34.tos-;/栈顶位置减135.return stcktos;

23、/返回栈顶数据36.41西安交通大学4137. /主函数38. main()39. 40.stack s1,s2; /定义两个栈S1，S241.int i; /定义变量42.s1.push(a); /压栈S143.s2.push(x); /压栈S244.cout pop s1:s1.pop()endl; /出栈S1并显示45.cout pop s2:s2.pop()endl; /出栈S2并显示46.return 1;47. 运算结果:pop s1:apop s2:x42西安交通大学428.58.5综合训练综合训练训练1： 设计一个堆栈的类模板，利用堆栈的类模板分别实现整数入栈和出栈处理，实数的

24、入栈和出栈处理，字符型的入栈和出栈处理。 分析: 定义一个栈的类模板。栈操作需要检测栈满和栈空。在主函数中使用三个模板类来说明三个对象。 一个完整的参考程序如下：43西安交通大学43举例举例: :定义通用数组类定义通用数组类1. 1. #include iostream.h#include 2. 2. template template 3. 3. class arrayclass array4. 4. 5. 5. public:public:6. 6.X X * *ptrptr; ;7. 7.array(int N) ptrarray(int N) ptr=new XN;=new XN;8.

25、 8. ; ;9. 9. intint main() main()10.10. 11.11.arrayintarray a(16); a(16);12.12.a.ptr0=168;a.ptr0=168;13.13.coutarray class: a.ptr0endlcoutarray class: a.ptr0endl; ;14.14.return 0;return 0;15.15. 运算结果:array class:16844西安交通大学44综合训练综合训练1 11.#include2.#include3.template4.class Stack5. public:6. Stack(in

26、t size); /构造函数7. Stack() /析构函数 8. delete s;9. void push(SType i); /入栈操作10. SType pop(); /出栈操作11. private:12. int tos,length; /length为栈的空间长度,tos为栈内已占空间的长度13. SType *s;14.;15.template 16.Stack:Stack(int size)17.18. s=new Stypesize;19. if(!s) /如果内存分配不成功45西安交通大学4520.21. coutCant Allocate stack.endl;22.

27、exit(1);23. 24. length=size;25. tos=0;26.27.template28.void Stack:push(SType i)29.30. if(tos=length) /如果栈满31. 32. coutStack is fullendl;33. 34. stos=i;35. tos+;36.37.template 38.Stype Stack:pop()39.40. if(tos=0) /如果栈空41. 46西安交通大学4642. coutStack overflow.endl;43. return 0;44. 45. tos-;46. return stos

28、;47.48.void main()49.50. Stacka(10);51. Stackb(10);52. Stackc(10);53. a.push(45);54. b.push(100-0.7);55. a.push(10);56. a.push(8+6);57. b.push(2*1.5);47西安交通大学4758. couta.pop(),;59. couta.pop(),;60. couta.pop();61. coutb.pop(),;62. coutb.pop()endl;63. for(int i=0;i10;i+)64. c.push(char)j-i);65. for(i

29、=0;i10;i+)66. coutc.pop();67. coutendl;68.48西安交通大学48综合训练综合训练2 2训练2：设计一个单向链表的类模板，输出26个英文字母。 分析: 类模板不是一个具体的实际的类，使用时必须首先将其实例化为具体的模板类，然后再通过模板类定义对象。一个完整的参考程序如下：49西安交通大学491.#include2.template3.class List4. public:5. List(DType d)data=d;next=0; /构造函数6. void Add(List *node)node-next=this;next=0;7. List*GetN

30、ext()return next;8. DType GetData()return data;9. private:10. DType data;11. List *next;12.;13.void main()14.15. Liststart(a); /定义模板类对象start16. List*p,*last; /定义模板类对象指针*p,*last50西安交通大学5018. last=&start;19. for(int i=1;i26;i+)20. 21. p=new List(a+i);22. p-Add(last);23. last=p;24. 25. coutendl;26. p=&

31、start;27. while(p)28. 29. coutGetData();30. p=p-GetNext();31. 32.51西安交通大学518.68.6本章小结本章小结本章主要介绍了面向对象程序设计思想中的一个非常具有特点的内容-模板。模板的使用充分体现了多态性的思想，利用模板，我们可以很方便地使用较少的程序段完成以往要使用诸多语句才能完成的工作，极大地优化了程序设计并提高了程序的易读性。 52西安交通大学52思考与练习题思考与练习题l需要编写一个对多维数组通用的算法（即各维的大小未定），怎样才能把实参多维数组的信息全部传递到函数中去？l什么叫函数模板？什么叫模板函数？什么叫类模板？

32、什么叫模板类？ l函数模板和模板函数，类模板和模板类之间的关系如何？l函数模板与同名的非模板函数重载时，调用的顺序是怎样的？ 53西安交通大学53什么是STL “什么是STL？”，假如你对STL还知之甚少，那么我想，你一定很想知道这个问题的答案，坦率地讲，要指望用短短数言将这个问题阐述清楚，也决非易事。 STL（Standard Template Library），即标准模板库，是一个具有工业强度的，高效的C+程序库。它被容纳于C+标准程序库（C+ Standard Library）中，是ANSI/ISO C+标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据

33、结构和基本算法。为广大C+程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。这种现象有些类似于Microsoft Visual C+中的MFC（Microsoft Foundation Class Library），或者是Borland C+ Builder中的VCL(Visual Component Library)， 54西安交通大学54 从逻辑层次来看，在STL中体现了泛型化程序设计的思想（generic programming），引入了诸多新的名词，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algo

34、rithmn），迭代子（iterator）等。与OOP（object-oriented programming）中的多态（polymorphism）一样，泛型也是一种软件的复用技术。 从实现层次看，整个STL是以一种类型参数化（type parameterized）的方式实现的，这种方式基于一个在早先C+标准中没有出现的语言特性-模板（template）。如果查阅任何一个版本的STL源代码，你就会发现，模板作为构成整个STL的基石是一件千真万确的事情。除此之外，还有许多C+的新特性为STL的实现提供了方便。 55西安交通大学55STL和C+ 没有C+语言就没有STL，这么说毫不为过。一般而言，

35、STL作为一个泛型化的数据结构和算法库，并不牵涉具体语言（当然，在C+里，它被称为STL）。也就是说，如果条件允许，用其他语言也可以实现之。这里所说的条件，主要是指类似于“模板”这样的语法机制。 C+只有在引入了“模板”之后，才直接导致了STL的诞生。这也正是为什么，用其他比C+更纯的面向对象语言无法实现泛型思想的一个重要原因。当然，事情总是在变化之中，像Java在这方面，就是一个很好的例子，jdk1.4中已经加入了泛型的特性。 56西安交通大学56 此外，STL对于C+的发展，尤其是模板机制，也起到了促进作用。比如：模板函数的偏特化（template function partial spe

36、cialization），它被用于在特定应用场合，为一般模板函数提供一系列特殊化版本。这一特性是继STL被ANSI/ISO C+标准委员会通过之后，在Bjarne和Stepanov共同商讨之下并由Bjarne向委员会提出建议的，最终该项建议被通过。这使得STL中的一些算法在处理特殊情形时可以选择非一般化的方式，从而保证了执行的效率。 57西安交通大学57STL和C+标准函数库 STL是最新的C+标准函数库中的一个子集，这个庞大的子集占据了整个库的大约80%的分量。而作为在实现STL过程中扮演关键角色的模板则充斥了几乎整个C+标准函数库。在这里，我们有必要看一看C+标准函数库里包含了哪些内容，其

37、中又有哪些是属于标准模板库（即STL）的。 C+标准函数库为C+程序员们提供了一个可扩展的基础性框架。我们从中可以获得极大的便利，同时也可以通过继承现有类，自己编制符合接口规范的容器、算法、迭代子等方式对之进行扩展。它大致包含了如下几个组件： C标准函数库，基本保持了与原有C语言程序库的良好兼容，尽管有些微变化。人们总会忍不住留恋过去的美好岁月，如果你曾经是一个C程序员，对这一点一定体会颇深。或许有一点会让你觉得奇怪，那就是在C+标准库中存在两套C的函数库，一套是带有.h扩展名的（比如），而另一套则没有（比如）。它们确实没有太大的不同。58西安交通大学58 语言支持（language support）部分，包含了一些标准类型的定义以及其他特性的定义，这些内容，被用于标准库的其他地方或是具体的应用程序中。 诊断（diagnostics）部分，提供了用于程序诊断和报错的功能，包含了异常处理（exception handling），断言（asser