信息学奥赛STL数据类型简介课件

不定数组（vector）单县第一中学2017级信息学奥林匹克竞赛知识选讲不定数组（vector）单县第一中学2017级1一、定义Vector是一个不定数组，其大小可根据需要随时变动，可定义为一维数组，或者二维数组，甚至多维。数据库为#include<vector>定义如下：1一维：vector<int>vec;//定义了一个名为vec 的一维数组2二维：vector<int>vec[10];//定义了一个第一 维为10，二维动态 的数组一、定义Vector是一个不定数组，其大小可根据需要随时变动2二、使用数组插入元素：vec.push_back(同类型量);作用是在vector的末尾插入新元素；2.insert()第一个参数为迭代器，作用为在迭代器前面插入新元素；3.assign(5,1)向vector中加入5个1，同时清除掉以前的元素。二、使用数组插入元素：3二、使用数组删除元素：1.pop_back()删除最后一个元素。2.erase（）删除指定位置元素。（其中的参数要是指针变量，比如begain(),end(),以及迭代器值），例如vec.erase(vec.begin()+2);删除第3个元素3.clear（）清除所有元素。4.empty（）判断该数组是否为空二、使用数组删除元素：4二、使用访问数组：1.front()访问第一个元素（第一个元素的值而不是地址！begin()相反）2.back()访问最后一个元素（最后一个元素的值而不是地址！end()相反）3.size()数组的元素个数二、使用访问数组：5三、使用范例#include<vector>#include<iostream>usingnamespacestd;intmain(){ vector<int>a; for(inti=1;i<=100;i++){ a.push_back(i); } cout<<a.size()<<"\n";

for(inti=a.size();i>=1;i--){ cout<<a.back()<<""; a.pop_back(); } cout<<"\n"<<a.size(); return0;}三、使用范例#include<vector>6集合（set）单县第一中学2017级信息学奥林匹克竞赛知识选讲集合（set）单县第一中学2017级7一、定义set的特点是： 会对集合中的元素根据键值自动排序，而且不允许集合中有重复元素头文件：#include<set>set中的函数：声明：set<类型>名称

例如：set<int>s1;begin()返回指向第一个元素的迭代器end()返回指向最后一个元素的迭代器一、定义set的特点是：8二、迭代器关于迭代器：声明：set<类型>::iterator名称访问迭代器指向元素时使用

*名称需要注意的是： 迭代器只能自增，不能+1或者-1 或者其他操作迭代器的类型要与 定义的set类型相同二、迭代器关于迭代器：9三、使用常用的函数：begin()

返回set容器的第一个元素的地址end()返回set容器的最后一个元素地址clear()

删除set容器中的所有的元素empty()判断set容器是否为空max_size()

返回set容器可能包含的元素最大个数size()返回当前set容器中的元素个数erase(it)

删除迭代器指针it处元素三、使用常用的函数：10使用样例#include<iostream>#include<set>usingnamespacestd;intmain(){set<int>s;s.insert(1);s.insert(2);s.insert(3);s.insert(1);cout<<"set的size值为："<<s.size()<<endl;cout<<"set的maxsize的值为："<<s.max_size()<<endl;cout<<"set中的第一个元素是："<<*s.begin()<<endl;cout<<"set中的最后一个元素是:"<<*s.end()<<endl;s.clear();if(s.empty()){cout<<"set为空！！！"<<endl;}cout<<"set的size值为："<<s.size()<<endl;cout<<"set的maxsize的值为："<<s.max_size()<<endl;return0;}使用样例#include<iostream>11三、使用1.count()

:用来查找set中某个元素出现的次数。这个函数在set并不是很实用，因为一个键值在set只可能出现0或1次，这样就变成了判断某一键值是否在set出现过了。2.find():

用来查找set中某个元素出现的位置。如果找到，就返回这个元素的迭代器，如果这个元素不存在，则返s.end()。(最后一个元素的下一个位置，s为set的变量名)三、使用1.count()

