程序设计实习第二十一讲标准模板.ppt

13:01,程序设计实习第二十一讲标准模板库STL-II,主讲教师：田永鸿yhtian,2,内容回顾,容器类模板和迭代器顺序：vector(随机)deque(随机)list(双向)关联：set(双向)multiset(双向)map(双向)multimap(双向)容器适配器：stack(不支持)queue(不支持)priority_queue(不支持)每一类迭代器所能执行的操作不一样。函数模板findp=find(v.begin(),v.end(),9);/vectorint*pp=find(array,array+4,20);/数组copyostream_iteratoroutput(cout,“*);copy(v.begin(),v.end(),output);重点介绍了vector类模板(其实就是动态数组,尾部添加数据,用户无需维护内存)空构造函数数组构造push_back()erase()vector:iteratorp,3,课堂问题(1),给定如下list容器，下述哪些语句是错误的？为什么？listv;list:const_iteratorii;(a)for(ii=v.begin();ii!=v.end();ii+)coutv;v.push_back(1);v.push_back(2);vector:reverse_iteratorr;for(r=v.rbegin();r!=v.rend();r-)cout*r,;,4,课堂问题(2),下面的迭代器的用法哪些（若存在的话）是错误的？constvectorivec(10);vectorsvec(10);listilist(10);(a)vector:iteratorit=ivec.begin();(b)list:iteratorit=ilist.begin()+2;(c)vector:iteratorit=+it)/对于下列程序任务，采用哪种顺序容器是实现最合适？解释选择的理由？(a)从一个文件中读入未知数目的单词，以生成英文句子；(b)读入固定数目的单词，在输入时将它们按字母序插入到容器中。(c)读入未知数目的单词，总在容器尾部插入新单词，在容器首部删除下一个值；(d)从一个文件中读入未知数目的整数，对这些整数排序，然后把它们输出到标准输出设备。,由于单词数目未知，且需要以非确定的顺序处理这些单词，因此vector最合适，因为它支持随机访问；采用list实现最合适，因为需要在容器的任意位置插入元素。（实际上本节将讲述的关联容器更好）采用deque实现最合适若一边输入一边排序，则list最合适，因为读入时需要在容器的任意位置插入元素来实现排序；若先读入所有整数再排序，采用vector最合适，因为进行排序最好有随机访问能力。,5,课堂问题(3),若iv是一个int型的vector容器，下面的程序错在哪里？如何改正？vector:iteratormid=iv.begin()+iv.size()/2;while(vector:iteratoriter!=mid)if(iter=some_val).添加一条语句后，下面的程序是否还有错？如何改正？vector:iteratoriter=iv.begin();vector:iteratormid=iv.begin()+iv.size()/2;while(vector:iteratoriter!=mid)if(*iter=some_val)iv.insert(iter,2*some_val);,vector:iteratoriter=iv.begin();while(iter!=iv.begin()+iv.size()/2)if(*iter=some_val)iter=iv.insert(iter,2*some_val);iter+=2;/使iter指向下一个要处理的原始元素elseiter+;/使iter指向下一个要处理的原始元素,6,内容提要,新概念函数对象pair模板STL中的其它容器类模板multiset/setmultimap/mapstack/queue/priority_queue复习copy函数模板,7,函数对象,是个对象，但是用起来看上去象函数调用，实际上也执行了函数调用classCMyAveragepublic:doubleoperator()(inta1,inta2,inta3)/重载()运算符return(double)(a1+a2+a3)/3;/重载()运算符时，参数可以是任意多个CMyAverageAverage;/函数对象coutAverage(3,2,3);/Average.operator(3,2,3)用起来看上去象函数调用输出2.66667,8,函数对象的应用,STL里有以下模板：templateTaccumulate(InItfirst,InItlast,Tval,Predpr);pr就是个函数对象，实际上是个函数也可以对first,last)中的每个迭代器I,执行val=pr(val,*I),返回最终的val,#include#include#include#include#includeusingnamespacestd;intsumSquares(inttotal,intvalue)returntotal+value*value;templateclassSumSquaresClasspublic:constT,intmain()constintSIZE=10;inta1=1,2,3,4,5,6,7,8,9,10;vectorv(a1,a1+SIZE);ostream_iteratoroutput(cout,);couts;result=accumulate(v.begin(),v.end(),0,s);/(1)cout3)平方和：result;return0;,输出：1)123456789102)平方和：3853)平方和：385,课本上是：classSumSquaresClass:publicbinary_functionpublic:constT/(1)效果一样,12,函数对象类模板,binary_function定义：templatestructbinary_functiontypedefArg1first_argument_type;typedefArg2second_argument_type;typedefResultresult_type;,13,函数对象类模板,STL的里还有以下函数对象类模板(v2版的P750/v5版的P879)：dividesequal_togreaterless.这些模板可以用来生成函数对象,14,greater函数对象类模板,templatestructgreater:publicbinary_functionbooloperator()(constT,15,greater的应用,list有两个sort函数，前面看到的是不带参数的sort函数，它将list按pr);可以用来进行降序排序,#include#includeusingnamespacestd;intmain()constintSIZE=5;intaSIZE=5,1,4,2,3;listlst(a,a+SIZE);lst.sort(greater();/greater()是个对象/本句进行降序排序ostream_iteratoroutput(cout,);copy(lst.begin(),lst.end(),output);coutclassmultiset;第二个参数Pred是个函数对象Pred决定了multiset中的元素，“一个比另一个小”是怎么定义的，即Pred(x,y)如果返回值为true,则x比y小Pred的缺省值是lessless模板的定义：templatestructless:publicbinary_functionbooloperator()(constT/less模板是靠a;由于less模板是用进行比较的，所以这都要求A的对象能用比较，即适当重载了,/出错的例子：#includeusingnamespacestd;classA;intmain()multiseta;a.insert(A();/errorreturn/编译出错是因为，插入元素时，multiset会将被插入元素和已有元素进行比较，以决定新元素的存放位置。本例中缺省地就是用less函数对象进行比较，然而less函数对象进行比较时，前提是A对象能用进行比较。但本例中没有适当重载,22,multiset的用法,从begin()到end()遍历一个multiset对象，就是从小到大遍历各个元素,23,pair模板,讲例子之前先看pair模板:templatestructpairtypedefTfirst_type;typedefUsecond_type;Tfirst;Usecond;pair();pair(constTpair模板可以用于生成key-value对m.equal_range(k)：返回一个迭代器的pair对象；它的first成员等价于m.lower_bound(k)，而second成员则等价于m.upper_bound(k),24,pair模板,pair模板类用来绑定两个对象为一个新的对象，该类型在头文件中定义。pair模板类支持如下操作：pairp1：创建一个空的pair对象，它的两个元素分别是T1和T2类型，采用值初始化pairp1(v1,v2)：创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2make_pair(v1,v2)：以v1和v2值创建一个新的pair对象，其元素类型分别是v1和v2的类型p1p2字典次序：如果p1.firstp2.first或者!(p2.firstp1.first)classMyLess;classAprivate:intn;public:A(intn_)n=n_;friendbooloperator(constA,classMyLesspublic:booloperator()(constA/MSET2里，元素的排序规则与MSET1不同，/假设le是一个MyLess对象，a1和a2是MSET2对象/里的元素，那么，le(a1,a2)=true就说明a1比a2小,intmain()constintSIZE=5;AaSIZE=4,22,19,8,33;ostream_iteratoroutput(cout,);MSET1m1;m1.insert(a,a+SIZE);m1.insert(22);cout1)m1.count(22)endl;MSET1:const_iteratorp;cout2);for(p=m1.begin();p!=m1.end();p+)cout*p,;coutendl;MSET2m2;m2.insert(a,a+SIZE);cout3);copy(m2.begin(),m2.end(),output);coutendl;,MSET1:iteratorpp=m1.find(19);if(pp!=m1.end()/找到coutpr;coutendl;cout6);cout*m1.lower_bound(22),;cout*m1.upper_bound(22)endl;pr=m1.equal_range(22);cout7)*pr.first,double_set;constintSIZE=5;doubleaSIZE=2.1,4.2,9.5,2.1,3.7;double_setdoubleSet(a,a+SIZE);ostream_iteratoroutput(cout,);coutp;p=doubleSet.insert(9.5);if(p.second)cout2)*(p.first)insertedendl;elsecout2)*(p.first)notinsertedmmid;mmidpairs;cout1)pairs.count(15)endl;pairs.insert(mmid:value_type(15,2.7);pairs.insert(mmid:value_type(15,99.3);cout“2)”pairs.count(15)endl;/求某关键值的个数pairs.insert(mmid:value_type(30,111.11);pairs.insert(mmid:value_type(10,22.22);,pairs.insert(mmid:value_type(25,33.333);pairs.insert(mmid:value_type(20,9.3);for(mmid:const_iteratori=pairs.begin();i!=pairs.end();i+)coutfirstsecond)classmap.typedefpairvalue_type;.;map中的元素关键字各不相同。元素按照关键字升序排列，缺省情况下用less定义“小于”,37,map,可以用pairskey访形式问map中的元素。pairs为map容器名，key为关键字的值。该表达式返回的是对关键值为key的元素的值的引用。如果没有关键字为key的元素，则会往pairs里插入一个关键字为key的元素，并返回其值的引用如：mappairs;则pairs50=5;会修改pairs中关键字为50的元素，使其值变成5,#include#includeusingnamespacestd;ostream,mmid:iteratori;cout3);for(i=pairs.begin();i!=pairs.end();i+)cout*i,;coutendl;cout4);intn=pairs40;/如果没有关键字为40的元素，则插入一个for(i=pairs.begin();i!=pairs.end();i+)cout*i,;coutendl;cout5);pairs15=6.28;/把关键字为15的元素值改成6.28for(i=pairs.begin();i!=pairs.end();i+)cout*iword)+wordCountword;for(map:iteratorit=wordCount.begin();it!=wordCount.end();+it)coutWord:(*it).firsttCount:(*it).secondclassqueue;同样也有push,pop,top函数但是push发生在队尾，pop,top发生在队头，先进先出,45,容器适配器:priority_queue,和queue类似，可以用vector和deque实现，缺省情况下用vector实现。priority_queue通常用堆排序技术实现，保证最大的元素总是在最前面。即执行pop操作时，删除的是最大的元素，执行top操作时，返回的是最大元素的引用。默认的元素比较器是less,#include#includeusingnamespacestd;intmain()priority_queuepriorities;priorities.push(3.2);priorities.push(9.8);priorities.push(5.4);while(!priorities.empty()coutpriorities.top();priorities.pop();return0;/输出结果：9.85.43.2,47,小结(1),新概念-函数对象classCMyAveragepublic:doubleoperator()(inta1,inta2,inta3)return(double)(a1+a2+a3)/3;CMyAverageAverage;/函数对象coutp;p=doubleSet.insert(9.5);if(p.second)cout2)*(p.first)insertedendl;,48,小结(2),STL中的其它容器类模板listsort函数升序降序multisetset/排序lessmultimapmap/排序lesspairstackqueuepriority_queue复习copy函数模板,49,作业,单词过滤程序：in1.txt,in2.txt都是纯文本文件，每行一个英文单词，最多可能有二十万行，一个单词长度最多可以有2000个字符。要求编程输出out.txt，out.txt里是in2.txt里有，而in1.txt里没有的单词，每个单词一行。单词不分大小写。,50,2008百度之星程序设计大赛,赛事将至2008年5月30日晚24时注册截止。注册网址：标准ANSIC，C+开发及运行环境竞赛的评分工作在Linux+Gcc环境下进行。评分以赛手提交的源码在此环境下的编译运行结果为准。网络资格赛（初赛）和晋级赛（复赛）时，赛手可以在自己的计算机上使用任何自己熟悉的开发调试软件和工具，进行代码开发和调试工作。完成后，赛手可以在线提交源码（百度提供在线Linux+Gcc编译环境），得到编译程序的输出信息。奖项设置一等奖1名15000元人民币；二等奖3名6000元人民币；三等奖5名3000元人民币；晋级奖大赛珍藏版T恤和08年特别版“度度熊”一只参与奖所有入围复赛的赛手都将获得大赛限量纪念版T恤一件。,