---
# System prepended metadata

title: 【5-3】排序關聯式容器 — set & multiset

---

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