# C++ STL --- # 前言 ---- # 資料結構 ---- ## 資料結構簡介 https://hackmd.io/GnFwiUwjQCmnxYsYL3DtNg#/10 --- # STL是什麼? ---- ## Standard Template Library #### (標準樣板函式庫) ---- #### STL 包含一組通用的模板類和函數，可以省下手刻的麻煩 --- # Vector(向量) ---- vector 是一種動態的陣列，提供了快速的插入和刪除操作(就像python的list)  圖片來源：Colin用Google試算表畫的 ---- | 常用成員函式 | 功用| | ------ | -------- | |push_back()|將元素複製到vector後端| | emplace_back() | 將元素建構到vector後端 | | size() | 回傳vector有幾個元素 | | operator[x] | 取得第x個元素的值 | |clear() | 清空vector| ---- ### 範例 ```cpp= #include <vector> using namespace std; int main(){ vector<int> vec; vec.push_back(1); cout<<vec[0]; } ``` --- # Stack(堆疊) ---- stack 是一種後進先出（Last-In-First-Out, LIFO）的線性資料結構，每次取出的資料是最晚放進去的資料。  圖片來源：Programiz ---- | 常用成員函式 | 功用| | ------ | -------- | |push()|將元素放入stack頂端| | pop() | 從stack頂端移出一個元素 | | top() | 取得stack頂端的元素 | | size() | 回傳stack有幾個元素| |empty()|判斷stack是否為空| ---- ### 範例 ```cpp= #include <iostream> #include <stack> using namespace std; int main() { stack<int> s; s.push(1); // 1 s.push(2); // 1 2 s.push(3); // 1 2 3 cout << s.top()<<endl; // 3 s.pop(); // 1 2 cout << s.top(); // 2 } ``` ---- # 練習 ## CSDC31 ---- ```cpp= #include<iostream> #include<stack> using namespace std; int main(){ string str; stack <int> s; int n; while(cin>>str){ if(str=="push"){ //push cin>>n; s.push(n); }else if(str=="pop"){ //pop cout<<S.top()<<endl; s.pop(); } } } ``` ---- # 應用 DFS、括號匹配、後序式運算 --- # Queue(佇列) ---- queue 是一種先進先出（First-In-First-Out, FIFO）的線性資料結構，每次取出的資料是最晚放進去的資料。  圖片來源：Programiz ---- | 常用成員函式 | 功用| | ------ | -------- | |push()|將元素放入queue前端| | pop() | 從queue後端移出一個元素 | | front() | 取得queue前端的元素 | |back()|取得queue後端的元素| | size() | 回傳queue有幾個元素| |empty()|判斷queue是否為空| ---- ### 範例 ```cpp= #include <iostream> #include <queue> using namespace std; int main() { queue<int> q; q.push(1); // 1 q.push(2); // 1 2 q.push(3); // 1 2 3 cout << q.front()<<endl; //1 q.pop(); // 2 3 cout << q.front(); // 2 } ``` ---- # 應用 BFS --- # set(集合) ---- set 是一個關聯式容器，set 容器裡面的元素是唯一的，具有不重複的特性，而且是有排序的容器，set 容器裡面元素的值是不可修改，但 set 容器可以插入或刪除元素。 ---- | 常用成員函式 | 功用| | ------ | -------- | |insert()|將元素插入到set| | erase() | 將指定元素從set刪除 | | count() | 判斷指定元素是否存在set中 | |find()|判斷指定元素是否存在set中| |size() | 回傳set有幾個元素| ---- ### 範例 ```cpp= #include <iostream> #include <set> #include <iterator> using namespace std; int main() { set<int> S = {5, 4, 3, 2, 1}; // 1 for (set<int>::iterator it = S.begin(); it != S.end(); ++it) { cout << *it << ' '; } cout << '\n'; S.insert(6); //插入6 S.erase(3); //插入3 // 2 for (auto it = S.begin(); it != S.end(); ++it) { cout << *it << ' '; } cout << '\n'; // 3 for (auto it : S) { cout << it << ' '; } cout << '\n'; return 0; } ``` ---- # 練習 ## CSDC163 ---- ```cpp= #include<iostream> #include<set> using namespace std; int main(){ set<int>s; int n; cin>>n; for(int i=0;i<n;i++){ int x; cin>>x; s.insert(x); } cout<<s.size(); //set大小 = 不重複的數量 } ``` --- # Map(集合 key-value) ---- map 是一個關聯式容器，用於存儲鍵-值對。map 提供了一種有效的方式來將鍵映射到相應的值，並且根據鍵的排序方式保持它們的有序性。 ---- | 物件 | | | ------ | -------- | |first|map的第一個變數(key)| | second | map的第二個變數(value) | ---- | 常用成員函式 | 功用| | ------ | -------- | |operator[x]|取得key為x的value| | insert() | 將pair<key,value>插入map | | erase() | 將指定元素從map刪除 | | find() | 判斷指定元素的key值是否存在map中 | |count() | 判斷指定元素的key值是否存在map中| |size()|回傳map有幾個元素| ---- ### 範例 ```cpp= #include <iostream> #include <map> using namespace std; int main(){ map<int, string> m; m[1] = "colin"; //插入{1,"colin"} m[2] = "yen"; //插入{2,"yen"} m.erase(1) for(auto i:m){ cout << i.first << ' ' << i.second << endl; } } ``` --- # Priority Queue(堆積) ---- priority_queue，實現了一個優先級隊列的數據結構。優先級隊列是一種特殊的容器，其中的元素按照一定的優先級進行排序，並且在操作時，具有最高優先級的元素會最先被取出。 ---- | 常用成員函式 | 功用| | ------ | -------- | |push()|將元素放入priority_queue| | pop() | 將priority_queue中優先級最高的元素刪除 | | top() | 取得priority_queue中優先級最高的元素 | | empty() | 判斷priority_queue是否為空 | |size() | 回傳priority_queue中有幾個元素| ---- ### 範例 ```cpp= #include <queue> ``` ---