【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/)
Sign in with Wallet
Connect another wallet