信息學奧賽STL數(shù)據(jù)類型簡介課件

不定數(shù)組（vector）單縣第一中學2017級信息學奧林匹克競賽知識選講不定數(shù)組（vector）單縣第一中學2017級1一、定義Vector是一個不定數(shù)組，其大小可根據(jù)需要隨時變動，可定義為一維數(shù)組，或者二維數(shù)組，甚至多維。數(shù)據(jù)庫為#include<vector>定義如下：1一維：vector<int>vec;//定義了一個名為vec 的一維數(shù)組2二維：vector<int>vec[10];//定義了一個第一 維為10，二維動態(tài) 的數(shù)組一、定義Vector是一個不定數(shù)組，其大小可根據(jù)需要隨時變動2二、使用數(shù)組插入元素：vec.push_back(同類型量);作用是在vector的末尾插入新元素；2.insert()第一個參數(shù)為迭代器，作用為在迭代器前面插入新元素；3.assign(5,1)向vector中加入5個1，同時清除掉以前的元素。二、使用數(shù)組插入元素：3二、使用數(shù)組刪除元素：1.pop_back()刪除最后一個元素。2.erase（）刪除指定位置元素。（其中的參數(shù)要是指針變量，比如begain(),end(),以及迭代器值），例如vec.erase(vec.begin()+2);刪除第3個元素3.clear（）清除所有元素。4.empty（）判斷該數(shù)組是否為空二、使用數(shù)組刪除元素：4二、使用訪問數(shù)組：1.front()訪問第一個元素（第一個元素的值而不是地址！begin()相反）2.back()訪問最后一個元素（最后一個元素的值而不是地址！end()相反）3.size()數(shù)組的元素個數(shù)二、使用訪問數(shù)組：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的特點是： 會對集合中的元素根據(jù)鍵值自動排序，而且不允許集合中有重復元素頭文件：#include<set>set中的函數(shù)：聲明：set<類型>名稱

例如：set<int>s1;begin()返回指向第一個元素的迭代器end()返回指向最后一個元素的迭代器一、定義set的特點是：8二、迭代器關于迭代器：聲明：set<類型>::iterator名稱訪問迭代器指向元素時使用

*名稱需要注意的是： 迭代器只能自增，不能+1或者-1 或者其他操作迭代器的類型要與 定義的set類型相同二、迭代器關于迭代器：9三、使用常用的函數(shù)：begin()

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

刪除set容器中的所有的元素empty()判斷set容器是否為空max_size()

返回set容器可能包含的元素最大個數(shù)size()返回當前set容器中的元素個數(shù)erase(it)

刪除迭代器指針it處元素三、使用常用的函數(shù)：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中某個元素出現(xiàn)的次數(shù)。這個函數(shù)在set并不是很實用，因為一個鍵值在set只可能出現(xiàn)0或1次，這樣就變成了判斷某一鍵值是否在set出現(xiàn)過了。2.find():

用來查找set中某個元素出現(xiàn)的位置。如果找到，就返回這個元素的迭代器，如果這個元素不存在，則返s.end()。(最后一個元素的下一個位置，s為set的變量名)三、使用1.count()

:用來查找set中某個元素出現(xiàn)的12使用樣例#include<iostream>#include<set>usingnamespacestd;intmain(){set<int>s;set<int>::iteratorit;//創(chuàng)建一個他對應的迭代器s.insert(1);s.insert(2);s.insert(3);s.insert(1);cout<<"set中1出現(xiàn)的次數(shù)是："<<s.count(1)<<endl;cout<<"set中4出現(xiàn)的次數(shù)是："<<s.count(4)<<endl;it1=st1.find(4);//查找數(shù)據(jù)if(it1!=st1.end())//如果找到就輸出數(shù)據(jù){cout<<*it1<<endl;}return0;}使用樣例#include<iostream>13三、使用//遍歷數(shù)據(jù)，用迭代器遍歷數(shù)據(jù) for(set<int>::iteratorit=s.begin();it!=s.end();++it { cout<<*it<<endl; }//這里用到了set中的元素已經從小到大排好序的性質三、使用//遍歷數(shù)據(jù)，用迭代器遍歷數(shù)據(jù)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//重載“<”操作符，自定義排序規(guī)則{//按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四、其他函數(shù)庫刪除函數(shù)erase();根據(jù)元素的值刪除元素不能根據(jù)第幾個元素進行刪除插入元素：insert();clear()--清除所有元素

