面向对象程序设计9模板

1、面向对象程序设计面向对象程序设计九、模板九、模板n模板的引入模板的引入n函数模板和模板函数函数模板和模板函数n类模板与模板类类模板与模板类nSTLSTL标准模板库的简单应用标准模板库的简单应用n【例【例】能否设计一个】能否设计一个“通用函数通用函数”，该函数能对，该函数能对各种数据类型的数组（基本类型数组或对象数组各种数据类型的数组（基本类型数组或对象数组）进行倒序？）进行倒序？n我们首先想到用已学知识我们首先想到用已学知识-重载来解决该问题重载来解决该问题第9章模板2022-5-204/对整型数组地址对整型数组地址beginbegin到到end-1end-1的元素倒序的元素倒序void Re

2、verse(intvoid Reverse(int* * begin,int begin,int* * end) end) /首尾元素交换首尾元素交换/然后然后beginbegin指针增指针增1 1，endend指针减指针减1 1for(;begin!=end&begin!=-end;beginfor(;begin!=end&begin!=-end;begin+)+) intint temp; temp;temp=temp=* *begin;begin;* *begin=begin=* *end;end;* *end=temp;end=temp; 第9章模板2022-5-205

3、/对实型数组地址对实型数组地址beginbegin到到end-1end-1的元素倒序的元素倒序void Reverse(floatvoid Reverse(float* * begin,float begin,float* * end) end) /首尾元素交换首尾元素交换/然后然后beginbegin指针增指针增1 1，endend指针减指针减1 1for(;begin!=end&begin!=-end;beginfor(;begin!=end&begin!=-end;begin+)+) intint temp; temp;temp=temp=* *begin;begin;*

4、 *begin=begin=* *end;end;* *end=temp;end=temp; n函数重载不仅方便用户对函数名的记忆，而且更函数重载不仅方便用户对函数名的记忆，而且更主要的是完善了同一个函数的代码功能，给调用主要的是完善了同一个函数的代码功能，给调用带来了许多方便。带来了许多方便。n它允许多个同名的函数存在，但同名的各个函数它允许多个同名的函数存在，但同名的各个函数的形参必须有区别：要从形参的类型、个数或顺的形参必须有区别：要从形参的类型、个数或顺序几个方面来区分。序几个方面来区分。n显然，如果需要处理所有数据类型的参数，则需显然，如果需要处理所有数据类型的参数，则需要更多的代码

5、进行函数重载。其冗余增加。要更多的代码进行函数重载。其冗余增加。n从例子代码可以看出，两个重载函数从算法上来从例子代码可以看出，两个重载函数从算法上来看是一样的，整个程序的区别仅仅在于函数所处看是一样的，整个程序的区别仅仅在于函数所处理数据类型的不同。如果可以将数据类型参数化理数据类型的不同。如果可以将数据类型参数化，那么我们只需要编写一个函数，就可以解决各，那么我们只需要编写一个函数，就可以解决各种数据类型数组的倒序问题，即函数模板。种数据类型数组的倒序问题，即函数模板。第9章模板2022-5-208n程序设计中，当参与运算的数的不同值会随实际程序设计中，当参与运算的数的不同值会随实际情况而

6、变化时，就使用变量来代替这个数。同理情况而变化时，就使用变量来代替这个数。同理，当处理的数据类型随实际情况变化时，可将数，当处理的数据类型随实际情况变化时，可将数据类型作为可变的部分（参数）从程序中抽取出据类型作为可变的部分（参数）从程序中抽取出来。当出现真实的数据类型时，再用具体的数据来。当出现真实的数据类型时，再用具体的数据类型代替；类型代替；n模板模板(Template)(Template)就是为解决这个问题而产生的；就是为解决这个问题而产生的；第9章模板2022-5-209n模板模板(Template)(Template)是对具有相同特性的函数或类的是对具有相同特性的函数或类的再抽象，

7、模板是一种参数化的多态性工具。再抽象，模板是一种参数化的多态性工具。n所谓参数化多态性，是指将程序所处理的对象的所谓参数化多态性，是指将程序所处理的对象的类型参数化，使一段程序代码可以用于处理多种类型参数化，使一段程序代码可以用于处理多种不同类型的对象。不同类型的对象。n采用模板编程，可以为各种逻辑功能相同而数据采用模板编程，可以为各种逻辑功能相同而数据类型不同的程序提供一种代码共享的机制。类型不同的程序提供一种代码共享的机制。第9章模板2022-5-2010n模板模板(Template)(Template)使用参数化的使用参数化的C+C+类型创建相应类型创建相应的函数和类，分为两种类型：的函

