資料結構(一)

--- title: STL type: slide --- 資料結構(一) === ### CS --- ### 陣列真的很方便嗎？ 1. 每次都要宣告長度 2. 排列都還要多用 sort 3. 多宣告的長度很浪費 4. 怎麼插入和刪除元素 5. 好難更新 ~ ~ ---- ### 總而言之陣列還有很多缺點 ---- 有一個可以取代陣列甚至是超越陣列的東西 ---- ### STL 標準函式庫 --- ### STL 標準函式庫 ---- ### 資料結構一種可以儲存資料的東東陣列當然也算是其中一種 **C++內建也有提供資料結構** ~~你要手刻也可以~~ ---- STL 函式庫就是內建提供的資料結構 ---- ### 需要手刻的資料結構 1. BIT (Binary Indexed Tree, 樹狀樹組) 2. Segment Tree (線段樹) 3. Treap (樹堆) 4. Sparse Table (稀疏表) ... ---- 以上我們都不會教基本上這些已經不是APCS的考試範圍了如果你想拚資奧的話這些都只是基本而已 ---- ### 內建的資料結構 1. [pbds](https://omeletwithoutegg.github.io/2021/07/23/pbds-split-join-is-slow/) (不會教) 2. **STL 函式庫** ---- ### 所以什麼是STL？ ---- ### 包含4個組件 1. 演算法：要執行的操作 🌰sort 2. 容器：放資料的地方 3. 函數：X(...) 可呼叫的函數(廣義) 🌰size() 4. 迭代器：類似指標的概念 ---- 其實演算法和函數都已經學過了迭代器的概念( [指標](https://hackmd.io/@cccccsssss/Pointer) ) 第一節課也學過了 **不會的話或不熟可以來問我們ㄡ** --- ### 迭代器 ---- 是一個可以幫助我們取得元素的工具迭代器可以想成該元素的 **位址** 所以我們只要加上 **取值符號\*** 就可以取到元素的值了 --- ### 容器 ---- 目前已經會的容器 **陣列** ---- 就 **排序** 大致分為兩種 1. **序列容器：** 依照存入順序排序 2. **關聯性容器：** 由小到大或由大到小(字串 ascii) **只要記得哪些有自動排序就好** ---- | 序列容器(不排序) | 關聯性容器(排序) | | :--: | :--: | | pair | set | | vector | multiset | | stack | map | | queue | multimap | | deque | priority_queue | ---- ### 小叮嚀因為 **STL** 的東西比較偏背用法需要透過練習大量題目來熟悉用錯資料結構題目就會變得很難寫所以一定要非常熟練各種資料結構的特性ㄛ ---- 我們這節課會先介紹 **不排序的容器** 會找題目給你們練習 --- ### STL 容器宣告方式 ---- ```cpp! 容器 <資料型態> 容器名稱; ``` --- ### pair ---- pair 跟其他容器比較不一樣一個pair只能存一組pair 就像int一次只能存一個整數 ---- pair 就跟他的名字一樣由兩個資料型態成對存在可以直接想成數學的座標 $x,y$ $x,y$ 的資料型態可同可不同 ---- ### 宣告 ```cpp= pair<int, string> p; ``` int,string依序為第一元素,第二元素的資料型態 ---- ### 賦值&取值和 struct 一樣使用成員運算子 . ```cpp= pair<int,int> p; p.first=1; p.second=2; //pair<int,int> p({1,2}); cout<<p.first<<" "<<p.second; ``` 第一個元素用 first 第二個元素用 second ---- ### 神奇用法 pair 裡面還可以包 pair ```cpp= pair <int, pair<int,string>> p; p.first=1; p.second.first=2; p.second.second="ABC"; ``` --- ### vector aka 動態陣列 ---- vector 就是功能超級無敵強大的陣列 ---- ### 宣告 ```cpp= vector <int> v; ``` 資料型態當然也可以放 **pair** ---- ### 存入資料只能從最後面插入相比陣列比較麻煩一點但就只有存入資料這點會比較麻煩 ---- 方法 ```cpp= vector名稱.push_back(要存的元素); ``` ---- 假如說我要輸入一個變數然後存進去 ```cpp= //陣列 int arr[10]; cin>>arr[0]; //vector vector <int> v; int tmp; cin>>tmp; v.push_back(tmp); ``` ---- ### 刪除資料只能從最後面開始刪但總比陣列不能刪來的好吧 ---- Code ```cpp= vector <int> v({1,5,2,5,3}); //可以這樣直接宣告已知的vectorㄡ v.pop_back(); for (auto i:v) cout<<i<<" "; //for i in v (python) // 1 5 2 5 ``` ---- <a href="https://blog.gtwang.org/programming/cpp-auto-variable-tutorial/">auto</a> ---- ### 取得vector大小 1. size()：取得目前 **有存放資料** 的記憶體大小 2. capacity()：vector目前 **預留** 的記憶體大小 能達到動態陣列就是運用了這個概念 先開一些不夠再繼續開 ---- ```cpp= vector <int> v({1,7,6,5,3}); cout<<v.size()<<"\n"; cout<<v.capacity()<<"\n"; ``` 去跑一次會發現都是 5 因為一開始就已經先宣告好了 ---- 如果是這樣寫的話 ```cpp= vector <int> v; v.push_back(1); v.push_back(7); v.push_back(6); v.push_back(5); v.push_back(2); cout<<v.size()<<"\n"; // 5 cout<<v.capacity()<<"\n"; // 8 每個IDE跑出來的結果可能不一樣 ``` 就會不一樣了 ---- 綜合上述兩段 CODE 可知先宣告其實會比較省空間但在競程中我們基本上沒有辦法這樣做 BTW size 比 capacity 常用 (capacity幾乎不會用到) ---- ### vector 迭代器(iterator) 1. begin() 2. end() 3. rbegin() 4. rend() ---- ![](https://hackmd.io/_uploads/SyyEj2LZa.png) ---- ![](https://hackmd.io/_uploads/SJUos3LZT.png) ---- ### 迭代器宣告 ```cpp= vector<資料型態>::iterator 名稱; //begin(), end() vector<資料型態>::reserve_iterator 名稱; //rbegin, rend() ``` 基本上我們不會記這個我也沒記 ---- 直接用 **auto** ```cpp= vector <int> v({1,5,3,6,7,9,10,6,87,71,17,100}); auto it=v.begin(); cout<<*it<<"\n"; //取得第一個元素的值 auto ite=v.rbegin(); //取得最後一個元素的值 cout<<*ite<<"\n"; for (auto i=v.begin();i!=v.end();i++) cout<<*i<<" ";//法一 for (auto k:v) cout<<k<<" "; //法二 for (int i=0;i<v.size();i++) cout<<v[i]<<" "; //法三 //記得要用取值符號 * ``` --- ### stack ---- stack 中文是 **堆疊** 從字面意思來看它就是一個一個疊上去的容器 ---- ![](https://hackmd.io/_uploads/rJmJf68b6.png) ---- 每次只能從最上面取出也只能從最上面放進去 **FILO** (**F**irst-**I**n-**L**ast-**O**ut) 或者 **LIFO** (**L**ast-**I**n-**F**irst-**O**ut) ---- ### 支援的操作 1. push() 2. pop() **注意：stack不支援迭代器** ---- ```cpp= stack <int> st; int n; cin>>n; for (int i=0;i<=n;i++) st.push(i); cout<<st.size()<<"\n"; while (!st.empty()){ //boolean 空return 1 else return 0 cout<<st.top()<<" "; //取得最上面元素的值 st.pop(); } ``` --- ### queue 讀音：Qˋ ---- queue 中文是 **單向佇列** ---- ![](https://hackmd.io/_uploads/SyCNua8-p.png) ---- **FIFO** (**F**irst-**I**n-**F**irst-**O**ut) 或是 **LILO** (**L**ast-**I**n-**L**ast-**O**ut) ---- ### 支援的操作 1. push() //enqueue 3. pop() //dequeue **注意：queue不支援迭代器** ---- ```cpp= queue <int> q; int n; cin>>n; for (int i=0;i<=n;i++) q.push(i); cout<<q.size()<<"\n"; cout<<q.back()<<"\n"; while (!q.empty()){ cout<<q.front()<<" "; q.pop(); } ``` --- ### deque 讀音：~~底Qˋ~~ deck ---- deque 中文是 **雙向佇列** 從字面意思就可以知道 deque 跟 queue 差不多 ---- ![](https://hackmd.io/_uploads/rkTC9C8-6.png) ---- ### 支援的操作 1. push_back() 2. push_front() 3. pop_back() 4. pop_front() ---- ### deque 迭代器 1. begin() 2. end() 3. rbegin() 4. rend() ---- ```cpp! push_back(...); //從最後面新增元素 push_front(...); //從最前面新增元素 pop_back(); //從最後面刪除元素 pop_front(); //從最前面刪除元素 front(); //取得第一個元素的值 back(); //取得最後一個元素的值 empty(); //boolean 判斷是否為空 size(); //取得大小 ``` ---- ```cpp= deque <int> dq; dq.push_back(3); dq.push_back(5); dq.push_front(6); for (auto i:dq) cout<<i<<" "; // 6 3 5 while (!dq.empty()){ cout<<dq.front()<<" "; dq.pop_front(); } ``` --- ### sort ---- 有支援迭代器的 **vector** 和 **deque** 都可以sortㄡ ---- 我們第一節課有講過的 [sort](https://hackmd.io/@cccccsssss/competitive_programming#/11) 用法也是一樣 ---- ```cpp= //array arr[5]={5,3,6,87,17}; sort(arr,arr+5); //vector vector<int> v({5,3,6,87,17}); sort(v.begin(),v.end()); //deque deque <int> dq({5,3,6,87,17}); sort(dq.begin(),dq.end()); ``` --- ![image](https://hackmd.io/_uploads/H1WOKYnpa.png) | | vector | stack | queue | deque | |---:|:---:|:---:|:---:|:---:| | size() | ✓ | ✓ | ✓ | ✓ | | empty() | ✓ | ✓ | ✓ | ✓ | | push_back() | ✓ | ✗ | ✗ | ✓ | | push_front() | ✗ | ✗ | ✗ | ✓ | | pop_back() | ✓ | ✗ | ✗ | ✓ | | pop_front() | ✗ | ✗ | ✗ | ✓ | | push() | ✗ | ✓ | ✓ | ✗ | | pop() | ✗ | ✓ | ✓ | ✗ | | front() | ✗ | ✗ | ✓ | ✓ | | back() | ✗ | ✗ | ✓ | ✓ | | 迭代器 | ✓ | ✗ | ✗ | ✓ | --- ### 補充：vector 二維 ---- 剛剛教的 vector 只能用在一維如果要二維怎麼辦 ---- ```cpp= vector <int> v[10]; for (int i=0;i<10;i++){ for (int j=0;j<i+1;j++){ v[i].push_back(j); } } cout<<v[0][0]; //v[0][0] 等同於 *v[0].begin() ``` --- ### 題目練習 ---- ### vector [MDCPP市排序問題](http://mdcpp.mingdao.edu.tw/problem/T014) [動態中位數](http://mdcpp.mingdao.edu.tw/problem/B015) ---- ### stack [Parentheses Balance](http://mdcpp.mingdao.edu.tw/problem/B005) [括弧配對](https://judge.tcirc.tw/ShowProblem?problemid=d026) [Rails](https://zerojudge.tw/ShowProblem?problemid=c123) [鐵路](https://zerojudge.tw/ShowProblem?problemid=f105) [加減乘除](https://judge.tcirc.tw/ShowProblem?problemid=d027) [四則運算](http://mdcpp.mingdao.edu.tw/problem/D055) [最接近的高人](https://judge.tcirc.tw/ShowProblem?problemid=d028) [後序運算式](https://zerojudge.tw/ShowProblem?problemid=f698) ---- ### queue [queue裸題](https://judge.tcirc.tw/ShowProblem?problemid=b043) [小組隊列](http://mdcpp.mingdao.edu.tw/problem/B002) [卑鄙約瑟夫](https://judge.tcirc.tw/ShowProblem?problemid=b044) ---- ### deque [字串解碼](https://zerojudge.tw/ShowProblem?problemid=i400) [固定長度區間的最大區段差](https://judge.tcirc.tw/ShowProblem?problemid=d032) --- ### 謝謝大家

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.