---
title:
Standard Template Library (STL) (Phần 1: Container adapters)
---
Standard Template Library (STL) (Phần 1: Container adapters)
===
---
###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]
---
# Giới thiệu chung
STL (Standard Template Library) là một thư viện vô cùng hữu ích trong C++. Nó đem đến cho ta một loạt các cấu trúc dữ liệu được dựng sẵn giúp cho việc xử lí dữ liệu trở nên dễ dàng hơn rất nhiều. Trong lập trình thi đấu, STL cũng được sử dụng rất rộng rãi trong nhiều bài tập cũng như thuật toán từ cơ bản đến nâng cao - đem lại một lợi thế lớn cho người dùng C++ trong các cuộc thi lập trình thi đấu.
Trong phần 1 của chuỗi 4 bài viết về STL, chúng mình sẽ giới thiệu về **container adapters** - các cấu trúc dữ liệu (CTDL) trong STL *không* sử dụng **chỉ số (index)** hay **con trỏ (iterator)** để truy cập các phần tử chứa trong chúng. Các CTDL này là **stack**, **queue** và **priority queue**.
# Stack (ngăn xếp)
## 1. Cấu trúc và cơ chế hoạt động
**Stack** có cấu trúc và cơ chế hoạt động tương tự như một **chồng sách**: Khi bạn muốn cho một quyển sách vào chồng sách thì bạn sẽ phải **đặt quyển sách đó lên đỉnh** của chồng sách, còn khi bạn muốn lấy một quyển sách ra khỏi chồng sách thì bạn sẽ **lấy ra quyển sách nằm trên đỉnh** của chồng sách.
*(Ảnh gốc: GeeksforGeeks)*
Cơ chế này được gọi là **last in-first out (LIFO)** (vào sau-ra trước), nghĩa là phần tử **cuối cùng** mà bạn đã **thêm vào** stack chính là phần tử **đầu tiên** mà bạn **lấy ra** được từ stack.
Các thao tác với stack tốn **độ phức tạp thời gian** là **$O(1)$**.
## 2. Các cú pháp và hàm thông dụng
- `stack <int> st` - khai báo stack `st` với kiểu dữ liệu int, tức là các phần tử trong stack `st` có kiểu dữ liệu là int.
- `st.push(x)` - **thêm** phần tử `x` vào **đỉnh** của stack `st`.
- `st.top()` - trả về **giá trị** của phần tử nằm trên **đỉnh** của stack `st`.
- `st.pop()` - **lấy ra** phần tử nằm trên **đỉnh** của stack `st`.
- `st.empty()` - trả về **true** nếu stack `st` **rỗng** (không có phần tử nào) và **false** nếu stack `st` có **ít nhất 1 phần tử**.
- `st.size()` - trả về **kích thước** (số lượng phần tử) của stack `st`.
## 3. Một số lưu ý khi sử dụng stack
- Khi stack đang **rỗng** mà ta **truy cập** vào phần tử nằm trên đỉnh của nó thì code sẽ bị **lỗi**. Vì vậy để đảm bảo code chạy đúng, trước khi truy cập phần tử nằm trên đỉnh của stack ta cần kiểm tra xem nó có rỗng không.
## 4. Bài tập ví dụ
### Đề bài
Cho một chuỗi $S$ bao gồm các dấu ngoặc tròn $()$. Kiếm tra xem liệu $S$ có phải một dãy ngoặc đúng hay không.
Một dãy ngoặc đúng được định nghĩa như sau:
- Xâu rỗng là dãy ngoặc đúng.
- Nếu $A$ là dãy ngoặc đúng thì $(A)$ cũng là dãy ngoặc đúng.
- Nếu $A$ và $B$ là hai dãy ngoặc đúng thì $AB$ cũng là dãy ngoặc đúng.
### Input
- Gồm một dòng là một chuỗi $S$.
### Output
- Gồm một dòng trả lời rằng liệu chuỗi $S$ có phải một dãy ngoặc đúng hay không. Nếu có in ra $YES$, ngược lại in ra $NO$.
### Sample input
```
())()(
```
### Sample output
```
NO
```
### Lời giải
- Ta sẽ duy trì 1 stack $st$ chứa lần lượt các dấu $($. Nếu như ta gặp dấu $)$, ta sẽ xoá $($ ở đầu stack đi. Từ đây ta lại gặp 1 trường hợp khác: Nếu như stack đang rỗng, có nghĩa là dấu ngoặc $)$ đang bị thừa, khi đó ta sẽ trả lại kết quả $NO$ ngay lập tức. Nếu chạy đến cuối cùng mà stack còn chưa trống (nghĩa là $($ thừa) ta trả về kết quả $NO$. Chỉ có duy nhất trường hợp stack rỗng đến cuối cùng mới được tính là dãy ngoặc đúng.
:::spoiler **Code mẫu**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
string s; cin >> s;
stack<int> st;
for (int i = 0; i < (int)s.size(); i++) {
if (s[i] == '(') {
st.push(s[i]);
} else {
if (st.empty()) {
cout << "NO" << endl;
return 0;
}
st.pop();
}
}
if (st.empty()) {
cout << "YES" << endl;
} else cout << "NO" << endl;
return 0;
}
```
:::
# Queue (hàng đợi)
## 1. Cấu trúc và cơ chế hoạt động
**Queue** có cấu trúc và cơ chế hoạt động tương tự như một **hàng đợi**: Khi một người muốn đứng vào hàng đợi thì họ sẽ phải **đứng vào vị trí cuối hàng**; người **đứng đầu hàng** sẽ được phục vụ (hay làm một cái gì đó khác) **trước** rồi họ sẽ rời khỏi hàng đợi và người đứng ở ngay phía sau trở thành người đứng đầu hàng.
*(Ảnh gốc: GeeksforGeeks)*
Cơ chế này được gọi là **first in-first out (FIFO)** (vào trước-ra trước), nghĩa là phần tử **đầu tiên** mà bạn đã **thêm vào** trong queue chính là phần tử **đầu tiên** mà bạn **lấy ra** được từ queue.
Các thao tác với queue tốn **độ phức tạp thời gian** là **$O(1)$**.
## 2. Các cú pháp và hàm thông dụng
- `queue <int> q` - khai báo queue `q` với kiểu dữ liệu int, tức là các phần tử trong queue `q` có kiểu dữ liệu là int.
- `q.push(x)` - **thêm** phần tử `x` vào **vị trí cuối** của queue `q`.
- `q.front()` - trả về **giá trị** của phần tử ở **vị trí đầu** của queue `q`.
- `q.pop()` - **lấy ra** phần tử nằm ở **vị trí đầu** của queue `q`.
- `q.empty()` - trả về **true** nếu queue `q` **rỗng** (không có phần tử nào) và **false** nếu queue `q` có **ít nhất 1 phần tử**.
- `q.size()` - trả về **kích thước** (số lượng phần tử) của queue `q`.
## 3. Một số lưu ý khi sử dụng queue
- Khi queue đang **rỗng** mà ta **truy cập** vào phần tử ở vị trí đầu của nó thì code sẽ bị **lỗi**. Vì vậy để đảm bảo code chạy đúng, trước khi truy cập phần tử ở vị trí đầu của queue ta cần kiểm tra xem nó có rỗng không.
## 4. Bài tập ví dụ
### Đề bài
Số siêu nguyên tố là số nguyên tố mà khi bỏ một số tuỳ ý các chữ số bên phải của nó thì phần còn lại vẫn tạo thành một số nguyên tố.
Ví dụ: $7331$ là một số siêu nguyên tố có $4$ chữ số vì $733$, $73$, $7$ cũng là các số nguyên tố.
Hiếu tình cờ nhặt được số nguyên dương $n$, và tự hỏi có có bao nhiêu số siêu nguyên tố có $n$ chữ số. Bạn hãy giúp Hiếu giải đáp câu hỏi trên nhé.
### Input
- Số nguyên dương $n \space (1 \le n \le 10)$.
### Output
- In ra các số siêu nguyên tố có $n$ chữ số trên cùng 1 hàng cách nhau bởi kí tự khoảng trắng.
### Sample input
```
1
```
### Sample output
```
2 3 5 7
```
### Lời giải
- Ta sẽ duy trì 1 hàng đợi $q$. Ban đầu ta sẽ bỏ số $2, 3, 5, 7$ vào trước vì đây là các số siêu nguyên tố đầu tiên. Ý tưởng là chúng ta sẽ nối lần lượt vào các số trong hàng đợi cho đến khi số lượng chữ số của hàng đợi vượt quá $n$.
- Ví dụ với $n = 2$, đầu tiên ta sẽ thêm $2, 3, 5, 7$ vào hàng đợi trước (lúc này hàng đợi $q = [2, 3, 5, 7]$. Sau đó ta sẽ lấy số $2$ ở đầu đỉnh hàng đợi ra và nối lần lượt các số từ $1$ đến $9$ để kiểm tra xem liệu $21 ... 29$ có số nào là số nguyên tố hay không, nếu có thì ta sẽ bỏ vào trong hàng đợi. Lúc này, $q = [3, 5, 7, 23, 29]$
- Ta tiếp tục lấy số $3$ ở đầu hàng đợi và nối lần lượt các số từ $1...9$ để kiểm tra xem liệu có số nào là số nguyên tố không. Lúc này $q = [5, 7, 23, 29, 31, 37]$.
- Ta tiếp tục lấy số $5$ ở đầu hàng đợi và nối lần lượt các số từ $1...9$ để kiểm tra xem liệu có số nào là số nguyên tố không. Lúc này $q = [7, 23, 29, 31, 37, 53, 59]$.
- Ta tiếp tục lấy số $7$ ở đầu hàng đợi và nối lần lượt các số từ $1...9$ để kiểm tra xem liệu có số nào là số nguyên tố không. Lúc này $q = [23, 29, 31, 37, 53, 59, 71, 73, 79]$.
- Ta tiếp tục lấy $23$ ở đầu hàng đợi thế nhưng lúc này $23$ đã có số lượng chữ số bằng $n$, ta sẽ không nối thêm nữa và lưu $23$ vào mảng kết quả.
- Tương tự như vậy với mọi số khác có số lượng chữ số bằng $n$ cho tới khi trong $q$ không còn gì nữa. Kết quả sẽ là những gì mà ta lưu lại.
:::spoiler **Code mẫu**
```cpp=
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int countDigit(ll t) {
int ans = 0;
while (t > 0) {
ans++;
t/=10;
}
return ans;
}
bool checkPrime(ll x) {
if (x <= 5) return x == 2 || x == 3 || x == 5;
if (x % 2 == 0 || x % 3 == 0 || x % 5 == 0) return false;
for (ll i = 5; i*i <= x; i+=6) {
if (x % i == 0 || x % (i + 2) == 0) return false;
}
return true;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
queue<ll> q;
q.push(2);
q.push(3);
q.push(5);
q.push(7);
vector<ll> ans;
while (!q.empty()) {
ll t = q.front(); q.pop();
int cntDigit = countDigit(t);
if (cntDigit == n) {
ans.push_back(t);
continue;
}
for (int i = 0; i <= 9; i++) {
ll newT = t*10 + i;
if (checkPrime(newT)) {
q.push(newT);
}
}
}
for (int i = 0; i < (int)ans.size(); i++) cout << ans[i] << " ";
return 0;
}
```
:::
# Priority queue (hàng đợi ưu tiên)
## 1. Cấu trúc và cơ chế hoạt động
Priority queue cũng tương tự như queue, nhưng phần tử ở **vị trí đầu/đỉnh** *không phải* là phần tử ta đã thêm vào đầu tiên mà là phần tử **lớn nhất** hoặc **nhỏ nhất** (tuỳ vào cách ta khai báo) nằm trong priority queue. Chính vì vậy, khi ta **xoá đi** phần tử trong priority queue thì phần tử bị xoá là phần tử **lớn nhất** hoặc **nhỏ nhất**.
Với cơ chế hoạt động này, priority queue sẽ phải sắp xếp lại các phần tử chứa trong nó mỗi khi ta thêm hay xoá phần tử cũng như tìm kiếm phần tử ở vị trí đầu/đỉnh mỗi khi ta muốn lấy giá trị của phần tử này. Điều này khiến cho các thao tác với priority queue tốn **độ phức tạp thời gian** là **$O(logN)$** ($N$ là kích thước của priority queue).
## 2. Các cú pháp và hàm thông dụng
- `priority_queue <int> pq` - khai báo priority queue `pq` với phần tử ở **vị trí đầu/đỉnh** là phần tử **lớn nhất**.
- `priority_queue <int, greater <int>> pq` - khai báo priority queue `pq` với phần tử ở **vị trí đầu/đỉnh** là phần tử **nhỏ nhất**. *(chúng mình không nhầm đâu, đúng là greater)*
- `pq.push(x)` - **thêm** phần tử `x` vào priority queue ```pq```.
- `pq.top()` - trả về **giá trị** của phần tử ở **vị trí đầu/đỉnh** của priority queue `pq`.
- `pq.pop()` - **lấy ra** phần tử ở **vị trí đầu/đỉnh** của priority queue `pq`.
- `pq.empty()` - trả về **true** nếu priority queue `pq` **rỗng** (không có phần tử nào) và **false** nếu priority queue `pq` có **ít nhất 1 phần tử**.
- `pq.size()` - trả về **kích thước** (số lượng phần tử) của priority queue `pq`.
## 3. Một số lưu ý khi sử dụng priority queue
- Khi priority queue đang **rỗng** mà ta **truy cập** vào phần tử ở vị trí đầu/đỉnh của nó thì code sẽ bị **lỗi**. Vì vậy để đảm bảo code chạy đúng, trước khi truy cập phần tử ở vị trí đầu của priority queue ta cần kiểm tra xem nó có rỗng không.
## 4. Bài tập ví dụ
### Đề bài
Cho $N$ sợi dây, mỗi sợi dây có độ dài $A_i$. Nhiệm vụ của bạn là nối $N$ sợi dây thành $1$ sợi sao cho tổng chi phí nối dây là nhỏ nhất. Biết chi phí nối $2$ sợi dây $i$ và $j$ là $A_i + A_j$.
### Input
- Dòng đầu tiên đưa vào số lượng bộ test $T$.
- Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test gồm hai dòng:
- Dòng đầu đưa vào số lượng sợi dây $N$.
- Dòng sau đưa vào $N$ số $A_i$ là độ dài của từng sợi dây. Các số được viết cách nhau bởi dấu cách.
- $T, N, A_i$ thoả mãn các ràng buộc: $1 \le T \le 100, 1 \le N \le 10^6, 0 \le A_i \le 10^6$
### Output
- Đưa ra kết quả là chi phí nhỏ nhất để nối dây theo từng dòng.
### Sample input
```
2
4
4 3 2 6
5
4 2 7 6 9
```
### Sample output
```
29
62
```
### Giải thích
- Ở test 1:
- **Bước 1:** Nối dây $2, 3$ có chi phí $5$. Các sợi dây lúc này là $[4, 5, 6]$
- **Bước 2:** Nối dây $4, 5$ có chi phí $9$. Các sợi dây lúc này là $[9, 6]$
- **Bước 3:** Nối dây $9, 6$ có chi phí $15$. Các sợi dây lúc này là $[15]$
- **Tổng chi phí:** $5 + 9 + 15 = 29$
### Lời giải
- Một ý tưởng ngây thơ cho bài này là chúng ta sẽ cố lấy 2 dây nhỏ nhất ra và thêm 1 sợi dây mới vào có độ dài là tổng 2 sợi dây nhỏ nhất. Làm lần lượt vậy cho tới khi chỉ còn lại đúng 1 sợi dây. Chúng ta sẽ sử dụng priority queue để áp dụng phương pháp trên.
- Đầu tiên ta lưu tất cả mảng $a$ vào priority queue $pq$, sau đó chúng ta sẽ lấy ra 2 phần tử trên đầu $pq$ và xoá $2$ phần tử đó trong $pq$ đi rồi thêm vào $pq$ một phần tử mới là tổng 2 phần tử trên và ta cộng chi phí 2 phần tử đó vào kết quả. Làm cho tới khi nào priority queue chỉ còn đúng 1 phần tử thì ta dừng.
- Ở đây ta dùng ```priority_queue <int, greater <int>> pq``` để phần tử nhỏ nhất được đưa lên đỉnh đầu hàng đợi.
:::spoiler **Code mẫu**
```cpp=
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 5;
ll a[maxn];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
priority_queue<ll, vector<ll>, greater<ll> > pq;
for (int i = 1; i <= n; i++) cin >> a[i], pq.push(a[i]);
ll ans = 0;
while (pq.size() > 1) {
ll x = pq.top(); pq.pop();
ll y = pq.top(); pq.pop();
ans += x + y;
pq.push(x + y);
}
cout << ans << endl;
}
return 0;
}
```
:::
# Bài tập áp dụng
## [Bài 1](https://cses.fi/problemset/task/1645)
Cho một mảng $a$ gồm $n$ phần tử. Với mỗi vị trí $i$, tìm phần tử gần nhất về bên trái bé hơn $a_i$.
### Input
- Dòng đầu tiên chứa số $n$: Số lượng phần tử trong mảng. $(1 \le n \le 2 \cdot 10^5)$
- Dòng thứ 2 chứa $n$ số $a_i$ cách nhau bởi dấu khoảng trắng. $(1 \le a_i \le 10^9)$
### Output
- Với mỗi vị trí $i$, in ra kết quả bài toán. Nếu không có in ra $0$.
### Sample input
```
8
2 5 1 4 8 3 2 5
```
### Sample output
```
0 1 0 3 4 3 3 7
```
# Nguồn tham khảo
:::info
[1] https://www.geeksforgeeks.org/the-c-standard-template-library-stl/
[2] https://vnoi.info/wiki/algo/data-structures/data-structures-overview.md#1-ctdl-lưu-trữ
[3] https://cplusplus.com/reference/stack/stack/
[4] https://cplusplus.com/reference/queue/queue/
[5] https://cplusplus.com/reference/queue/priority_queue/
:::
Sign in with Wallet
Connect another wallet