<style> .reveal .slides { text-align: left; font-size:30px; } </style> ## STL ---- <div style="font-size:30px"> - STL - pair / tuple - vector - iterator - priority_queue - stack / queue - set / multiset - map / multimap </div> ---- ### pair 常用來儲存一組的資料(Ex:平面上的(x,y)) * 宣告 ```cpp pair<int,int> pair<double,int> ``` * 取值 ```cpp= pair<int,int> a a.first (可以取到第一個值) a.second (可以取到第二個值) ``` ---- ### vector ```cpp= #include <vector> //宣告 vector<int> v; vector<int> v(n,m); n:陣列開的大小, m:想要陣列初始化的值 vector<vector<int>> v; vector二維陣列 ``` ---- - 常用函式: push_back , pop_back , size , empty , begin , end clear, resize, assign ```cpp= #include <iostream> #include <vector> // vector 的標題檔 using namespace std; int main() { vector<int> v; //宣告一個 vector 名稱叫 v 用來裝 int 元素 for (int i=1; i<=5; i++) v.push_back(i); for (int i=5; i>=1; i--) v.push_back(i); cout << v.size() << "\n"; for (int i=1; i<=4; i++) v.pop_back();// 將 vector 尾端元素刪掉 cout << v.size() << "\n"; cout << v.empty() << "\n"; // empty() 函式為查詢 vector 裡面是否有元素 // 回傳值為 bool v.clear(); } ``` ---- - vector可以使用iterator來遍歷，你可以把iterator想成是類似指標的東西! ```cpp= #include <iostream> #include <vector> using namespace std; int main() { vector<int> vt; vector<int>::iterator iter; for (int i=95; i<=100; i++) { vt.push_back(i); } iter = vt.begin(); for(iter = vt.begin(); iter != vt.end(); iter++) { cout << *iter << "\n"; // 一定要 「 * 」 號 } } ``` ---- ### stack 一種先進後出的資料結構，先放進去的會最慢拿出來 - stack的常用函式 : push , size , empty , top , pop - 不支援隨機存取：O(N) 查找速度慢：O(N) 在集合中增刪元素很快：O(1) ---- 實際演練: ```cpp= #include <iostream> #include <stack> // stack 的標題檔 using namespace std; int main() { stack<int> Stk; //宣告一個 stack 名稱叫 stk 用來裝int元素 for (int i=4; i<=10; i++) { Stk.push(i); } cout << Stk.top() << "\n"; // 輸出 stack 最上層的元素，所以會輸出 10 Stk.pop(); // 刪除 stack 最上層的元素 cout << Stk.top() << "\n"; //9 cout << "裡面有多少元素" <<Stk.size() << "\n"; // 查詢 stk 裡面有幾個元素，裡面元素有 4 5 6 7 8 9共六個，所以會輸出 6 cout << Stk.empty() << "\n"; // empty() 函式為查詢 stack 裡面是否有元素 // 回傳值為bool //清除 stack的元素 while(Stk.size() != 0) { // 或是 while(Stk.empty == 0) Stk.pop(); //O(N) } cout << "裡面有多少元素" << Stk.size() << "\n"; cout << Stk.empty() << "\n"; } ``` ---- # stack的超經典題! 括號配對 判斷一串括號"{}","()","[]"是否都能成功配對 想法: - 有左括號就一定有右括號 - 越晚出現的左括號，其所對應的右括號就越早出現! ---- ### queue 一種先進先出的資料結構 - queue的常用函式 : push , size , empty , front , pop . - 不支援隨機存取：O(N) 查找速度慢：O(N) 在集合中增刪元素很快：O(1) ---- 實際演練: ```cpp= #include <iostream> #include <queue> // queue 的標題檔 using namespace std; int main() { queue<int> que; //宣告一個 queue 名稱叫 que 用來裝int元素 //一開始裡面的容器是空的 for (int i=4; i<=10; i++) { que.push(i); } cout << que.front() << "\n"; // 輸出 queue 最上層的元素，所以會輸出 4 que.pop(); // 刪除 queue 最上層的元素 cout << que.front() << "\n"; // 輸出 queue 最上層的元素，所以會輸出 5 cout << "裡面有多少元素" <<queue.size() << "\n"; // 查詢 queue 裡面有幾個元素，裡面元素有 5 6 7 8 9 10共六個，所以會輸出 6 cout << que.empty() << "\n"; // empty() 函式為查詢 queue 裡面是否有元素 // 回傳值為bool 1 裡面沒有元素 0 則是 //清除 queue的元素 while(que.size() != 0) { // 或是 while(que.empty == 0) que.pop(); } cout << "裡面有多少元素" << que.size() << "\n"; cout << que.empty() << "\n"; } ``` ---- ### priority queue 排序過後的queue，其原理是用heap去排序 ---- priority_queue 的常用函式 : push , size , empty , *top , pop . ---- 實際演練: ```cpp= #include <queue> priority_queue<int> pq; priority_queue<int, vector<int>, greater<int> > pq1; //從小到大 變成min_heap pq.push(5); pq.push(8); pq.push(4); // 元素可重複，會個別保留 pq.push(5); cout << pq.size() << "\n"; cout << pq.top() << "\n"; pq.pop(); cout << pq.size() << "\n"; cout << pq.top() << "\n"; cout << pq.empty() << "\n"; ``` ---- ### set ``` #include<set> ``` ---- - set 是有序的，對 set 遍歷時，會以定義的大小順序遍歷，預設是由小到大 - 大多數操作皆為 $O(\log N)$ - set 的常用函式：insert, erase, count, size, empty, begin, end, lower_bound, upper_bound ---- 實際演練 ```cpp set<int> s; // [] s.insert(1); // s = [1] s.insert(3); // s = [1, 3] s.insert(1); // s = [1, 3] s.erase(3); // s = [1, 3] s.count(3) // return 1代表3有在集合內 s.count(4) // return 0 //找最大/最小值 cout << *s.begin() << endl; cout << *s.rbegin() << endl; ``` ---- ### map ``` #include<map> ``` 映射，基本上就是多了個對應值的set，單位型態為 pair<key,value> 用法跟 set 很像，但多了 operator[] 可以取值或存值。 ---- * 大多操作皆為 $O(\log n)$ * map 的常用函式：insert, erase, count, size, empty, begin, end, lower_bound, upper_bound. ---- ### 使用範例： ```cpp map<int, int> mp; mp[3] = 1; //[3] = 1, mp[2] = 2; //[2] = 2, [3] = 1; mp[3] = 5; //[2] = 2, [3] = 5; ``` <!-- 加個 string 當 key 的粒子--> --- 常和STL搭配的一些function ---- sort ```cpp #include<algorithm> ``` - 排序區間 [l, r) 的資料，複雜度為 $O(n\log n)$ - l, r 為指標或者迭代器 ### 範例 ```cpp= #include<iostream> #include<algorithm> // sort int arr[48763]={4, 8, 7, 6, 3}; int main(){ sort(arr,arr+5); // 3 4 6 7 8 } ``` ---- 自訂比較關係 傳入兩個參數做為比較對象 lhs代表左邊的元素, rhs代表右邊的元素 ```cpp= #include<iostream> #include<algorithm> // sort bool cmp(int lhs, int rhs){ // compare function return lhs > rhs; } int arr[5] = {3, 2, 7}; int main(){ sort(arr, arr+3, cmp); } ``` --- STL更多補充: https://hackmd.io/@LeeShoWhaodian/STLandfunction https://hackmd.io/@konchin/book/%2FuX4pl05vRpKAgiuR0XHi_g