8、数和类，分为两种类型：- -函数模板（函数模板（Function TemplateFunction Template）- -类模板（类模板（Class TemplateClass Template）n一个模板并非一个实实在在的类或函数，仅仅是一个模板并非一个实实在在的类或函数，仅仅是一个类或函数的描述，是参数化的函数和类。一个类或函数的描述，是参数化的函数和类。n模板是一种使用通用类型参数来产生一族函数或模板是一种使用通用类型参数来产生一族函数或类的机制。类的机制。第9章模板2022-5-2011函数模板函数模板类模板类模板模板函数模板函数模板类模板类对象对象对象对象模板模板参数实例化参数实例

9、化参数实例化参数实例化第9章模板2022-5-2012n先看一个例子先看一个例子template template T max(T a,TT max(T a,T b) b) return (ab)?a:b return (ab)?a:b; ; n参数类型、返回值类型或函数体中使用的类型是参数类型、返回值类型或函数体中使用的类型是通用类型的函数称为函数模板，它定义了一类函通用类型的函数称为函数模板，它定义了一类函数。数。第9章模板2022-5-2013n函数模板的定义格式函数模板的定义格式 template template () n templatetemplate为声明模板的关键词，声明一个

10、参数化的类或为声明模板的关键词，声明一个参数化的类或函数集；函数集；n 类型参数用类型参数用typenametypename或或classclass关键字指明：关键字指明：template template template typename T1, typename T2, typenametemplate T3第9章模板2022-5-2014n函数模板是对一组函数的描述，它以任意类型函数模板是对一组函数的描述，它以任意类型T T为参数及函数返回值。为参数及函数返回值。n它不是一个实实在在的函数，编译系统并不产生它不是一个实实在在的函数，编译系统并不产生任何执行代码。任何执行代码。n当编译系

11、统在程序中发现有与函数模板中相匹配当编译系统在程序中发现有与函数模板中相匹配的函数调用时，便生成一个重载函数，该重载函的函数调用时，便生成一个重载函数，该重载函数的函数体与函数模板的函数体相同。数的函数体与函数模板的函数体相同。 第9章模板2022-5-2015/示例函数模板实现对不同数据类型数组进行排序示例函数模板实现对不同数据类型数组进行排序template template void Sort(Tvoid Sort(T* * begin,T begin,T* * end) end) T T* * pi, pi,* *pjpj; ;for(pi=end;pibegin;pifor(pi=e

12、nd;pibegin;pi-)-) for(pj=begin+1;pjpi;pjfor(pj=begin+1;pj(pj-1)* *pjpj) /) /采用冒泡法排序采用冒泡法排序 T temp;T temp;temp=temp=* *(pj-1);(pj-1);* *(pj-1)=(pj-1)=* *pjpj; ;* *pjpj=temp;=temp; 第9章模板2022-5-2016/自定义函数模板，实现对任意类型数组倒序自定义函数模板，实现对任意类型数组倒序template template void Reverse(Tvoid Reverse(T* * _F,T _F,T* * _L)

13、 _L) /_F/_F表示首指针，指向首元素；表示首指针，指向首元素；/_L/_L表示尾指针，指向最后一个元素。表示尾指针，指向最后一个元素。for(; _F != _L & _F != -_L; +_F)for(; _F != _L & _F != -_L; +_F) /交换首位两个元素后，交换首位两个元素后，_F_F加加1 1，_L_L减减1 1T temp;T temp;temp=temp=* *_F;_F;* *_F=_F=* *_L;_L;* *_L=temp;_L=temp; 第9章模板2022-5-2017n一个类模板允许用户为类定义一种模式，使得类一个类模板允许

14、用户为类定义一种模式，使得类中的某些数据成员、某些成员函数的参数或某些中的某些数据成员、某些成员函数的参数或某些成员函数的返回值，能取任意类型；成员函数的返回值，能取任意类型；n如果一个类中数据成员的类型不能确定，或者某如果一个类中数据成员的类型不能确定，或者某个成员函数的参数或返回值类型不能确定，就必个成员函数的参数或返回值类型不能确定，就必须将此类声明为模板；须将此类声明为模板；n类模板的存在不是代表一个具体的、实际的类，类模板的存在不是代表一个具体的、实际的类，而是代表着而是代表着“一类一类”类。类。第9章模板2022-5-2018n数据成员类型、成员函数的参数、返回值或函数数据成员类型