:用来查找set中某个元素出现的12使用样例#include<iostream>#include<set>usingnamespacestd;intmain(){set<int>s;set<int>::iteratorit;//创建一个他对应的迭代器s.insert(1);s.insert(2);s.insert(3);s.insert(1);cout<<"set中1出现的次数是："<<s.count(1)<<endl;cout<<"set中4出现的次数是："<<s.count(4)<<endl;it1=st1.find(4);//查找数据if(it1!=st1.end())//如果找到就输出数据{cout<<*it1<<endl;}return0;}使用样例#include<iostream>13三、使用//遍历数据，用迭代器遍历数据 for(set<int>::iteratorit=s.begin();it!=s.end();++it { cout<<*it<<endl; }//这里用到了set中的元素已经从小到大排好序的性质三、使用//遍历数据，用迭代器遍历数据14使用样例#include<bits/stdc++.h>#include<set>usingnamespacestd;set<int>a;intmain(){ intb; for(inti=1;i<=10;i++){ cin>>b; a.insert(b); } for(set<int>::iteratori=a.begin();i!=a.end();i++){ cout<<*i<<endl; } return0;}使用样例#include<bits/stdc++.h>15三、使用（结构体）structInfo{stringname;doublescore;booloperator<(constInfo&a)const//重载“<”操作符，自定义排序规则{//按score由大到小排序。如果要由小到大排序，使用“>”即可。returna.score<score;}};intmain(){set<Info>s;Infoinfo;//插入三个元素="Jack";info.score=80;s.insert(info);="Tom";info.score=99;s.insert(info);="Steaven";info.score=60;s.insert(info);set<Info>::iteratorit;for(it=s.begin();it!=s.end();it++)cout<<(*it).name<<":"<<(*it).score<<endl;return0;}运行结果：Tom:99Jack:80Steaven:60三、使用（结构体）structInfo运行结果：16四、其他函数库删除函数erase();根据元素的值删除元素不能根据第几个元素进行删除插入元素：insert();clear()--清除所有元素

count()--返回某个值元素的个数

empty()--如果集合为空，返回true

equal_range()--返回集合中与给定值相等的上下限的两个迭代器

find()--返回一个指向被查找到元素的迭代器

get_allocator()--返回集合的分配器

lower_bound()--返回指向大于（或等于）某值的第一个元素的迭代器

key_comp()--返回一个用于元素间值比较的函数

max_size()--返回集合能容纳的元素的最大限值rbegin()--返回指向集合中最后一个元素的反向迭代器

rend()--返回指向集合中第一个元素的反向迭代器

size()--集合中元素的数目

swap()--交换两个集合变量

upper_bound()--返回大于某个值元素的迭代器

value_comp()--返回一个用于比较元素间的值的函数四、其他函数库删除函数erase();根据元素的值删除元素17映射（map）单县第一中学2017级信息学奥林匹克竞赛知识选讲映射（map）单县第一中学2017级18一、定义Map就是从键（key）到值（value）的映射。因为重载了[]运算符，map像是数组的高级版。头文件：#include<map>定义：例如：map<char,int>a//建立一个 char到int的映 射a一、定义Map就是从键（key）到值（value）的映射。因19使用样例#include<iostream>#include<map>usingnamespacestd;map<string,int>date;intmain(){date["7月30日"]=730;cout<<date["7月30日"];return0;}使用样例#include<iostream>20二、使用常用语句：begin（）返回map头部迭代器

end（）返回尾部迭代器

clear（）清空所有元素

erase（）删除一个元素

find（）查找一个元素

empty（）如果为空则返回true

size（）返回map大小

count（elem）返回某个元素个数二、使用常用语句：begin（）返回map头部迭代器21三、例题题目是这样的：给出一串数以及一个数字

C，要求计算出所有

A-B=C

的数对

的个数。（

注意：不同位置的数字一样的数对算不同的数对）

InputFormat第一行包括

2

个非负整数

N

和

C，中间用空格隔开。

第二行有

N

个整数，中间用空格隔开，作为要求处理的那串数。

OutputFormat输出一行，表示该串数中包含的所有满足

A-B=C

的数对的个数。

SampleInput

41

1123

SampleOutput

3

DataLimit对于

50%的数据，

N<=2000；

对于

100%的数据，

N<=200000。三、例题题目是这样的：给出一串数以及一个数字

