map 是什麼？
之前我們在陣列章節時，介紹了這樣一個語法：
1
2
| a[5] = 1;
cout << a[5] << '\n';
|
這個的意思，是將 a 的第五項改變為 1，並將其輸出。當我們執行時，程式就去找： a 的第五項是什麼？再從索引(5)對到值(1)，這是一種一對一的對應關係。
但是，能作為索引的東西，一定只有整數嗎？或者更進一步說，只有從 0 開始到陣列大小 - 1 嗎？能不能自訂？
是可以的，map 在做的，就是這件事情。map 能夠將一個鍵(key)，對應到一個值(value)。
假設今天，我們想查詢一本書的資料，於是輸入了書名，我希望書的作者、出版社等等資訊就出現在眼前。在 C++ 裡，可以這樣寫：
1
2
3
4
| map<string, string> author, publisher;
author["Le Petit Prince"] = "Antoine de Saint-Exupéry";
publisher["Le Petit Prince"] = "Gallimard";
cout << author["Le Petit Prince"] << " " << publisher["Le Petit Prince"] << '\n';
|
將書名作為 key，對應到一個作者與一個出版社。
map 的語法
新增與指派：
1
2
| map<int, int> mp;
mp[5] = 45;
|
如果 key 不存在，則這是一個新增操作。如果 key 已存在，則是會將原來的值改掉，為一個指派操作。
查詢：
1
2
| cout << mp[5] << '\n';
cout << mp[0] << '\n';
|
如果 key 已存在，會輸出索引所對應的值。如果索引不存在，則會先新增一個值為預設值的索引，再將其輸出。
刪除：
與 set 相同。
遍歷：
1
2
3
4
5
6
| map<int, int> mp;
mp[5] = 45;
cout << mp[0] << '\n';
for(auto i:mp){
cout << i.first << " " << i.second << '\n';
}
|
輸出結果：
遍歷時，會照著 key 大小由小到大輸出，型態是一個 pair，first 是 key，second 是 value。
map 的底層結構
與 set 一樣使用紅黑樹實作，插入、查詢、刪除的複雜度均為$O(log N)$，其中 N 是 map 的大小。
key 不需要排序？
跟 set 一樣，在前面加上 unordered，實作方式改為 hash，失去照順序功能，但插入、查詢、刪除的複雜度降為 $O(1)$。
練習
TOJ 55
ZJ d518
AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
#include<bits/stdc++.h>
using namespace std;
unordered_map<int, int> mp;
int n, q;
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for(int i=1,x;i<=n;i++) cin >> x, mp[x]++;
cin >> q;
for(int i=1,x;i<=q;i++) cin >> x, cout << mp[x] << '\n';
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include<bits/stdc++.h>
using namespace std;
unordered_map<string, int> mp;
string str;
int n, id;
int main(){
ios::sync_with_stdio(0), cin.tie(0);
while(cin>>n){
mp.clear();
id = 0;
for(int i=1;i<=n;i++){
cin >> str;
if(!mp[str]) cout << "New! ", mp[str] = ++id;
else cout << "Old! ";
cout << mp[str] << '\n';
}
}
}
|