15、、成员函数的参数、返回值或函数体中使用的类型为通用数据类型的类称为类模板体中使用的类型为通用数据类型的类称为类模板，它定义了一类类。类模板可以派生出另一个类，它定义了一类类。类模板可以派生出另一个类模板。模板。n类模板的定义格式类模板的定义格式template template class class ；第9章模板2022-5-2019n可以放在类模板的定义体中（此时与类中的成员可以放在类模板的定义体中（此时与类中的成员函数的定义方法一致）函数的定义方法一致）n也可以放在类模板的外部定义成员函数，此时成也可以放在类模板的外部定义成员函数，此时成员函数的定义格式如下：员函数的定义格式如下：tem

16、plate template : （ ） 第9章模板2022-5-2020n类模板的所有成员函数一定是函数模板，因为类类模板的所有成员函数一定是函数模板，因为类的声明体内采用了模板参数，而成员函数可以对的声明体内采用了模板参数，而成员函数可以对数据成员进行操作，那么成员函数必须是函数模数据成员进行操作，那么成员函数必须是函数模板才行。板才行。 n在类模板外定义成员函数时，每一个函数前都要在类模板外定义成员函数时，每一个函数前都要加上：加上：template template 第9章模板2022-5-2021n利用类模板定义的只是对类的描述，它本身还不利用类模板定义的只是对类的描述，它本身还不是

17、一个实实在在的类。要定义类模板的对象（即是一个实实在在的类。要定义类模板的对象（即实例），需要用下列格式的语句：实例），需要用下列格式的语句：- -类模板名类模板名 - -类模板名类模板名 (实际参数表实际参数表););第9章模板2022-5-2022/示例类模板示例类模板template template class Exampleclass Example public:public:T1 getxT1 getx( ) return x; ( ) return x; T2 getyT2 gety( ) return y; ( ) return y; private:private:T1 x

18、;T1 x;T2 y;T2 y;n 类模板类模板ExampleExample中中T1T1、T2T2为类型参数；为类型参数；n 类模板不能直接使用，必须先实例化为具体的类，才能类模板不能直接使用，必须先实例化为具体的类，才能用来定义对象。用来定义对象。第9章模板2022-5-2023类模板类模板Example模板类模板类Example模板类模板类Example模板类模板类Example实例化实例化实例化实例化实例化实例化对象对象a1(c,1)对象对象a2(4,3.2)对象对象a3(d,3.5)实例化实例化实例化实例化实例化实例化第9章模板2022-5-2024n类模板可以作为基类派生出新的类模板

19、，即可以类模板可以作为基类派生出新的类模板，即可以派生类模板；派生类模板；n派生类模板声明注意：派生类模板声明注意：1 1、在声明前加上、在声明前加上“Template Template ”；2 2、在指出基类时缀上模板参数；、在指出基类时缀上模板参数；3 3、其余的与一般派生类定义相似。、其余的与一般派生类定义相似。第9章模板2022-5-2025/示例类模板派生示例类模板派生#include iostream.h#include template template class A class A public: public: void showA(T a) cout a endl voi

20、d showA(T a) cout a endl;template template / /类模板的派生类模板的派生class B: public A class B: public A public: public: void showB(X b)cout b endl void showB(X b)cout b endl;intint main( ) main( ) B char, intB bb; bb;bb.showA(10);bb.showA(10);bb.showB(Abb.showB(A);); 第9章模板2022-5-2026nSTL(StandardSTL(Standard

21、Template Library) Template Library)，即标准模板，即标准模板库，是一个具有工业强度的，高效的库，是一个具有工业强度的，高效的C+C+程序库程序库。它被容纳于。它被容纳于C+C+标准程序库标准程序库(C+ Standard (C+ Standard Library)Library)中，是中，是ANSI/ISO C+ANSI/ISO C+标准中最新的也是标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。科学领域里所常用的基本数据结构和基本算法。为广大为广大C+C+程序员们提

