# STL(2)
## 11/10 社課
---
## queue
----
隊列、佇列
可以想像成排隊
每次都只能從最後面排隊，從最前面離開
先進先出（First in First out, FIFO）
----
宣告
```cpp=
queue<data_type> q;
```
----
把資料加進 queue 裡（多一個人排隊）
```cpp=
q.push(a);
```
把最前端資料刪掉（最前面的人離開）
```cpp=
q.pop();
```
----
取得最前端的資料
```cpp=
q.front()
```
清空 queue
```cpp=
q=queue<data_type>();
```
----
其實大部分 STL container 都可以用這種方式清空
```cpp=
vector<int> v;
v=vector<int>();
```
如果這種 STL 沒有 clear() 那這會是一個好選擇
----
範例
```cpp=
queue<int> q;
q.push(2); // {2}
q.push(3); // {2, 3}
q.push(6); // {2, 3, 6}
cout << q.front(); // 2
q.pop(); // {3, 6}
q=queue<int>(); // {}
```
---
## stack
----
堆疊
可以想像成疊盤子
每次都只能拿最上面的
後進先出（Last in First out, LIFO）
----
宣告
```cpp=
stack<data_type> stk;
```
----
把資料加進 stack 裡（把一個盤子堆到最上面）
```cpp=
stk.push(a);
```
把最頂端的資料刪掉（把最上面的盤子拿走）
```cpp=
stk.pop();
```
----
取得最頂端的資料
```cpp=
stk.top()
```
清空 stack
```cpp=
stk=stack<data_type>();
```
----
範例
```cpp=
stack<int> stk;
stk.push(2); // {2}
stk.push(3); // {2, 3}
stk.push(6); // {2, 3, 6}
cout >> stk.top(); // 6
stk.pop(); //{2, 3}
stk=stack<int>(); // {}
```
---
## priority_queue
----
優先佇列
權重越大的排前面
預設為數值大的排前面
實作是 [heap](https://reurl.cc/l72ygA)
----
宣告
```cpp=
priority_queue<data_type> pq; // 預設取數值最大的
priority_queue<type, vector<type>, greater<type>> pq2;
// 取數值最小的
priority_queue<type, vector<type>, cmp> pq3; // 自定義排序
```
----
資料結構中自定義排序
```cpp=
struct cmp{
bool operator()(type a, type b){
return //...
}
};
```
```cpp=
struct cmp{
bool operator()(string a, string b){
return a.size()<b.size();
}
};
```
priority_queue 最終取到的會是權重最大的
在以上範例就是字串長度最大的
----
把資料加進去
```cpp=
pq.push(a);
```
把權重最大的資料刪掉
```cpp=
pq.pop();
```
----
取得權重最大的資料
```cpp=
pq.top()
```
清空 priority_queue
```cpp=
pq=priority_queue<...>();
```
----
範例
```cpp=
priority_queue<int> pq;
pq.push(3); // {3}
pq.push(6); // {3, 6}
pq.push(2); // {2, 3, 6}
cout << pq.top(); // 6
pq.pop(); // {2, 3}
pq=priority_queue<int>(); // {}
```
實際上他內部位置的操作不是這樣
就只是方便各位理解
---
## set
----
集合
就和數學上的集合類似
元素藉權重由小排到大（預設為數值小到大）
一個集合裡的每個元素最多只會出現一次
實作 [紅黑樹](https://reurl.cc/ka2MrK)
----
宣告
```cpp=
set<data_type> s;
set<data_type, cmp> s2; // 自定義排序
```
----
把元素加進去
```cpp=
s.insert(a);
```
把元素刪除
```cpp=
s.erase(a);
```
----
查詢元素位置
```cpp=
s.find(a);
```
這會回傳 iterator，類似指標
如果沒有這個元素則會回傳 s.end()
我們也可以用以判斷是否在 set 中
```cpp=
if(s.find(a)!=s.end()){
//...
} // 如果找的到 a -> set 裡面有存在 a
```
----
清除 set
```cpp=
s.clear();
```
----
可以用 prev(iter), next(iter)
找到某個 iterator 前後一個的 iterator
```cpp=
set<int> s;
s.insert(1);
s.insert(2);
s.insert(4);
cout << *prev(s.find(2)); // 1
cout << *next(s.find(2)); // 4
```
----
類似的資料結構
[multiset](https://cplusplus.com/reference/set/multiset/) 可以存在相同元素
[unordered_set](https://cplusplus.com/reference/unordered_set/unordered_set/) 不排序的 set
---
## map
----
鍵值對（key-value pair）
對於每個 key 都有一個對應的 value
其實就是一個放 pair 的 set
按照 key 排序
----
宣告
```cpp=
map<data_type_1, data_type_2> mp;
```
----
加入一個健值對
```cpp=
mp[key]=val;
mp.insert(make_pair(key, val));
```
刪除某個 key
```cpp=
mp.erase(key);
```
拿到某個 key 的 value
```cpp=
mp[key]
```
----
查詢是否存在某個 key（回傳布林值）
```cpp=
mp.count(key);
```
清空 map
```cpp=
mp.clear();
```
----
map 在還沒加入某個 key 時就呼叫他的話
電腦會給他一個預設值，之後將他們加進 map 中
```cpp=
map<int, int> mp;
cout << mp.count(1); // 0
cout << mp[1]; // 0
cout << mp.count(1); // 1
```
----
類似的資料結構
[multimap](https://cplusplus.com/reference/map/multimap/) ~~其實我不知道這是幹嘛的~~
[unordered_map](https://cplusplus.com/reference/unordered_map/unordered_map/) 不排序，比 map 快一點
----
以上共用的東西
.size() 回傳大小
.empty() 回傳是否為空
---
今天講的內容很多
各位加油
如果把這部分熟悉
你就脫離新手期了！
{"description":"type=slide","title":"11/10 C++社課","contributors":"[{\"id\":\"1a0296c8-ce58-4742-acda-22c02ae81a74\",\"add\":3683,\"del\":56}]"}