---
# System prepended metadata

title: 【5-4】排序關聯式容器 — map & multimap

---

# 【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 子柚筆