C，要求计算出22例题分析咱们定义一个map桶：map<long,int>m;这个桶的用法（就是普通的桶的用法）：m[i]表示数字i出现的次数。如果我们用普通数组，那么根据题意，我们定义的数组的成员个数至少为2147483647，就是长整型的最大值。而map为什么不会超呢？因为map是映射，它那个中括号里的数字只是一个键（这说起来很复杂……）……唉，口头表达能力不行，简单了说吧，就是说map你没有定义过某个键，它就不会占用空间，当你去映射一个没有访问过的键时，它会自动返回0。等于是说map桶去除了所有的空桶所占的空间。那么这题中我们只会用到<=200000个桶。例题分析咱们定义一个map桶：23代码展示（缺少头文件）map<long,int>m;//咱们的map桶intn;longc,num[200005];intmain(){scanf("%d%ld",&n,&c);//n个数字，c是差值intans=0,i=n;while(i--){scanf("%d",&num[i]);m[num[i]]++;//装到桶里去~}i=n;if(c>0)//特判0while(i--)ans+=m[num[i]+c];elsewhile(i--)ans=ans+m[num[i]+c]-1;//当c为0时每个数字还得排掉自己呢~printf("%d",ans);return0;}代码展示（缺少头文件）map<long,int>m;//咱24三、例题（UVa156-反片语）输入一些单词，找出所有满足如下条件的单词：该单词不能通过字母重拍，得到输入文本中的另外一些单词。在判断是否满足条件时，字母不区分大小写，但在输出时应保留输入中的大小写，按字典序进行排序（所有大写字母在所有小写字母的前面）。Sampleinput：laddercametapesoonleaderacmeRIDEloneDreispeatScAlEorbeyeRidesdealerNotEderailLaCeSdrIednoeldireDiskmaceRobdries#Sampleoutput：DiskNotEderaildrIedeyeladdersoon三、例题（UVa156-反片语）输入一些单词，找出所有25试题分析整体思路：

1.写一个标准化函数（实现大写字母转换为小写（tolower（）函数），单词排序。注意使用const是为了不改变s的初值）

2.两个vector容器（words，ans），一个map容器（cnt）

words存储所有的单词

map存储标准化后对应单词以及出现次数的值，相当于一个表格。

words经过查表map，把对应的符合值给ans试题分析整体思路：

1.写一个标准化函数（实现大写字母转换为26代码无课后习题（map）代码无课后习题（map）27加法模板单县第一中学2017级信息学奥林匹克竞赛知识选讲加法模板单县第一中学2017级28代码展示#include<bits/stdc++.h>usingnamespacestd;template<typenamet>structpoint{ tx,y; point(tx=0,ty=0):x(x),y(y){};};template<typenamet>point<t>operator+(constpoint<t>&a,constpoint<t>&b){ returnpoint<t>(a.x+b.x,a.y+b.y);}template<typenamet>ostream&operator<<(ostream&out,constpoint<t>&p){ out<<"("<<p.x<<","<<p.y<<")"; returnout;}intmain(){ point<int>a(1,2),b(3,4); point<double>c(1.1,2.2),d(3.3,4.4); cout<<a+b<<""<<c+d<<"\n"; return0;}代码展示#include<bits/stdc++.h>29谢谢观看谢谢观看30不定数组（vector）单县第一中学2017级信息学奥林匹克竞赛知识选讲不定数组（vector）单县第一中学2017级31一、定义Vector是一个不定数组，其大小可根据需要随时变动，可定义为一维数组，或者二维数组，甚至多维。数据库为#include<vector>定义如下：1一维：vector<int>vec;//定义了一个名为vec 的一维数组2二维：vector<int>vec[10];//定义了一个第一 维为10，二维动态 的数组一、定义Vector是一个不定数组，其大小可根据需要随时变动32二、使用数组插入元素：vec.push_back(同类型量);作用是在vector的末尾插入新元素；2.insert()第一个参数为迭代器，作用为在迭代器前面插入新元素；3.assign(5,1)向vector中加入5个1，同时清除掉以前的元素。二、使用数组插入元素：33二、使用数组删除元素：1.pop_back()删除最后一个元素。2.erase（）删除指定位置元素。（其中的参数要是指针变量，比如begain(),end(),以及迭代器值），例如vec.erase(vec.begin()+2);删除第3个元素3.clear（）清除所有元素。4.empty（）判断该数组是否为空二、使用数组删除元素：34二、使用访问数组：1.front()访问第一个元素（第一个元素的值而不是地址！begin()相反）2.back()访问最后一个元素（最后一个元素的值而不是地址！end()相反）3.size()数组的元素个数二、使用访问数组：35三、使用范例#include<vector>#include<iostream>usingnamespacestd;intmain(){ vector<int>a; for(inti=1;i<=100;i++){ a.push_back(i); } cout<<a.size()<<"\n";

