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

2023/9/14,程序设计实习第二十一讲 标准模板库 STL-II,主讲教师：田永鸿2008年5月26日,2,内容回顾,容器类模板和迭代器顺序：vector(随机)deque(随机)list(双向)关联：set(双向)multiset(双向)map(双向)multimap(双向)容器适配器：stack(不支持)queue(不支持)priority_queue(不支持)每一类迭代器所能执行的操作不一样。函数模板find p=find(v.begin(),v.end(),9);/vector int*pp=find(array,array+4,20);/数组copy ostream_iterator output(cout,“*);copy(v.begin(),v.end(),output);重点介绍了vector类模板(其实就是动态数组,尾部添加数据,用户无需维护内存)空构造函数 数组构造 push_back()erase()vector:iterator p,3,课堂问题(1),给定如下list容器，下述哪些语句是错误的？为什么？list v;list:const_iterator ii;(a)for(ii=v.begin();ii!=v.end();ii+)cout v;v.push_back(1);v.push_back(2);vector:reverse_iterator r;for(r=v.rbegin();r!=v.rend();r-)cout*r,;,4,课堂问题(2),下面的迭代器的用法哪些（若存在的话）是错误的？const vector ivec(10);vector svec(10);list ilist(10);(a)vector:iterator it=ivec.begin();(b)list:iterator it=ilist.begin()+2;(c)vector:iterator it=+it)/对于下列程序任务，采用哪种顺序容器是实现最合适？解释选择的理由？(a)从一个文件中读入未知数目的单词，以生成英文句子；(b)读入固定数目的单词，在输入时将它们按字母序插入到容器中。(c)读入未知数目的单词，总在容器尾部插入新单词，在容器首部删除下一个值；(d)从一个文件中读入未知数目的整数，对这些整数排序，然后把它们输出到标准输出设备。,由于单词数目未知，且需要以非确定的顺序处理这些单词，因此vector最合适，因为它支持随机访问；采用list实现最合适，因为需要在容器的任意位置插入元素。（实际上本节将讲述的关联容器更好）采用deque实现最合适若一边输入一边排序，则list最合适，因为读入时需要在容器的任意位置插入元素来实现排序；若先读入所有整数再排序，采用vector最合适，因为进行排序最好有随机访问能力。,5,课堂问题(3),若iv是一个int型的vector容器，下面的程序错在哪里？如何改正？vector:iterator mid=iv.begin()+iv.size()/2;while(vector:iterator iter!=mid)if(iter=some_val).添加一条语句后，下面的程序是否还有错？如何改正？vector:iterator iter=iv.begin();vector:iterator mid=iv.begin()+iv.size()/2;while(vector:iterator iter!=mid)if(*iter=some_val)iv.insert(iter,2*some_val);,vector:iterator iter=iv.begin();while(iter!=iv.begin()+iv.size()/2)if(*iter=some_val)iter=iv.insert(iter,2*some_val);iter+=2;/使iter指向下一个要处理的原始元素 else iter+;/使iter指向下一个要处理的原始元素,6,内容提要,新概念函数对象pair 模板STL中的其它容器类模板multiset/set multimap/map stack/queue/priority_queue复习copy函数模板,7,函数对象,是个对象，但是用起来看上去象函数调用，实际上也执行了函数调用class CMyAverage public:double operator()(int a1,int a2,int a3)/重载()运算符return(double)(a1+a2+a3)/3;/重载()运算符时，参数可以是任意多个 CMyAverage Average;/函数对象 cout Average(3,2,3);/Average.operator(3,2,3)用起来看上去象函数调用输出 2.66667,8,函数对象的应用,STL里有以下模板：template T accumulate(InIt first,InIt last,T val,Pred pr);pr 就是个函数对象，实际上是个函数也可以对first,last)中的每个迭代器 I,执行 val=pr(val,*I),返回最终的val,#include#include#include#include#include using namespace std;int sumSquares(int total,int value)return total+value*value;template class SumSquaresClasspublic:const T,int main()const int SIZE=10;int a1=1,2,3,4,5,6,7,8,9,10;vector v(a1,a1+SIZE);ostream_iterator output(cout,);cout s;result=accumulate(v.begin(),v.end(),0,s);/(1)cout 3)平方和：result;return 0;,输出：1)1 2 3 4 5 6 7 8 9 102)平方和：3853)平方和：385,课本上是：class SumSquaresClass:public binary_function public:const T/(1)效果一样,12,函数对象类模板,binary_function定义：template struct binary_function typedef Arg1 first_argument_type;typedef Arg2 second_argument_type;typedef Result result_type;,13,函数对象类模板,STL 的 里还有以下函数对象类模板(v2版的P750/v5版的P879)：dividesequal_togreaterless.这些模板可以用来生成函数对象,14,greater 函数对象类模板,template struct greater:public binary_function bool operator()(const T,15,greater 的应用,list 有两个sort函数，前面看到的是不带参数的sort函数，它将list按 pr);可以用来进行降序排序,#include#include using namespace std;int main()const int SIZE=5;int aSIZE=5,1,4,2,3;list lst(a,a+SIZE);lst.sort(greater();/greater()是个对象/本句进行降序排序ostream_iterator output(cout,);copy(lst.begin(),lst.end(),output);cout endl;return 0;/输出：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,19,multiset,定义：template,class A=allocator class multiset;第二个参数 Pred 是个函数对象Pred决定了multiset 中的元素，“一个比另一个小”是怎么定义的，即 Pred(x,y)如果返回值为true,则 x比y小Pred的缺省值是 lessless 模板的定义：template struct less:public binary_function bool operator()(const T/less模板是靠 来比较大小的,20,multiset的用法,class A.;multiset a;就等效于multiset a;由于less模板是用 进行比较的，所以这都要求 A 的对象能用 比较，即适当重载了,/出错的例子：#include using namespace std;class A;int main()multiset a;a.insert(A();/error return/编译出错是因为，插入元素时，multiset会将被插入元素和已有元素进行比较，以决定新元素的存放位置。本例中缺省地就是用less函数对象进行比较，然而less函数对象进行比较时，前提是A对象能用 进行比较。但本例中没有适当重载,22,multiset的用法,从 begin()到 end()遍历一个 multiset对象，就是从小到大遍历各个元素,23,pair模板,讲例子之前先看 pair 模板:template struct pair typedef T first_type;typedef U second_type;T first;U second;pair();pair(const T pair模板可以用于生成 key-value对m.equal_range(k)：返回一个迭代器的pair对象；它的first成员等价于m.lower_bound(k)，而second成员则等价于m.upper_bound(k),24,pair模板,pair模板类用来绑定两个对象为一个新的对象，该类型在头文件中定义。pair模板类支持如下操作：pair p1：创建一个空的pair对象，它的两个元素分别是T1和T2类型，采用值初始化pair p1(v1,v2)：创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2make_pair(v1,v2)：以v1和v2值创建一个新的pair对象，其元素类型分别是v1和v2的类型p1 p2字典次序：如果p1.firstp2.first或者!(p2.first p1.first)&p1.secondp2.second，则返回truep1=p2：如果两个pair对象的first和second成员依次相等，则这两个对象相等。p.first：返回p中名为first的（公有）数据成员p.second：返回p中名为second的（公有）数据成员,#include#include using namespace std;class MyLess;class A private:int n;public:A(int n_)n=n_;friend bool operator(const A,class MyLess public:bool operator()(const A/MSET2 里，元素的排序规则与 MSET1不同，/假设 le 是一个 MyLess对象，a1和a2是MSET2对象/里的元素，那么，le(a1,a2)=true 就说明 a1比a2小,int main()const int SIZE=5;A aSIZE=4,22,19,8,33;ostream_iterator output(cout,);MSET1 m1;m1.insert(a,a+SIZE);m1.insert(22);cout 1)m1.count(22)endl;MSET1:const_iterator p;cout 2);for(p=m1.begin();p!=m1.end();p+)cout*p,;cout endl;MSET2 m2;m2.insert(a,a+SIZE);cout 3);copy(m2.begin(),m2.end(),output);cout endl;,MSET1:iterator pp=m1.find(19);if(pp!=m1.end()/找到 cout pr;cout endl;cout 6);cout*m1.lower_bound(22),;cout*m1.upper_bound(22)endl;pr=m1.equal_range(22);cout 7)*pr.first,*pr.second;return 0;,输出：1)22)4,8,19,22,22,33,3)22,33,4,8,19,found4)4,8,19,22,22,33,6)22,337)22,33,30,set,template,class A=allocator class set 插入set中已有的元素时，插入不成功。,#include#include using namespace std;int main()typedef set double_set;const int SIZE=5;double aSIZE=2.1,4.2,9.5,2.1,3.7;double_set doubleSet(a,a+SIZE);ostream_iterator output(cout,);cout p;p=doubleSet.insert(9.5);if(p.second)cout 2)*(p.first)inserted endl;else cout 2)*(p.first)not inserted endl;return 0;,insert函数返回值是一个pair对象,其first是被插入元素的迭代器，second代表是否成功插入了,输出：1)2.1 3.7 4.2 9.52)9.5 not inserted,33,multimap,template,class A=allocator class multimap.typedef pair value_type;.;/Key 代表关键字multimap中的元素由 组成，每个元素是一个pair对象。multimap 中允许多个元素的关键字相同。元素按照关键字升序排列，缺省情况下用 less 定义关键字的“小于”关系,#include#include using namespace std;int main()typedef multimap mmid;mmid pairs;cout 1)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_iterator i=pairs.begin();i!=pairs.end();i+)cout first second),;/输出：1)02)2(10,22.22),(15,2.7),(15,99.3),(20,9.3),(25,33.333),(30,111.11),36,map,template,class A=allocator class map.typedef pair value_type;.;map 中的元素关键字各不相同。元素按照关键字升序排列，缺省情况下用 less 定义“小于”,37,map,可以用pairskey 访形式问map中的元素。pairs 为map容器名，key为关键字的值。该表达式返回的是对关键值为key的元素的值的引用。如果没有关键字为key的元素，则会往pairs里插入一个关键字为key的元素，并返回其值的引用如：map pairs;则 pairs50=5;会修改pairs中关键字为50的元素，使其值变成5,#include#include using namespace std;ostream,mmid:iterator i;cout 3);for(i=pairs.begin();i!=pairs.end();i+)cout*i,;cout endl;cout 4);int n=pairs40;/如果没有关键字为40的元素，则插入一个for(i=pairs.begin();i!=pairs.end();i+)cout*i,;cout endl;cout 5);pairs15=6.28;/把关键字为15的元素值改成6.28for(i=pairs.begin();i!=pairs.end();i+)cout*i,;return 0;,输出：1)02)13)(15,2.7),(20,9.3),4)(15,2.7),(20,9.3),(40,0),5)(15,6.28),(20,9.3),(40,0),41,思考题,如何用程序用来统计一篇英文文章中单词出现的频率（为简单起见，假定依次从键盘输入该文章）#include#include using namespace std;int main()map wordCount;string word;while(cin word)+wordCountword;for(map:iterator it=wordCount.begin();it!=wordCount.end();+it)coutWord:(*it).first tCount:(*it).secondendl;return 0;,42,容器适配器:stack,可用 vector,list,deque来实现缺省情况下，用deque实现用 vector和deque实现，比用list实现性能好template class stack.;stack 是后进先出的数据结构，只能插入、删除、访问栈顶的元素,43,容器适配器:stack,stack 上可以进行以下操作：push:插入元素pop:弹出元素top:返回栈顶元素的引用,44,容器适配器:queue,和stack 基本类似，可以用 list和deque实现，缺省情况下用deque实现template class queue;同样也有push,pop,top函数但是push发生在队尾，pop,top发生在队头，先进先出,45,容器适配器:priority_queue,和 queue类似，可以用vector和deque实现，缺省情况下用vector实现。priority_queue 通常用堆排序技术实现，保证最大的元素总是在最前面。即执行pop操作时，删除的是最大的元素，执行top操作时，返回的是最大元素的引用。默认的元素比较器是 less,#include#include using namespace std;int main()priority_queue priorities;priorities.push(3.2);priorities.push(9.8);priorities.push(5.4);while(!priorities.empty()cout priorities.top();priorities.pop();return 0;/输出结果：9.8 5.4 3.2,47,小结(1),新概念-函数对象class CMyAverage public:double operator()(int a1,int a2,int a3)return(double)(a1+a2+a3)/3;CMyAverage Average;/函数对象cout p;p=doubleSet.insert(9.5);if(p.second)cout 2)*(p.first)inserted endl;,48,小结(2),STL中的其它容器类模板list sort函数 升序 降序multiset set/排序 less multimap map/排序 less pair stack queue priority_queue复习copy函数模板,49,作业,单词过滤程序：in1.txt,in2.txt 都是纯文本文件，每行一个英文单词，最多可能有二十万行，一个单词长度最多可以有2000个字符。要求编程输出out.txt，out.txt里是in2.txt里有，而in1.txt里没有的单词，每个单词一行。单词不分大小写。,50,2008百度之星程序设计大赛,赛事将至 2008 年 5 月 30 日 晚 24 时注册截止。注册网址：http:/整个赛事包括网络资格赛（初赛）、网络晋级赛（复赛）和现场总决赛。编程语言 标准 ANSI C，C+开发及运行环境竞赛的评分工作在 Linux+Gcc 环境下进行。评分以赛手提交的源码在此环境下的编译运行结果为准。网络资格赛（初赛）和晋级赛（复赛）时，赛手可以在自己的计算机上使用任何自己熟悉的开发调试软件和工具，进行代码开发和调试工作。完成后，赛手可以在线提交源码（百度提供在线 Linux+Gcc 编译环境），得到编译程序的输出信息。奖项设置 一等奖 1 名 15000 元 人民币；二等奖 3 名 6000 元 人民币；三等奖 5 名 3000 元 人民币；晋级奖 大赛珍藏版 T 恤和 08 年特别版“度度熊”一只参与奖 所有入围复赛的赛手都将获得大赛限量纪念版 T 恤一件。,