程序设计实习第二十讲标准模板库stli.ppt
《程序设计实习第二十讲标准模板库stli.ppt》由会员分享,可在线阅读,更多相关《程序设计实习第二十讲标准模板库stli.ppt(49页珍藏版)》请在装配图网上搜索。
程序设计实习第二十讲标准模板库STLI,主讲教师:田永鸿yhtian,2,课堂问题,下列代码是否存在错误,若存在,该如何改正?templateclassCTempfriendvoidmyClass:func();private:Telementssize;public:CTemp(Targ);templatevoidmyClass:func()CTempa(10);inti;for(i=0;iobj;obj.func();,3,课堂问题,有如下类模板定义templateclassCTempfriendmyClassA;friendmyClassB;private:T1elementssize;public:CTemp(Targ);则myClassA、myClassB、myClassA、myClassA都是CTemp的友员类,4,课堂问题,找出下列代码中的错误之处,并解释a(10)(或b(8.9)、的含义)templateclassCTempfriendvoidfunc(int);private:Telementssize;public:CTemp(Targ);voidfunc(intsize)CTempa(10);CTempb(8.9);CTempc(10);CTempd(10);inti;for(i=0;i50;i+)couta.elementsi“”b.elementsiendl;return;,5,提纲,1.引言2.STL中的基本概念3.容器概述4.迭代器5.算法简介6.顺序容器,6,概论,C+语言的核心优势之一就是便于软件的重用C+中有两个方面体现重用:1.面向对象的思想:继承和多态,标准类库2.泛型程序设计(genericprogramming)的思想:模板机制,以及标准模板库STL,7,泛型程序设计,泛型程序设计,简单地说就是使用模板的程序设计法。将一些常用的数据结构(比如链表,数组,二叉树)和算法(比如排序,查找)写成模板,以后则不论数据结构里放的是什么对象,算法针对什么样的对象,则都不必重新实现数据结构,重新编写算法。标准模板库(StandardTemplateLibrary)就是一些常用数据结构和算法的模板的集合。主要由AlexStepanov开发,于1998年被添加进C+标准有了STL,不必再从头写大多的标准数据结构和算法,并且可获得非常高的性能。,8,STL中的几个基本概念,容器:可容纳各种数据类型的数据结构。迭代器:可依次存取容器中元素的东西算法:用来操作容器中的元素的函数模板。例如,STL用sort()来对一个vector中的数据进行排序,用find()来搜索一个list中的对象。函数本身与他们操作的数据的结构和类型无关,因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。比如,数组intarray100就是个容器,而int*类型的指针变量就可以作为迭代器,可以为这个容器编写一个排序的算法,9,容器概述,可以用于存放各种类型的数据(基本类型的变量,对象等)的数据结构。容器分为三大类:1)顺序容器vector:后部插入/删除,直接访问deque:前/后部插入/删除,直接访问list:双向链表,任意位置插入/删除2)关联容器set:快速查找,无重复元素multiset:快速查找,可有重复元素map:一对一映射,无重复元素,基于关键字查找multimap:一对一映射,可有重复元素,基于关键字查找前2者合称为第一类容器3)容器适配器stack:LIFOqueue:FIFOpriority_queue:优先级高的元素先出,10,容器概述,对象被插入容器中时,被插入的是对象的一个复制品。许多算法,比如排序,查找,要求对容器中的元素进行比较,所以,放入容器的对象所属的类,还应该实现=和=,=,!=empty:判断容器中是否有元素max_size:容器中最多能装多少元素size:容器中元素个数swap:交换两个容器的内容,比较两个容器的例子:#include#includeclassAprivate:intn;public:friendbooloperatorv1;std:vectorv2;v1.push_back(A(5);v1.push_back(A(1);v2.push_back(A(1);v2.push_back(A(2);v2.push_back(A(3);std:cout(v1v2);return0;,输出:0,若两容器长度相同、所有元素相等,则两个容器就相等,否则为不等。若两容器长度不同,但较短容器中所有元素都等于较长容器中对应的元素,则较短容器小于另一个容器若两个容器均不是对方的子序列,则取决于所比较的第一个不等的元素,16,容器的成员函数,2)只在第一类容器中的函数:begin返回指向容器中第一个元素的迭代器end返回指向容器中最后一个元素后面的位置的迭代器rbegin返回指向容器中最后一个元素的迭代器rend返回指向容器中第一个元素前面的位置的迭代器erase从容器中删除一个或几个元素clear从容器中删除所有元素,Head,Tail,begin,rbegin,rend,end,17,迭代器,用于指向第一类容器中的元素。有const和非const两种。通过迭代器可以读取它指向的元素,通过非const迭代器还能修改其指向的元素。迭代器用法和指针类似。定义一个容器类的迭代器的方法可以是:容器类名:iterator变量名;或:容器类名:const_iterator变量名;访问一个迭代器指向的元素:*迭代器变量名,18,迭代器,迭代器上可以执行+操作,以指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面,则迭代器变成past-the-end值。使用一个past-the-end值的迭代器来访问对象是非法的,就好像使用NULL或未初始化的指针一样。,例如:#include#includeusingnamespacestd;intmain()vectorv;/一个存放int元素的向量,一开始里面没有元素v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector:const_iteratori;/常量迭代器for(i=v.begin();i!=v.end();i+)cout*i,;coutendl;,vector:reverse_iteratorr;/反向迭代器for(r=v.rbegin();r!=v.rend();r+)cout:iteratorj;/非常量迭代器for(j=v.begin();j!=v.end();j+)*j=100;for(i=v.begin();i!=v.end();i+)cout*i=p1,24,容器所支持的迭代器类别,容器迭代器类别vector随机deque随机list双向set/multiset双向map/multimap双向stack不支持迭代器queue不支持迭代器priority_queue不支持迭代器,例如,vector的迭代器是随机迭代器,所以遍历vector可以有以下几种做法:vectorv(100);vector:value_typei;/等效于写inti;(P687)for(i=0;i:const_iteratorii;for(ii=v.begin();ii!=v.end();ii+)cout*ii;/间隔一个输出:ii=v.begin();while(iiv.end()cout*ii;ii=ii+2;,而list的迭代器是双向迭代器,所以以下代码可以:listv;list:const_iteratorii;for(ii=v.begin();ii!v.end();ii+)cout*ii;以下代码则不行:for(ii=v.begin();iiv.end();ii+)cout*ii;/双向迭代器不支持for(inti=0;iv.size();i+)coutvi;/双向迭代器不支持,27,算法简介,STL中提供能在各种容器中通用的算法,比如插入,删除,查找,排序等。大约有70种标准算法。算法就是一个个函数模板。算法通过迭代器来操纵容器中的元素。许多算法需要两个参数,一个是起始元素的迭代器,一个是终止元素的后面一个元素的迭代器。比如,排序和查找有的算法返回一个迭代器。比如find()算法,在容器中查找一个元素,并返回一个指向该元素的迭代器。算法可以处理容器,也可以处理C语言的数组,28,算法分类,变化序列算法copy,remove,fill,replace,random_shuffle,swap,.会改变容器非变化序列算法:adjacent-find,equal,mismatch,find,count,search,count_if,for_each,search_n以上函数模板都在中定义V2,P692(V5,P834)此外还有其他算法,比如中的算法,29,算法示例:find(),templateInItfind(InItfirst,InItlast,constTfirst和last这两个参数都是容器的迭代器,它们给出了容器中的查找区间起点和终点。这个区间是个左闭右开的区间,即区间的起点是位于查找范围之中的,而终点不是val参数是要查找的元素的值函数返回值是一个迭代器。如果找到,则该迭代器指向被找到的元素。如果找不到,则该迭代器指向查找区间终点。,#include#include#includeusingnamespacestd;main()intarray10=10,20,30,40;vectorv;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector:iteratorp;p=find(v.begin(),v.end(),3);if(p!=v.end()cout*pendl;,p=find(v.begin(),v.end(),9);if(p=v.end()coutnotfoundendl;p=find(v.begin()+1,v.end()-2,1);if(p!=v.end()cout*pendl;int*pp=find(array,array+4,20);cout*ppendl;输出:3notfound320,32,顺序容器,除前述共同操作外,顺序容器还有以下共同操作:front():返回容器中第一个元素的引用back():返回容器中最后一个元素的引用push_back():在容器末尾增加新元素pop_back():删除容器末尾的元素比如,查list:front的help,得到的定义是:referencefront();const_referencefront()const;list有两个front函数,33,顺序容器,reference和const_reference是typedef的类型,含义见P687对于list,list:reference实际上就是doubleinta5=1,2,3,4,5;vectorv(5);coutv2(a,a+5);/构造函数v2.insert(v2.begin()+2,13);/在begin()+2位置插入13for(i=0;iv2.size();i+)coutv2ioutputInt(cout);*outputInt=n1+n2;coutendl;inta5=1,2,3,4,5;copy(a,a+5,outputInt);/输出整个数组return0;,41,程序运行后输入7890敲回车,则输出结果为:78,9016812345,42,list容器,在任何位置插入删除都是常数时间,不支持随机存取。除了具有所有顺序容器都有的成员函数以外,还支持8个成员函数:push_front:在前面插入pop_front:删除前面的元素sort:排序(list不支持STL的算法sort)remove:删除和指定值相等的所有元素unique:删除所有和前一个元素相同的元素merge:合并两个链表,并清空被合并的那个reverse:颠倒链表splice:在指定位置前面插入另一链表中的一个或多个元素,并在另一链表中删除被插入的元素,#include#include#includeusingstd:list;usingstd:ostream;usingstd:cout;usingstd:endl;classAprivate:intn;public:A(intn_)n=n_;friendbooloperator(constA,booloperatorvoidPrintList(conststd:list,intmain()listlst1,lst2;lst1.push_back(1);lst1.push_back(3);lst1.push_back(2);lst1.push_back(4);lst1.push_back(2);lst2.push_back(10);lst2.push_front(20);lst2.push_back(30);lst2.push_back(30);lst2.push_back(30);lst2.push_front(40);lst2.push_back(40);cout1);PrintList(lst1);coutendl;cout2);PrintList(lst2);coutendl;lst2.sort();cout3);PrintList(lst2);coutendl;lst2.pop_front();cout4);PrintList(lst2);coutendl;lst1.remove(2);/删除所有和A(2)相等的元素cout5);PrintList(lst1);coutendl;lst2.unique();/删除所有和前一个元素相等的元素,cout:iteratorp1,p2,p3;p1=std:find(lst1.begin(),lst1.end(),3);p2=std:find(lst2.begin(),lst2.end(),200);p3=std:find(lst2.begin(),lst2.end(),400);lst1.splice(p1,lst2,p2,p3);/将p2,p3)插入p1之前,/并从lst2中删除p2,p3)cout11);PrintList(lst1);coutendl;cout12);PrintList(lst2);coutendl;return0;,47,输出:,1)1,3,2,4,2,2)40,20,10,30,30,30,40,3)10,20,30,30,30,40,40,4)20,30,30,30,40,40,5)1,3,4,6)20,30,40,7)1,3,4,20,30,40,8)9)40,30,20,4,3,1,11)40,30,20,4,200,300,3,1,12)100,400,48,deque容器,所有适用于vector的操作都适用于dequedeque还有push_front(将元素插入到前面)和pop_front(删除最前面的元素)操作,49,作业,1.阅读V2版P757的自测练习及答案;2.完成V2版P758的20.14.3.上周的作业,- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 程序设计 实习 第二十 标准 模板 stli
装配图网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文