C STL泛型编程分析

1C++STL泛型编程（GenericProgramming）2为什么要采用泛型编程？•项目中,需要用到数组、链表、字符串、栈、队列、平衡二叉树等数据结构，以及排序、搜索等算法；•若全部自行编写比较麻烦；•ANSIC++中包含了C++STL(StandardTemplateLibrary,标准模板库,又称C++泛型库)，定义了常用的数据结构和算法，使用十分方便。•有了STL，不必再从头写大多的标准数据结构和算法，并且可获得非常高的性能。但这不意味着我们不需要掌握基本数据结构与算法;相反,只有透彻理解了,才能更好的使用泛型!泛型程序设计•由AlexanderStepanov和DavidMusser创立，于1998年被添加进C++标准.•含义：编写不依赖于具体数据类型的程序.•目标：将程序写得尽可能通用.•将算法从特定的数据结构中抽象出来，成为通用的.•C++的模板为泛型程序设计奠定了关键的基础.•STL(标准模板库,StandardTemplateLibrary)是泛型程序设计的一个范例.代码重用(reuse)!函数模板简介4【引例】交换2个整数和交换2个浮点数的C++程序://交换2个整数voidSwap(int&a,int&b){inttmp=0;tmp=a;a=b;b=tmp;}//交换2个浮点数voidSwap(float&a,float&b){floattmp=0.0;tmp=a;a=b;b=tmp;}intmain(){inta=10,b=20;floatc=1.2,d=2.4;couta=ab=b;coutc=cd=c;Swap(a,b);couta=ab=b;Swap(c,d);coutc=cd=c;return0;}两个Swap函数实现的功能相同，只是参数类型不同，但为了实现不同类型的数据交换必须分别编写函数。造成了重复劳动。函数重载5能否提供一种方法将两个函数合并，以节省开发成本？引例typedefintDataType;voidSwap(DataType&a,DataType&b){DataTypetmp;tmp=a;a=b;b=tmp;}intmain(){inta=10,b=20;Swap(a,b);return0;}当需要交换两个浮点数时可以将DataType定义成float型数据即可。typedeffloatDateType;存在问题：•更改一种数据类型时，需要修改程序源代码，必须重新编译程序。•如果程序中需要交换多种数据类型数据,怎么办？6引例#includeiostreamusingnamespacestd;templateclassTvoidSwap(T&x,T&y){Ttmp=x;x=y;y=tmp;}intmain(){inta=10,b=20;floatc=1.2,d=2.4;couta=ab=bendl;coutc=cd=cendl;Swap(a,b);couta=ab=bendl;Swap(c,d);coutc=cd=cendl;return0;}模板声明定义函数模板通用的Swap!能否将Swap函数的形式参数，作为一种无类型的参数，当使用它的时候再将它用具体的参数实现？模板机制模板的概念1.模板是一种使用无类型参数来产生一系列函数或类的机制。2.模板是以一种完全通用的方法来设计函数或类而不必预先说明将被使用的每个对象的类型。3.通过模板可以产生类或函数的集合，使它们操作不同的数据类型，从而避免需要为每一种数据类型产生一个单独的类或函数。7模板分类•函数模板(functiontemplate)–是独立于类型的函数–可产生函数的特定版本•类模板(classtemplate)–与类相关的模板，如vector–可产生类对特定类型的版本，如vectorint8模板工作方式•模板只是说明，需要实例化后才能执行或使用.9模板函数模板类模板模板类模板函数对象实例化实例化实例化函数模板(functiontemplate)定义格式：template模板参数表类型名函数名（参数表）{函数体}templateclassTvoidSwap(T&x,T&y){Ttmp=x;x=y;y=tmp;}10•template:函数模板定义关键字.•中是函数的模板参数，参数可有一个或多个，逗号隔开。不能为空！•模板参数常用形式：class标识符或者typename标识符模板参数表明函数可以接收的类型参数，可以是内部类型，也可以是自定义类型.templatetypenameTvoidSwap(T&x,T&y){Ttmp=x;x=y;y=tmp;}【例1】简单函数模板定义和应用.#includeiostreamusingnamespacestd;templatetypenameTTMax(Ta,Tb){returnab?a:b;}intmain(){coutMax(3,5)isMax(3,5)endl;coutMax('y','e')isMax('y','e')endl;coutMax(9.3,0.5)isMax(9.3,0.5)endl;return0;}函数模板intMax(inta,intb){returnab?a:b;}由实参类型实例化charMax(chara,charb){returnab?a:b;}doubleMax(doublea,doubleb){returnab?a:b;}编译器生成的模板函数函数模板实例化函数模板的原理分析：•函数模板中声明了类型参数T，表示了一种抽象类型.•编译器检测到程序调用函数模板Max时，用其第一个实参类型替换掉模板中的T，同时建立一个完整的函数Max，并编译该新建的函数.•本例中，针对三种数据类型，生成了三种函数.【练习1】编写一个对具有n个元素的数组a[]求最小值的程序，要求将求最小值的函数设计成函数模板。#includeiostreamusingnamespacestd;templateclassTTMinArray(Ta[],intn){inti;Tmina=a[0];for(i=1;in;i++){if(minaa[i])mina=a[i];}returnmina;}intmain(){intarr1[]={1,3,0,2,7,6,4,5,2};doublearr2[]={1.2,-3.4,6.8,9,8};coutarr1数组的最小值为：MinArray(arr1,9)endl;coutarr2数组的最小值为：MinArray(arr2,4)endl;return0;}注意点1：实参类型与形参类型必须严格匹配.#includeiostreamusingnamespacestd;templateclassTTMax(Ta,Tb){returnab?a:b;}intmain(){inta=3;floatb=1.5;coutMax(a,b)isMax(a,b)endl;return0;}错误！模板类型不能提供类型的隐式转换注意点2：在函数模板中允许使用多个类型参数。在template定义部分的每个模板形参前必须有关键字class或typename.#includeiostreamusingnamespacestd;templateclassT1,classT2voidmyfunc(T1x,T2y){coutx,yendl;}intmain(){myfunc(100,hao);myfunc(3.14,10L);return0;}•注意点3：在template语句与函数模板定义语句之间不允许有别的语句。TemplateclassTinti;//错误，不允许有别的语句TMax(Tx,Ty){return(xy)?x:y;}8模板优缺点优点:函数模板方法克服了C语言用大量不同函数名表示相似功能的弊端;克服了宏定义不能进行参数类型检查的弊端;克服了C++函数重载用相同函数名字重写几个函数的繁琐.缺点:调试比较困难.一般先写一个特殊版本的函数运行正确后，改成模板函数1617【练习2】编写一个函数模板，它返回两个值中的较小者，同时要求能正确处理字符串。分析：•由于C++字符串比较的方法与字符型、数值型都不同，因此函数模板不适用于字符串比较；̶这里设计一个函数模板templateclassTTmin(Ta,Tb)，可以处理int、float和char等数据类型；̶为了能正确处理字符串，添加一个重载函数专门处理字符串比较，即char*min(char*a,char*b)。#includeiostream.h#includestring.htemplateclassTTmin(Ta,Tb){return(ab?a:b);}char*min(char*a,char*b){return(strcmp(a,b)0?a:b);}voidmain(){doublea=3.14,b=8.28;chars1[]=Bad,s2[]=Good;cout输出结果:endl;coutmin(a,b)endl;coutmin(s1,s2)endl;}函数模板函数重载19也可以显式指定（explicitlyspecify），如：i=maxint(ia,5);d=maxdouble(da,6);这样可读性更好。这里数组名是作为指向数组首元素的指针进行传递，数组长度是由size参数进行传递的。用函数模板求数组元素中最大值templatetypenameGroapGroapmax(constGroap*r_array,intsize){inti;Groapmax_val=r_array[0];for(i=1;isize;++i)if(r_array[i]max_val)max_val=r_array[i];returnmax_val;}20函数模板可以重载,形参表不同即可例,下面两个模板可以同时存在:templateclassT1,classT2voidprint(T1arg1,T2arg2){coutarg1arg2endl;}templateclassTvoidprint(Targ1,Targ2){coutarg1arg2endl;}21匹配顺序C++编译器遵循以下优先顺序:Step1:先找参数完全匹配的普通函数(非由模板实例化而得的函数)Step2:再找参数完全匹配的模板函数Step3:再找实参经过自动类型转换后能够匹配的普通函数Step4:上面的都找不到,则报错22例:函数模板调用顺序templateclassTTMax(Ta,Tb){coutTemplateMax1endl;return0;}templateclassT,classT2TMax(Ta,T2b){coutTemplateMax2endl;return0;}23doubleMax(doublea,doubleb){coutMyMaxendl;return0;}voidmain(){inti=4,j=5;Max(1.2,3.4);Max(i,j);Max(1.2,3);}//调用Max(double,double)函数//调用第一个TMax(Ta,Tb)模板生成的函数//调用第二个TMax(Ta,T2b)模板生成的函数运行结果:MyMaxTemplateMax1TemplateMax224可以在函数模板中使用多个类型参数,可以避免二义性templateclassT1,classT2T1myFunction(T1arg1,T2arg2){coutarg1“”a