count()--返回某個值元素的個數(shù)

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

equal_range()--返回集合中與給定值相等的上下限的兩個迭代器

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

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

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

key_comp()--返回一個用于元素間值比較的函數(shù)

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

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

size()--集合中元素的數(shù)目

swap()--交換兩個集合變量

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

value_comp()--返回一個用于比較元素間的值的函數(shù)四、其他函數(shù)庫刪除函數(shù)erase();根據(jù)元素的值刪除元素17映射（map）單縣第一中學2017級信息學奧林匹克競賽知識選講映射（map）單縣第一中學2017級18一、定義Map就是從鍵（key）到值（value）的映射。因為重載了[]運算符，map像是數(shù)組的高級版。頭文件：#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）返回某個元素個數(shù)二、使用常用語句：begin（）返回map頭部迭代器21三、例題題目是這樣的：給出一串數(shù)以及一個數(shù)字

C，要求計算出所有

A-B=C

的數(shù)對

的個數(shù)。（

注意：不同位置的數(shù)字一樣的數(shù)對算不同的數(shù)對）

InputFormat第一行包括

2

個非負整數(shù)

N

和

C，中間用空格隔開。

第二行有

N

個整數(shù)，中間用空格隔開，作為要求處理的那串數(shù)。

OutputFormat輸出一行，表示該串數(shù)中包含的所有滿足

A-B=C

的數(shù)對的個數(shù)。

SampleInput

41

1123

SampleOutput

3

DataLimit對于

50%的數(shù)據(jù)，

N<=2000；

對于

100%的數(shù)據(jù)，

N<=200000。三、例題題目是這樣的：給出一串數(shù)以及一個數(shù)字

C，要求計算出22例題分析咱們定義一個map桶：map<long,int>m;這個桶的用法（就是普通的桶的用法）：m[i]表示數(shù)字i出現(xiàn)的次數(shù)。如果我們用普通數(shù)組，那么根據(jù)題意，我們定義的數(shù)組的成員個數(shù)至少為2147483647，就是長整型的最大值。而map為什么不會超呢？因為map是映射，它那個中括號里的數(shù)字只是一個鍵（這說起來很復雜……）……唉，口頭表達能力不行，簡單了說吧，就是說map你沒有定義過某個鍵，它就不會占用空間，當你去映射一個沒有訪問過的鍵時，它會自動返回0。等于是說map桶去除了所有的空桶所占的空間。那么這題中我們只會用到<=200000個桶。例題分析咱們定義一個map桶：23代碼展示（缺少頭文件）map<long,int>m;//咱們的map桶intn;longc,num[200005];intmain(){scanf("%d%ld",&n,&c);//n個數(shù)字，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時每個數(shù)字還得排掉自己呢~printf("%d",ans);return0;}代碼展示（缺少頭文件）map<long,int>m;//咱24三、例題（UVa156-反片語）輸入一些單詞，找出所有滿足如下條件的單詞：該單詞不能通過字母重拍，得到輸入文本中的另外一些單詞。在判斷是否滿足條件時，字母不區(qū)分大小寫，但在輸出時應保留輸入中的大小寫，按字典序進行排序（所有大寫字母在所有小寫字母的前面）。Sampleinput：laddercametapesoonleaderacmeRIDEloneDreispeatScAlEorbeyeRidesdealerNotEderailLaCeSdrIednoeldireDiskmaceRobdries#Sampleoutput：DiskNotEderaildrIedeyeladdersoon三、例題（UVa156-反片語）輸入一些單詞，找出所有25試題分析整體思路：

