# 【5-4】排序關聯式容器 — map & multimap
`map` 和 `set` 很像，都是 STL 中會**自動排序**、**快速查找**的容器，但在儲存方式上有明顯不同。
`set` 是單純地儲存「元素本身」，而 `map` 則是用**鍵值對**（key-value pair）來儲存資料：**每個鍵（key）對應一個值（value）**。
這樣的概念，其實和我們熟悉的「**陣列**」很像——你可以把 key 想成「index」，value 就是「對應的值」。
但 `map` 比陣列強大多了，它的優勢包括：
* **key 不一定要是數字**
* **不必照順序編號**
* **自動排序 key**
* **查找、插入都很快**
可以說是「**Pro Max 版的陣列**」。
另外，由於 `map` 的每一筆資料都是「鍵值對」，在底層實作上，其實就是使用 `pair`（忘記可以複習 [【3-4】動態陣列 — vector](https://hackmd.io/@LAfWxjSxRASps-4O_bppsA/SknbSSzSxl)），也就是 `pair<key, value>` 的形式，這點我們在遍歷時會更清楚看到。
## map
`map` 是 STL 中一個用來儲存鍵值對（key-value pair）的容器，具有以下特性：
* 鍵（`key`）不重複，每個鍵對應一個值（`value`）
* 鍵自動排序（默認按鍵由小到大排序）
* 搜尋效率高（底層邏輯基於紅黑樹）
### 複雜度分析
| 操作 | 時間複雜度 | 空間複雜度 |
| -- | ------------- | -------- |
| 插入 | $O(\log n)$ | $O(n)$ |
| 刪除 | $O(\log n)$ | $O(n)$ |
| 查找 | $O(\log n)$ | $O(n)$ |
### 宣告
```cpp
map<int, string> m; // 宣告一個名稱為 m，存放「整數」鍵對應「字串」值的 map
map<int, string> m2 = {{1, "apple"}, {2, "banana"}, {3, "cherry"}}; // 初始化
```
### 插入資料
```cpp
m.insert({key, value}); // 插入一個鍵值對 (key, value) 到 map 中
m[key] = value; // 也可以用這種方式來插入鍵值對
m.at(key); // 用這種方法，若 key 不存在會報錯
```
* 若 `key` 已存在，`insert` 不會更新值，`[]` 則會覆蓋原本的值。
### 刪除資料
```cpp
m.erase(key); // 刪除指定 key 的元素
m.erase(iterator); // 刪除 iterator 所指位置的元素
m.clear(); // 清空 map
```
### 其他操作
```cpp
m.count(key); // 若 key 存在回傳 1，否則回傳 0
m.size(); // 回傳整數，表示 map 的大小
m.empty(); // 回傳布林值，若 map 為空則返回 true，否則返回 false
iterator->first // 取得 value 對應的 key
iterator->second // 取得 key 對應的 value
```
### 遍歷整個 map
忘記的話去複習[【3-5】指標](https://hackmd.io/@LAfWxjSxRASps-4O_bppsA/rJPSm8fSex)、[【3-6】迭代器](https://hackmd.io/@LAfWxjSxRASps-4O_bppsA/S16spNGrxg)
```cpp=1
for (auto p : m) {
p.first; // key
p.second; // value
}
for (auto it = m.begin(); it != m.end(); ++it) {
it->first; // key
it->second; // value
}
```
### Python對照
Python 的 `map` 沒有排序，相當於 C++ 中的 `unordered_map`，會在[【5-5】非排序關聯式容器 — unordered_set & unordered_map](https://hackmd.io/@LAfWxjSxRASps-4O_bppsA/rkIlEGcSel) 介紹。
```python
# 宣告
m = dict()
m2 = {1: "apple", 2: "banana", 3: "cherry"}
# 插入資料
m[key] = value # 插入或更新 key 對應的值
m.setdefault(key, value) # 若 key 不存在才插入，否則不變
# 存取資料
val = m[key] # 直接存取（若 key 不存在會報錯）
val = m.get(key) # 安全存取（key 不存在回傳 None）
# 刪除資料
m.pop(key, None) # 刪除指定 key，若不存在不報錯
del m[key] # 刪除指定 key，若不存在會報錯
m.clear() # 清空整個 dict
# 其他操作
key in m # 判斷 key 是否存在（類似 count）
len(m) # 回傳大小
not m # 判斷是否為空
# 遍歷
for k, v in m.items():
print(k, v) # k 相當於 key, v 相當於 value
# 排序
sorted_items = sorted(m.items()) # 依 key 排序（回傳 list of pair）
sorted_by_value = sorted(m.items(), key=lambda x: x[1]) # 依 value 排序
```
---
## multimap
`multimap` 和 `map` 類似，不同點在於
* 鍵可以重複
* 自動排序（根據 key）
### 複雜度分析
| 操作 | 時間複雜度 | 空間複雜度 |
| -- | ------------- | -------- |
| 插入 | $O(\log n)$ | $O(n)$ |
| 刪除 | $O(\log n)$ | $O(n)$ |
| 查找 | $O(\log n)$ | $O(n)$ |
### 宣告
```cpp=1
multimap<int, string> mm; // 宣告一個名稱為 mm，存放「整數」鍵對應「字串」值的 multimap
multimap<int, string> mm2 = {{1, "apple"}, {1, "banana"}, {2, "cherry"}}; // 初始化
```
### 插入資料
```cpp
mm.insert({key, value}); // 插入一個鍵值對 (key, value) 到 multimap 中
```
### 刪除資料
```cpp
mm.erase(key); // 刪除所有該 key 的元素
mm.erase(iterator); // 刪除指定位置
mm.clear(); // 清空 multimap
```
### 其他操作
```cpp
mm.count(key); // 回傳該 key 出現的次數
mm.size(); // 回傳整體鍵值對數量（含重複）
mm.empty(); // 若 multimap 為空則回傳 true
iterator->first // 取得 value 對應的 key
iterator->second // 取得 key 對應的 value
```
### 遍歷
忘記的話去複習[【3-5】指標](https://hackmd.io/@LAfWxjSxRASps-4O_bppsA/rJPSm8fSex)、[【3-6】迭代器](https://hackmd.io/@LAfWxjSxRASps-4O_bppsA/S16spNGrxg)
```cpp=1
for (auto p : mm) {
p.first; // key
p.second; // value
}
for (auto it = mm.begin(); it != mm.end(); ++it) {
it->first; // key
it->second; // value
}
```
### Python對照
Python 本身沒有 `multimap`，但可以用 `defaultdict(list)` 模擬：
```python
from collections import defaultdict
# 宣告
mm = defaultdict(list)
mm2 = defaultdict(list, {1: ["apple", "banana"], 2: ["cherry"]})
# 插入資料
mm[key].append(value) # 插入一筆鍵值對（允許重複 key）
# 刪除資料
del mm[key] # 刪除該 key 對應的所有值
mm.clear() # 清空 multimap
# 其他操作
len(mm[key]) # 回傳該 key 對應的數量（等同 mm.count(key)）
sum(len(v) for v in mm.values()) # 所有鍵值對總數（含重複）
not mm # 判斷是否為空
# 遍歷
for key, values in mm.items():
for value in values:
key # 等同 iterator->first
value # 等同 iterator->second
```
---
聯絡方式：[codecodefunny@gmail.com](mailto:codecodefunny@gmail.com)
最後編修時間：2025/07/12 子柚筆
Sign in with Wallet
Connect another wallet