# 【5-3】排序關聯式容器 — set & multiset
在 [【5-2】排序演算法 & sort](https://hackmd.io/@LAfWxjSxRASps-4O_bppsA/Byv_lBUHel) 我們學到了排序資料的方法，但每次都宣告一個陣列，再用 `sort()`，一來效率極差，二來這是一次性的排序，排序後如果再插入新的資料，並不會自動排序，導致必須再用一次 `sort()`。
舉例原先資料排序如下：
```
5 3 1 2 4
```
經過 `sort()` 排序後：
```
1 2 3 4 5
```
再插入三筆資料：
```
1 2 3 4 5 8 6 7
```
這時候就要再用一次 `sort()`：
```
1 2 3 4 5 6 7 8
```
但別忘了，`sort()` 的時間複雜度是 $O(n\log n)$，一直用可能會吃 TLE！
---
## set
`set` 是 STL 中一個用來儲存元素的容器，具有以下特性：
* 元素**不重複**
* 自動**排序**（從小到大）
* **搜尋效率高**（底層為紅黑樹）
### 複雜度分析
| 操作 | 時間複雜度 | 空間複雜度 |
| --------- | ------------- | -------- |
| 插入 | $O(\log n)$ | $O(n)$ |
| 刪除 | $O(\log n)$ | $O(n)$ |
| 查找 | $O(\log n)$ | $O(n)$ |
### 宣告
```cpp
set<int> s; // 宣告一個名稱為 a，存放整數的 set
set<int> s2 = {10, 20, 30, 40, 50}; // 初始化列表
```
### 插入資料
```cpp
s.insert(num); // 插入 num 到 set 中，自動排序，不會重複
```
### 刪除資料
```cpp
s.erase(sum); // 將 sum 從 set 中刪除
s.erase(iterator); // 刪除 iterator 所指位置的元素
s.clear(); // 清空 set
```
### 其他操作
```cpp
s.size(); // 回傳 set 的大小（整數）
s.empty(); // 若為空回傳 true，否則 false
```
### Python對照
Python 的 `set` 沒有排序，相當於 C++ 中的 `unordered_set`，會在[【5-5】非排序關聯式容器 — unordered_set & unordered_map](https://hackmd.io/@LAfWxjSxRASps-4O_bppsA/rkIlEGcSel) 介紹。
```python
# 宣告
s = set()
s2 = {10, 20, 30, 40, 50}
# 插入資料
s.add(num) # 插入 num（實際上是無序集合，但可轉成 list 再排序），不會重複
# 刪除資料
s.discard(sum) # 若 sum 存在就刪掉，不報錯
s.clear() # 清空 set
# 其他操作
len(s) # 回傳 set 的大小
not s # 判斷是否為空，空集合為 True
# 排序
sorted_list = sorted(s) # 轉成 list 再排序
```
## multiset
`multiset` 和 `set` 類似，不同點在於：
* **允許重複元素**
* 自動排序（從小到大）
### 複雜度分析
| 操作 | 時間複雜度 | 空間複雜度 |
| --------- | ------------- | -------- |
| 插入 | $O(\log n)$ | $O(n)$ |
| 刪除 | $O(\log n)$ | $O(n)$ |
| 查找 | $O(\log n)$ | $O(n)$ |
### 宣告
```cpp
multiset<int> ms; // 宣告一個 multiset 存放整數
multiset<int> ms2 = {10, 20, 20, 30}; // 初始化列表，可儲存重複值
```
### 插入資料
```cpp
ms.insert(num); // 同 set，但插入值重複不會覆蓋
```
### 刪除資料
```cpp
ms.erase(ms.find(num)); // 僅刪除一個 num（find 是 iterator，待會會介紹）
ms.erase(num); // 刪除所有 num
```
### 其他操作
```cpp
ms.count(num); // 回傳值為 num 的數量
ms.size(); // 回傳整體元素數量（含重複）
ms.empty(); // 若為空回傳 true，否則 false
ms.clear(); // 清空 multiset
```
### Python對照
Python 本身沒有 `multiset`，但可以用 `collections.Counter` 模擬：
```python
from collections import Counter
# 宣告
ms = Counter()
ms2 = Counter([10, 20, 20, 30])
# 插入資料
ms[num] += 1 # 插入一個 num（允許重複）
# 刪除資料
if ms[num] > 0:
ms[num] -= 1 # 僅刪除一個 num
if ms[num] == 0:
del ms[num]
del ms[num] # 刪除所有 num（等同 erase(num)）
# 其他操作
ms[num] # 回傳 num 的數量
sum(ms.values()) # 回傳整體元素數量（含重複）
not ms # 判斷是否為空
ms.clear() # 清空 multiset
```
---
## 進階操作 — find()
我們可以使用 `find()` 來用 iterator 指向想查找的元素。忘記 iterator 可以去複習 [【3-5】指標](https://hackmd.io/@LAfWxjSxRASps-4O_bppsA/rJPSm8fSex)。
```cpp=1
#include <bits/stdc++.h>
using namespace std;
int main() {
set<int> numbers = {10, 20, 30, 40, 50};
int target = 30;
auto it = numbers.find(target);
// it 為指標，指向 target 的位置
// 若沒找到，it == numbers.end()
if (it != numbers.end()) {
cout << "Found " << target << " in the set." << endl;
} else {
cout << target << " not found in the set." << endl;
}
return 0;
}
```
### Python對照
```python
numbers = {10, 20, 30, 40, 50}
target = 30
if target in numbers:
print(f"Found {target} in the set.")
else:
print(f"{target} not found in the set.")
```
---
聯絡方式：codecodefunny@gmail.com
最後編修時間：2025/07/12 子柚筆
Sign in with Wallet
Connect another wallet