# 進階STL：vector ## 2021/11/19 電算社第九堂社課 --- ## STL ？ standard template library（標準模板庫） 更多的資料結構 ---- 複習一下之前遇到的資料結構 std::string 字串 ex `string s = "C8763";` c-array （c式陣列） ex `int arr[100] = {0};` 除了這兩種，我們之後會學到更多種類的資料結構。 --- ## STL簡介 ---- 將來會學到的東西 一覽 `vector` `queue` , `stack` , `deque` `set` , `map` `priority_queue` （可能有更動） --- ## c-array ---- ```cpp= #include<iostream> using namespace std; int main() { int arr[10]; for(int i=0 ; i<10 ; i++) cin >> arr[i]; int found = 5 cout << arr[found]; } ``` ---- ### 缺點 1. 使用長度固定（size改不了） 2. 存取size之外的位置，程式會直接crash --- ## vector ---- What is "vector" -> 多功能陣列 ---- ### 標頭檔 ```cpp= #include<vector> ``` ---- ### 宣告 ```cpp= #include<vector> using namespace std; // 沒打的話，vector前面要加 std:: vector <type> name(size , memset); //最完整的寫法 // or vector <type> name(); // size = 0 , memset = 0 ``` ---- ### 初始化 ```cpp= #include<vector> #include<iostream> using namespace std; int main() { vector<int> v(10 , -1); // {-1,-1,-1,-1,-1,-1,-1,-1,-1-,-1} cout << v[9]; // -1 } ``` `Tips： 除了初始化，剩下的時候，c-array的用法，vector都可以用。` `但是 vector 多了很多功能` ---- ### 缺點 1. n維陣列宣告要打超長 （下面會詳細說明） 2. 要打標頭檔 `#include<vector>` --- ## 功能 ---- ### 空間相關功能 <font color="#FFF300">v.empty() ： </font> if v 的 size 為 0 ，回傳 1 ， else 回傳 0。 <font color="#FFF300">v.size() ： </font> 輸出 v 的 size <font color="#FFF300">v.resize( , ) ： </font> 重新分配空間 - 像是一開始初始化的`( , )` <font color="#FFF300">v.clear() ： </font> 把 v 清空 ---- ```cpp= #include<iostream> #include<vector> using namespace std; int main() { vector<int> v(3,5); // 5 5 5 cout << v.empty() << " " << v.size() << "\n"; // 0 3 v.resize(5,2); // 2 2 2 2 2 v.clear(); // } ``` ---- ### 位置相關功能 （假設 v 的 size 為 5） v.front() ： `v[0]` 的值 v.back() ： `v[4]` 的值 v.begin() ： `v[0]` 的**偽指標** v.end() : **`v[5]`** 的**偽指標** // 它常會跟其他功能一起用 ---- ```cpp= #include <iostream> #include <vector> using namespace std; int main(){ vector<int> v = {1,2,3,4,5,6,7,8,9,10}; cout << v.front(); // 1 cout << v.back(); // 10 cout << v.end() - v.begin(); // 10 (v.size()); } ``` ---- ### 資料相關功能 v.push_back() v.pop_back() ---- ```cpp= #include <iostream> #include <vector> using namespace std; int main(){ vector<int> v; // (size = 0) v.push_back(1); // 1 v.push_back(2); // 1 2 v.pop_back(); // 1 } ``` ---- ### Vector額外功能 刪除或新增中間的第 i 項 v.insert(v.begin() + i, a)：在第 i 項插入a v.erase(v.begin() + i)：把第 i 項移掉 ```cpp= #include<iostream> #include<vector> using namespace std; int main(){ vector<int> v(5); // size = 5 for(int i = 0 ; i < 5 ; i++) v[i] = 2 * i; // {0 , 2 , 4 , 6 , 8} v.erase(v.begin() + 0); // 2 4 6 8 v.erase(v.begin() + 2 , v.begin() + 3); // 2 4 8 v.insert(v.begin() + 1 , 5); // 2 5 4 8 } ``` --- ## algorithm x vector ---- ### sort ```cpp= #include <iostream> #include <vector> #include <algorithm> // sort的函式庫 using namespace std; int main(){ vector<int> v = {5,6,3,1,2,9,8,7,0,4}; sort(v.begin(), v.end()); for(int i = 0; i < 10; i++){ cout << v[i] << ' '; // 0 1 2 3 4 5 6 7 8 9 } sort(v.begin(), v.begin() + 5, greater<int>()); for(int i = 0; i < 10; i++){ cout << v[i] << ' '; // 4 3 2 1 0 5 6 7 8 9 } } ``` ---- ### upper_bound , lower_bound `upper_bound(v.begin() , v.end() , num);` 第一個 **大於** num 的偽指標（類似 `v.begin()` ）; `lower_bound(v.begin() , v.end() , num);` 第一個 **大於等於** num 的偽指標（類似 `v.begin()` ）; **使用前，陣列要先 <font color="#F00">由小到大</font> 排列過** ---- ```cpp= #include<iostream> #include<algorithm> #include<vector> using namespace std; int main() { vector<int> v(10); for(int i=0 ; i<10 ; i++) v[i] = i*2; // {0, 2, 4, 6, 8, 10, 12, 14, 16, 18} cout << upper_bound(v.begin() , v.end() , 14) - v.begin(); // 8 cout << lower_bound(v.begin() , v.end() , 14) - v.begin(); // 7 } ``` --- ### 二維陣列 ---- ```cpp= vector< vector<type> > name(size1 , vector<type>(size2 , memset)); type name[size1][size2]; ``` ---- ```cpp= #include <iostream> #include <vector> using namespace std; int main(){ vector<vector<int>> v(2, vector<int>(3, 2)); // { {2, 2, 2}, {2, 2, 2} } int arr[2][3]; for(int i = 0; i < 2; i++){ for(int j = 0; j < 3; j++){ arr[i][j] = i + j; } } // 0 1 2 // 1 2 3 } ``` --- ## 小練習 卡森社長找到了一個好玩的機器，上面有兩個按鈕，按1可以放入一顆球，按2可以從最前端射出一顆球，現在卡森社長要進行$n$輪操作，你可以幫他看看最終機器裡面剩下的球依序為何嗎 ---- 輸入說明：輸入一個整數$n$，代表會有$n$輪操作，接著輸入數字$m$，代表要按的按鈕，若$m = 1$，則輸入一個數字$k$，代表放入球的編號 輸出說明：輸出最後機器裡剩下的球依序為何 範例輸入： ``` 5 1 2 1 3 1 4 2 2 ``` 範例輸出：`4` ---- 我是防雷頁:D ---- ```cpp= #include <iostream> #include <vector> using namespace std; int main(){ vector<int> v; int n; cin >> n; for(int i = 0; i < n; i++){ int m; cin >> m; if(m == 1){ int k; cin >> k; v.push_back(k); } if(m == 2){ if(!v.empty()){ v.erase(v.begin() + 0); } } } for(int i = 0; i < v.size(); i++){ cout << v[i] << ' '; } return 0; } ``` --- ## OJ練習題 [zerojudge a104排序](https://zerojudge.tw/ShowProblem?problemid=a104)