第十八章标准模板库

第十八章标准模板库第1页，共13页，2023年，2月20日，星期三课程内容安排标准库模板库算法容器迭代器综合练习思考和习题第2页，共13页，2023年，2月20日，星期三标准模板库STL是最新的C++标准函数库中的一个子集，这个庞大的子集占据了整个库的大约80%的分量。而作为在实现STL过程中扮演关键角色的模板则充斥了几乎整个C++标准函数库。STL提供了一系列具有良好结构的通用C++组件，这些组件紧密协作，提供强大的功能。标准库的设计必须确保所有的模板算法既能操作库中的数据类型，也能操作C++固有的数据类型。第3页，共13页，2023年，2月20日，星期三第一个STL程序该范例中调用了STL中的函数，是第一个使用STL的程序，其实现功能如下。第4页，共13页，2023年，2月20日，星期三代码清单1 #include<vector> //包含头文件2 #include<iostream>3 intmain()4 {5 std::vector<double>a; //定义数据变量6 std::vector<double>::const_iteratori; //定义变量7 a.push_back(1); //调用STL中函数8 a.push_back(2);9 a.push_back(3);10 a.push_back(4);11 a.push_back(5); //调用STL中函数12 for(i=a.begin();i!=a.end();++i) //循环输出13 {14 std::cout<<(*i)<<std::endl; //输出该容器内所有元素15 }16 return0;17 }第5页，共13页，2023年，2月20日，星期三STL的组成STL的代码从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），几乎所有的代码都采用了模板类和模版函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。简单来说，其关系如图18-3所示。

第6页，共13页，2023年，2月20日，星期三算法算法部分主要由头文件<algorithm>，<numeric>和<functional>组成。<algorithm>是所有STL头文件中最大的一个，它是由一大堆模版函数组成的。一般可以认为每个函数在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。头文件<numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。头文件<functional>中则定义了一些模板类，用以声明函数对象。第7页，共13页，2023年，2月20日，星期三容器容器部分主要由头文件<vector>，<list>，<deque>，<set>，<map>，<stack>和<queue>组成。对于常用的一些容器和容器适配器（可以看作由其它容器实现的容器），可以通过下表18-1总结一下它们和相应头文件的对应关系。第8页，共13页，2023年，2月20日，星期三数据结构描述实现头文件向量(vector)连续存储的元素<vector>列表(list)由节点组成的双向链表，每个结点包含着一个元素<list>双队列(deque)连续存储的指向不同元素的指针所组成的数组<deque>集合(set)由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种作用于元素对的谓词排列，没有两个不同的元素能够拥有相同的次序<set多重集合(multiset)允许存在两个次序相等的元素的集合<set>栈(stack)后进先出的值的排列<stack>队列(queue)先进先出的执的排列<queue>优先队列(priority_queue)元素的次序是由作用于所存储的值对上的某种谓词决定的的一种队列<queue>映射(map)由{键，值}对组成的集合，以某种作用于键对上的谓词排列<map>多重映射(multimap)允许键对有相等的次序的映射<map>第9页，共13页，2023年，2月20日，星期三迭代器迭代器实际上是一种泛化指针，如果一个迭代器指向了容器中的某一成员，那么迭代器将可以通过自增自减来遍历容器中的所有成员。迭代器是联系容器和算法的媒介，是算法操作容器的接口，如图18-10所示。第10页，共13页，2023年，2月20日，星期三综合练习该范例求出范围在2~N中的所有素数，其中N在程序运行时由键盘输入。第11页，共13页，2023年，2月20日，星期三代码清单1 #include<iostream>2 #include<iomanip> //包含I/O流控制头文件3 #include<vector> //包含向量容器头文件4 usingnamespacestd; //使用存储过程5 voidmain() //主函数6 {7 vector<int>A(10); //定义向量对象8 intn; //定义整型变量9 intprimecount=0,i,j; //定义变量并初始化10 cout<<"Enteravalue>=2asupperlimit:"; //输入提示11 cin>>n; //接收n的输入12 A[primecount++]=2; //赋值13 for(i=3;i<n;i++) //循环输出素数14 {15 if(primecount==A.size()) //到达向量大小16 A.resize(primecount+10); //调用函数重新设置向量大小17 if(i%2==0) //不是素数18 continue; //继续循环19 j=3; //赋初值20 while(j<=i/2&&i%j!=0) //循环判断是否素数21 j+=2; //变量递加222 if(j>i/2) //是素数23 A[primecount++]=i; //写入向量中24 }25 for(i=0;i<primecount;i++) //输出素数26 {27 cout<<setw(5)<<A[i]; //设置输出格式并输出28 f((i+1)%10==0) //每输出10个数换行一次29 cout<<endl; //输出换行30 }31 cout<<endl; //输出换行32 }第12页，共13页，2023年