轉載請注明出處,部分內容引自李煜東《算法競賽進階指南》
?
前置知識:?? ?C++、C語言入門
STL list。
Map是什么
Map是從鍵(key)到值(value)的映射,其內部實現是一棵以key為關鍵碼的紅黑樹
Map的相關操作
STLset和map的區別。
頭文件
?
#include<map>
聲明:
像這樣:
map<key的類型,value的類型>名稱;
比如:
map<long long,bool>mp;
map<string,int>mp;
map<pair<int,int>,vector<int>>mp;
就像其他需要排序的數據類型一樣,key為一個結構體的map,需要重載小于號
struct pos{int x,y,s;string move[100];
};
map<pos,int>mp;
bool operator <(const pos &ai,const pos &bi)
{return (ai.x==bi.x)?ai.y>bi.y:ai.x>bi.x;
}
[]運算符
map重載了[]運算符,map[key]返回key到value的引用,時間復雜度O(log n)
[]操作符是map最吸引人的地方。我們可以很方便地通過map[key]來得到key對應的value,還可以對map[key]進行賦值操作,改變key對應的value。
若查找的key不存在,則執行map[key]后,map會自動新建一個二元組(key,zero),并返回zero的引用。
eg.
map<string,int>mp;
for(int i=1;i<=n;i++)
{string s;int num;cin>>s>>num;mp[s]=num;
}
for(int i=1;i<=m;i++)
{string s;cin>>s;cout<<mp[s]<<endl;
}
map.size()
統計map中元素個數,函數返回一個整形變量,表示map中元素個數,時間復雜度O(1)
用法:名稱.size();
eg.
int num=mp.size();
map.empty()
檢查map是否為空,返回一個bool型變量,1表示map為空,否則為非空,時間復雜度O(1)
用法:名稱.empty();
eg.
if(mp.empty())cout<<"Mymap is Empty."<<endl;
map.clear()
清空map,無返回值
用法:名稱.clear();
eg.
mp.clear();
map.count(x)
返回map中key為x的元素個數,時間復雜度為O(log n)
用法:名稱.count(x)
eg.
if(!mp.count(x))mp[x]=1;
迭代器
雙向訪問迭代器,不支持隨機訪問,支持星號解除引用,僅支持“++”,“--”這兩個算術操作
引用和操作:
map<類型,類型>::iterator it;
eg.
map<int,int>::iterator it=mp.begin();
it++;
it--;
若把it++,則it將會指向“下一個”元素。這里的下一個是指在key從小到大排序的結果中,排在it下一名的元素。同理,若把it--,則it會指向排在上一個的元素
“++”,“--”操作的復雜度均為O(log n)
對map的迭代器解除引用后,將得到一個二元組pair<...,...>
遍歷map及訪問其中的元素
for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++)if(it->second==ans) //訪問二元組中第二個,即valuecout<<it->first<<endl; //訪問key
map.find(x)
在map中查找key為x的二元組,并返回指向該二元組的迭代器,若不存在,返回map.end(),時間復雜度為O(log n)
用法:名稱.find(x);
eg.
if(mp.find(s)!=mp.end())cout<<"Have Found!"<<endl;
map.insert(pair<...,...>)
在map中插入,參數是pair<key.type,value.type>,返回插入地址的迭代器和是否插入成功的bool并成的pair,時間復雜度為O(log n)
PS:insert在進行插入的時候是不允許有重復的鍵值的,如果新插入的鍵值與原有的鍵值重復則插入無效
用法:名稱.insert(pair<key的類型,value的類型>);
eg.
mp.insert(make_pair(2,3));
map.erase(參數)
刪除,參數可以是pair或者迭代器,返回下一個元素的迭代器,時間復雜度為O(log n)
用法:名稱.erase(參數);
eg.
map<int,int>::iterator it=mp.begin();
mp.erase(it);
mp.erase(make_pair(2,3));