1.寫一個標準化函數(shù)（實現(xiàn)大寫字母轉換為小寫（tolower（）函數(shù)），單詞排序。注意使用const是為了不改變s的初值）

2.兩個vector容器（words，ans），一個map容器（cnt）

words存儲所有的單詞

map存儲標準化后對應單詞以及出現(xiàn)次數(shù)的值，相當于一個表格。

words經過查表map，把對應的符合值給ans試題分析整體思路：

1.寫一個標準化函數(shù)（實現(xiàn)大寫字母轉換為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不定數(shù)組（vector）單縣第一中學2017級信息學奧林匹克競賽知識選講不定數(shù)組（vector）單縣第一中學2017級31一、定義Vector是一個不定數(shù)組，其大小可根據(jù)需要隨時變動，可定義為一維數(shù)組，或者二維數(shù)組，甚至多維。數(shù)據(jù)庫為#include<vector>定義如下：1一維：vector<int>vec;//定義了一個名為vec 的一維數(shù)組2二維：vector<int>vec[10];//定義了一個第一 維為10，二維動態(tài) 的數(shù)組一、定義Vector是一個不定數(shù)組，其大小可根據(jù)需要隨時變動32二、使用數(shù)組插入元素：vec.push_back(同類型量);作用是在vector的末尾插入新元素；2.insert()第一個參數(shù)為迭代器，作用為在迭代器前面插入新元素；3.assign(5,1)向vector中加入5個1，同時清除掉以前的元素。二、使用數(shù)組插入元素：33二、使用數(shù)組刪除元素：1.pop_back()刪除最后一個元素。2.erase（）刪除指定位置元素。（其中的參數(shù)要是指針變量，比如begain(),end(),以及迭代器值），例如vec.erase(vec.begin()+2);刪除第3個元素3.clear（）清除所有元素。4.empty（）判斷該數(shù)組是否為空二、使用數(shù)組刪除元素：34二、使用訪問數(shù)組：1.front()訪問第一個元素（第一個元素的值而不是地址！begin()相反）2.back()訪問最后一個元素（最后一個元素的值而不是地址！end()相反）3.size()數(shù)組的元素個數(shù)二、使用訪問數(shù)組：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的特點是： 會對集合中的元素根據(jù)鍵值自動排序，而且不允許集合中有重復元素頭文件：#include<set>set中的函數(shù)：聲明：set<類型>名稱

例如：set<int>s1;begin()返回指向第一個元素的迭代器end()返回指向最后一個元素的迭代器一、定義set的特點是：38二、迭代器關于迭代器：聲明：set<類型>::iterator名稱訪問迭代器指向元素時使用

*名稱需要注意的是： 迭代器只能自增，不能+1或者-1 或者其他操作迭代器的類型要與 定義的set類型相同二、迭代器關于迭代器：39三、使用常用的函數(shù)：begin()

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

刪除set容器中的所有的元素empty()判斷set容器是否為空max_size()

返回set容器可能包含的元素最大個數(shù)size()返回當前set容器中的元素個數(shù)erase(it)

刪除迭代器指針it處元素三、使用常用的函數(shù)：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中某個元素出現(xiàn)的次數(shù)。這個函數(shù)在set并不是很實用，因為一個鍵值在set只可能出現(xiàn)0或1次，這樣就變成了判斷某一鍵值是否在set出現(xiàn)過了。2.find():

用來查找set中某個元素出現(xiàn)的位置。如果找到，就返回這個元素的迭代器，如果這個元素不存在，則返s.end()。(最后一個元素的下一個位置，s為set的變量名)三、使用1.count()

