---
# System prepended metadata

title: 【5-5】非排序關聯式容器 — unordered_set & unordered_map

---

# 【5-5】非排序關聯式容器 — unordered_set & unordered_map

在前面的小節[【5-3】關聯式容器 — set & multiset](https://hackmd.io/@LAfWxjSxRASps-4O_bppsA/H1gKXwPHgg)、[【5-4】關聯式容器 — map & multimap](https://hackmd.io/@LAfWxjSxRASps-4O_bppsA/ryw3txFSxl)，我們學到了排序關聯式容器（`set`、`multiset`、`map`、`multimap`），但如果不需要排序，只在意快速插入、刪除、查找，就可以考慮**非排序關聯式容器**。底層採用哈希表（Hash Table）實作，平均情況下能提供 \$O(1)\$ 的操作效率。

## unordered_set

`unordered_set` 是用來儲存單一元素的容器，特性如下：

* 元素**不重複**
* **不保證順序**（根據哈希函式分佈）
* 多數情況下存取效率比 `set` 快

### 複雜度分析

| 操作 | 平均時間複雜度  | 最差時間複雜度  | 空間複雜度    |
| -- | -------- | -------- | -------- |
| 插入 | $O(1)$ | $O(n)$ | $O(n)$ |
| 刪除 | $O(1)$ | $O(n)$ | $O(n)$ |
| 查找 | $O(1)$ | $O(n)$ | $O(n)$ |

### 宣告

```cpp
unordered_set<int> us;              // 宣告一個存放整數的 unordered_set
unordered_set<int> us2 = {5, 3, 1}; // 初始化列表
```

### 插入資料

```cpp
us.insert(x);    // 插入元素 x，若已存在則跳過
```

### 刪除資料

```cpp
us.erase(x);     // 刪除所有值為 x 的元素
us.clear();      // 清空整個 unordered_set
```

### 其他操作

```cpp
us.size();       // 返回元素個數
us.empty();      // 判斷是否為空
us.count(x);     // 返回 x 在集合中的數量（0 或 1）
```
### Python對照
詳見[【5-3】關聯式容器 — set & multiset](https://hackmd.io/@LAfWxjSxRASps-4O_bppsA/H1gKXwPHgg)

---

## unordered_map

`unordered_map` 是用來儲存鍵-值對的容器，特性如下：

* **鍵（key）不重複**，可對應一個值（value）
* **不保證鍵的順序**
* 多數情況下存取效率比 `map` 快

### 複雜度分析

| 操作 | 平均時間複雜度  | 最差時間複雜度  | 空間複雜度    |
| -- | -------- | -------- | -------- |
| 插入 | $O(1)$ | $O(n)$ | $O(n)$ |
| 刪除 | $O(1)$ | $O(n)$ | $O(n)$ |
| 查找 | $O(1)$ | $O(n)$ | $O(n)$ |

### 宣告

```cpp
unordered_map<int, string> um;   // 宣告一個名稱為 um，存放「整數」鍵對應「字串」值的 unordered_map
unordered_map<int, string> um2 = {{1, "one"}, {2, "two"}}; // 初始化列表
```

### 插入與存取

```cpp
um.insert({key, value});   // 插入 (key, value)，若 key 已存在則不更新
um[key] = value;           // 插入或更新 key 對應的 value
um.at(key);                // 使用 at，若 key 不存在會報錯
```

### 刪除資料

```cpp
um.erase(key);            // 刪除指定 key 的元素
um.clear();               // 清空整個 unordered_map
```

### 其他常用操作

```cpp
um.size();                // 返回鍵值對數量
um.empty();               // 判斷是否為空
um.count(key);            // 返回 key 是否存在（0 或 1）
```
### Python對照
詳見 [【5-4】關聯式容器 — map & multimap](https://hackmd.io/@LAfWxjSxRASps-4O_bppsA/ryw3txFSxl)

---

聯絡方式：[codecodefunny@gmail.com](mailto:codecodefunny@gmail.com)
最後編修時間：2025/07/12 子柚筆
