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