:用來查找set中某個元素出現(xiàn)的42使用樣例#include<iostream>#include<set>usingnamespacestd;intmain(){set<int>s;set<int>::iteratorit;//創(chuàng)建一個他對應的迭代器s.insert(1);s.insert(2);s.insert(3);s.insert(1);cout<<"set中1出現(xiàn)的次數(shù)是："<<s.count(1)<<endl;cout<<"set中4出現(xiàn)的次數(shù)是："<<s.count(4)<<endl;it1=st1.find(4);//查找數(shù)據(jù)if(it1!=st1.end())//如果找到就輸出數(shù)據(jù){cout<<*it1<<endl;}return0;}使用樣例#include<iostream>43三、使用//遍歷數(shù)據(jù)，用迭代器遍歷數(shù)據(jù) for(set<int>::iteratorit=s.begin();it!=s.end();++it { cout<<*it<<endl; }//這里用到了set中的元素已經從小到大排好序的性質三、使用//遍歷數(shù)據(jù)，用迭代器遍歷數(shù)據(jù)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//重載“<”操作符，自定義排序規(guī)則{//按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四、其他函數(shù)庫刪除函數(shù)erase();根據(jù)元素的值刪除元素不能根據(jù)第幾個元素進行刪除插入元素：insert();clear()--清除所有元素

count()--返回某個值元素的個數(shù)

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

equal_range()--返回集合中與給定值相等的上下限的兩個迭代器

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

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

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

key_comp()--返回一個用于元素間值比較的函數(shù)

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

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

size()--集合中元素的數(shù)目

swap()--交換兩個集合變量

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

value_comp()--返回一個用于比較元素間的值的函數(shù)四、其他函數(shù)庫刪除函數(shù)erase();根據(jù)元素的值刪除元素47映射（map）單縣第一中學2017級信息學奧林匹克競賽知識選講映射（map）單縣第一中學2017級48一、定義Map就是從鍵（key）到值（value）的映射。因為重載了[]運算符，map像是數(shù)組的高級版。頭文件：#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）返回某個元素個數(shù)二、使用常用語句：begin（）返回map頭部迭代器51三、例題題目是這樣的：給出一串數(shù)以及一個數(shù)字

C，要求計算出所有

A-B=C

的數(shù)對

的個數(shù)。（

注意：不同位置的數(shù)字一樣的數(shù)對算不同的數(shù)對）

InputFormat第一行包括

2

個非負整數(shù)

N

和

C，中間用空格隔開。

第二行有

N

個整數(shù)，中間用空格隔開，作為要求處理的那串數(shù)。

OutputFormat輸出一行，表示該串數(shù)中包含的所有滿足

A-B=C

的數(shù)對的個數(shù)。

SampleInput

41

1123

SampleOutput

3

DataLimit對于

50%的數(shù)據(jù)，

N<=2000；

對于

100%的數(shù)據(jù)，

N<=200000。三、例題題目是這樣的：給出一串數(shù)以及一個數(shù)字

C，要求計算出52例題分析咱們定義一個map桶：map<long,int>m;這個桶的用法（就是普通的桶的用法）：m[i]表示數(shù)字i出現(xiàn)的次數(shù)。如果我們用普通數(shù)組，那么根據(jù)題意，我們定義的數(shù)組的成員個數(shù)至少為2147483647，就是長整型的最大值。而map為什么不會超呢？因為map是映射，它那個中括號里的數(shù)字只是一個鍵（這說起來很復雜……）……唉，口頭表達能力不行，簡單了說吧，就是說map你沒有定義過某個鍵，它就不會占用空間，當你去映射一個沒有訪問過的鍵時，它會自動返回0。等于是說map桶去除了所有的空桶所占的空間。那么這題中我們只會用到<=200000個桶。例題分析咱們定義一個map桶：53代碼展示（缺少頭文件）map<long,int>m;//咱們的map桶intn;longc,num[200005];intmain(){scanf("%d%ld",&n,&c);//n個數(shù)字，c是差值intans=0,i=n;while(i--){scan