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

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

簡介

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

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

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

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

set 特性

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

語法（Syntax）

1	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. 插入操作

#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. 存取操作

#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;
}

輸出結果：

1 2	min : 1 third min : 4

3. 查詢操作

#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. 刪除操作

#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;
}

輸出結果：

1	size of set s : 0

5. 自訂排序

#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，另外也說不定有可能會出現以下這種測資：

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

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

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

#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;
}