---
# System prepended metadata

title: C++ STL

---

# C++ STL
---
## 什麼是STL?
* 標準模板庫(Standard Template Library)，是C++內建的函式庫
* 為了可以套用不同資料型態，其實作方式都是採用**模板(template)**
* STL分成以下六個部分
    * 容器 Container
    * 演算法 Algorithm
    * 迭代器 Iterator
    * 適配器 Adaptor
    * 仿函數 Function Object
    * 空間配置器 Allocator
---
## C++ 標準庫的說明文件
- 官方標準文件(比較文鄒鄒)：https://eel.is/c++draft/
- 第三方整理(比較容易懂)：https://en.cppreference.com/w/
- 其他參考1：https://4yu.dev/post/STL/
- 其他參考2：https://io.zouht.com/154.html


## 迭代器 Iterator
* 可以用來取代指標的一種型別
* iterator有很多種，下表中愈下方的功能愈強大(i.e. 隨機存取迭代器功能最強大)
![image](https://hackmd.io/_uploads/ry_o9LDwke.png)

用途：
* 可以比較兩個位址是否相同
* 可以使用dereference * 來取得裡面的值
* 依照類別不同可以進行整數加減法來進行前後移，能位移多少個資料就看他是表中的哪一種迭代器
    * 隨機存取迭代器：可以往前往後移x項，也可以遞增遞減(前一項後一項)
    * 雙向迭代器：只能遞增遞減(前一項後一項)
    * 單向迭代器：只能遞增
* 迭代器可以拿來遍歷容器裡面的內容，分為iterator跟reverse_iterator
    * iterator: container.begin(), container.end()
    * reverse_iterator: container.rbegin(), container.rend();
![image](https://hackmd.io/_uploads/S1EQnLwP1g.png)

---
---
# 資料結構
## Vector
- ```#include <vector>```
- 連續的順序的儲存結構，長度可以動態調整
### 1. 常用語法
#### 建立vector - $O(n)$
```vector<datatype> arr(length, [value])```


```cpp
vector<int> arr;           // 創建陣列
vector<int> arr(100);      // 創建初始長度為100的陣列
vector<int> arr(100, 1);   // 創建初始長度為100的陣列，陣列元素初始值為1

vector<vector<int>> dp(5, vector<int>(6));     // 創建 5 rows, 6 columns的二維陣列，初始值為0
vector<vector<int>> dp(5, vector<int>(6, 10)); // 創建 5 rows, 6 columns的二維陣列，初始值為10

// 創建5個6x4的三維陣列
vector<vector<vector<int>>> dp(5, vector<vector<int>>(6, vector<int>(4)));
```

#### 尾部增減 - $均攤O(1)$
- ```push_back()```
- ```pop_back()```
- 因為涉及長度變化，所以時間複雜度要均攤之後才會是$O(1)$
Example
```cpp
#include <bits/stdc++.h>
using namespace std;

int main() 
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    
    v.pop_back();
    v.pop_back();
    
    for (auto& ele : v)
      cout << ele << ' ';
    cout << endl;
    
    return 0;
}
```
#### 取得元素 - $O(1)$
- ```v[i]```(i as indices)
#### 取得長度 - $O(1)$
- ```v.size()```

#### 清空 - $O(n)$
- ```v.clear()```

#### 是否為空 - $O(1)$
* ```v.empty()```
* return bool

#### 改變長度 - $O(N)$
* ```v.resize(length, [value])```
* 改長會有初始值
* 改短會刪值

### 2. 注意事項
#### 若知道長度的話一定要提前指定長度
* 如果一開始不宣告長度，而是用迴圈push_back的話，會一直重分配空間造成時間效率不佳

#### 注意size_t overflow
```v.size()``` 的回傳值類型是size_t，會依照不同編譯器而有不同範圍


---
## Stack
- ```#include <stack>```
- 二次封裝deque的容器，實現FILO
### 1. 常用語法
#### 建立
```stack<type> stk```

#### 插入/刪除
- ```stk.push(5)```
- ```stk.pop()```

#### 取得頂部
- ```stk.top()```

#### 取得長度
- ```stk.size()```

#### 是否為空
* ```stk.empty()```


### 2. 注意事項
* 無法使用迴圈+index進行元素存取


---
## Queue
- ```#include <queue>```
- 二次封裝deque的容器，實現FIFO
### 1. 常用語法
#### 建立
```queue<type> que```

#### 插入/刪除
- ```que.push(5)```
- ```que.pop()```

#### 取得頭部元素/尾部元素
- ```que.front()```
- ```que.back()```

#### 取得長度
- ```que.size()```

#### 是否為空
* ```que.empty()```

### 2. 注意事項
* 無法使用迴圈+index進行元素存取

---
## Priority Queue
* ```#include <queue>```

### 1. 常用語法

#### 建立
```priority_queue<type, container<type>, compare> pque```
* type: 元素類型
* container: 底層容器，默認為vector\<type\>，平常使用不需要更改
* compare: 比大小，默認為less，可以自定義

<font color="orange">**預設是max heap，如果要改成min heap需要傳入greater仿函式**</font>
```cpp
priority_queue<int> pque;  // max heap
priority_queue<int, vector<int>, greater<int>> pque; // min heap
```

#### 插入/刪除
- ```pque.push(5)```
- ```pque.pop()```

#### 取得頂部
- ```pque.top()```

#### 取得長度
- ```pque.size()```

#### 是否為空
* ```pque.empty()```

### 2. 使用情形
* 需要維持元素的有序性，每次都要向queue插入大小不定的元素
* 每次從queue裡面取出「最大」或「最小」的元素(數量n，插入操作數量k) - $k*log(n)$

### 3. 注意事項
* 無法使用迴圈+index進行元素存取
* 也無法使用\[\]運算子來進行賦值

---

## Set
* ```#include <set>```
提供$O(LogN)$的插入、刪除、尋找。底層原理是紅黑樹。


| 性質 | set | multiset |unordered_set |
| -------- | -------- | -------- | -------- |
| 元素要嘛在裡面，要嘛不在裡面    | O     | O    |  O  |
| 元素只能在集合裡面出現一次    | O    | X (任意次)    |O     |
| 元素是沒有順序的    | X(升序)     | X(升序)    |O    |


### 1. 常用語法
```set<type, compare> st;```
* type: 元素類型
* compare: 比大小，默認為less，可以自定義

#### 插入/刪除 - $O(LogN)$
* ```st.insert(4)```
* ```st.erase(4)```
    * 刪除不存在的元素不會發生任何事情

#### 查找 - $O(LogN)$
* 找到：返回該元素的迭代器
* 沒找到：返回end()迭代器
```cpp
set<int> st;

if (st.find(4) == st.end()) // 迭代器為end()亦即找不到
{
    // do something
}
```
#### <font color="orange">另一種查找方式，使用count()</font>
* 若元素存在，則返回個數
* 若元素不存在，則返回0
可以用以上邏輯套用到if-else condition
```cpp
if (st.count(2))
    cout << "Found" << endl;
else
    cout << "Not Found" << endl;
```

#### 取得長度
* ```st.size()```

#### 清空
* ```st.clear()```

#### 是否為空
* ```st.empty()```

#### 遍歷：使用迭代器
標準迴圈
```cpp
for (auto it = st.begin(); it != st.end(); ++it)
    // do something
```
For each
```cpp
for (auto& ele : st)
    // do something
```
#### 找min/max
```cpp
// min
cout << *st.begin();
```
```cpp
// max
cout << *st.rbegin();
```

### 2. 使用情形
* 去除重複
* 維護順序
* 判斷元素是否出現過(測資範圍如果太大，用binary array會無法做，這時就可以用set)

### 3. 注意事項
* 也無法使用\[\]運算子來進行存取
* 元素只能讀，不能修改，若要修改要先erase()
* <font color="orange">set的迭代器無法計算index</font>


---
## Map
* ```#include <map>```

| 性質 | map | multimap |unordered_map |
| -------- | -------- | -------- | -------- |
| key只能出現一次    | O     | X (任意次)    |  O  |
| key沒有順序   | X (升序)    | X (升序)     |O     |


### 1. 常用語法
```map<key_type, value_type, compare> mp```
- key_type: key值類型
- value_type: value類型
- compare: 比較器


#### 插入 - $O(LogN)$
* ```mp[key] = value```
* 如果key值不存在，就會新增一個kv pair，value預設值會是0
* ```mp.erase(key)```

#### 查找 - $O(LogN)$
* 找到：返回該元素的迭代器
* 沒找到：返回end()迭代器
``` if (mp.find(key) == mp.end())```

#### 取得長度
* ```mp.size()```

#### 清空
* ```mp.clear()```

#### 是否為空
* ```mp.empty()```

#### 遍歷：使用迭代器
* 內部元素是pair，要取得key或value就要使用first, second
* 記得迭代器是類似指標的東西，所以要用->去訪問
```cpp
	for (auto it = mp.begin(); it != mp.end(); ++it)
		cout << it->first << ", " << it->second << endl;
```
For each
```cpp
for (auto& ele : st)
    // do something
```

### 2. 使用情形
* 統計元素出現次數

### 3. 注意事項
* 使用\[ \]運算子時，如果key值不存在，value會變成預設值
* <font color="orange">map的迭代器無法計算index</font>

---
## String
```#include <string>```

### 1. 常用語法
#### 創建
```cpp
string s1;
string s2 = "something";
```

#### 修改、查詢
```s[i]```

#### 是否相等
```s1 == s2```

#### Concatenate
```s1 + s2```

#### Append
```s1 += s2```

#### Substring
```s1.substr(starting index, substring length)```


#### Find
```s1.find(s2, [starting index])```

if-else
<font color="orange">**string::npos**</font>會返回一個數字，如果沒找到可以直接跟這個數比
```cpp
string s = "123123456789";

if (s.find("321") == string::npos)
    cout << "not found" << endl;
else
    cout << "found" << endl;
```


#### Type Casting
| From | To | Syntax |
| -------- | -------- | -------- |
| int / long long / float / double / long double | 	string | to_string() |
| string | 	int | stoi() |
| string | 	long long | stoll() |
| string | 	float | stof() |
| string | 	double | stod() |
| string | 	long double | stold() |


### 2. 使用情形
萬用，不要再用字元陣列了

### 3. 注意事項
* <font color="orange">**拼接的時候一定要用 ```+=```**</font>
* .substr()**第二個參數是『子字串長度』**！
* **.find()的時間複雜度是$O(n^2)$**

---
## pair
```#include <utility>```

### 1. 常用語法
#### 創建
```cpp
pair<int, int> p1;
pair<int, long long> p2;
pair<char, int> p3;
```
#### 賦值
old version
```cpp
pair<int, char> pr = make_pair(1, 'a');
```

after c++11
```cpp
pair<int, char> pr = {1, 'a'};
```

#### 取值
* 取第一個值: ```.first()```
* 取第二個值: ```.second()```


---
---
# 演算法
## 常用函數
* swap()
* reverse()
    * ```.reverse(v.begin(), v.end())```
* unique()
    * 消除相鄰元素的重複值
    * 單獨使用並不能達成去除重複的效果，所以要加上排序
    * 消除後，尾部會出現一些無效資料，所以要配合erase
    * **```arr.erase(unique(arr.begin(), arr.end()), arr.end())``` 可以直接背下來**
    * Example
    ```cpp
    vector<int> arr{1, 2, 1, 4, 5, 4, 4};
	
	sort(arr.begin(), arr.end());
	// before 1 1 2 4 4 4 5
	// after 1 2 4 5 * // unique返回值就是*的位置，所以從*開始刪除到結尾
	arr.erase(unique(arr.begin(), arr.end()), arr.end());
	
	for (auto& ele : arr)
		cout << ele << ", ";
    ```
* sort()
    * 預設(升序): ```sort(v.begin(), v.end())```
    * 降序: ```sort(v.begin(), v.end(), greater<int>());``` 
        <font color="orange">**(記得greater\<int\>要加小括號)**</font>
    * 特殊排序(自定義排序): <font color="orange">**記得不要加等號**</font>
    ```cpp
    bool cmp(pair<int, int> a, pair<int, int> b)
    {
        if (a.second != b.second)
            return a.second < b.second;
        return a.first > b.first
    }

    int main()
    {
        vector<pair<int, int>> arr{{0, 1}, {2, 9}, {8, 1}, {0, 0}};
        sort(arr.begin(), arr.end(), cmp);
        return 0;
    }
    ```
* **lower_bound() / upper_bound(): binary search分支，一定要排序**
    * <font color="orange">**lower_bound(): 尋找 >=x 的第一個元素位置**</font>
    * <font color="orange">**upper_bound(): 尋找 >x 的第一個元素位置**</font>
    * <font color="orange">**因為返回的是迭代器，因此可以減去.begin()得到index**</font>
    
    Example:
    ```cpp
    vector<int> v{0, 1, 1, 1, 8, 9, 9};

    int pos = lower_bound(v.begin(), v.end(), 8) - v.begin();
    cout << pos << endl; // 4

    pos = upper_bound(v.begin(), v.end(), 8) - v.begin();
    cout << pos << endl; // 5
    ```
* max() / min()