泛型程序设计与C标准模板库.ppt
《泛型程序设计与C标准模板库.ppt》由会员分享,可在线阅读,更多相关《泛型程序设计与C标准模板库.ppt(97页珍藏版)》请在三一办公上搜索。
1、第十章 泛型程序设计 与C+标准模板库,清华大学 郑 莉,目录,10.1 泛型程序设计及STL的结构10.2 迭代器10.3 容器的基本功能与分类10.4 顺序容器10.5 关联容器10.6 函数对象10.7 算法10.8 综合实例对个人银行账户管理程序的改进10.9 深度探索10.10 小结,2,10.1.1 泛型程序设计的基本概念,编写不依赖于具体数据类型的程序将算法从特定的数据结构中抽象出来,成为通用的C+的模板为泛型程序设计奠定了关键的基础几个术语概念(concept):用来界定具备一定功能的数据类型,如“支持运算符”的数据类型构成Comparable这一概念;模型(model):符合
2、一个概念的数据类型称为该概念的模型,如int型是Comparable概念的模型。,3,10.1 泛型程序设计及STL的结构,10.1.2 STL简介,标准模板库(Standard Template Library,简称STL)提供了一些非常常用的数据结构和算法STL程序实例(例10-1):,4,10.1 泛型程序设计及STL的结构,/包含的头文件略去using namespace std;int main()const int N=5;vector s(N);for(int i=0;i si;transform(s.begin(),s.end(),ostream_iterator(cout,)
3、,negate();cout endl;return 0;,容器,函数对象,算法,STL的组成部分,5,STL是泛型程序设计的一个范例 容器(container)迭代器(iterator)算法(algorithms)函数对象(function object),10.1 泛型程序设计及STL的结构 10.1.2 STL简介,输入流迭代器和输出流迭代器,输入流迭代器istream_iterator以输入流(如cin)为参数构造可用*(p+)获得下一个输入的元素输出流迭代器ostream_iterator构造时需要提供输出流(如cout)可用(*p+)=x将x输出到输出流二者都属于适配器适配器是用来
4、为已有对象提供新的接口的对象输入流适配器和输出流适配器为流对象提供了迭代器的接口,6,10.2 迭代器,例10-2从标准输入读入几个实数,分别将它们的平方输出,/10_2.cpp#include#include#include using namespace std;/求平方的函数double square(double x)return x*x;int main()/从标准输入读入若干个实数,分别将它们的平方输出 transform(istream_iterator(cin),istream_iterator(),ostream_iterator(cout,t),square);cout e
5、ndl;return 0;,7,10.2 迭代器 输入流迭代器和输出流迭代器,10.2.2 迭代器的分类,8,10.2 迭代器,迭代器支持的操作,迭代器是泛化的指针,提供了类似指针的操作(诸如+、*、-运算符)输入迭代器可以用来从序列中读取数据,如输入流迭代器输出迭代器允许向序列中写入数据,如输出流迭代器前向迭代器既是输入迭代器又是输出迭代器,并且可以对序列进行单向的遍历双向迭代器与前向迭代器相似,但是在两个方向上都可以对数据遍历随机访问迭代器也是双向迭代器,但能够在序列中的任意两个位置之间进行跳转,如指针、使用vector的begin()、end()函数得到的迭代器,9,10.2 迭代器 1
6、0.2.2 迭代器的分类,10.2.3 迭代器的区间,两个迭代器表示一个区间:p1,p2)STL算法常以迭代器的区间作为输入,传递输入数据合法的区间p1经过n次(n 0)自增(+)操作后满足p1=p2区间包含p1,但不包含p2,10,10.2 迭代器,例10-3 综合运用几种迭代器的示例,/10_3.cpp#include#include#include#include using namespace std;/将来自输入迭代器p的n个T类型的数值排序,将结果通过输出迭代器result输出template void mySort(InputIterator first,InputIterato
7、r last,OutputIterator result)/通过输入迭代器p将输入数据存入向量容器s中vector s;for(;first!=last;+first)s.push_back(*first);sort(s.begin(),s.end();/对s进行排序,sort函数的参数必须是随机访问迭代器copy(s.begin(),s.end(),result);/将s序列通过输出迭代器输出,11,10.2 迭代器 10.2.3 迭代器的区间,例10-3(续),int main()/将s数组的内容排序后输出double a5=1.2,2.4,0.8,3.3,3.2;mySort(a,a+5
8、,ostream_iterator(cout,);cout(istream_iterator(cin),istream_iterator(),ostream_iterator(cout,);cout endl;return 0;,12,10.2 迭代器 10.2.3 迭代器的区间,运行结果:0.8 1.2 2.4 3.2 3.32-4 5 8-1 3 6-5-5-4-1 2 3 5 6 8,10.2.4 迭代器的辅助函数,advance(p,n)对p执行n次自增操作distance(first,last)计算两个迭代器first和last的距离,即对first执行多少次“+”操作后能够使得fi
9、rst=last,13,10.2 迭代器,10.3 容器的基本功能与分类,容器类是容纳、包含一组元素或元素集合的对象。七种基本容器:向量(vector)双端队列(deque)列表(list)集合(set)多重集合(multiset)映射(map)多重映射(multimap),14,10.3 容器的基本功能与分类(续),15,容器(Container),容器(Container),list,容器的通用功能,容器的通用功能用默认构造函数构造空容器支持关系运算符:=、!=、=begin()、end():获得容器首、尾迭代器clear():将容器清空empty():判断容器是否为空size():得到容
10、器元素个数s1.swap(s2):将s1和s2两容器内容交换相关数据类型(S表示容器类型)S:iterator:指向容器元素的迭代器类型S:const_iterator:常迭代器类型,16,10.3 容器的基本功能与分类,可逆容器、随机访问容器,可逆容器S:reverse_iterator:逆向迭代器类型S:const_reverse_iterator:逆向常迭代器类型rbegin():指向容器尾的逆向迭代器rend():指向容器首的逆向迭代器随机访问容器sn:获得容器s的第n个元素,17,10.3 容器的基本功能与分类,10.4.1 顺序容器的基本功能,顺序容器的接口赋值assign插入函数
11、insert,push_front(只对list和deque),push_back删除函数erase,clear,pop_front(只对list和deque),pop_back其他顺序容器访问函数front,back改变大小resize,18,10.4 顺序容器,例10-4 顺序容器的基本操作,/10_4.cpp,包含的头文件略去/输出指定的整型顺序容器的元素template void printContainer(const char*msg,const T,19,10.4 顺序容器 10.4.1 顺序容器的基本功能,例10-4(续),printContainer(deque at fir
12、st,s);/用s容器的内容的逆序构造列表容器llist l(s.rbegin(),s.rend();printContainer(list at first,l);/将列表容器l的每相邻两个容器顺序颠倒list:iterator iter=l.begin();while(iter!=l.end()int v=*iter;iter=l.erase(iter);l.insert(+iter,v);printContainer(list at last,l);/用列表容器l的内容给s赋值,将s输出s.assign(l.begin(),l.end();printContainer(deque at
13、last,s);return 0;,20,10.4 顺序容器 10.4.1 顺序容器的基本功能,例10-4(续),运行结果如下:0 9 8 6 4 3 2 1 5 4 deque at first:4 5 1 2 3 4 6 8 9 0 list at first:0 9 8 6 4 3 2 1 5 4 list at last:9 0 6 8 3 4 1 2 4 5 deque at last:9 0 6 8 3 4 1 2 4 5,21,10.4 顺序容器 10.4.1 顺序容器的基本功能,10.4.2 三种顺序容器的特性 向量(Vector),特点一个可以扩展的动态数组随机访问、在尾部插
14、入或删除元素快在中间或头部插入或删除元素慢向量的容量容量(capacity):实际分配空间的大小s.capacity():返回当前容量s.reserve(n):若容量小于n,则对s进行扩展,使其容量至少为n,22,10.4 顺序容器,双端队列(deque),特点在两端插入或删除元素快在中间插入或删除元素慢随机访问较快,但比向量容器慢,23,10.4 顺序容器 10.4.2 三种顺序容器的特性,例10-5 奇偶排序,先按照从大到小顺序输出奇数,再按照从小到大顺序输出偶数。,24,10.4 顺序容器 10.4.2 三种顺序容器的特性,/头部分省略int main()istream_iterator
15、 i1(cin),i2;/建立一对儿输入流迭代器 vector s1(i1,i2);/通过输入流迭代器从标准输入流中输入数据 sort(s1.begin(),s1.end();/将输入的整数排序 deque s2;/以下循环遍历s1 for(vector:iterator iter=s1.begin();iter!=s1.end();+iter)if(*iter%2=0)/偶数放到s2尾部 s2.push_back(*iter);else/奇数放到s2首部 s2.push_front(*iter);/将s2的结果输出 copy(s2.begin(),s2.end(),ostream_itera
16、tor(cout,);cout endl;return 0;,列表(list),特点在任意位置插入和删除元素都很快不支持随机访问接合(splice)操作s1.splice(p,s2,q1,q2):将s2中q1,q2)移动到s1中p所指向元素之前,25,10.4 顺序容器 10.4.2 三种顺序容器的特性,例10-6列表容器的splice操作,/头部分省略int main()string names1=Alice,Helen,Lucy,Susan;string names2=Bob,David,Levin,Mike;list s1(names1,names1+4);/用names1数组的内容构造
17、列表s1list s2(names2,names2+4);/用names2数组的内容构造列表s2/将s1的第一个元素放到s2的最后s2.splice(s2.end(),s1,s1.begin();list:iterator iter1=s1.begin();/iter1指向s1首advance(iter1,2);/iter1前进2个元素,它将指向s1第3个元素list:iterator iter2=s2.begin();/iter2指向s2首+iter2;/iter2前进1个元素,它将指向s2第2个元素,26,10.4 顺序容器 10.4.2 三种顺序容器的特性,例10-6(续),27,lis
18、t:iterator iter3=iter2;/用iter2初始化iter3 advance(iter3,2);/iter3前进2个元素,它将指向s2第4个元素/将iter2,iter3)范围内的结点接到s1中iter1指向的结点前 s1.splice(iter1,s2,iter2,iter3);/分别将s1和s2输出 copy(s1.begin(),s1.end(),ostream_iterator(cout,);cout(cout,);cout endl;return 0;,10.4 顺序容器 10.4.2 三种顺序容器的特性,运行结果:Helen Lucy David Levin Sus
19、anBob Mike Alice,三种顺序容器的比较,STL所提供的三种顺序容器各有所长也各有所短,我们在编写程序时应当根据我们对容器所需要执行的操作来决定选择哪一种容器。如果需要执行大量的随机访问操作,而且当扩展容器时只需要向容器尾部加入新的元素,就应当选择向量容器vector;如果需要少量的随机访问操作,需要在容器两端插入或删除元素,则应当选择双端队列容器deque;、如果不需要对容器进行随机访问,但是需要在中间位置插入或者删除元素,就应当选择列表容器list。,28,10.4 顺序容器 10.4.2 三种顺序容器的特性,10.4.3 顺序容器的插入迭代器,插入迭代器用于向容器头部、尾部或
20、中间指定位置插入元素的迭代器包括前插迭代器(front_inserter)、后插迭代器(back_insrter)和任意位置插入迭代器(inserter)例:list s;back_inserter iter(s);*(iter+)=5;/通过iter把5插入s末尾,29,10.4 顺序容器,10.4.4 顺序容器的适配器,以顺序容器为基础构建一些常用数据结构栈(stack):最先压入的元素最后被弹出队列(queue):最先压入的元素最先被弹出优先级队列(priority_queue):最“大”的元素最先被弹出,30,10.4 顺序容器,例10-7 利用栈反向输出单词,/10_7.cpp,省略
21、头部分int main()stack s;string str;cin str;/从键盘输入一个字符串/将字符串的每个元素顺序压入栈中for(string:iterator iter=str.begin();iter!=str.end();+iter)s.push(*iter);/将栈中的元素顺序弹出并输出while(!s.empty()cout s.top();s.pop();cout endl;return 0;,31,10.4 顺序容器 10.4.4 顺序容器的适配器,运行结果如下:congratulationssnoitalutargnoc,优先级队列,优先级队列也像栈和队列一样支持元
22、素的压入和弹出,但元素弹出的顺序与元素的大小有关,每次弹出的总是容器中最“大”的一个元素。template class priority_queue;例10-8 细胞分裂模拟一种细胞在诞生(即上次分裂)后会在500到2000秒内分裂为两个细胞,每个细胞又按照同样的规律继续分裂。,32,10.4 顺序容器 10.4.4 顺序容器的适配器,/10.8.cpp,头部分省略const int SPLIT_TIME_MIN=500;/细胞分裂最短时间const int SPLIT_TIME_MAX=2000;/细胞分裂最长时间class Cell;priority_queue cellQueue;cla
23、ss Cell/细胞类private:static int count;/细胞总数int id;/当前细胞编号int time;/细胞分裂时间public:Cell(int birth):id(count+)/birth为细胞诞生时间/初始化,确定细胞分裂时间time=birth+(rand()%(SPLIT_TIME_MAX-SPLIT_TIME_MIN)+SPLIT_TIME_MIN;int getId()const return id;/得到细胞编号int getSplitTime()const return time;/得到细胞分裂时间bool operator s.time;/定义“
24、”,33,例10-8(续),10.4 顺序容器 10.4.4 顺序容器的适配器,/细胞分裂void split()Cell child1(time),child2(time);/建立两个子细胞cout(time(0);int t;/模拟时间长度cout t;cellQueue.push(Cell(0);/将第一个细胞压入优先级队列while(cellQueue.top().getSplitTime()=t)cellQueue.top().split();/模拟下一个细胞的分裂cellQueue.pop();/将刚刚分裂的细胞弹出return 0;,34,例10-8(续),10.4 顺序容器 1
25、0.4.4 顺序容器的适配器,例10-8(续),运行结果如下:Simulation time:5000971s:Cell#0 splits to#1 and#21719s:Cell#1 splits to#3 and#41956s:Cell#2 splits to#5 and#62845s:Cell#6 splits to#7 and#83551s:Cell#3 splits to#9 and#103640s:Cell#4 splits to#11 and#123919s:Cell#5 splits to#13 and#144162s:Cell#10 splits to#15 and#1641
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 程序设计 标准 模板
链接地址:https://www.31ppt.com/p-6305242.html