--- ###### tags: `sprout` --- # STL Container *slide: https://hackmd.io/@htting/HksIP5wiI#/* *slido: 99601* *2020/6/6 丁緒慈* --- ## 資料結構 *你會怎麼儲存這些資料*    ---- 電腦中儲存、組織資料的方式，就成為資料結構  ---- *等等...那 STL 又是甚麼* - Standard Template Library - 包含資料結構與演算法的模板 -> 不用慢慢刻啦 --- ## Queue  跟排隊一樣，先進先出（First In First Out） - 把東西塞進去的動作叫做 enqueue - 把東西拿出來的動作叫做 dequeue ---- ### [函式庫](http://www.cplusplus.com/reference/queue/queue/) *使用前記得 #includle <queue>* ```cpp std::queue<T> myqueue // 宣告 myqueue.push(val); // 加入元素（不能插隊，只能放在尾端） myqueue.pop(); // 刪除元素（讓排頭離開隊伍，只能刪除頭） ``` T 可以是任何資料型態 （int、char、自己寫的 struct、STL container） 注意：對空的 queue pop 會噴錯 ---- ### [函式庫](http://www.cplusplus.com/reference/queue/queue/) ```cpp std::queue<T> myqueue // 宣告 myqueue.push(val); // 加入元素（不能插隊，只能放在尾端） myqueue.pop(); // 刪除元素（讓排頭離開隊伍，只能刪除頭） T f = myqueue.front(); // 看看第一個元素 T b = myqueue.back(); // 看看最後一個元素 bool emp = myqueue.empty(); // 是空的嗎？ int size = myqueue.size(); // 有幾個元素？ ``` 這些都是O(1)操作 ---- ### Example 想想看會輸出甚麼 ```cpp= #include <iostream> #include <queue> int main() { std::queue<int> myqueue; myqueue.push(0); myqueue.push(1); myqueue.push(2); myqueue.pop(); myqueue.push(3); myqueue.pop(); std::cout << "first element = " << myqueue.front() << "\n"; std::cout << "last element = " << myqueue.back() << "\n"; std::cout << "#element = " << myqueue.size() << "\n"; } ``` ---- ### Example Answer ```cpp myqueue.push(0); // 0 myqueue.push(1); // 0 1 myqueue.push(2); // 0 1 2 myqueue.pop(); // 1 2 myqueue.push(3); // 1 2 3 myqueue.pop(); // 2 3 ``` first element = 2 last element = 3 #element = 2 ---- ### 課堂練習 [Neoj 37 Queue 練習](https://neoj.sprout.tw/problem/37/) --- ## Stack  如果要你拿一本書，你會拿哪一本 如果要你把一本書放到這堆裡面，你會放在哪裡 後進先出的資料型態（Last In First Out） ---- ### [函式庫](http://www.cplusplus.com/reference/stack/stack/) *使用前記得 #includle <stack>* ```cpp std::stack<T> mystack // 宣告 mystack.push(val); // 加入元素（把書放在最上面，只能放在尾） mystack.pop(); // 刪除元素（拿走最上面的一本書，只能刪除尾） T t = mystack.top(); // 看看最後一個元素 bool emp = mystack.empty(); // 是空的嗎？ int size = mystack.size(); // 有幾個元素？ ``` T 可以是任何資料型態 這些都是O(1)操作 ---- ### Example 想想看會輸出甚麼 ```cpp= #include <iostream> #include <stack> int main() { std::stack<int> mystack; mystack.push(0); mystack.push(1); mystack.push(2); mystack.pop(); mystack.push(3); mystack.pop(); std::cout << "last element = " << mystack.top() << "\n"; std::cout << "#element = " << mystack.size() << "\n"; } ``` ---- ### Example Answer ```cpp mystack.push(0); // 0 mystack.push(1); // 0 1 mystack.push(2); // 0 1 2 mystack.pop(); // 0 1 mystack.push(3); // 0 1 3 mystack.pop(); // 0 1 ``` last element = 1 #element = 2 ---- ### 課堂練習 [Neoj 36 Stack 練習](https://neoj.sprout.tw/problem/36/) --- ## Deque - 念作 deck - Double-Ended QUEue - 小孩子才做選擇，我全都要  ---- ### [函式庫](http://www.cplusplus.com/reference/deque/deque/) *使用前記得 #includle <deque>* ```cpp std::deque<T> mydeque; // 宣告 mydeque.push_back(val); // 把資料放在最後面 mydeque.push_front(val); // 把資料放在最前面 mydeque.pop_back(); // 刪除最後面的資料 mydeque.pop_front(); // 刪除最前面的資料 T f = mydeque.front(); // 查看最前面的資料 T b = mydeque.back(); // 查看最後面的資料 bool emp = mydeque.empty(); // 是空的嗎？ int size = mydeque.size(); // 有幾個元素 ``` T 可以是任何資料型態 這些都是O(1)操作 ---- ### Example 想想看會輸出甚麼 ```cpp #include <iostream> #include <string> #include <deque> using namespace std; struct student { int id; string name; student(int _id, string _name) { id = _id; name = _name; } }; int main() { deque<student> s; s.push_back(student(15, "Alice")); s.push_front(student(23, "Bob")); s.push_front(student(32, "Carol")); std::cout << s.back().name << "\n"; s.pop_back(); std::cout << s.front().name << "\n"; s.pop_front(); std::cout << s.back().name << "\n"; } ``` ---- ### Example Answer ```cpp s.push_back(student(15, "Alice")); // {15, Alice} s.push_front(student(23, "Bob")); // {23, Bob} {15, Alice} s.push_front(student(32, "Carol")); // {32, Carol} {23, Bob} {15, Alice} std::cout << s.back().name << "\n"; s.pop_back(); // {32, Carol} {23, Bob} std::cout << s.front().name << "\n"; s.pop_front(); // {23, Bob} std::cout << s.back().name << "\n"; ``` --- ## Vector ```cpp #include <iostream> int main() { int n; std::cin >> n; int arr[n] = {}; // WRONG!!! } ``` ```cpp #include <iostream> int main() { int n; int arr[1000000000] = {}; // 沒有更好的方法嗎 } ``` ---- ### Dynamic Array  空間滿了再擴充到兩倍 ---- ### Vector - 就是一種 Dynamic Array - 宣告 ```cpp std::vector<T> mv1; // 空的vector std::vector<T> mv2(n); // 放n個東西 std::vector<T> mv3(n,val); // 放n個val ``` ---- ### [函式庫](http://www.cplusplus.com/reference/vector/vector/) *使用前記得 #includle <vector>* ```cpp std::vector<T> mv mv.push_back(val); // 把資料放在最後面 mv.pop_back(); // 刪除最後面的資料 bool emp = mv.empty(); // 是空的嗎 int size = mv.size(); // 有幾個元素 ``` ---- ### Example 想想看會輸出甚麼 ```cpp #include <iostream> #include <vector> using namespace std; int main() { vector<int> mv; for(int i = 0; i<5; ++i) mv.push_back(i); mv[3] = 100; // 就像陣列 mv.pop_back(); for(int i = 0; i<mv.size(); ++i) cout << mv[i] << " "; } ``` ---- ### Example Answer ```cpp #include <iostream> #include <vector> using namespace std; int main() { vector<int> mv; for(int i = 0; i<5; ++i) mv.push_back(i); // 0 1 2 3 4 mv[3] = 100; // 0 1 2 100 4 mv.pop_back(); // 0 1 2 100 for(int i = 0; i<mv.size(); ++i) cout << mv[i] << " "; } ``` 0 1 2 100 ---- 如果要對 Vector 中間的元素做操作呢？ 例如 刪除中間的元素、在中間插入元素 --- ## Iterator - 迭代器 - 可以想成 STL 的指標 ---- ### Recall - 宣告一個指標 ptr - int *ptr; - double *ptr; - int arr[10] - 開頭指標：arr / 結尾指標：arr + 10 - 看看指標指向甚麼 - *ptr - 變成下一個 pointer - ptr++ ---- ### Vector & Iterator - 宣告 - vector<int>::iterator iter - vector<int> mv - 開頭指標：mv.begin() - 結尾指標：mv.end() - 看看 iterator 指向甚麼 - *iter - 變成下一個 iterator - iter++ ---- ### Vector & Iterator  ---- ### 遍歷所有元素  ```cpp vector<int>::iterator iter; for(iter = mv.begin(); iter!=mv.end(); iter++) cout << *iter << " "; ``` ---- ### 插入 & 刪除  ```cpp mv.insert(mv.begin()+2, 3); mv.erase(mv.begin()+1); ``` ---- ### auto ```cpp vector<int>::iterator iter = mv.begin(); auto iter = mv.begin(); ``` - 一般的變數不會使用 - 有正確的型別概念才可以使用 ---- ### auto  ```cpp for(auto iter = mv.begin(); iter != mv.end(); iter++) cout << *iter << " "; ``` ---- ### Range-based For ```cpp for(auto i : mv) cout << i << " "; ``` ---- ### 注意！ 會輸出幾個'#' ```cpp vector<int> v(10); for(auto i = v.size() ; i>=0 ; i--){ cout << '#'; } ``` --- ## List - double linked-list  ---- ### [函式庫](http://www.cplusplus.com/reference/list/list/) *使用前記得 #includle <list>* ```cpp std::list<T> mylist // 宣告 mylist.push_front(val); // 把資料放在最前面 mylist.push_back(val); // 把資料放在最後面 mylist.pop_front(); // 刪除最前面的資料 mylist.pop_back(); // 刪除最後面的資料 std::list<T>::iterator it1 = mylist.begin(); std::list<T>::iterator it2 = mylist.end(); mylist.insert(it, val); mylist.erase(it); ``` 注意：list 的 iterator 可以 ++、-- 但不能 +=k ----  ---- ### Example  ```cpp std::list<int> mylist; for(int i = 0; i<5; ++i) mylist.push_back(i); for(auto i : mylist) cout << i << " "; cout << "\n"; ``` ---- ### erase  ```cpp // 刪除 3 auto to_delete = mylist.begin(); for(int i = 0; i<3; ++i) to_delete++; mylist.erase(to_delete); for(auto i : mylist) cout << i << " "; cout << "\n"; ``` ---- ### insert  ```cpp // 把 5 插入在 2 之前 auto to_insert = mylist.begin(); for(int i = 0; i<2; ++i) to_insert++; mylist.insert(to_insert, 5); for(auto i : mylist) cout << i << " "; cout << "\n"; ``` ---- 感覺 list 可以取代 stack, queue, deque和vector？？？ ---- 雖然 list 包含了很多好用的函式庫 但代價是速度很慢