第十八章标准模板库优秀课件.ppt

第十八章标准模板库第十八章标准模板库第1页，本讲稿共13页课程内容安排课程内容安排标准库模板库标准库模板库算法算法容器容器 迭代器迭代器 综合练习综合练习 思考和习题思考和习题 第2页，本讲稿共13页标准模板库标准模板库 STL是是最最新新的的C+标标准准函函数数库库中中的的一一个个子子集集，这这个个庞庞大大的的子子集集占占据据了了整整个个库库的的大大约约80%的的分分量量。而而作作为为在在实实现现STL过过程程中中扮扮演演关关键键角角色色的的模模板板则则充充斥斥了了几几乎乎整整个个C+标准函数库。标准函数库。STL提提供供了了一一系系列列具具有有良良好好结结构构的的通通用用C+组组件件，这这些些组组件件紧紧密密协协作作，提提供供强强大大的的功功能能。标标准准库库的的设设计计必必须须确确保保所所有有的的模模板板算算法法既既能能操操作作库库中中的的数数据据类类型型，也也能能操操作作C+固有的数据类型。固有的数据类型。第3页，本讲稿共13页第一个第一个STL程序程序 该范例中调用了该范例中调用了STL中的函数，是第一个使用中的函数，是第一个使用STL的程的程序序，其实现功能如下。，其实现功能如下。第4页，本讲稿共13页代码清单代码清单1#include/包含头文件包含头文件2#include 3int main()45std:vector a;/定义数据变量定义数据变量6std:vector:const_iterator i;/定义变量定义变量7a.push_back(1);/调用调用STL中函数中函数8a.push_back(2);9a.push_back(3);10a.push_back(4);11a.push_back(5);/调用调用STL中函数中函数12for(i=a.begin();i!=a.end();+i)/循环输出循环输出1314std:cout(*i)std:endl;/输出该容器内所有元素输出该容器内所有元素1516return 0;17第5页，本讲稿共13页STL的组成的组成 STL的的代代码码从从广广义义上上讲讲分分为为三三类类：algorithm（算算法法）、container（容容器器）和和iterator（迭迭代代器器），几几乎乎所所有有的的代代码码都都采采用用了了模模板板类类和和模模版版函函数数的的方方式式，这这相相比比于于传传统统的的由由函函数数和和类类组组成成的的库库来来说说提提供供了了更更好好的的代代码码重重用用机机会会。简单来说，其关系如图简单来说，其关系如图18-3所示。所示。第6页，本讲稿共13页算法算法 算法部分主要由头文件算法部分主要由头文件，和和组成。组成。是所有是所有STL头文件中头文件中最大的一个，它是由一大堆模版函数组成的。一般可以最大的一个，它是由一大堆模版函数组成的。一般可以认为每个函数在很大程度上都是独立的，其中常用到的认为每个函数在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。修改、移除、反转、排序、合并等等。头文件头文件体积很小，只包括几个在序列上面进体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。头文件的一些操作。头文件中则定义了一些模板中则定义了一些模板类，用以声明函数对象。类，用以声明函数对象。第7页，本讲稿共13页容器容器 容器部分主要由头文件容器部分主要由头文件，和和组成。对于常用组成。对于常用的一些容器和容器适配器（可以看作由其它容器实现的的一些容器和容器适配器（可以看作由其它容器实现的容器），可以通过下表容器），可以通过下表18-1总结一下它们和相应头文件总结一下它们和相应头文件的对应关系。的对应关系。第8页，本讲稿共13页数据结构描述实现头文件向量(vector)连续存储的元素列表(list)由节点组成的双向链表，每个结点包含着一个元素双队列(deque)连续存储的指向不同元素的指针所组成的数组集合(set)由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种作用于元素对的谓词排列，没有两个不同的元素能够拥有相同的次序set多重集合(multiset)允许存在两个次序相等的元素的集合栈(stack)后进先出的值的排列队列(queue)先进先出的执的排列优先队列(priority_queue)元素的次序是由作用于所存储的值对上的某种谓词决定的的一种队列映射(map)由键，值对组成的集合，以某种作用于键对上的谓词排列多重映射(multimap)允许键对有相等的次序的映射第9页，本讲稿共13页迭代器迭代器 迭迭代代器器实实际际上上是是一一种种泛泛化化指指针针，如如果果一一个个迭迭代代器器指指向向了了容容器器中中的的某某一一成成员员，那那么么迭迭代代器器将将可可以以通通过过自自增增自自减减来来遍遍历历容容器器中中的的所所有有成成员员。迭迭代代器器是是联联系系容容器器和和算算法法的的媒媒介介，是算法操作容器的接口，如图是算法操作容器的接口，如图18-10所示。所示。第10页，本讲稿共13页综合练习综合练习 该范例求出范围在该范例求出范围在2N中的所有素数，其中中的所有素数，其中N在程序运在程序运行时由键盘输入。行时由键盘输入。第11页，本讲稿共13页代码清单代码清单1#include 2#include/包含包含I/O流控制头文件流控制头文件3#include/包含向量容器头文件包含向量容器头文件4using namespace std;/使用存储过程使用存储过程5void main()/主函数主函数6 7vector A(10);/定义向量对象定义向量对象8int n;/定义整型变量定义整型变量9int primecount=0,i,j;/定义变量并初始化定义变量并初始化10cout=2 as upper limit:;/输入提示输入提示11cin n;/接收接收n的输入的输入12Aprimecount+=2;/赋值赋值13for(i=3;i n;i+)/循环输出素数循环输出素数14 15if(primecount=A.size()/到达向量大小到达向量大小16 A.resize(primecount+10);/调用函数重新设置向量大小调用函数重新设置向量大小17 if(i%2=0)/不是素数不是素数18 continue;/继续循环继续循环19j=3;/赋初值赋初值20while(j i/2)/是素数是素数23 Aprimecount+=i;/写入向量中写入向量中2425for(i=0;iprimecount;i+)/输出素数输出素数26 27coutsetw(5)Ai;/设置输出格式并输出设置输出格式并输出28f(i+1)%10=0)/每输出每输出10个数换行一次个数换行一次29cout endl;/输出换行输出换行30 31coutendl;/输出换行输出换行32第12页，本讲稿共13页思考和习题思考和习题C+标准中为什么要引入标准中为什么要引入STL的概念？的概念？STL是一个模板库，但其中也包含了许多个部分。一般是一个模板库，但其中也包含了许多个部分。一般来说，来说，STL由六大部分组成，其分别是哪由六大部分组成，其分别是哪6个部分，其个部分，其作用分别是什么？作用分别是什么？什么是迭代器？其作用是什么？什么是迭代器？其作用是什么？使用容器实现一个序列的排序，将一个序列按照升序排使用容器实现一个序列的排序，将一个序列按照升序排列输出。列输出。第13页，本讲稿共13页