22、供了一个可扩展的应用框程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。架，高度体现了软件的可复用性。 第9章模板2022-5-2027n从逻辑层次来看，在从逻辑层次来看，在STLSTL中体现了泛型化程序设中体现了泛型化程序设计的思想计的思想(generic programming)(generic programming)，引入了诸多，引入了诸多新的名词，比如像需求新的名词，比如像需求(requirements)(requirements)，概念，概念(concept)(concept)，模型，模型(model)(model)，容器，容器(container)(container

23、)，算法算法(algorithmn(algorithmn) )，迭代子，迭代子(iterator(iterator) )等。与等。与OOP(objectOOP(object-oriented programming)-oriented programming)中的多态中的多态(polymorphism)(polymorphism)一样，泛型也是一种软件的复用一样，泛型也是一种软件的复用技术。技术。第9章模板2022-5-2028n从实现层次看，整个从实现层次看，整个STLSTL是以一种数据类型参数是以一种数据类型参数化化(type parameterized)(type parameteriz

24、ed)的方式实现的，这种方的方式实现的，这种方式基于式基于C+C+语言特性语言特性-模板模板(template)(template)。如果查。如果查阅任何一个版本的阅任何一个版本的STLSTL源代码，你就会发现，模源代码，你就会发现，模板作为构成整个板作为构成整个STLSTL的基石是一件千真万确的事的基石是一件千真万确的事情。除此之外，还有许多情。除此之外，还有许多C+C+的新特性为的新特性为STLSTL的实的实现提供了方便。现提供了方便。第9章模板2022-5-2029n没有没有C+C+语言就没有语言就没有STLSTL，这么说毫不为过。一般，这么说毫不为过。一般而言，而言，STLSTL作为一

25、个泛型化的数据结构和算法库作为一个泛型化的数据结构和算法库，并不牵涉具体语言。也就是说，如果条件允许，并不牵涉具体语言。也就是说，如果条件允许，用其他语言也可以实现之。这里所说的条件，用其他语言也可以实现之。这里所说的条件，主要是指类似于主要是指类似于“模板模板”这样的语法机制。这样的语法机制。STLSTL的创始人的创始人Alexander StepanovAlexander Stepanov在选择在选择C+C+语言作语言作为实现工具之前，曾采用过多种程序设计语言。为实现工具之前，曾采用过多种程序设计语言。但是，为什么最终还是选择但是，为什么最终还是选择C+C+来实现来实现STLSTL呢？原呢

26、？原因不仅在于前述那个条件，还在于因不仅在于前述那个条件，还在于C+C+的某些优的某些优越特性，比如：高效而灵活的指针。越特性，比如：高效而灵活的指针。C+C+只有在只有在引入了引入了“模板模板”之后，才直接导致了之后，才直接导致了STLSTL的诞生的诞生。第9章模板2022-5-2030nSTLSTL是最新的是最新的C+C+标准库中的一个子集，这个庞大标准库中的一个子集，这个庞大的子集占据了整个库的大约的子集占据了整个库的大约80%80%的分量。而作为的分量。而作为在实现在实现STLSTL过程中扮演关键角色的模板则充斥了过程中扮演关键角色的模板则充斥了几乎整个几乎整个C+C+标准库。在这里，

27、我们有必要看一标准库。在这里，我们有必要看一看看C+C+标准库里包含了哪些内容，其中又有哪些标准库里包含了哪些内容，其中又有哪些是属于标准模板库（即是属于标准模板库（即STLSTL）的。）的。 第9章模板2022-5-2031第9章模板2022-5-2032nC+C+标准库为标准库为C+C+程序员们提供了一个可扩展的基程序员们提供了一个可扩展的基础性框架。我们从中可以获得极大的便利，同时础性框架。我们从中可以获得极大的便利，同时也可以通过继承现有类，自己编制符合接口规范也可以通过继承现有类，自己编制符合接口规范的容器、算法、迭代子等方式对之进行扩展。它的容器、算法、迭代子等方式对之进行扩展。它

28、大致包含了如下几个组件：大致包含了如下几个组件：n语言支持（语言支持（language supportlanguage support）部分，包含了一）部分，包含了一些标准类型的定义以及其他特性的定义，这些内些标准类型的定义以及其他特性的定义，这些内容，被用于标准库的其他地方或是具体的应用程容，被用于标准库的其他地方或是具体的应用程序中。序中。第9章模板2022-5-2033n诊断（诊断（diagnosticsdiagnostics）部分，提供了用于程序诊）部分，提供了用于程序诊断和报错的功能，包含了异常处理（断和报错的功能，包含了异常处理（exception exception handli

29、nghandling），断言（），断言（assertionsassertions），错误代码（），错误代码（error number codeserror number codes）三种方式。）三种方式。n通用工具（通用工具（general utilitiesgeneral utilities）部分，这部分）部分，这部分内容为内容为C+C+标准库的其他部分提供支持，当然你标准库的其他部分提供支持，当然你也可以在自己的程序中调用相应功能。比如：动也可以在自己的程序中调用相应功能。比如：动态内存管理工具，日期态内存管理工具，日期/ /时间处理工具。记住，时间处理工具。记住，这里的内容也已经被泛化了

