0%

0-21 map

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 已存在,會輸出索引所對應的值。如果索引不存在,則會先新增一個值為預設值的索引,再將其輸出。

刪除:

1
mp.erase(5);

與 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';
}

輸出結果:

1
2
0 0
5 45

遍歷時,會照著 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
// TOJ 55
#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
// ZJ d518
#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';
}
}
}