---
title: C++ STL 大全
top: 8
date: 2023/12/31
cover: /img/data_structure_basic.webp
description: 完整的基礎資料結構教學筆記
categories:
- 筆記
- DSA
tags:
- C++
- 資料結構 Data Structures
- 動態陣列 vector
- 串列 list
- 字串 string
- 數對 pair
- 數組 tuple
- 堆疊 stack
- 佇列 queue
- 雙端佇列 deque
- 優先佇列 priority_queue
- 集合 set
- 映射 map
- 多重集合 multiset
- 多重映射 multimap
- 無序集合 unordered_set
- 無序映射 unordered_map
- 位集 bitset
---

> 本篇文章連結：https://4yu.dev/post/STL/
> 公開發布日期：2023/12/31

# Intro

學完 C++ 基礎語法之後，接著就該進入資料結構的世界了！
本篇筆記要介紹的是 C++ STL，彙整了許多基礎資料結構的概念與用法
文章內容較多，大部分內容為自行收集資料後經過整理而成
若有任何錯誤或需要補充的地方都歡迎使用右側聊天室傳送訊息給我
我將會儘速修改，謝謝

# 先備知識

標準模板庫（Standard Template Library），簡稱 **STL**，為 C++ 內建的函式庫
為了應對各種資料型態，因此 STL 內部採用 `模板 template` 來實作，分為六大部分：

1. 容器（Containers）
2. 演算法（Algorithm）
3. 迭代器（Iterator）
4. 適配器（Adaptor）
5. 仿函數（Function object）
6. 空間配置器（allocator）

> 本篇文章內容著重於前四大部分

## 符號解釋

對於本篇文章中各種符號的解釋

- C：某種容器（container）
- T：某種資料型態（type）
- S：長度（size）
- i：索引（index）
- K：鍵（key）
- val：值（value）
- it：迭代器（iterator）

## 迭代器（iterator）

C++ STL 為每個容器提供一個成員型別：`迭代器 Iterator`，我們可以用 `指標 pointer` 的概念來理解迭代器

迭代器透過運算子重載，為不同資料結構定義「如何走訪下一步」，模擬出指標的走訪功能，但能在移動前進行安全判斷或執行額外功能，解決了指標走訪時容易發生越界或亂指的問題

假設現在有個迭代器 `it`，如果要存取 `it` 所指向的內容，就在前面加上星號 `*it`，與指標相同

迭代器有以下三種類型：

1. 隨機存取迭代器：能夠作整數的加減法，往 `後移 x 項`、往 `前移 x 項` 皆可，也能 `遞增 (++)` 和 `遞減 (−−)`，可以把指標當作這種迭代器
2. 雙向迭代器：只能做 `遞增 (++)` 和 `遞減 (−−)` 的運算，也就是 `後一項` 和 `前一項`
3. 單向迭代器：只能做 `遞增 (++)` 的運算，也就是 `後一項`

利用迭代器可**遍歷容器中的元素**，又分為 `iterator` 和 `reverse_iterator`（反向迭代器）
- iterator
- .begin()：指向容器的起始元素
- .end()：指向容器最後一個元素的下一個位置
- reverse_iterator
- .rbegin()：指向容器的最後一個元素
- .rend()：指向容器起始元素的前一個位置

