C++ STL - HackMD

# 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，可以自定義 **預設是max heap，如果要改成min heap需要傳入greater仿函式** ```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 } ``` #### 另一種查找方式，使用count() * 若元素存在，則返回個數 * 若元素不存在，則返回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() * set的迭代器無法計算index --- ## 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會變成預設值 * map的迭代器無法計算index --- ## 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 **string::npos**會返回一個數字，如果沒找到可以直接跟這個數比 ```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. 注意事項 * **拼接的時候一定要用 ```+=```** * .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>());``` **(記得greater\<int\>要加小括號)** * 特殊排序(自定義排序): **記得不要加等號** ```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分支，一定要排序** * **lower_bound(): 尋找 >=x 的第一個元素位置** * **upper_bound(): 尋找 >x 的第一個元素位置** * **因為返回的是迭代器，因此可以減去.begin()得到index** 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()