30、，即采用了模板机制这里的内容也已经被泛化了，即采用了模板机制进行实现。进行实现。第9章模板2022-5-2034n输入输入/ /输出输出(input/output)(input/output)部分，就是经过模板部分，就是经过模板化了的原有标准库中的化了的原有标准库中的iostreamiostream部分，它提供了部分，它提供了对对C+C+程序输入输出的基本支持。在功能上保持程序输入输出的基本支持。在功能上保持了与原有了与原有iostreamiostream的兼容，并且增加了异常处理的兼容，并且增加了异常处理机制，并支持国际化机制，并支持国际化(internationalization)(int

31、ernationalization)。n国际化国际化(internationalization)(internationalization)部分，作为部分，作为OOPOOP特性之一的封装机制在这里扮演着消除文化和地特性之一的封装机制在这里扮演着消除文化和地域差异的角色，采用域差异的角色，采用localelocale和和facetfacet可以为程序可以为程序提供众多国际化支持，包括对各种字符集的支持提供众多国际化支持，包括对各种字符集的支持，日期和时间的表示，数值和货币的处理等。，日期和时间的表示，数值和货币的处理等。第9章模板2022-5-2035n数值（数值（numericsnumeric

32、s）部分，包含了一些数学运算功）部分，包含了一些数学运算功能，提供了复数运算的支持。能，提供了复数运算的支持。n字符串字符串(string)(string)部分，用来代表和处理文本。它部分，用来代表和处理文本。它提供了足够丰富的功能。事实上，文本是一个提供了足够丰富的功能。事实上，文本是一个stringstring对象，它可以被看作是一个字符序列，字对象，它可以被看作是一个字符序列，字符类型可能是符类型可能是charchar，或者，或者wchar_twchar_t等等。等等。stringstring可以被转换成可以被转换成charchar* *类型，这样便可以和以前所类型，这样便可以和以前所写

33、的写的C/C+C/C+代码和平共处了。代码和平共处了。stringstring也可以算做也可以算做是是STLSTL的一部分。的一部分。第9章模板2022-5-2036n容器容器(containers)(containers)部分，涵盖了许多基本的重要部分，涵盖了许多基本的重要的数据结构，比如的数据结构，比如list(list(链表链表) )，还有，还有vector(vector(大大小可动态增加的数组小可动态增加的数组) )、queue(queue(队列队列) )、stack(stack(堆堆栈栈) )、set(set(集合集合) )、map(map(映射映射) )等。等。n迭代器迭代器(it

34、erators)(iterators)部分，事实上，每个容器都部分，事实上，每个容器都有自己的迭代器。迭代器实际是一种泛化指针，有自己的迭代器。迭代器实际是一种泛化指针，如果一个迭代器指向了容器中的某一成员，那么如果一个迭代器指向了容器中的某一成员，那么迭代器将可以通过自增自减来遍历容器中的所有迭代器将可以通过自增自减来遍历容器中的所有成员。迭代器是联系容器和算法的媒介，是算法成员。迭代器是联系容器和算法的媒介，是算法操作容器的接口。在运用算法操作容器的时候，操作容器的接口。在运用算法操作容器的时候，我们常常在不知不觉中已经使用了迭代器。我们常常在不知不觉中已经使用了迭代器。第9章模板2022

35、-5-2037n算法算法(algorithms)(algorithms)部分，包含了大约部分，包含了大约100100个实现个实现算法的模板函数，用于操控各种容器，同时也可算法的模板函数，用于操控各种容器，同时也可以操控内建数组。常用的功能范围涉及到比较、以操控内建数组。常用的功能范围涉及到比较、交换、遍历操作、复制、修改、移除、反转、排交换、遍历操作、复制、修改、移除、反转、排序、合并等。比如：序、合并等。比如：findfind用于在容器中查找等于用于在容器中查找等于某个特定值的元素，某个特定值的元素，for_eachfor_each用于将某个函数应用于将某个函数应用到容器中的各个元素上，用到

36、容器中的各个元素上，sortsort用于对容器中的用于对容器中的元素排序。所有这些操作都是在保证执行效率的元素排序。所有这些操作都是在保证执行效率的前提下进行的。前提下进行的。第9章模板2022-5-2038nSTLSTL的背后蕴含着泛型化程序设计的背后蕴含着泛型化程序设计(GP)(GP)的思想，的思想，在这种思想里，大部分基本算法被抽象，被泛化在这种思想里，大部分基本算法被抽象，被泛化，独立于与之对应的数据结构，用于以相同或相，独立于与之对应的数据结构，用于以相同或相近的方式处理各种不同情形。这一思想和面向对近的方式处理各种不同情形。这一思想和面向对象程序设计思想象程序设计思想(OOP)(O

37、OP)不尽相同，因为，在不尽相同，因为，在OOPOOP中中更注重的是对数据的抽象，即所谓抽象数据类型更注重的是对数据的抽象，即所谓抽象数据类型(Abstract Data Type)(Abstract Data Type)，而算法则通常被附属于，而算法则通常被附属于数据类型之中。几乎所有的事情都可以被看作类数据类型之中。几乎所有的事情都可以被看作类或者对象或者对象( (即类的实例即类的实例) )，通常，我们所看到的算，通常，我们所看到的算法被作为成员函数，包含在类中，类和类则构成法被作为成员函数，包含在类中，类和类则构成了错综复杂的继承体系。了错综复杂的继承体系。第9章模板2022-5-203

