---
# System prepended metadata

title: 非常不完整的STL

---

---
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 則表示容量大小（就像上面可以先預開的容量）。

![image](https://hackmd.io/_uploads/BJ0hC6kxlg.png)

---

### 常用函式:

#### `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 的限制也是特色。
![image](https://hackmd.io/_uploads/r1dmTJleeg.png)


### 常用函式:
#### 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實作就好)
![image](https://hackmd.io/_uploads/Hy4WFUxxxx.png)







#### 解題步驟
遍歷字串：

如果遇到左括號（(, [, {），將其推入堆疊，並記錄它的位置。
如果遇到右括號（), ], }）：
就再看如果堆疊為空，說明右括號多餘，直接輸出 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），就像排隊一樣，先進來的會先出去。
![image](https://hackmd.io/_uploads/Hkjgleeleg.png)
白話點就要刪只能刪前面，要加只能加後面


--- 

### 常用函式:

#### `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`。
![image](https://hackmd.io/_uploads/Bkn0Leggee.png)

白話點就是有天才把兩個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();
```

---