for(inti=a.size();i>=1;i--){ cout<<a.back()<<""; a.pop_back(); } cout<<"\n"<<a.size(); return0;}三、使用范例#include<vector>36集合（set）单县第一中学2017级信息学奥林匹克竞赛知识选讲集合（set）单县第一中学2017级37一、定义set的特点是： 会对集合中的元素根据键值自动排序，而且不允许集合中有重复元素头文件：#include<set>set中的函数：声明：set<类型>名称

例如：set<int>s1;begin()返回指向第一个元素的迭代器end()返回指向最后一个元素的迭代器一、定义set的特点是：38二、迭代器关于迭代器：声明：set<类型>::iterator名称访问迭代器指向元素时使用

*名称需要注意的是： 迭代器只能自增，不能+1或者-1 或者其他操作迭代器的类型要与 定义的set类型相同二、迭代器关于迭代器：39三、使用常用的函数：begin()

返回set容器的第一个元素的地址end()返回set容器的最后一个元素地址clear()

删除set容器中的所有的元素empty()判断set容器是否为空max_size()

返回set容器可能包含的元素最大个数size()返回当前set容器中的元素个数erase(it)

删除迭代器指针it处元素三、使用常用的函数：40使用样例#include<iostream>#include<set>usingnamespacestd;intmain(){set<int>s;s.insert(1);s.insert(2);s.insert(3);s.insert(1);cout<<"set的size值为："<<s.size()<<endl;cout<<"set的maxsize的值为："<<s.max_size()<<endl;cout<<"set中的第一个元素是："<<*s.begin()<<endl;cout<<"set中的最后一个元素是:"<<*s.end()<<endl;s.clear();if(s.empty()){cout<<"set为空！！！"<<endl;}cout<<"set的size值为："<<s.size()<<endl;cout<<"set的maxsize的值为："<<s.max_size()<<endl;return0;}使用样例#include<iostream>41三、使用1.count()

:用来查找set中某个元素出现的次数。这个函数在set并不是很实用，因为一个键值在set只可能出现0或1次，这样就变成了判断某一键值是否在set出现过了。2.find():

用来查找set中某个元素出现的位置。如果找到，就返回这个元素的迭代器，如果这个元素不存在，则返s.end()。(最后一个元素的下一个位置，s为set的变量名)三、使用1.count()

:用来查找set中某个元素出现的42使用样例#include<iostream>#include<set>usingnamespacestd;intmain(){set<int>s;set<int>::iteratorit;//创建一个他对应的迭代器s.insert(1);s.insert(2);s.insert(3);s.insert(1);cout<<"set中1出现的次数是："<<s.count(1)<<endl;cout<<"set中4出现的次数是："<<s.count(4)<<endl;it1=st1.find(4);//查找数据if(it1!=st1.end())//如果找到就输出数据{cout<<*it1<<endl;}return0;}使用样例#include<iostream>43三、使用//遍历数据，用迭代器遍历数据 for(set<int>::iteratorit=s.begin();it!=s.end();++it { cout<<*it<<endl; }//这里用到了set中的元素已经从小到大排好序的性质三、使用//遍历数据，用迭代器遍历数据44使用样例#include<bits/stdc++.h>#include<set>usingnamespacestd;set<int>a;intmain(){ intb; for(inti=1;i<=10;i++){ cin>>b; a.insert(b); } for(set<int>::iteratori=a.begin();i!=a.end();i++){ cout<<*i<<endl; } return0;}使用样例#include<bits/stdc++.h>45三、使用（结构体）structInfo{stringname;doublescore;booloperator<(constInfo&a)const//重载“<”操作符，自定义排序规则{//按score由大到小排序。如果要由小到大排序，使用“>”即可。returna.score<score;}};intmain(){set<Info>s;Infoinfo;//插入三个元素="Jack";info.score=80;s.insert(info);="Tom";info.score=99;s.insert(info);="Steaven";info.score=60;s.insert(info);set<Info>::iteratorit;for(it=s.begin();it!=s.end();it++)cout<<(*it).name<<":"<<(*it).score<<endl;return0;}运行结果：Tom:99Jack:80Steaven:60三、使用（结构体）structInfo运行结果：46四、其他函数库删除函数erase();根据元素的值删除元素不能根据第几个元素进行删除插入元素：insert();clear()--清除所有元素

