map翻譯為映射，是STL中的常用容器。其實(shí)，數(shù)組就是一種映射，比如：int a[100]；就是定義了一個(gè)int到int的映射。而a[5]=25;就是把5映射到25。數(shù)組總是將int類型映射到其它基本類型（稱為數(shù)組的基類型），這同時(shí)也帶來(lái)了一個(gè)問(wèn)題，有時(shí)候我們希望把string映射成一個(gè)int，數(shù)組就不方便了。這時(shí)就可以使用map，map可以將任何基本類型（包括STL容器）映射到任何基本類型（包括STL容器）。

要使用map，必須先添加map頭文件，即#include ，同時(shí)必須要有“using namespace std”。
定義一個(gè)map的方法為：map<typename1,typename2> name;
其中，typename1是映射前的類型（鍵key），typename2是映射后的類型（值value），name為映射的名字。
普通int數(shù)組a就是map<int,int> a。而**如果是字符串到整型的映射，就必須使用string，而不能使用char，即map<string,int> a。**map的鍵和值也可以是STL容器，比如：map<set,string> mp。當(dāng)然，map的鍵和值都是唯一的。

訪問(wèn) map 的元素有兩種方式，一種是通過(guò)下標(biāo)訪問(wèn)；另一種是通過(guò)迭代器訪問(wèn)。
通過(guò)下標(biāo)訪問(wèn)就像普通的數(shù)組元素訪問(wèn)，例如先定義map<char,int> mp，然后就可以通過(guò)mp[‘c’]的方式來(lái)訪問(wèn)它對(duì)應(yīng)的元素，如mp[‘c’]=124。
通過(guò)迭代器訪問(wèn)，先作如下定義：
map<typename1,typename2>::iterator it；
因?yàn)閙ap的每一對(duì)映射都有兩個(gè)typename，所以，我們使用“it->first”來(lái)訪問(wèn)鍵，而使用“it->second”來(lái)訪問(wèn)值。

map常用函數(shù)：
（1）find()和 size()
find(key)是返回鍵為 key 的映射的迭代器，時(shí)間復(fù)雜度為 0(log 2 n)，n 為 map 中映射的對(duì)數(shù)。size()用來(lái)獲得map中映射的對(duì)數(shù)，時(shí)間復(fù)雜度為O(1)。
（2）clear()
clear()用來(lái)清空 map，時(shí)間復(fù)雜度為 0(n)。
（3）erase()
erase()可以刪除單個(gè)元素，也可以刪除一個(gè)區(qū)間內(nèi)的所有元素。
刪除單個(gè)元素可以用：erase(it)，it為要?jiǎng)h除的元素的迭代器，時(shí)間復(fù)雜度為O(1)。
也可以用：erase(key)，key為要?jiǎng)h除的映射的鍵，時(shí)間復(fù)雜度為O(log2n)。
刪除一個(gè)區(qū)間內(nèi)的所有元素用：erase(first，last)，first為區(qū)間的起始迭代器，last為區(qū)間的末尾迭代器的下一個(gè)地址，也就是左閉右開的區(qū)間[first,last)，時(shí)間復(fù)雜度為O(last-first)。

保齡球-map

map的key存得是保齡球數(shù)，value存得是位置
注意這里輸出不能用cout，會(huì)超時(shí)

#include <bits/stdc++.h> using namespace std; map<int,int>vis; int n,q,m,p; int main() {ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++){cin>>p;vis[p]=i;}cin>>q;while(q--){cin>>m;if(vis[m])printf("%d\n",vis[m]);elseprintf("0\n");}return 0; }

查字典

模板題

#include <bits/stdc++.h> using namespace std; map<string,int>vis; string name; int p,m,n; int main() {cin>>n;for(int i=1;i<=n;i++){cin>>name;cin>>vis[name];}cin>>m;for(int i=1;i<=m;i++){cin>>name;cout<<vis[name]<<endl;}return 0;

眼紅的Medusa

這題有意思，一開始一直不知道錯(cuò)哪里了，結(jié)果再一看題目，要求按前者的順序輸出hhh。。。。。。

#include <bits/stdc++.h> using namespace std; map<int,int>vis; int x,m,n,a[100005],b[100005];//a存第一個(gè)獎(jiǎng)項(xiàng)的得主編號(hào)，b存兩個(gè)獎(jiǎng)項(xiàng)的得主編號(hào)，x輸入第二個(gè)獎(jiǎng)項(xiàng)的得主編號(hào) int main() {cin>>n>>m;int cnt=0;for(int i=1;i<=n;i++){cin>>a[i];//第一個(gè)獎(jiǎng)項(xiàng)得主先不用放map里}for(int i=1;i<=m;i++){cin>>x;vis[x]++;//先放第二個(gè)獎(jiǎng)項(xiàng)的得主}for(int i=1;i<=n;i++){if(vis[a[i]])//在這里判斷是否是兩個(gè)獎(jiǎng)項(xiàng)得主b[++cnt]=a[i];}for(int i=1;i<=cnt;i++){i==cnt?cout<<b[i]:cout<<b[i]<<" ";}return 0; }

指數(shù)序列

萬(wàn)惡的二進(jìn)制，一到了這種題，我腦子就不夠用。。。。。。

一個(gè)由 n 個(gè)非負(fù)整數(shù)組成的序列 a1 ，a2 ，…，an 。這個(gè)序列保證單調(diào)不降。
另一個(gè)序列 2^a1 ，2^a2 ，…，2^an，最少要在這個(gè)序列中添加多少個(gè)形式為 2^x 的數(shù)（x 為非負(fù)整數(shù)），才能使這個(gè)序列所有整數(shù)的和為 2^v-1 ，其中 v 為某個(gè)非負(fù)整數(shù)。
思考到用二進(jìn)制的思想（不然都是2的冪次是干嘛的。。。。。。）
只有當(dāng)二進(jìn)制的每一位都是1的時(shí)候才滿足題意，有幾個(gè)0，就加上幾個(gè)數(shù)，這就是最少的，因此題目的意思就是要找二進(jìn)制有幾位是0，考慮到題目的數(shù)范圍很大，因此不能用數(shù)組，要用map，而且要注意，正因?yàn)樾蛄惺遣唤档?#xff0c;所以需要進(jìn)位，有兩個(gè)相同的就要進(jìn)一位！
但是還不能直接找0的個(gè)數(shù)，因?yàn)?序列是單調(diào)不降的，所以map的第一個(gè)必定是第一個(gè)寫入的數(shù)，這個(gè)數(shù)可能不是0，比如說(shuō)第一個(gè)數(shù)是3，那么后續(xù)的數(shù)都是>=3的，所以其實(shí)隱藏了第一位，第二位也是0，但是現(xiàn)在直接在map找0，是找不到這兩個(gè)的，所以要找有多少個(gè)1，再找一共有多少位，（這里應(yīng)該是map里的最高位+1，因?yàn)檫€有第一位（自己理解一下就能明白）），他們的差就是結(jié)果了！

#include <bits/stdc++.h> using namespace std; typedef long long ll; map<ll,int>vis; int n,x; int main() {cin>>n;int cnt=0,maxn=0;while(n--){cin>>x;vis[x]++;if(vis[x]==2){ll i=x;while(vis[i]==2)//進(jìn)位{vis[i]-=2;vis[i+1]++;i++;}}}map<ll,int>::iterator it;for(it=vis.begin();it!=vis.end();it++){if(it->second!=0){cnt++;//記錄1的個(gè)數(shù)if(it->first>maxn)//記錄最高位maxn=it->first;}}cout<<maxn+1-cnt<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的2020年OJ习题【map】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。