STL list，STL整理之map

轉載請注明出處，部分內容引自李煜東《算法競賽進階指南》
?

---

前置知識：?? ?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));