38、9n可以得出这样的结论，在可以得出这样的结论，在OOPOOP中所体现的思想与中所体现的思想与GPGP的思想确实是相异的。的思想确实是相异的。C+C+并不是一种纯面向并不是一种纯面向对象的程序设计语言，它的绝妙之处，就在于既对象的程序设计语言，它的绝妙之处，就在于既满足了满足了OOPOOP，又成全了，又成全了GPGP。对于后者，模板立下。对于后者，模板立下了汗马功劳。另外，需要指出的是，尽管了汗马功劳。另外，需要指出的是，尽管GPGP和和OOPOOP有诸多不同，但这种不同还不至于到有诸多不同，但这种不同还不至于到 水火不水火不容容 的地步。并且，在实际运用的时候，两者的的地步。并且，在实际运用的

39、时候，两者的结合使用往往可以使问题的解决更为有效。结合使用往往可以使问题的解决更为有效。第9章模板2022-5-2040nANSI/ISO C+ANSI/ISO C+文件中的文件中的STLSTL是一个仅被描述在纸是一个仅被描述在纸上的标准，对于诸多上的标准，对于诸多C+C+编译器而言，需要有各编译器而言，需要有各自实际的自实际的STLSTL，它们或多或少的实现了标准中所，它们或多或少的实现了标准中所描述的内容，这样才能够为我们所用。描述的内容，这样才能够为我们所用。n几个常见的几个常见的STLSTL实现版本实现版本nHP STLHP STL是所有其它是所有其它STLSTL实现版本的根源。它是实

40、现版本的根源。它是STLSTL之父之父Alexander StepanovAlexander Stepanov在惠普的在惠普的Palo AltoPalo Alto实实验室工作时，和验室工作时，和MengMeng Lee Lee共同完成的，是第一个共同完成的，是第一个STLSTL的实现版本。这个的实现版本。这个STLSTL是开放源码的。是开放源码的。第9章模板2022-5-2041nP.J.PlaugerP.J.Plauger STL STL属于个人作品，由属于个人作品，由P.J.PlaugerP.J.Plauger本人实现，是本人实现，是HP STLHP STL的一个继承版本。这一的一个继承版

41、本。这一STLSTL便是被用于便是被用于MicrosoftMicrosoft的的Visual C+Visual C+中的，不是中的，不是开放源码的，是不能修改和销售的。开放源码的，是不能修改和销售的。nRouge Wave STLRouge Wave STL是由是由Rouge WaveRouge Wave公司实现的，也公司实现的，也是是HP STLHP STL的一个继承版本，该版本被的一个继承版本，该版本被Borland Borland C+ BuilderC+ Builder所采用，可以在所采用，可以在C+ BuilderC+ Builder的的IncludeInclude子目录下找到所有头

42、文件。在子目录下找到所有头文件。在Borland Borland C+ Builder 6.0C+ Builder 6.0中，它的地位被另一个中，它的地位被另一个STLSTL的实的实现版本现版本-STLport-STLport（见后）取代了。（见后）取代了。第9章模板2022-5-2042nSGI STLSGI STL是由是由Silicon Graphics Computer Silicon Graphics Computer System, IncSystem, Inc公司实现的，其设计者和编写者包公司实现的，其设计者和编写者包括括Alexander StepanovAlexander St

43、epanov和和Matt AusternMatt Austern，同样它，同样它也是也是HP STLHP STL的一个继承版本。它属于开放源码，的一个继承版本。它属于开放源码，因此可以修改和销售它。因此可以修改和销售它。SGI STLSGI STL被被GCC(linuxGCC(linux下下的的C+C+编译器编译器) )所采用，可以在所采用，可以在GCCGCC的的IncludeInclude子目子目录下找到所有头文件。由于录下找到所有头文件。由于GCCGCC对对C+C+语言标准的语言标准的支持很好，支持很好，SGI STLSGI STL在在linuxlinux平台上的性能相当出平台上的性能相当

