# STL Container STL 容器 --- - Stack - Queue - Deque - Vector - Map - Set - List --- # Stack & Queue ---- ## Stack 後進先出(LIFO, Last-in-First-out) 先進後出(FILO, First-in-Last-out) **ex.** 疊盤子 ---- \<stack\> ```cpp std::stack<T> mystack // 宣告 mystack.push(val); // 加入元素（把書放在最上面，只能放在尾） mystack.pop(); // 刪除元素（拿走最上面的一本書，只能刪除尾） T t = mystack.top(); // 看看最後一個元素 bool emp = mystack.empty(); // 是空的嗎？ int size = mystack.size(); // 有幾個元素？ ``` ---- ## Queue 先進先出(FIFO, First-in-First-out) **ex.** 排隊、等公車 ---- \<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(); // 有幾個元素？ ``` ----  --- # Deque ---- ### stack + queue  ---- \<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(); // 有幾個元素 ``` --- # Vector ---- ### Dynamic Array  ---- capacity ```cpp query : size_t capacity() modify : void reserve(size_t) ``` size ```cpp query : size_t size() modify : void resize(size_t) ``` ----  ---- \<vector\> ```cpp std::vector<T> mv; std::vector<T> mv2(n); // 放n個東西 std::vector<T> mv3(n,val); // 放n個val mv.push_back(val); // 把資料放在最後面 mv.pop_back(); // 刪除最後面的資料 bool emp = mv.empty(); // 是空的嗎 int size = mv.size(); // 有幾個元素 ``` --- # Iterator 迭代器 ---- ### Declaration ##### Pointer ```cpp int arr[10]; int* ptr = arr; // 指標指向陣列的頭 ``` ##### Container Pointer ```cpp vector<int> vec; vector<int>::iterator it; it = vec.begin(); // 迭代器指向vec的頭 it = vec.end(); // 迭代器指向vec的尾 ``` ---- ### Loop & Search ##### Pointer ```cpp int arr[10]; for(ptr = arr ; ptr-arr<10 ; ptr++) cout<<(*ptr); ``` ##### Container Pointer ```cpp vector<int> vec; for(vector<int>::iterator it = vec.begin() ; it!=vec.end() ; it++) cout<<(*it); ``` --- # Map & Set ---- ### Red Black Tree (R-B Tree)  \<map\> \<set\> \<multimap\> \<multiset\> ---- ### Hash Table  \<unordered_map\> \<unordered_set\> \<unordered_multimap\> \<unordered_multiset\> ---- \<map\> ```cpp std::map<T1, T2> m; // 空的map std::map<string, int> id; id["Sally"] = 1; id.insert(make_pair("Hsia",2)); id.insert(std::pair<string, int>("Wan",3)); cout<<id["Hsia"]; // 查詢 id.erase("Wan"); // 消除一個特定key id.erase(id.find("Hsia")); // 消除一個特定的位置 id.size(); // 有幾個元素 id.empty(); // 是空的嗎 // 遍歷所有的(key,value) std::map<string, int>::iterator it; for(it = id.begin() ; it != id.end() ; it++) cout<<'('<<it->first<<','<<it->second<<")\n"; ``` ---- \<set\> ```cpp std::set<T> m; // 空的set std::set<char> alpha; char arr[] = {'b','c','d','e'}; alpha.insert('a'); // 放一個 alpha.insert(arr,arr+4); // 放好多個 if(alpha.find('b') != alpha.end()); // 有沒有元素 if(alpha.count('b'); // 有沒有元素 alpha.erase('a'); // 消除一個特定key alpha.erase(alpha.find('b')); // 消除一個特定的位置 alpha.size(); // 有幾個元素 alpha.empty(); // 是空的嗎 // 遍歷所有的元素 std::set<char>::iterator it; for(it = alpha.begin() ; it != alpha.end() ; it++) cout<<*it<<' '; ``` --- # List ##### Double Linked List  ---- \<list\> ```cpp std::list<T> m; // 空的list std::list<int> ls; int arr[] = {1,2,3,4}; ls.insert('a'); // 放一個 ls.insert(arr,arr+4); // 放好多個 ls.insert(4,100); // 放4個100 if(ls.find('b') != ls.end()); // 有沒有元素 if(ls.count('b'); // 有沒有元素 ls.erase('a'); // 消除一個特定key ls.erase(ls.find('b')); // 消除一個特定的位置 ls.size(); // 有幾個元素 ls.empty(); // 是空的嗎 // 遍歷所有的元素 std::list<int>::iterator it; for(it = ls.begin() ; it != ls.end() ; it++) cout<<*it<<' '; ``` ---