71北京大学程序设计实习课程

《程序设计实习》课程(C++ProgrammingPractice)程序设计实习第二十二讲标准模板库STL-III主讲教师：田永鸿[e-mail]://idm.pku.edu.cn/jiaoxue-CPP/cpp08.htm2008年5月28日北京大学《程序设计实习》课程2内容回顾新概念函数对象pair模板STL中的其它容器类模板multiset/setmultimap/mapstack/queue/priority_queue复习copy函数模板北京大学《程序设计实习》课程3课堂问题(1)1.下面各描述说明了STL中迭代器与C++指针的关系，不正确的有哪些？(1)迭代器包含内存地址的获得，是面向对象版本的指针。迭代器可以包括指针，但迭代器又不仅是一个指针。(2)迭代器保存所操作的特定容器需要的状态信息，从而实现与每种容器类型相适应的迭代器。(3)从本质上说，STL提供的所有算法都是模板，我们可以通过使用自己指定的迭代器来对这些模板实例化。(4)++运算符总是返回容器下一个元素的迭代器，--运算符总是返回容器上一个元素的迭代器。2.下面有关函数对象的说法中，正确的有哪些?(1)函数对象是一个类，它重载了函数调用操作符（operator()）。典型情况下，函数对象被作为实参传递给泛型算法。(2)函数指针是间接引用，不能作为内联函数，而函数对象可以，这样速度更快。(3)编译时对函数对象和函数指针均作类型检查。(4)类有数据域，函数对象可以拥有任意数量的额外数据，用这些数据可以用来缓冲当前数据和结果，提高运行质量。北京大学《程序设计实习》课程4课堂问题(2)3.指出下述程序中的错误之处#includesetusingnamespacestd;classA{intn;public:A(intn_){n=n_;}booloperator==(constint&m){returnn==m;}};intmain(){multisetAa;a.insert(A(5));return0;}4.以下关于STL中stack类模板的正确说法是：A.stack是关联容器B.对于stack上的迭代器p，能够执行p++操作C.stack可以用deque实现D.可以用sort算法对stack进行排序北京大学《程序设计实习》课程5课堂问题(3)5.以下程序编译、连接都能通过，请写出运行时输出的结果。你认为没有输出的，就写无输出#includevector#includeiostreamusingnamespacestd;classA{private:intnId;public:A(intn){nId=n;coutnIdcontructorendl;};~A(){coutnIddestructorendl;}};intmain(){vectorA*vp;vp.push_back(newA(1));vp.push_back(newA(2));vp.clear();Aa(4);return0;}1contructor2contructor4contructor4destructor北京大学《程序设计实习》课程6内容提要–算法fill、remove、replace系列算法数学算法排序和查找算法交换、合并等算法集合操作算法位操作算法作业北京大学《程序设计实习》课程7fill、remove、replace系列算法fill与fill_ntemplateclassFwdIt,classTvoidfill(FwdItfirst,FwdItlast,constT&x);templateclassOutIt,classSize,classTvoidfill_n(OutItfirst,Sizen,constT&x);fill,fill_n:将容器中某一区间的元素全部设为某值，比如：vectorintv(100);fill(v.begin(),v.end(),5);//将全部元素设为5vectorcharvc(100);fill_n(vc.begin(),5,‘A’);//将begin()及其后5个元//素设为‘A’北京大学《程序设计实习》课程8fill、remove、replace系列算法generate和generate_n依次将容器中某一区间的值，设为g()templateclassFwdIt,classGenvoidgenerate(FwdItfirst,FwdItlast,Geng);templateclassOutIt,classPred,classGenvoidgenerate_n(OutItfirst,Distn,Geng);#includevector#includeiostream#includealgorithmusingnamespacestd;charnextLetter(){staticcharletter='A';returnletter++;}intmain(){vectorcharv(5);ostream_iteratorcharoutput(cout,,);generate(v.begin(),v.end(),nextLetter);copy(v.begin(),v.end(),output);coutendl;generate_n(v.begin(),5,nextLetter);copy(v.begin(),v.end(),output);return0;}//输出：A,B,C,D,E,F,G,H,I,J,北京大学《程序设计实习》课程10fill、remove、replace系列算法remove,remove_if,remove_copy，remove_copy_iftemplateclassFwdIt,classTFwdItremove(FwdItfirst,FwdItlast,constT&val);删除[first,last)中所有和val相等的元素，这里“删除”的意思是用该区间后面的元素替换，后面的元素往前移动的意思，因此该函数不会使容器里的元素真正减少。返回值是迭代器，指向被修改后序列的终点，即被修改后的序列是[first,fwdIt)如果被删除的是[first,last)中的最后一个元素，那么就等于什么操作都没做，因为[first,last)里没有元素可以往前移,来替换被删除元素了，此时返回值指向last的前一个元素。如果[first,last)中没有元素等于val，那么fdwIt等于last例：#includevector#includeiostream#includealgorithmusingnamespacestd;intmain(){ostream_iteratorintoutput(cout,,);constintSIZE=5;inta[SIZE]={1,2,3,4,5};vectorintv(a,a+SIZE);vectorint::iteratori=remove(v.begin(),v.end(),5);cout1);copy(v.begin(),i,output);coutendl;i=remove(v.begin(),v.begin()+1,1);cout2);copy(v.begin(),i,output);coutendl;cout3);copy(v.begin(),v.end(),output);coutendl;i=remove(v.begin(),v.begin()+2,1);cout4);copy(v.begin(),v.end(),output);coutendl;return0;}输出：1)1,2,3,4,2)3)1,2,3,4,5,4)2,2,3,4,5,北京大学《程序设计实习》课程13remove_iftemplateclassFwdIt,classPredFwdItremove_if(FwdItfirst,FwdItlast,Predpr);remove_if和remove类似，不同之处在于，被删除的元素e必须是满足pr(e)==true的。pr可以是函数对象或函数北京大学《程序设计实习》课程14remove_copytemplateclassInIt,classOutIt,classTOutItremove_copy(InItfirst,InItlast,OutItx,constT&val);将[first,last)中所有不等于val的元素，拷贝到另一容器中从x开始的位置(会覆盖另一容器中原有的元素，须确保另一容器足够长，否则会出错）返回值是另一容器的迭代器，指向被拷贝序列的最后一个元素的后面。如果操作在同一容器上进行，则[x,x+(last-first))不能和[first,last)有重叠，否则会出错。remove_copy示例：#includevector#includeiostream#includealgorithmusingnamespacestd;intmain(){ostream_iteratorintoutput(cout,,);constintSIZE=5;inta[SIZE]={1,2,3,4,5};vectorintv(a,a+SIZE);vectorintv2(10);vectorint::iteratori=remove_copy(v.begin(),v.end(),v2.begin(),5);cout1);copy(v2.begin(),i,output);coutendl;i=remove_copy(v.begin(),v.begin()+1,v2.begin(),1);cout2);copy(v2.begin(),i,output);coutendl;cout3);copy(v2.begin(),v2.end(),output);coutendl;i=remove_copy(v.begin(),v.begin()+2,v2.begin(),1);cout4);copy(v2.begin(),i,output);coutendl;cout5);copy(v2.begin(),v2.end(),output);coutendl;return0;}输出：1)1,2,3,4,2)3)1,2,3,4,0,0,0,0,0,0,4)2,5)2,2,3,4,0,0,0,0,0,0,北京大学《程序设计实习》课程18remove_copy_iftemplateclassInIt,classOutIt,classPredOutItremove_copy_if(InItfirst,InItlast,OutItx,Predpr);将[first,last)中所有pr(e)为false的元素e,拷贝到另一容器中从x开始的位置(会覆盖另一容器中原有的元素，须确保另一容器足够长，否则会出错）返回值是另一容器的迭代器，指向被拷贝序列的最后一个元素的后面。如果操作在同一容器上进行，则[x,x+(last-first))不能和[first,last)有重叠，否则会出错。北京大学《程序设计实习》课程19replace,replace_if,replace_copy,replace_copy_iftemplatecaassFwdIt,classTvoidreplace(FwdItfirst,FwdItlast,constT&vold,constT&vnew);将[first,last)区间中，所有等于vold的元素,替换为vnewtemplateclassFwdIt,class