---
title: ''
disqus: hackmd
---
STL containers
===
## 前言
這是為了試教誕生出來的講義，也是我第一次編講義，有哪裡寫錯或排很醜請見諒，之後有問題可以回來加減看，或許有點幫助(?
每個容器也都會有一個DDJ的練習題可以寫，希望各位能用前面教的容器寫寫看。
然後之後應該會再加更多容器的介紹，可以期待一下(?
沒那麼完整的完整版:https://hackmd.io/@nowob/rkaS0PNsgg
## Vector
### 標頭檔:
```cpp=
#include <vector>
```
### 宣告:
```cpp=
// 最基本的宣告
vector<資料型態> 名稱(大小);
// 如果想先把東西丟進去的宣告
vector<資料型態> 名稱{內容};
// 空 vector，大小為 0
vector<int> v;
// 建立大小為 10 的 vector，只預開容量裡面沒東西
vector<int> v(10);
// 建立大小為 10 的 vector，初始值全為 `-1`
vector<int> v(10, -1);
// 開一個內容為 {1, 2, 3} 的 vector，大小為 3
vector<int> v = {1, 2, 3};
// 複製 v1
vector<int> v2(v1);
```
### vector 的樣子 (?
size 表示的是 vector 中的元素個數，capacity 則表示容量大小（就像上面可以先預開的容量）。
---
### 常用函式:
#### `push_back()` / `pop_back()`
顧名思義，`push_back()` 會把括號裡面的東西丟到 vector 後面。需要注意的是，放進去的東西要跟一開始設的資料型態一樣，而`pop_back()`就是把vector最後面的元素刪掉。
```cpp=
vector<int> vec;
vec.push_back(1); // 1
vec.push_back(2); // 1 2
vec.push_back(3); // 1 2 3
vec.pop_back(); // 1 2
vec.push_back(1); // 1 2 1
```
:::spoiler 在容量用完的時候 `push_back` 會發生什麼事？
大部分情況下，capacity（容量）會變成兩倍，這麼做很顯然會有點浪費。所以如果今天解題的時候你很懶，全部用 `push_back` 沒有預開時，吃到 MLE（Memory Limit Exceeded），可以嘗試先預開。
:::
---
#### `size()`
取得目前 vector 的大小，也可以說是元素數量，常常用來遍歷 vector。
```cpp=
vector<int> vec = {1, 2, 3, 4, 5};
cout << vec.size(); // 5
// 遍歷輸出 vector
for (int i = 0; i < vec.size(); i++) {
cout << vec[i] << ' ';
}
```
---
#### `empty()`
用來檢測這個 vector 是不是完全空了。是的話會回傳 `true`，注意這裡指的空是「完全沒東西」，也可以說是 `size() = 0`。
```cpp=
vector<int> vec = {0};
cout << vec.empty(); // 0 (false) 有東西
vec.pop_back(); // 沒東西了
cout << vec.empty(); // 1 (true) 沒東西
```
---
#### `clear()`
顧名思義，直接清空整個 vector，把它的 `size()` 變成 0。
```cpp=
vector<int> vec = {1, 1, 4, 5, 1, 4};
vec.clear();
cout << vec.empty(); // 1 (true)
cout << vec.size(); // 0
```
---
#### `erase()`
刪除指定 iterator 的元素，iterator要解釋可能有點複雜，在這裡知道要先寫個begin給他定位到你指定的vector的頭就好，要砍後面的元素就往後加。
```cpp=
vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin() + 2); // 刪除第三個元素
```
---
### 其他函式（有更多但真的很少用）
- **`resize()`**
重設容器的大小，這裡指的是 `size()`，如果原本大小超過，會把多的刪掉。
- **`front()`**
存取第一個元素。
- **`back()`**
存取最後一個元素。
- **`data()`**
存取第一項元素的指標。
- **`assign()`**
分配容器新的內容替換當前內容，並修改大小。
- **`insert()`**
插入元素。
- **`swap()`**
交換兩個容器。
#### 題目練習:
a864 記得vector裡面也可以擺string應該就行
## Stack
### 標頭檔:
```cpp=
#include<stack>
```
### 宣告:
```cpp=
//最基本的宣告
stack<資料型態> 名稱;
//空 stack
stack<int> s;
```
### stack 的特性
Stack 是一種後進先出（LIFO, Last In First Out）的神奇容器，可以想像成一個酷酷的容器(如圖)，每個資料都是盤子，慢慢堆起來，但很顯然這個容器只有一個開口，無論要做甚麼操作都只能對最上面做，所有的操作都只能對最上層的元素進行，這是 Stack 的限制也是特色。
### 常用函式:
#### push()/pop()
`push()` 會將元素放到堆疊頂端，而 `pop()` 會移除堆疊頂端的元素。
```cpp=
stack<int> s;
s.push(1); // 1
s.push(2); // 1 2
s.push(3); // 1 2 3
s.pop(); // 1 2
s.push(4); // 1 2 4
```
#### top()
`top()` 用來取得堆疊頂端的元素，但不會移除該元素。
```cpp=
stack<int> s;
s.push(10);
s.push(20);
cout << s.top(); // 20
```
#### empty()
`empty()` 用來檢查堆疊是否為空，若為空則回傳 `true`，否則回傳 `false`。
```cpp=
stack<int> s;
cout << s.empty(); // 1 (true)
s.push(5);
cout << s.empty(); // 0 (false)
```
#### size()
`size()` 用來取得堆疊中目前的元素數量。
```cpp=
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
cout << s.size(); // 3
```
#### 其他函式
- `emplace`：原地建構物件並加入堆疊頂端（會比`push`更好一點，但不會差太多，反正我都用`push`）。
- `swap`：交換兩個堆疊的內容。
```cpp=
// 使用 swap 範例
stack<int> s1, s2;
s1.push(1); s1.push(2);
s2.push(3); s2.push(4);
s1.swap(s2);
// s1 現在為 3, 4
// s2 現在為 1, 2
```
### 然後呢?
看到這裡你可能會疑惑，不是有個vector很好用了嗎，為什麼我要用這個只能動頂端的怪容器??
答案很簡單
總會有題目是專門來搞人的
像是這題 a204
基本上不用stack很難解
看完題目後感覺一頭霧水的話沒關係
這裡會慢慢的教怎麼用stack去處理題目中的括號問題
但應該不會完整教完，涉及到一點別的技巧
(然後這題不一定真的要拿到AC，懂怎麼用stack實作就好)
#### 解題步驟
遍歷字串：
如果遇到左括號（(, [, {），將其推入堆疊，並記錄它的位置。
如果遇到右括號（), ], }）：
就再看如果堆疊為空，說明右括號多餘，直接輸出 No 並附上當前位置。
堆疊有東西的話從堆疊頂部取出對應的左括號，檢查是否匹配：
如果匹配：繼續處理下一個字元。
如果不匹配：輸出 No 並附上當前位置。
檢查堆疊是否為空：
如果遍歷結束後，堆疊中還有多的左括號，就代表左括號多餘，輸出 No 並附上堆疊頂部括號的位置。
輸出結果：
如果字串完全匹配，輸出 Yes。
:::spoiler AC Code(可參考但希望你各位不要抄)
```cpp=
#include <bits/stdc++.h>
#define ll long long
#define ul unsigned long long
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
string line;
while (getline(cin, line)){
stack<char> s;
stack<int> wh;
bool bo = true;
for (int i = 0; i < line.length(); i++){
char ch = line[i];
if (ch == '(' || ch == '[' || ch == '{'){
s.push(ch);
wh.push(i + 1);
}
else if (ch == ')' || ch == ']' || ch == '}'){
if (s.empty()) {
cout << "No " << i + 1 << '\n';
bo = false;
break;
}
char tc = s.top();
s.pop();
int ti = wh.top();
wh.pop();
if ((ch == ')' && tc != '(') || (ch == ']' && tc != '[') || (ch == '}' && tc != '{')){
cout << "No " << i + 1 << '\n';
bo = false;
break;
}
}
}
if (bo && !s.empty()){
cout << "No " << wh.top() << '\n';
bo = false;
}
if (bo){
cout << "Yes" << '\n';
}
}
}
```
:::
希望在解這題的過程中可以讓大家體會到stack的魅力所在，也可以意識到它的存在是有意義的(不然上面那題要用vector硬寫會痛苦死，而且八成會吃tle)，有興趣的學員也可以嘗試慢慢把這題解出來
stack也當然不只適用在括號，更難的還有深度優先搜尋（DFS, Depth First Search）,單調棧（Monotonic Stack）之類的神奇演算法適用
## Queue
### 標頭檔:
```cpp=
#include <queue>
```
### 宣告:
```cpp=
// 最基本的宣告
queue<資料型態> 名稱;
// 空 queue
queue<int> q;
// 複製 q1
queue<int> q2(q1);
```
### queue 長啥樣
queue 是一種先進先出的資料結構（FIFO, First In First Out），就像排隊一樣，先進來的會先出去。
白話點就要刪只能刪前面，要加只能加後面
---
### 常用函式:
#### `push()` / `pop()`
`push()` 會把括號裡面的東西放到 queue 的尾端，而 `pop()` 則會把 queue 的前端元素移除。就跟前面提到的基本上一樣。
```cpp=
queue<int> q;
q.push(1); // 1
q.push(2); // 1 2
q.push(3); // 1 2 3
q.pop(); // 2 3
q.push(4); // 2 3 4
```
---
#### `front()` / `back()`
顧名思義`front()` 用來存queue 中的第一個元素，而 `back()` 用來存最後一個元素。
```cpp=
queue<int> q;
q.push(11);
q.push(45);
q.push(14);
cout << q.front(); // 11
cout << q.back(); // 14
```
---
#### `size()`
取得目前 queue 的大小，也就是其中的元素數量。
```cpp=
queue<int> q;
q.push(1919);
q.push(114514);
q.push(780);
cout << q.size(); // 3
```
---
#### `empty()`
檢查 queue 是否為空。如果 queue 是空的，會回傳 `true`，否則會回傳 `false`。
```cpp=
queue<int> q;
cout << q.empty(); // 1 (true)
q.push(22);
cout << q.empty(); // 0 (false)
```
---
#### `swap()`
用於交換兩個 queue 的內容。
```cpp=
queue<int> q1, q2;
q1.push(1);
q1.push(2);
q2.push(3);
q2.push(4);
q1.swap(q2);
// q1: 3 4
// q2: 1 2
```
---
### 然後呢?
相信聰明的各位在看完stack和前面的講解後，可以猜到queue的最常見題型
沒錯! 就是排隊問題
不過我找不到難度適合的題目
這裡會拿a979來講一下
雖然他好像說這題不是queue:
會跟stack一樣一步一步慢慢看要怎麼解
真的有興趣想練習可以說一下我可以出一題
然後想練習的可以到隔壁zerojudge寫e447
---
### 需要注意的小地方
在用queue想pop的時候，記得要先判一下queue裡面有沒有東西，假如裡面沒東西你硬pop的話會導致程式壞掉
---
### 一些酷酷的queue變體：
#### priority_queue`（優先佇列）
如果需要處理優先順序（例如最大值或最小值），可以使用 `priority_queue`。
```cpp=
#include <queue>
priority_queue<int> pq; // 預設是最由大到小
pq.push(5); // 5
pq.push(1); // 5 1
pq.push(10); // 10 5 1
cout << pq.top(); // 10
pq.pop();
cout << pq.top(); // 5
```
如果需要由小到大，則可以這樣宣告：
```cpp=
priority_queue<int, vector<int>, greater<int>> pq;
```
基本上就是自己排好的queue，很好用，不過需要注意他的時間複雜度比較高，所以在時間卡的比較緊的題目要小心使用
---
#### 2. 模擬雙向佇列（`deque`）
如果需要同時操作頭尾，可以考慮使用 `deque`。
白話點就是有天才把兩個queue拚在一起變成一個很酷的容器，原本的queue要加元素只能加在後面，要刪元素只能刪最後面，不過用了deque後就能對頭尾都做新增值和刪除值的動作。
```cpp=
#include <deque>
deque<int> dq;
dq.push_front(1);
dq.push_back(2);
cout << dq.front(); // 1
cout << dq.back(); // 2
dq.pop_front();
dq.pop_back();
```
---
Sign in with Wallet
Connect another wallet