44、出色。色。第9章模板2022-5-2043nSTLportSTLport是开放源码的，目前已经被是开放源码的，目前已经被C/C+C/C+技术委技术委员会接受成为工业标准，且在许多平台上都支持员会接受成为工业标准，且在许多平台上都支持。根据测试，。根据测试，STLportSTLport的效率比的效率比VCVC中的中的STLSTL要快。要快。比比Rouge Wave STLRouge Wave STL更符合标准，也更容易移植。更符合标准，也更容易移植。Borland C+ BuilderBorland C+ Builder已经在其已经在其6.06.0版中加入了对版中加入了对STLportSTLpo

45、rt的支持，它使用的的支持，它使用的STLportSTLport就是就是4.54.5版的版的，C+ Builder 6.0C+ Builder 6.0同时还提供了同时还提供了STLportSTLport的使用的使用说明。可以在说明。可以在C+ BuilderC+ Builder的的IncludeStlportIncludeStlport子子目录下找到所有头文件。目录下找到所有头文件。第9章模板2022-5-2044STL家族的谱系 第9章模板2022-5-2045n示例。从标准输入设备（一般是键盘）读入一些示例。从标准输入设备（一般是键盘）读入一些整型数据，然后对它们进行排序，最终将结果输整型

46、数据，然后对它们进行排序，最终将结果输出到标准输出设备（一般是显示器屏幕）。这是出到标准输出设备（一般是显示器屏幕）。这是一种典型的处理方式，程序本身具备了一个系统一种典型的处理方式，程序本身具备了一个系统所应该具有的几乎所有的基本特征：所应该具有的几乎所有的基本特征：输入输入 + + 处处理理 + + 输出输出。将有三个不同版本的程序。第一个。将有三个不同版本的程序。第一个是没有使用是没有使用STLSTL的普通的普通C+C+程序，第二个程序的主程序，第二个程序的主体部分使用了体部分使用了STLSTL特性，第三个程序则将特性，第三个程序则将STLSTL的功的功能发挥到了极至。能发挥到了极至。第

47、9章模板2022-5-2046#include stdlib.h#include #include iostream.h#include int compare(constint compare(const void void * *arg1, const void arg1, const void * *arg2);arg2);void main(voidvoid main(void) ) const int max_sizeconst int max_size = 10; = 10;/数组元素的最大个数数组元素的最大个数int nummax_sizeint nummax_size;/整型数

48、组整型数组/ / 从标准输入设备读入整数，同时累计输入个数，从标准输入设备读入整数，同时累计输入个数，/ / 直到输入的是非整型数据为止直到输入的是非整型数据为止intint n; n;/使用使用cincin输入数据时，中间用空格隔开！输入结束时输入数据时，中间用空格隔开！输入结束时/先先EnterEnter然后然后CtrlCtrlz z或者按或者按TabTab键，然后回车键，然后回车for (n = 0; cin numnfor (n = 0; cin numn; n +); n +);/ C/ C标准库中的快速排序（标准库中的快速排序（quick-sortquick-sort）函数）函数q

49、sort(num, n, sizeof(intqsort(num, n, sizeof(int), compare);), compare);第9章模板2022-5-2047/ / 将排序结果输出到标准输出设备将排序结果输出到标准输出设备for (intfor (int i = 0; i n; i +) i = 0; i n; i +)cout numicout numi n; n; / / 比较两个数的大小，比较两个数的大小，/ / 如果如果* *(int(int * *)arg1)arg1比比* *(int(int * *)arg2)arg2小，则返回小，则返回-1-1/ / 如果如果*

50、*(int(int * *)arg1)arg1比比* *(int(int * *)arg2)arg2大，则返回大，则返回1 1/ / 如果如果* *(int(int * *)arg1)arg1等于等于* *(int(int * *)arg2)arg2，则返回，则返回0 0int compare(constint compare(const void void * *arg1, const void arg1, const void * *arg2)arg2) return (return (* *(int (int * *)arg1 )arg1 )arg1 * *(int(int * *)ar

51、g2) ? 1 : )arg2) ? 1 : 0;0; 第9章模板2022-5-2048nqsortqsort是是C C程序库程序库stdlib.hstdlib.h中的一个函数。中的一个函数。 void qsort(void void qsort(void * *base, size_t num, size_t base, size_t num, size_t width, int (_cdeclwidth, int (_cdecl * *compare )(const void compare )(const void * *elem1, const void elem1, const vo

52、id * *elem2 ) );elem2 ) );n 第一个参数指明要排序的数组第一个参数指明要排序的数组( (比如：程序中的比如：程序中的num)num)，第二个参数给出数组的大小第二个参数给出数组的大小(qsort(qsort不能预知传给它的数不能预知传给它的数组的实际大小组的实际大小) )，第三个参数给出数组中每个元素以字，第三个参数给出数组中每个元素以字节为单位的大小。最后那个参数，给出了排序时比较元节为单位的大小。最后那个参数，给出了排序时比较元素的方法。素的方法。n 输入：输入：0 9 2 1 50 9 2 1 5n 输出：输出：0 1 2 5 90 1 2 5 9第9章模板20