`iterator` 示意圖 ([圖片來源](https://crmne0707.pixnet.net/blog/post/318479072-c%2B%2B-%E8%BF%AD%E4%BB%A3%E5%99%A8-iterator))


---

# 資料結構的詳細介紹

本篇介紹以下 C++ STL 內建基礎資料結構：

- 動態陣列 vector
- 串列 list
- 字串 string
- 數對 pair
- 數組 tuple
- 堆疊 stack
- 佇列 queue
- 雙端佇列 deque
- 優先佇列 priority_queue
- 集合 set
- 映射 map
- 多重集合 multiset
- 多重映射 multimap
- 無序集合 unordered_set
- 無序映射 unordered_map
- 多重無序集合 unordered_multiset
- 多重無序映射 unordered_multimap
- 位集 bitset

## vector 動態陣列

可以當作是 C++ `陣列（array）` 的擴充版，能支援原有的操作，還可以`動態新增元素`且會自行改變長度，也就是說不用事先宣告固定大小，基本上學完 `vector` 大多數情況可以直接取代 `array`

### 可支援的操作方法

| 編號 | 操作方法 | 功能介紹 | 時間複雜度 |
| --- | --- | --- | --- |
| 1 | `v[i]` | 支援下標讀取 `v` 的第 `i` 項（不做邊界檢查） | $O(1)$ |
| 2 | `v.empty()` | 回傳一個 `bool`，表示 `v` 是否為空的 | $O(1)$ |
| 3 | `v.clear()` | 清空 `v`，但原本的**容量**不會被釋放 | $O(n)$ |
| 4 | `v.size()` | 回傳 `v` 目前的長度 | $O(1)$ |
| 5 | `v.resize(S, val)` | 將 `v` 的長度變為 `S`：若比原本長，則在尾端添加 val 直到長度為 S；反之則將多餘的元素捨去 | 平均 $O(S - S_{old})$ |
| 6 | `v.insert(it, val)` | 在 `it` 位置插入 `val`，必須向後搬動其餘元素 | 均攤 $O(n)$（尾端 $O(1)$） |
| 7 | `v.erase(it)` | 刪除 it 位置元素，也須向前搬動其餘元素 | 均攤 $O(n)$（尾端 $O(1)$） |
| 8 | `v.begin() / v.end()` | 回傳首個元素或最後一個元素的 `iterator` | $O(1)$ |
| 9 | `v.front() / v.back()` | 回傳容器的首個元素或最後一個元素（未檢查是否為空） | $O(1)$ |
| 10 | `v.push_back(val)` / `v.emplace_back(args...)` | 在 `v` 的尾端加入 `val / args`（`push_back` 複製/移動 `val`；`emplace_back` 原地建構） | $O(1)$ |
| 11 | `v.pop_back()` | 刪除 `v` 的最末項，若 `v` 為空則是未定義行為 | $O(1)$ |

<!--
| 12 | `v.reserve(S)` | 預留容量 `S`，若 `S > capacity()` 會重新配置 | $O(1)$（不重配置）or $O(n)$（重新配置） |
| 13 | `v.capacity()` | 取得目前的容量（預分配的內存空間） | $O(1)$ |
| 14 | `v.shrink_to_fit()` | 請求將 `v` 的容量 `capacity()` 縮到剛好等於大小 `size()` | $O(n)$ or $O(1)$（若未執行） |
-->

### 可支援的演算法函數

| 編號 | 演算法函數 | 功能介紹 | 時間複雜度 |
| --- | --- | --- | --- |
| 1 | `swap(v1, v2)` / `v1.swap(v2)` | 交換兩 vector | $O(1)$ |
| 2 | `find(v.begin(), v.end(), val)` | 在 `v` 中搜尋 val，找到就返回對應元素的迭代器，否則返回 `v.end()` | $O(n)$ |
| 3 | `count(v.begin(), v.end(), val)` | 計算 `v` 中 `val` 出現的次數 | $O(n)$ |
| 4 | `replace(v.begin(), v.end(), val, new_val)` | 將 `v` 中所有的 `val` 替換成 `new_val` | $O(n)$ |
| 5 | `sort(v.begin(), v.end())` | 排序 `v` ，預設為遞增 | $O(n \log n)$ |
| 6 | `reverse(v.begin(), v.end())` | 反轉 `v` 內所有元素 | $O(n)$ |
| 7 | `merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin())` | **將已排序**的 `v1` 和 `v2` 合併至 `v3`（結果為已排序狀態） | $O(v1 + v2)$ |
| 8 | `binary_search(v.begin(), v.end(), val)` | 二分搜尋：若找到 `val` 回傳 `true`，否則回傳 `false`（v 須排序） | $O(\log n)$ |
| 9 | `lower_bound(v.begin(), v.end(), val)` | 回傳在包含 `v.begin()` 到不含 `v.end()` 的區間中第一個 $\ge$`val` 的 iterator（`v` 須排序） | $O(\log n)$ |
| 10 | `upper_bound(v.begin(), v.end(), val)` | 回傳在包含 `v.begin()` 到不含 `v.end()` 的區間中第一個 >`val` 的 iterator（`v` 須排序） | $O(\log n)$ |
| 11 | `next_permutation(v.begin(), v.end())` | 變成下一个排列 | $O(n)$ |
| 12 | `prev_permutation(v.begin(), v.end())` | 變成上一个排列 | $O(n)$ |
| 13 | `unique(v.begin(), v.end())` | 移除**相鄰重複元素**（保留第一個），回傳新結尾 iterator，需搭配 `erase` 真正刪除 | $O(n)$ |
| 14 | `max_element(v.begin(), v.end())` / `min_element(...)` | 找出最大或最小值的 iterator | $O(n)$ |
| 15 | `fill(v.begin(), v.end(), val)` | 將整個區間都填上 `val` | $O(n)$ |
| 16 | `copy(v1.begin(), v1.end(), v2.begin())` | 將 `v1` 的內容複製到 `v2`（須保證 `v2` 有足夠空間） | $O(n)$ |
| 17 | `equal(v1.begin(), v1.end(), v2.begin())` | 比較 `v1` 和 `v2` 內容是否完全相等 | $O(n)$ |

> `lower_bound` / `upper_bound` 可透過 ` * ` 取值，需在**由小到大排列好的陣列**中才可使用，若回傳的值是 `v.end()`，代表沒有符合的元素

### 常用基本操作 Code

// 宣告
vector<int> v;    // 長度為 0 的空 vector
vector<int> v(5); // 長度為 5 的 vector
vector<int> v(5, 10); 
// 長度為 5 且每個元素皆被初始化為 10 的 vector，複雜度為 O(n)
vector<int> v = {1, 2, 3};

// 宣告雙層 vector
vector< vector<int> > vv;    // 可想像成二維陣列，但每一列長度可以不一樣

// 宣告雙層 vector 同時初始化為大小為 10x10 且每個元素皆為 0
vector< vector<int> > vv(10, vector<int>(10, 0));

// 下標取值
int n = v[0];    // 與陣列一樣可使用 index 取值

// 取得長度
int s = v.size();

// 更改大小
v.resize(5);    // 將 v 的長度更改為 5

// 在尾端加入元素
int n = 10;
v.push_back(n);
v.emplace_back(n);

// 移除尾端元素
v.pop_back();

// 尋找
vector<int> v = {1,3,5,7,9};
int val; cin >> val
if(find(v.begin(), v.end(), val) == v.end()) {
    cout << "Not find\n";
} else cout << "Find!";
// input : 5 , output : Find!
// input : 6 , output : Not Find

// 排序（預設升冪：由小到大）
sort(v.begin(), v.end());
sort(v, v+v.size());

// 排序（降冪：由大到小）
sort(v.rbegin(), v.rend());
sort(v.begin(), v.end(), greater<int>());

// 反轉
reverse(v.begin(), v.end());

// 二分搜
binary_search(v.begin(), v.end(), val)
upper_bound(v.begin(), v.end(), val);
lower_bound(v.begin(), v.end(), val);

// 合併
vector<int> v1 = {1,3,5},
            v2 = {2,4,6},
            v3(6);
merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
for(auto i : v3) cout << i << " ";
// output : 1 2 3 4 5 6

// 全排列
vector<int> v = {1,3,5};
while(next_permutation(v.begin(),v.end())) 
{
    for(auto i : v) cout << i << " ";
    cout << "\n";
}
// output : 
// 1 5 3 
// 3 1 5 
// 3 5 1 
// 5 1 3 
// 5 3 1

> 注意：`vector` **不支援**對**前端元素**使用 `新增` 或 `刪除` 的操作

### 補充

> `push_back()` 與 `emplace_back()` 功能相同，但如果以效能為優先，`emplace_back()` 通常比 `push_back()` 更快一點，因為是直接呼叫 constructor 不會複製 object，所以有時候執行效率會比較快。
[延伸閱讀：codingninjas - emplace_back() vs push_back() in C++ Vectors
](https://www.codingninjas.com/studio/library/vector-push_back-vs-emplace_back)

> 在知道需要多少元素後，可以先對 `vector` 做 `reserve()` 擴充 `capacity` 再 `emplace_back()` ，會比 `空 vector` 慢慢 `emplace_back()` 快
[延伸閱讀：ping 不見路 - STL vector 效率小記](https://arc.net/l/quote/tslhdeoj)
示意圖 ([圖片來源](https://blog.csdn.net/JACKSONMHLK/article/details/114396650))

## list 串列

list 是雙向鏈結串列（Doubly Linked List），每個節點包含前一個節點與下一個節點的指標，因此可以從任意位置快速插入或刪除元素，且不需要搬移其他元素。
不同於 vector，list 不支援下標，也就是不能使用 `[index]` 隨機存取

| 編號 | 操作方法 | 功能介紹 | 時間複雜度 |
| -- | -------------------------------------------- | ------------------- | ------------- |
| 1 | `lt.size()` | 取得元素個數 | $O(1)$ |
| 2 | `lt.empty()` | 判斷是否為空 | $O(1)$ |
| 3 | `lt.front()` / `lt.back()` | 取得首尾元素 | $O(1)$ |
| 4 | `lt.push_front(val)` / `lt.push_back(val)` | 在前/後加入元素 | $O(1)$ |
| 5 | `lt.pop_front()` / `lt.pop_back()` | 移除前/後元素 | $O(1)$ |
| 6 | `lt.insert(it, val)` | 在迭代器 `it` 前插入 `val` | $O(1)$ |
| 7 | `lt.erase(it)` | 刪除迭代器 `it` 指向的元素 | $O(1)$ |
| 8 | `lt.clear()` | 清空整個 list | $O(n)$ |
| 9 | `lt.sort()` | 對 list 元素排序 | $O(n \log n)$ |
| 10 | `lt.reverse()` | 反轉 list | $O(n)$ |
| 11 | `lt.merge(lt2)` | 合併另一個已排序 list，結果為排序 | $O(n+m)$ |

### 常用基本操作 Code

list<int> lt;

// 尾端加入元素
lt.push_back(1);
lt.push_back(2);

// 前端加入元素
lt.push_front(0);

// 遍歷
for(auto x : lt) cout << x << " ";
cout << "\n"; 
// output : 0 1 2

// 插入
auto it = lt.begin();
advance(it, 2); // 移動到 index 2
lt.insert(it, 5); 
for(auto x : lt) cout << x << " ";
cout << "\n"; 
// output : 0 1 5 2

// 刪除
lt.pop_front();
lt.pop_back();
for(auto x : lt) cout << x << " ";
cout << "\n"; 
// output : 1 5

// 反轉
lt.reverse();
for(auto x : lt) cout << x << " ";
cout << "\n"; 
// output : 5 1

## string 字串

雖然 string 不在 STL 裡，但是由**連續的字元**組成，實際上就是 `vector<char>`，加上有一些字串的操作，所以我就順便放進來了

### 可支援的操作方法

`vector` 有的 `string` 幾乎都有

### 常用基本操作 Code

// 宣告
string s;    // 預設為空字串
string s1 = "ABC";

// 賦值
cin >> s;        // 以空白作為輸入分隔
getline(cin,s);  // 以換行作為輸入分隔
s = "ShiYu";
s = s1;

// 串接
s = "ShiYu";
s1 = "ABC";
s += s1;
cout << s;
// output : ShiYuABC

// 字串轉數字
int a = stoi("123");            // stoi : string to int
long b = stol("12345678900");   // stol : string to long
double c = stod("3.14159");     // stod : string to double

// 字串轉數字
int a = 123;
double b = 3.14159;
string sa = to_string(a);
string sb = to_string(b);

// 刪除最後一個字元
s.pop_back();

// 下標讀取字元
cout << s[3];
// output : Y

// 擷取子字串
cout << s.substr(0,3);
// output : Shi

// 取得長度
cout << s1.size();
// output : 5

> 注意：取得字串長度請不要用 `strlen()`，應該要用 `.size()`，因為前者複雜度為 $O(n)$，後者為 $O(1)$

## pair 數對

**可將兩個型態的資料合併**，透過成員變數 `first` 和 `second` 來存取元素，`pair` 支援以**元素字典序**來比較或排序，以 `first` 為優先

### 常用基本操作 Code

// 宣告
pair<int, double> p;

// 賦值
p = {1, 2.5};
p = make_pair(1, 2.5);

// 取值
int f = p.first;    // 1
double s = p.second;// 2.5

// 比較
pair<int, double> a, b;
a = {1, 2.5};
b = {1, 2.6};
cout << (a < b) << "\n"; 
// output : 1 (true)

// 交換兩 pair
pair<int, int> a,b;
a = {1, 3};
b = {2, 4};
swap(a, b); // or a.swap(b)
cout << a.first << " " << a.second << "\n"; 
// output : 2 4

// pair 搭配 vector 新增元素
vector< pair<int,int> > vp;
vp.push_back(make_pair(1,2));
vp.emplace_back(3,4); // 用 emplace_back 可以不用 make_pair
for(auto i : vp) {
    cout << i.first << " " << i.second << "\n";
}
// output : 
// 1 2
// 3 4

// 使用 vector 排序多個 pair
pair<int,int> a = {1,3},
              b = {2,4},
              c = {1,2};
vector< pair<int, int> > v{a, b, c};

sort(v.begin(), v.end());

for(auto i : v) {
    cout << i.first << " " << i.second << "\n";
}
// output : 
// 1 2
// 1 3
// 2 4

## tuple 數組

與 `pair` 相似，但可以**同時組合多個不同型別的元素**( `pair` 只能 2 個)

### 常用基本操作 Code

// 宣告
tuple<string, int, bool> tp;

// 初始化
tuple<string, int, bool> tp("ShiYu", 16, true); 

// 賦值
tp = {"ShiYu", 16, true};
tp = make_tuple("ShiYu", 16, true);

// 賦值（使用 tie，須放變數）
string name = "ShiYu"; 
int age = 16;
bool b = true;
tie(name, age, b) = tp;

// 取值
int age = get<1>(tp); // 16

// 修改值
get<2>(tp) = false;

// 取得元素個數
cout << tuple_size<decltype(tp)>::value << "\n"; 
// output : 3

// tuple 搭配 vector 新增元素
vector< tuple<int, int, int> > vt;
vt.push_back(make_tuple(1, 2, 3));
vt.emplace_back(4, 5, 6); // 用 emplace_back 可以不用 make_tuple

for(auto& [a,b,c] : vt) {
    cout << a << " " << b << " " << c << "\n";
}
// output : 
// 1 2 3
// 4 5 6

## stack 堆疊

可以想像成**一疊盤子**，每次只能在**最上面** `放置` 或 `拿走` 一個盤子
有著 `後進先出 Last In First Out (LIFO)` 的規則
> C++ 的 `stack` 是 `容器適配器（Container Adapter）`，預設以 `deque` 為底層容器，也可使用 `vector` 或 `list`

### 可支援的操作方法

| 編號 | 操作方法 | 功能介紹 |
| --- | --- | --- |
| 1 | `s.size()` | 取得 s 大小 |
| 2 | `s.empty()` | 回傳 s 是否為空 |
| 3 | `s.top()` | 取得 s 頂端元素 |
| 4 | `s.push(val) / s.emplace(val)` | 將 val 放入 s 頂端 |
| 5 | `s.pop()` | 移除 s 頂端元素 |

> 複雜度皆為 `O(1)`
> stack 不支援隨機存取，只能操作頂端元素，也不支援迭代器，無法直接遍歷
> 注意：.top() 與 .pop() 不會檢查 stack 是否為空，若 stack 為空則是未定義行為，使用前須自行以 .empty() 檢查確保不會出錯

### 示意圖


([圖片來源](https://www.programiz.com/dsa/stack))

### 常用基本操作 Code

依照示意圖實作

stack<int> stk;
for(int i=1;i<=3;++i) {
    stk.push(i);
}
while(!stk.empty()) {
    cout << stk.top() << "\n";
    stk.pop();
}
// output : 
// 3
// 2
// 1

### 常見應用

- 表達式求值
- 括號匹配
- 維護單調序列

## queue 佇列

可以想像為**排隊的人群**：新來的人排在隊伍的尾端，最前面的人結完帳離開隊伍
有著 `先進先出 First In First Out (FIFO)` 的規則
> C++ 的 queue 是 `容器適配器（Container Adapter）`，預設以 `deque` 為底層容器，也可以使用 `list`

### 可支援的操作方法

| 編號 | 操作方法 | 功能介紹 |
| --- | --- | --- |
| 1 | `q.size()` | 取得 q 長度 |
| 2 | `q.empty()` | 回傳 q 是否為空 |
| 3 | `q.front()` | 取得 q 最前端（最早加入）的元素 |
| 4 | `q.back()` | 取得 q 最尾端（最後加入）的元素 |
| 5 | `q.push(val) / q.emplace(val)` | 將 val 加入 q 尾端 |
| 6 | `q.pop()` | 移除 q 最前端元素 |

> 複雜度皆為 `O(1)`
> queue 不支援隨機存取，只能操作前端元素，也不支援迭代器，無法直接遍歷
> 注意：.front() 與 .pop() 不會檢查 queue 是否為空，若 queue 為空則是未定義行為，使用前須自行以 .empty() 檢查確保不會出錯

### 示意圖


([圖片來源](https://www.boardinfinity.com/blog/working-of-queue-using-stl))

### 常用基本操作 Code

queue<int> q;
q.emplace(1);
q.emplace(2);
q.emplace(3);
while(!q.empty()) {
    cout << q.size() << " " << q.front() << " " << q.back() << "\n";
    q.pop();
}
// output : 
// 3 1 3
// 2 2 3
// 1 3 3

### 常見應用

- BFS
- 拓墣排序
- 任務排程

## deque 雙端佇列

為 `double ended queue` 的縮寫，唸作 `deck` 而非 `de-queue`
一般的 `queue` 只能從尾端新增元素、從前端刪除元素，而 `deque` 的**前後**都可以使用**新增**和**刪除**的操作，
也支援下標隨機讀取 `dq[i]`，基本上就是多了 `emplace_front()`、`pop_front()` 的 `vector`
雖然功能方便但由於**常數較大**，在程式競技比賽中非必要不會去使用

### 示意圖


([圖片來源](https://www.codingninjas.com/studio/library/difference-between-queue-and-deque-in-c))

### 可支援的操作方法

`deque` 與 `vector` 相比只是多了針對 `front` 的操作，少了針對記憶體的操作，因為 `vector` 記憶體連續，`deque` 則是分段儲存

| 編號 | 操作方法 | 功能介紹 |
| --- | --- | --- |
| 1 | `dq[i]` | 隨機讀取第 i 個元素 |
| 2 | `dq.size()` | 取得元素個數 |
| 3 | `dq.empty()` | 判斷是否為空 |
| 4 | `dq.push_front(val) / dq.emplace_front(val)` | 將 val 加入 dq 前端 |
| 5 | `dq.push_back(val) / dq.emplace_back(val)` | 將 val 加入 dq 尾端 |
| 6 |` dq.pop_front()` | 移除 dq 最前端元素 |
| 7 | `dq.pop_back()` | 移除 dq 最尾端元素 |

> 複雜度皆為 `O(1)`

### 常用基本操作 Code

deque<int> dq;

// 前後新增元素
dq.emplace_front(1);
dq.emplace_back(2);
for(auto i : dq) cout << i << " ";
cout << "\n";

// 刪除前端元素
dq.pop_front();
for(auto i : dq) cout << i << " ";
cout << "\n";

// 刪除尾端元素
dq.pop_back();
cout << dq.size() << "\n";

// output : 
// 1 2 
// 2 
// 0

### 常見應用

- 滑動窗口
- 0-1 BFS

## priority_queue 優先佇列

`priority_queue` 是基於`堆積（heap）`結構實作的容器適配器，它可以維持最頂端的元素永遠是最大或最小的，所以可以很方便且**快速地存取極值**

### 示意圖


([圖片來源](https://www.programiz.com/dsa/priority-queue))

### 可支援的操作方法

| 編號 | 操作方法 | 功能介紹 | 時間複雜度 |
| --- | --- | --- | --- |
| 1 | `pq.size()` | 取得元素個數 | $O(1)$ |
| 2 | `pq.empty()` | 判斷是否為空 | $O(1)$ |
| 2 | `pq.top()` | 回傳 pq 中最大或最小的元素 | $O(1)$ |
| 3 | `pq.push(val)` / pq.emplace(val) | 將 val 加入 pq 中| $O(\log n)$ |
| 4 | `pq.pop()` | 將 pq 中最大或最小的元素移除 | $O(\log n)$ |

### 常用基本操作 Code

priority_queue<int> pq;
pq.emplace(3);
pq.emplace(5);
pq.emplace(9);
cout << pq.top();
// output : 9

// 最小堆
priority_queue< int, vector<int>, greater<int> > pq;
pq.emplace(3);
pq.emplace(5);
pq.emplace(9);
cout << pq.top();
// output : 3

### 補充

> `priority_queue` 有三個型別參數 `T`、`C`、`Cmp`
`T` 是**內容物的型別**，`C` 是**所採用的容器**，`Cmp` 是**比大小的依據**
`priority_queue` 能使用的容器有 `vector` 和 `deque`
`Cmp` 的預設值是 `less<T>`，此時的 `priority_queue` 是**最大堆 max heap**
若改成 `greater<T>`，則 `priority_queue` 為 **最小堆 min heap**
建構式如上方 Code 第 8 行，而 output 為最小值

### 延伸閱讀

- [Binary Heap 的排序原理](https://medium.com/starbugs/%E4%BE%86%E5%BE%81%E6%9C%8D%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E8%88%87%E6%BC%94%E7%AE%97%E6%B3%95%E5%90%A7-%E6%90%9E%E6%87%82-binary-heap-%E7%9A%84%E6%8E%92%E5%BA%8F%E5%8E%9F%E7%90%86-96768ea30d3f)
- [資料結構大便當： Binary Heap](https://arc.net/l/quote/asrwfvnj)

### 常見應用

- 動態維護極值
- 動態第 K 大
- 最短路徑演算法（Dijkstra）

## set 集合
`set` 是一個平衡二元搜尋樹容器，底層使用 紅黑樹（Red-Black Tree）實作
主要的特性為以下三種：
1. 內部元素自動排序（從小到大）
2. 沒有重複元素（方便去重）
3. 插入、刪除和查詢的時間複雜度皆為 $O(\log n)$

### 示意圖


([圖片來源](http://www.ccplusplus.com/2014/01/std-set-example-c.html))

### 可支援的操作方法

| 編號 | 操作方法 | 功能介紹 | 時間複雜度 |
| --- | --- | --- | --- |
| 1 | `s.size()` | 取得元素個數 | $O(1)$ |
| 2 | `s.empty()` | 判斷是否為空 | $O(1)$ |
| 3 | `s.insert(K)` | 插入元素 K，若已存在則忽略 | $O(\log n)$ |
| 4 | `s.erase(K)` | 刪除鍵為 K 的元素，回傳刪除數量（0 或 1） | $O(\log n)$ |
| 5 | `s.erase(it)` | 刪除迭代器指向元素 | $O(\log n)$ |
| 6 | `s.erase(it_first, it_last)` | 刪除區間 `[first,last)` | $O(k \log n)$，k = 刪除數量 |
| 7 | `s.find(K)` | 尋找 K，回傳迭代器，找不到則回傳 `s.end()` | $O(\log n)$ |
| 8 | `s.count(K)` | 回傳鍵為 K 的個數（0 或 1） | $O(\log n)$ |
| 9 | `s.lower_bound(K)` | 回傳第一個大於等於 K 的元素迭代器 | $O(\log n)$ |
| 10 | `s.upper_bound(K)` | 回傳第一個大於 K 的元素迭代器 | $O(\log n)$ |

### 常用基本操作 Code

// 宣告
set<int> s;

// 插入
s.insert(10);

// 刪除
s.erase(10);
s.erase(s.begin());

// 回傳該元素的 iterator，若 set 內部無該元素，則回傳 end()
s.find(10);

// 問一個元素在不在 set 裡。可透過 find 的 return 值，或使用 s.count
if(s.find(10) != s.end()) cout << "In!\n";
if(s.count(10)) cout << "In!\n";

// 遍歷 set 元素
for(auto &i : s) cout << i << " ";

### 延伸閱讀

- [資料結構 — 紅黑樹(Red-Black Tree)](https://ithelp.ithome.com.tw/m/articles/10333136)
- [Shengyuu - 紅黑樹 - HackMD](https://hackmd.io/@_01X9rimQmWH33Djf8QhoA/Bkm3enQ8N)
- [hwdong - 最好懂的红黑树教程 - Youtube](https://www.youtube.com/watch?v=Ij8-xX3PreE)

## map 映射

類似於 python 中的 `字典 dict`，內部為 `鍵值對 key-value pair`，
主要的特性為以下三種：

1. 每個元素都是 `pair<key, value>`
2. 內部依 `鍵 key` 自動排序
3. 可以修改 `值 value` ，但不能修改 `鍵 key` （因為會破壞排序）
4. 插入/刪除/查詢鍵的值，時間複雜度皆為 $O(\log n)$

### 示意圖


([圖片來源](https://www.mropengate.com/2015/12/cc-map-stl.html))

### 可支援的操作方法

| 編號 | 操作方法 | 功能介紹 | 時間複雜度 |
| --- | --- | --- | --- |
| 1 | `m[k]` | 存取鍵值 k 對應的 value，若不存在則插入預設值 | $O(\log n)$ |
| 2 | `m.size()` | 取得元素數量 | $O(1)$ |
| 3 | `m.empty()` | 判斷是否為空 | $O(1)$ |
| 4 | `m.insert(pair<K,T> p)` | 插入鍵值對 p，若 key 已存在則不修改 value；回傳 pair（first=迭代器，second=是否插入成功） | $O(\log n)$ |
| 5 | `m.erase(k)` | 刪除 key 為 k 的元素，回傳刪除數量（0 或 1） | $O(\log n)$ |
| 6 | `m.erase(it)` | 刪除迭代器指向的元素 | $O(\log n)$ |
| 7 | `m.erase(it_first, it_last)` | 刪除區間 `[first,last)` 的元素 | $O(k \log n)$，k=刪除數量 |
| 8 | `m.find(k)` | 查找 key=k，回傳指向元素的迭代器，找不到回傳 `m.end()` | $O(\log n)$ |
| 9 | `m.count(k)` | 回傳 key=k 的元素數量（map 中 0 或 1） | $O(\log n)$ |
| 10 | `m.lower_bound(k)` | 回傳第一個 key >= k 的元素迭代器 | $O(\log n)$ |
| 11 | `m.upper_bound(k)` | 回傳第一個 key > k 的元素迭代器 | $O(\log n)$ |
| 12 | `m.clear()` | 清空 map | $O(n)$ |

### 常用基本操作 Code

map<int, string> m;

// 讀取指定 key 的 value
cout << m[1] << "\n";        // output: one
cout << m[2] << "\n";        // output: two

// 插入元素
m[1] = "one";                // 使用 operator[]
m.insert({2, "two"});        // 使用 insert
m.insert(make_pair(3, "three"));

// 刪除元素
m.erase(2);
m.erase(m.begin());

// 查詢 key 是否存在
if(m.find(3) != m.end()) cout << "3 in map\n";

// 遍歷 map
for(auto &p : m) cout << p.first << ":" << p.second << " ";
cout << "\n";

## multiset 多重集合 & multimap 多重映射

兩者為 `set`、`map` 的延伸，用法相似但**允許有重複元素**，且 `multimap` 中一個鍵值可能對應到不同的值，所以**不支援下標**

### 示意圖


([圖片來源](http://www.ccplusplus.com/2014/01/std-set-example-c.html))

## unordered_set 無序集合 & unordered_map 無序映射

兩者為 `set`、`map` 的延伸，用法相似但因為底層使用 `雜湊表 Hash Table` 實作，所以**內部不排序**
因為無序，所以當然沒有 `lower_bound()`、`upper_bound()`，`unordered_map` 支援下標
插入/刪除/查詢的時間複雜度平均 $O(1)$，最壞 $O(n)$（Hash 碰撞）
常數較大，競賽中非必要時不常用

### 示意圖


([圖片來源](https://conglang.github.io/2015/01/01/stl-unordered-container/))

### 延伸閱讀

- [資料結構 - 雜湊表 Hash Table](https://ithelp.ithome.com.tw/articles/10268077?sc=iThelpR)
- [雜湊表（Hash Table）- 拉爾夫的技術隨筆](https://medium.com/@ralph-tech/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E5%AD%B8%E7%BF%92%E7%AD%86%E8%A8%98-%E9%9B%9C%E6%B9%8A%E8%A1%A8-hash-table-15f490f8ede6)
示意圖([圖片來源](https://conglang.github.io/2015/01/01/stl-unordered-container/))

## unordered_multiset 無序多重集合 & unordered_multimap 無序多重映射

依名稱即可知道為前兩者的結合，**內部不排序且可允許重複元素**

### set / map 延伸容器對照表
| 容器 | 是否排序 | 是否允許重複 | 下標支援 | 插入/刪除/查找平均時間複雜度 |
| --- | --- | --- | --- | --- |
| set | ✅ | ❌ | ❌ | $O(\log n)$ |
| map | ✅ | ❌ | ✅ | $O(\log n)$ |
| multiset | ✅ | ✅ | ❌ | $O(\log n)$ |
| multimap | ✅ | ✅ | ❌ | $O(\log n)$ |
| unordered_set | ❌ | ❌ | ❌ | 平均 $O(1)$ |
| unordered_map | ❌ | ❌ | ✅ | 平均 $O(1)$ |
| unordered_multiset | ❌ | ✅ | ❌ | 平均 $O(1)$ |
| unordered_multimap | ❌ | ✅ | ❌ | 平均 $O(1)$ |

## bitset 位集

`bitset` 為固定長度的位元集合，可以視為一個**效率很快的 bool 陣列**
因為 `bool` 這個型別明明只能表示 `true` 或 `false`，但通常卻佔了 `1 byte` 的記憶體空間
用 `bitset` 可以**宣告固定長度的 bits**，可以想像為一堆 0 和 1 的陣列
並且 `bitset` 的**位元運算**是被優化過的，對常數優化及空間壓縮有不錯的效果，速度大約是 **bool 的 32 倍**

### 可支援的操作函數

| 編號 | 操作方法 | 功能介紹 | 時間複雜度 |
| -- | ---------------------- | ------------------------------- | ------ |
| 1 | `b[i]` | 存取第 i 位 | $O(1)$ |
| 2 | `b.size()` | 回傳 b 的總位數 | $O(1)$ |
| 3 | `b.count()` | 計算 b 中為 1 的位數 | $O(N)$ |
| 4 | `b.set()` | 將所有位元設為 1 | $O(N)$ |
| 5 | `b.reset()` | 將所有位元設為 0 | $O(N)$ |
| 6 | `b.flip()` | 將所有位元取反（0 ↔ 1） | $O(N)$ |
| 7 | `b.any()` / `b.none()` | 檢查是否有至少一個位元為 1 / 全部為 0 | $O(N)$ |
| 8 | `b.to_string()` | 將 bitset 轉為字串 | $O(N)$ |
| 9 | `b.to_ulong()` | 將 bitset 轉為 unsigned long（注意溢位） | $O(N)$ |

### 常用基本操作 Code

// 宣告
bitset<5> b; // 大小為 5，初始值 00000

// 賦值
b[0] = 1; // 00001 以右邊為低位

// 設置
b.set();	// 11111
b.reset();  // 00000
b.flip();   // 11111

// 計數與檢查
cout << b.count() << "\n"; // 5
cout << b.any() << "\n";   // 1 (true)
cout << b.none() << "\n";  // 0 (false)

// 轉換
cout << b.to_string() << "\n";  // "11111"
cout << b.to_ulong() << "\n";   // 31

// 位元運算
bitset<5> a("10101"), b("01110");
cout << (a & b) << "\n"; // 00100
cout << (a | b) << "\n"; // 11111
cout << (a ^ b) << "\n"; // 11011

### 常見應用

- 空間優化
- 狀態壓縮 DP

---

# 容器分類表格
| 類別分類 | 主要容器 | 用途 / 特點 |
| --- | --- | --- |
| **序列式容器** | `vector`, `deque`, `list` | 存放有序元素，支援迭代器操作；`vector` 隨機存取快，`deque` 前後操作靈活，`list` 雙向鏈結串列，插入刪除快 |
| **容器適配器** | `stack`, `queue`, `priority_queue` | 封裝序列式容器，提供特定操作：`stack`（後進先出）、`queue`（先進先出）、`priority_queue`（依優先權排序） |
| **關聯容器** | `set`, `map`, `multiset`, `multimap` | 自動排序，快速查找、插入、刪除；`set` 存唯一元素，`map` 存 key-value；`multiset`/`multimap` 允許重複 |
| **無序容器** | `unordered_set`, `unordered_map`, `unordered_multiset`, `unordered_multimap` | 基於 Hash 表，平均 O(1) 查找、插入；最壞情況 O(n)；元素無序 |
| **工具型容器** | `pair`, `tuple`, `bitset` | 儲存固定數量元素或位元資訊；`pair` 兩個元素，`tuple` 多個元素，`bitset` 二進位操作與狀態壓縮 |

# 題單

看完這篇筆記相信大家對 STL 有一定的瞭解了，不過還是要實際練習才能掌握，所以我把曾經寫過的題目整理成資料庫，來自各大 Online Judge，有依照不同的難度及不同資料結構分類好，歡迎大家自行運用，多練習才能讓你更加熟練。
## [STL 題單連結 - Notion](https://shiyu0318.notion.site/C-STL-ShiYu-s-Blog-c2ed8c6b22fb4118bab30b62dbad5299?pvs=4)

---

# Outro

這篇文章只用了兩天的時間，從收集資料、整理資訊、規劃架構，再來開始寫每個資料結構的內容，製作表格、寫 Code、找圖片（每張圖片皆有附上來源）、找補充資料，到最後不斷地重複新增和修改內容，直到整篇文章逐漸完整，我從中學習到的不只有這篇文章所呈現的知識，還有很多重要的能力，也感受到了學習的快樂，日後會不斷地學習新知識，也會針對各主題寫成一篇筆記發佈，感謝大家的閱讀

## 下回預告：{% btn /post/Data-Structures/,點擊前往,fa-solid fa-hand-point-right,blue %} C++ 實作資料結構

---

# 參考資料

- [The C++ Standard Template Library (STL)
](https://www.geeksforgeeks.org/the-c-standard-template-library-stl/)
- [從零開始的演算法競賽入門教學 - STL](https://emanlaicepsa.github.io/2020/11/30/0-16/)
- [Ian Shih - STL Containers - HackMD](https://hackmd.io/@konchin/BkGVGVd9I)
- [C++ 中 STL 用法超詳細總結 - Github](https://github.com/0voice/cpp_backend_awsome_blog/blob/main/%E3%80%90NO.19%E3%80%91C++%E4%B8%ADSTL%E7%94%A8%E6%B3%95%E8%B6%85%E8%AF%A6%E7%BB%86%E6%80%BB%E7%BB%93%EF%BC%88%E6%94%B6%E8%97%8F%E7%BA%A7%EF%BC%89.md)
- [進階 C++ STL 迭代器 - HackMD](https://hackmd.io/@Greenleaf/advanced_cpp)
- [C++ STL 常用容器以及操作簡介](https://blog.csdn.net/zygood_/article/details/122457444)
- [C++ STL 學習總結(全面)](https://jasonblog.github.io/note/c++/c++_stl_xue_xi_zong_7d5028_quan_976229.html)
- [STL in C++ - Youtube](https://youtube.com/playlist?list=PLk6CEY9XxSIA-xo3HRYC3M0Aitzdut7AA&si=q5I7ppldSRGBKsKq)
- [cplusplus reference](https://cplusplus.com/reference/)
- [cppreference](https://en.cppreference.com/w/)

---

{% btn '/post/Sitemap/',回到導覽頁面,far fa-hand-point-right,blue block center larger %}

---