您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 人事档案/员工关系 > 程序设计实习第二十一讲标准模板
《程序设计实习》课程(C++ProgrammingPractice)20:39程序设计实习第二十一讲标准模板库STL-II主讲教师:田永鸿yhtian@pku.edu.cn://idm.pku.edu.cn/jiaoxue-CPP/cpp08.htm2008年5月26日北京大学《程序设计实习》课程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_iteratorintoutput(cout,“*);copy(v.begin(),v.end(),output);重点介绍了vector类模板(其实就是动态数组,尾部添加数据,用户无需维护内存)空构造函数数组构造push_back()erase()vectorint::iteratorp北京大学《程序设计实习》课程3课堂问题(1)1.给定如下list容器,下述哪些语句是错误的?为什么?listintv;listint::const_iteratorii;(a)for(ii=v.begin();ii!=v.end();ii++)cout*ii;(b)for(ii=v.begin();iiv.end();ii++)cout*ii;(c)for(inti=0;iv.size();i++)coutv[i];2.下列语句是否存在错误?若有,则改正;若无,请输出结果vectorintv;v.push_back(1);v.push_back(2);vectorint::reverse_iteratorr;for(r=v.rbegin();r!=v.rend();r--)cout*r,;北京大学《程序设计实习》课程4课堂问题(2)3.下面的迭代器的用法哪些(若存在的话)是错误的?constvectorintivec(10);vectorstringsvec(10);listintilist(10);(a)vectorint::iteratorit=ivec.begin();(b)listint::iteratorit=ilist.begin()+2;(c)vectorstring::iteratorit=&svec[0];(d)for(vectorstring::iteratorit=svec.begin();it!=0;++it)//……4.对于下列程序任务,采用哪种顺序容器是实现最合适?解释选择的理由?(a)从一个文件中读入未知数目的单词,以生成英文句子;(b)读入固定数目的单词,在输入时将它们按字母序插入到容器中。(c)读入未知数目的单词,总在容器尾部插入新单词,在容器首部删除下一个值;(d)从一个文件中读入未知数目的整数,对这些整数排序,然后把它们输出到标准输出设备。1.由于单词数目未知,且需要以非确定的顺序处理这些单词,因此vector最合适,因为它支持随机访问;2.采用list实现最合适,因为需要在容器的任意位置插入元素。(实际上本节将讲述的关联容器更好)3.采用deque实现最合适4.若一边输入一边排序,则list最合适,因为读入时需要在容器的任意位置插入元素来实现排序;若先读入所有整数再排序,采用vector最合适,因为进行排序最好有随机访问能力。北京大学《程序设计实习》课程5课堂问题(3)5.若iv是一个int型的vector容器,下面的程序错在哪里?如何改正?vectorint::iteratormid=iv.begin()+iv.size()/2;while(vectorint::iteratoriter!=mid)if(iter==some_val)…..6.添加一条语句后,下面的程序是否还有错?如何改正?vectorint::iteratoriter=iv.begin();vectorint::iteratormid=iv.begin()+iv.size()/2;while(vectorint::iteratoriter!=mid)if(*iter==some_val)iv.insert(iter,2*some_val);vectorint::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函数对象是个对象,但是用起来看上去象函数调用,实际上也执行了函数调用classCMyAverage{public:doubleoperator()(inta1,inta2,inta3){//重载()运算符return(double)(a1+a2+a3)/3;}};//重载()运算符时,参数可以是任意多个CMyAverageAverage;//函数对象coutAverage(3,2,3);//Average.operator(3,2,3)用起来看上去象函数调用输出2.66667北京大学《程序设计实习》课程8函数对象的应用STL里有以下模板:templateclassInIt,classT,classPredTaccumulate(InItfirst,InItlast,Tval,Predpr);pr就是个函数对象,实际上是个函数也可以对[first,last)中的每个迭代器I,执行val=pr(val,*I),返回最终的val#includeiostream#includevector#includealgorithm#includenumeric#includefunctionalusingnamespacestd;intsumSquares(inttotal,intvalue){returntotal+value*value;}templateclassTclassSumSquaresClass{public:constT&operator()(constT&total,constT&value){returntotal+value*value;}};intmain(){constintSIZE=10;inta1[]={1,2,3,4,5,6,7,8,9,10};vectorintv(a1,a1+SIZE);ostream_iteratorintoutput(cout,);cout1);copy(v.begin(),v.end(),output);coutendl;intresult=accumulate(v.begin(),v.end(),0,sumSquares);cout2)平方和:resultendl;SumSquaresClassints;result=accumulate(v.begin(),v.end(),0,s);//(1)cout3)平方和:result;return0;}输出:1)123456789102)平方和:3853)平方和:385课本上是:classSumSquaresClass:publicbinary_functionT,T,T{public:constT&operator()(constT&total,constT&value){returntotal+value*value;}};….result=accumulate(v.begin(),v.end(),0,SumSquaresClassint());//(1)效果一样北京大学《程序设计实习》课程12函数对象类模板binary_function定义:templateclassArg1,classArg2,classResultstructbinary_function{typedefArg1first_argument_type;typedefArg2second_argument_type;typedefResultresult_type;};北京大学《程序设计实习》课程13函数对象类模板STL的functional里还有以下函数对象类模板(v2版的P750/v5版的P879):dividesTequal_toTgreaterTlessT…….这些模板可以用来生成函数对象北京大学《程序设计实习》课程14greaterT函数对象类模板templateclassTstructgreater:publicbinary_functionT,T,bool{booloperator()(constT&x,constT&y)const{returnxy;}};北京大学《程序设计实习》课程15greaterT的应用list有两个sort函数,前面看到的是不带参数的sort函数,它将list按规定的比较方法升序排列list还有另一个sort函数:voidsort(greaterTpr);可以用来进行降序排序#includelist#includeiostreamusingnamespacestd;intmain(){constintSIZE=5;inta[SIZE]={5,1,4,2,3};listintlst(a,a+SIZE);lst.sort(greaterint());//greaterint()是个对象//本句进行降序排序ostream_iteratorintoutput(cout,,);copy(lst.begin(),lst.end(),output);coutendl;return0;}//输出:5,4,3,2,1,北京大学《程序设计实习》课程17关联容器set,multiset,map,multimap内部元素有序排列,新元素插入的位置取决于它的值,查找速度快map关联数组:元素通过键来存储和读取set大小可变的集合,支持通过键实现的快速读取multimap支持同一个键多次出现的map类型multiset支持同一个键多次出现的set类型与顺序容器的本质区别关联容器是通过键(key)存储和读取元素的而顺序容器则通过元素在容器中的位置顺序存储和访问元素。北京大学《程序设计实习》课程18关联容器除了各容器都有的函数外,还支持以下成员函数:设m表容器,k表键值m.find(k):如果容器中存在键为k的元素,则返回指向该元素的迭代器。如果不存在,则返回end()值。m.lower_bound(k):返回一个迭代器,指向键不小于k的第一个元素m.upper_bound(k):返回一个迭代器,指向键大于k的第一个元素m.count(k):返回m中k的出现次数插入元素用insert北京大学《程序设计实习》课程19multiset定义:templateclassKey,classPred=lessKey,classA=
本文标题:程序设计实习第二十一讲标准模板
链接地址:https://www.777doc.com/doc-6133864 .html