53、22-5-2049#include iostream#include #include #include #include #include using namespace std;using namespace std;void main(voidvoid main(void) ) vectorintvector num; num;/ STL/ STL中的中的vectorvector容器容器intint element; element;/ / 从标准输入设备读入整数，从标准输入设备读入整数，/ / 直到输入的是非整型数据为止直到输入的是非整型数据为止while (cinwhile (cin

54、 element) element)num.push_back(elementnum.push_back(element););/ STL/ STL中的排序算法中的排序算法sort(num.begin(), num.endsort(num.begin(), num.end();();/ / 将排序结果输出到标准输出设备将排序结果输出到标准输出设备for (int i = 0; i num.sizefor (int i = 0; i num.size(); i +)(); i +)cout numicout numi n; n; 第9章模板2022-5-2050n程序中用到了程序中用到了vect

55、orvector，它是，它是STLSTL中的一个标准容中的一个标准容器，可以用来存放一些元素。你可以把器，可以用来存放一些元素。你可以把vectorvector理理解为解为intint ? ?，一个整型的数组。之所以大小未，一个整型的数组。之所以大小未知是因为，知是因为，vectorvector是一个可以动态调整大小的容是一个可以动态调整大小的容器，当容器已满时，如果再放入元素则器，当容器已满时，如果再放入元素则vectorvector会会悄悄扩大自己的容量。悄悄扩大自己的容量。push_backpush_back是是vectorvector容器容器的一个类属成员函数，用来在容器尾端插入一个的

56、一个类属成员函数，用来在容器尾端插入一个元素。元素。mainmain函数中第一个函数中第一个whilewhile循环做的事情就循环做的事情就是不断向是不断向vectorvector容器尾端插入整型数据，同时自容器尾端插入整型数据，同时自动维护容器空间的大小。动维护容器空间的大小。第9章模板2022-5-2051nsortsort是是STLSTL中的标准算法，用来对容器中的元素中的标准算法，用来对容器中的元素进行排序。它需要两个参数用来决定容器中哪个进行排序。它需要两个参数用来决定容器中哪个范围内的元素可以用来排序。这里用到了范围内的元素可以用来排序。这里用到了vectorvector的另两个类

57、属成员函数。的另两个类属成员函数。begin()begin()用以指向用以指向vectorvector的首端，而的首端，而end()end()则指向则指向vectorvector的末端。的末端。返回值是迭代器类型，可以当作是一个指向整型返回值是迭代器类型，可以当作是一个指向整型数据的指针。数据的指针。end()end()回值所指向的是回值所指向的是vectorvector中最中最末端元素的后面一个位置，即所谓末端元素的后面一个位置，即所谓pass-the-end pass-the-end valuevalue。size()size()函数用来返回函数用来返回vectorvector中的元素个中

58、的元素个数，就相当于第一个程序中的变量数，就相当于第一个程序中的变量n n。第9章模板2022-5-2052#include iostream#include #include #include #include #include #include iterator#include using namespace std;using namespace std;void main(voidvoid main(void) ) typedef vectortypedef vectorint_vectorint_vector; ;typedef istream_iteratortypedef ist

59、ream_iteratoristream_itristream_itr; ;typedef ostream_iteratortypedef ostream_iteratorostream_itrostream_itr; ;typedef back_insert_iteratortypedef back_insert_iteratorback_ins_itrback_ins_itr; ;/ STL/ STL中的中的vectorvector容器容器int_vectorint_vector num; num;/ / 从标准输入设备读入整数，直到输入的是非整型数据为止从标准输入设备读入整数，直到输入的

60、是非整型数据为止copy(istream_itr(cin),istream_itr(),back_ins_itr(numcopy(istream_itr(cin),istream_itr(),back_ins_itr(num););/ STL/ STL中的排序算法中的排序算法sort(num.begin(), num.endsort(num.begin(), num.end();();/ / 将排序结果输出到标准输出设备将排序结果输出到标准输出设备copy(num.begin(), num.end(), ostream_itr(coutcopy(num.begin(), num.end(), ostream_itr(cout, n);,