--- ###### tags: `2021 師大附中資訊科暑期培訓` --- # 基礎資料結構與 STL 2021 師大附中資訊科暑期培訓 joylintp --- ## 什麼是資料結構？ 資料結構即為儲存資料的一種「結構」 根據目的選擇適當的資料結構搭配演算法 考慮其時間、空間、實作複雜度來解決不同的問題 --- ## 標準模板庫（STL） 標準模板庫（Standard Template Library） 提供多種基本資料結構可直接使用 ```cpp= using namespace std; ``` --- ### Pair ---- * 將兩個變數綁成一對 ---- ```cpp= pair<string, int> p = make_pair("joylintp", 87); cout << p.first << '\n'; // -> joylintp cout << p.second << '\n'; // -> 87 ``` ---- #### 初始化 ```cpp= pair<int, int> pii = make_pair(8, 7); // pii = (8, 7) ``` ```cpp= pair<int, int> pii = {8, 7}; // pii = (8, 7) ``` --- ### Stack  ---- * Last-In-First-Out * 最後一個放入stack中的元素會最先被取出 ---- ```cpp= stack<int> stk; stk.push(4); // stk = [4] stk.push(5); // stk = [4, 5] stk.push(3); // stk = [4, 5, 3] stk.pop(); // stk = [4, 5] cout << stk.top() << '\n'; // -> 5 cout << stk.size() << '\n'; // -> 2 cout << stk.empty() << '\n'; // -> 0 (false) ``` --- ### Queue  ---- * First-In-First-Out * 最先放入queue中的元素會最先被取出 ---- ```cpp= queue<int> quu; quu.push(4); // quu = [4] quu.push(5); // quu = [4, 5] quu.push(3); // quu = [4, 5, 3] quu.pop(); // quu = [5, 3] cout << quu.front() << '\n'; // -> 5 cout << quu.size() << '\n'; // -> 2 cout << quu.empty() << '\n'; // -> 0 (false) ``` --- ### Deque  ---- * deque的兩端皆可放入或取出元素 ---- ```cpp= deque<int> deq; deq.push_front(4); // deq = [4] deq.push_front(5); // deq = [5, 4] deq.push_back(3); // deq = [5, 4, 3] deq.push_back(9); // deq = [5, 4, 3, 9] deq.pop_front(); // deq = [4, 3, 9] deq.pop_back(); // deq = [4, 3] cout << deq.front() << '\n'; // -> 4 cout << deq.back() << '\n'; // -> 3 cout << deq.size() << '\n'; // -> 2 cout << deq.empty() << '\n'; // -> 0 (false) ``` --- ### Priority Queue  ---- * 取出元素時優先取出權重最高的元素 ---- ```cpp= priority_queue<int> pq; pq.push(4); // pq = [4] pq.push(5); // pq = [4, 5] pq.push(3); // pq = [3, 4, 5] pq.pop(); // pq = [3, 4] cout << pq.top() << '\n'; // -> 4 cout << pq.size() << '\n'; // -> 2 cout << pq.empty() << '\n'; // -> 0 (false) ``` ---- 若想優先取出最小的元素， 可使用內建函數greater ```cpp= priority_queue<int, vector<int>, greater<int>> pq; pq.push(4); // pq = [4] pq.push(5); // pq = [5, 4] pq.push(3); // pq = [5, 4, 3] pq.pop(); // pq = [5, 4] ``` --- ### Vector  ---- * 不定長度動態陣列 ---- ```cpp= vector<int> v; v.push_back(4); // v = [4] v.push_back(5); // v = [4, 5] v.push_back(3); // v = [4, 5, 3] cout << v[0] << '\n'; // -> 4 cout << v.size() << '\n'; // -> 3 cout << v.empty() << '\n'; // -> 0 (false) v.clear(); // v = [] cout << v.empty() << '\n'; // -> 1 (true) ``` ---- #### 初始化 ```cpp= vector<int> a; // a = [] vector<int> b(5); // b = [0, 0, 0, 0, 0] vector<int> c(5, 3); // c = [3, 3, 3, 3, 3] vector<int> d = {1, 2, 3}; // d = [1, 2, 3] ``` ---- #### 存取vector中的每個元素 ```cpp= vector<int> v = {8, 8, 0, 3, 0, 1}; for (int i = 0; i < v.size(); i++) cout << v[i] << ' '; // 8 8 0 3 0 1 ``` ```cpp= vector<int> v = {8, 8, 0, 3, 0, 1}; for (vector<int>::iterator it = v.begin(); it != v.end(); it++) cout << *it << ' '; // 8 8 0 3 0 1 ``` ```cpp= vector<int> v = {8, 8, 0, 3, 0, 1}; for (int i : v) cout << i << ' '; // 8 8 0 3 0 1 ``` --- ### Set  ---- * 集合 * set中元素遞增排序 ---- ```cpp= set<int> s; s.insert(4); // s = {4} s.insert(5); // s = {4, 5} s.insert(3); // s = {3, 4, 5} s.erase(4); // s = {3, 5} cout << s.size() << '\n'; // -> 2 cout << s.empty() << '\n'; // -> 0 (false) cout << s.count(4) << '\n'; // -> 0 cout << s.count(3) << '\n'; // -> 1 s.clear(); // s = {} cout << s.empty() << '\n'; // -> 1 (true) ``` ---- #### 初始化 ```cpp= set<int> a; // a = {} set<int> b = {1, 2, 3}; // b = {1, 2, 3} set<int> c = {1, 2, 2}; // c = {1, 2} ``` ---- #### 存取set中的每個元素 ```cpp= set<int> s = {1, 4, 8, 7, 6}; for (set<int>::iterator it = s.begin(); it != s.end(); it++) cout << *it << ' '; // 1 4 6 7 8 ``` ```cpp= set<int> s = {1, 4, 8, 7, 6}; for (int i : s) cout << i << ' '; // 1 4 6 7 8 ``` --- ### Unordered Set ---- * 也是集合 * unordered set中元素不排序 ---- ```cpp= set<int> s = {1, 4, 8, 7, 6}; for (int i : s) cout << i << ' '; // 1 4 6 7 8 ``` ```cpp= unordered_set<int> us = {1, 4, 8, 7, 6}; for (int i : us) cout << i << ' '; // 6 1 4 8 7 ``` --- ### Multiset ---- * 多重集合 * multiset中元素可重複 * 內部元素遞增排序 ---- ```cpp= set<int> s = {1, 1, 4, 8, 7, 6, 7}; for (int i : s) cout << i << ' '; // 1 4 6 7 8 ``` ```cpp= multiset<int> ms = {1, 1, 4, 8, 7, 6, 7}; for (int i : ms) cout << i << ' '; // 1 1 4 6 7 7 8 ``` ---- #### multiset的刪除元素 ```cpp= multiset<int> ms = {1, 1, 4, 8, 7, 6, 7}; ms.erase(1); // ms = {4, 6, 7, 7, 8} //會刪掉所有1 ``` ```cpp= multiset<int> ms = {1, 1, 4, 8, 7, 6, 7}; ms.erase(ms.find(1)); // ms = {1, 4, 6, 7, 7, 8} //只刪掉一個1 ``` --- ### Map ---- * 類似陣列，但索引值不一定為非負整數 * 內部元素依照索引值遞增排序 ---- ```cpp= map<string, int> mp; mp["joylintp"] = 0; // mp = {"joylintp" : 0} mp["QQ"] = 9487; // mp = {"joylintp" : 0, "QQ" : 9487} mp["joylintp"] = 524; // mp = {"joylintp" : 524, "QQ" : 9487} mp.erase("QQ"); // mp = {"joylintp" : 524} cout << mp["joylintp"] << '\n'; // -> 524 cout << mp.size() << '\n'; // -> 1 cout << mp.empty() << '\n'; // -> 0 (false) cout << mp.count("QQ") << '\n'; // -> 0 cout << mp.count("joylintp") << '\n'; // -> 1 mp.clear(); // mp = {} cout << mp.empty() << '\n'; // -> 1 (true) ``` ---- #### 存取map中的每個元素 ```cpp= map<int, int> mp; mp[8] = 7, mp[4] = 2, mp[2] = 1, mp[9] = 0; for (map<int, int>::iterator it = mp.begin(); it != mp.end(); it++) cout << (*it).first << ',' << (*it).second << ' '; // 2,1 4,2 8,7 9,0 ``` ```cpp= map<int, int> mp; mp[8] = 7, mp[4] = 2, mp[2] = 1, mp[9] = 0; for (pair<int, int> i : mp) cout << i.first << ',' << i.second << ' '; // 2,1 4,2 8,7 9,0 ```