count()--返回某个值元素的个数

empty()--如果集合为空，返回true

equal_range()--返回集合中与给定值相等的上下限的两个迭代器

find()--返回一个指向被查找到元素的迭代器

get_allocator()--返回集合的分配器

lower_bound()--返回指向大于（或等于）某值的第一个元素的迭代器

key_comp()--返回一个用于元素间值比较的函数

max_size()--返回集合能容纳的元素的最大限值rbegin()--返回指向集合中最后一个元素的反向迭代器

rend()--返回指向集合中第一个元素的反向迭代器

size()--集合中元素的数目

swap()--交换两个集合变量

upper_bound()--返回大于某个值元素的迭代器

value_comp()--返回一个用于比较元素间的值的函数四、其他函数库删除函数erase();根据元素的值删除元素47映射（map）单县第一中学2017级信息学奥林匹克竞赛知识选讲映射（map）单县第一中学2017级48一、定义Map就是从键（key）到值（value）的映射。因为重载了[]运算符，map像是数组的高级版。头文件：#include<map>定义：例如：map<char,int>a//建立一个 char到int的映 射a一、定义Map就是从键（key）到值（value）的映射。因49使用样例#include<iostream>#include<map>usingnamespacestd;map<string,int>date;intmain(){date["7月30日"]=730;cout<<date["7月30日"];return0;}使用样例#include<iostream>50二、使用常用语句：begin（）返回map头部迭代器

end（）返回尾部迭代器

clear（）清空所有元素

erase（）删除一个元素

find（）查找一个元素

empty（）如果为空则返回true

size（）返回map大小

count（elem）返回某个元素个数二、使用常用语句：begin（）返回map头部迭代器51三、例题题目是这样的：给出一串数以及一个数字

C，要求计算出所有

A-B=C

的数对

的个数。（

注意：不同位置的数字一样的数对算不同的数对）

InputFormat第一行包括

2

个非负整数

N

和

C，中间用空格隔开。

第二行有

N

个整数，中间用空格隔开，作为要求处理的那串数。

OutputFormat输出一行，表示该串数中包含的所有满足

A-B=C

的数对的个数。

SampleInput

41

1123

SampleOutput

3

DataLimit对于

50%的数据，

N<=2000；

对于

100%的数据，

N<=200000。三、例题题目是这样的：给出一串数以及一个数字

C，要求计算出52例题分析咱们定义一个map桶：map<long,int>m;这个桶的用法（就是普通的桶的用法）：m[i]表示数字i出现的次数。如果我们用普通数组，那么根据题意，我们定义的数组的成员个数至少为2147483647，就是长整型的最大值。而map为什么不会超呢？因为map是映射，它那个中括号里的数字只是一个键（这说起来很复杂……）……唉，口头表达能力不行，简单了说吧，就是说map你没有定义过某个键，它就不会占用空间，当你去映射一个没有访问过的键时，它会自动返回0。等于是说map桶去除了所有的空桶所占的空间。那么这题中我们只会用到<=200000个桶。例题分析咱们定义一个map桶：53代码展示（缺少头文件）map<long,int>m;//咱们的map桶intn;longc,num[200005];intmain(){scanf("%d%ld",&n,&c);//n个数字，c是差值intans=0,i=n;while(i--){scan