---
# System prepended metadata

title: 【C++】競程筆記（資料結構：set）
tags: [資料結構, 程式設計, C++, 競程, 排序, CP]

---

【C++】競程筆記（資料結構：set）
===

[TOC]

程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。

簡介
---

set 是基於紅黑樹（Red-black tree）所實現的，紅黑樹是一種自平衡避免退化的二元搜尋樹，而因為 STL 幫我們實作出來了，所以不用再重造輪子。

所以 set 在查詢、插入、刪除這方面都是對數時間 $O(logn)$ 。

另外 set 也是一種關聯式容器（Associative Container），就是使用 key 來做資料存取（set 以輸入的 value 作為 key，可查找 value 是否存在 set 中）。

關聯式容器也可再細分為有序（ordered）與無序（unordered）。

### set 特性

1. 唯一性：
    - set 中的元素不能重複出現，若 insert 重複值，會自動被忽略。
2. 有序性：
    - set 中的元素會依照升序（預設）自動排序，可改成降序。
3. 無法直接修改：
    - 因為直接修改會破壞 set 的有序性，所以要改的話要先刪除再插入。

### 語法（Syntax）

```
set<T, comp> s;
```

T：在 set 中元素的資料型態。

comp：比較函式。使用 `greater <T>` 可改成降序排序。

s：set 容器名稱。

### 標頭檔

使用前引入標頭檔：`<set>`。

### 基本操作

- 插入操作：
    - `insert()`、`emplace()`。
- 存取元素：
    - `begin()`、`end()` 用迭代器存取，之後用 `*` Dereference 解參考運算子得到值，也可藉助 `next()`、`advance()` 完成。
- 搜尋元素：
    - `find()`，找到元素就回傳他的迭代器，找不到就是回傳 `end()`。
- 遍歷元素：
    - range-based for loop 或是用一般的 for（只是要用迭代器）。
- 刪除元素：
    - `erase(element)` or `erase(iterator)` or `erase(begin(), end())`
- 計算元素數量：
    - `count()`
- set 大小：
    - `size()`
- 清空 set：
    - `clear()`

### insert() 和 emplace() 的差異

其實就跟 vector 中的 push_back 和 emplace_back() 的差異一樣（基本上就是這個概念）。

insert() 是在函式外面建構好物件在把它插入，emplace() 是在容器裡面就建立好物件，能避免像 insert() 不必要的複製與移動，有更好的效能。

emplace() 對於自訂的資料型態（如 struct、class）會更有優勢，普通的型態如 int、string 等用 insert() 其實就夠了。

操作範例
---

### 1. 插入操作

```cpp=
#include <iostream>
#include <set>

using namespace std;

int main(){
    set <int> s;
    
    s.insert(10);
    s.insert(5);
    s.insert(10);
    
    s.emplace(20);
    s.emplace(5);
    
    for (int i : s){
        cout << i << " ";
    }
    return 0;
}
```

輸出結果：

```
5 10 20
```

### 2. 存取操作

```cpp=
#include <iostream>
#include <set>

using namespace std;

int main(){
    set <int> s = {3, 1, 4};
    
    auto it = s.begin();
    cout << "min : " << *it << '\n';
    
    it = next(it, 2);
    cout << "third min : " << *it;
    return 0;
}
```

輸出結果：

```
min : 1
third min : 4
```

### 3. 查詢操作

```cpp=
#include <iostream>
#include <set>

using namespace std;

int main(){
    set <int> s = {8, 3, 7};
    
    auto it = s.find(3);
    if (it != s.end()){
        cout << "find!";
    }
    else{
        cout << "this element is not exist.";
    }
    return 0;
}
```

輸出結果：

```
find!
```

### 4. 刪除操作

```cpp=
#include <iostream>
#include <set>

using namespace std;

int main(){
    set <int> s = {10, 20, 30, 40};
    
    s.erase(30);
    
    auto it = s.find(40);
    s.erase(it);
    
    s.erase(s.begin(), s.end());
    
    cout << "size of set s : " << s.size();
    return 0;
}
```

輸出結果：

```
size of set s : 0
```

### 5. 自訂排序

```cpp=
#include <iostream>
#include <set>

using namespace std;

int main(){
    set <int, greater<int>> s = {2, 5, 1, 3, 4};
    
    for (int i : s){
        cout << i << " ";
    }
    return 0;
}
```

輸出結果：

```
5 4 3 2 1
```

multiset
---

multiset 是 STL 提供的序列容器之一，跟 set 一樣屬於關聯式容器（Associative Container），其餘功能基本上與 set 類似，但有一點不一樣就是：

:::info
multiset 是一個可以存放重複元素的容器，而 set 只能存放唯一的元素。
:::

除了這個之外，其他所有特性基本上跟 set 一樣，就連語法、用的函式也是。

習題練習
---

### 今晚打老虎

Source：https://zerojudge.tw/ShowProblem?problemid=a091

為何用 multiset 而非 set？因為題目沒有提到數字不能重複，所以保險起見用 multiset，另外也說不定有可能會出現以下這種測資：

```
1 100
1 100
1 100
2
```

細節還要再更細節！既然都用到 multiset 了，所以不要忘了它是一個升序的容器，最小值就是 `begin()`，最大值為 `prev(end())`！

第 18 行，至於為何要加上 `prev()`，讓迭代器往前一位？

這是因為 multiset 的 `end()` 迭代器回傳結果是最後一個元素再往後一位，直接寫 `end()` 的話會造成未定義行為，所以要加上 `prev()`。

```cpp=
#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int op;
    multiset <int> ms;
    while (cin >> op){
        if (op == 1){
            int x;
            cin >> x;
            ms.emplace(x);
        }
        else if (op == 2){
            if (!ms.empty()){
                auto it = prev(ms.end());
                cout << *it << '\n';
                ms.erase(it);
            }
        }
        else{
            if (!ms.empty()){
                auto it = ms.begin();
                cout << *it << '\n';
                ms.erase(it);
            }
        }
    }
    return 0;
}
```

參考資料
---

[STL container特性介紹.容器的選用 | Medium](https://wither23265.medium.com/stl-container%E7%89%B9%E6%80%A7-cc28fd8bc246)

[Set in C++ STL - GeeksforGeeks](https://www.geeksforgeeks.org/cpp/set-in-cpp-stl/)

[multiset begin() and end() function in C++ STL - GeeksforGeeks](https://www.geeksforgeeks.org/cpp/multiset-begin-and-end-function-in-c-stl/)