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

《程序设计实习》课程(C++ProgrammingPractice)20:39程序设计实习第二十一讲标准模板库STL-II主讲教师：田永鸿[e-mail]://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/setmultimap/mapstack/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)：dividesTequal_toTgreaterTlessT…….这些模板可以用来生成函数对象北京大学《程序设计实习》课程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=