---
title:
Standard Template Library (STL) (Phần 2: Sequential containers)
---

Standard Template Library (STL) (Phần 2: Sequential containers)
===

---

###### ✍️ Author: 2School Guideline
###### 📋 Content:
[TOC]

---

# Giới thiệu chung
Tiếp tục chuỗi 4 bài viết về STL (Standard Template Library), trong phần 2 này chúng mình sẽ giới thiệu về **sequential containers** - các cấu trúc dữ liệu (CTDL) sử dụng **chỉ số (index)** *và* **con trỏ (iterator)** để truy cập các phần tử chứa trong chúng. Trong bài viết này, chúng mình sẽ giới thiệu về 2 CTDL dạng sequential container là **vector** và **deque**.

Ngoài ra còn có thêm các CTDL dạng **sequential containers** khác là **array**, **list** và **forward list** *(từ C++11 trở đi)*. *Tuy nhiên chúng không được ứng dụng rộng rãi trong kì thi tuyển sinh chuyên tin 10 nên mọi người có thể tự tìm hiểu thêm nếu thích ^^.*

# Iterator (con trỏ)
## 1. Khái niệm
**Iterator** là một đối tượng có thể đi qua (hay trỏ vào) các phần tử nằm trong một CTDL dạng **container** (như vector, deque,...) mà không cần biết trật tự bên trong. Iterator cũng có thể truy cập giá trị của phần tử mà nó đang trỏ vào.

## 2. Các cú pháp, toán tử và hàm thông dụng
### a. Cách khai báo
**Cú pháp:** `container <type>::iterator iterator_name`
- `container`: loại CTDL dạng container (như vector, deque) mà bạn muốn iterator này trỏ vào.
- `type`: kiểu dữ liệu của iterator trùng với kiểu dữ liệu của CTDL dạng container.
- `iterator_name`: tên của iterator.

**Ví dụ:**

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector <int>::iterator it1;
    deque <char>::iterator it2;
    return 0;
}

Iterator `it1` có chức năng trỏ vào phần tử của một `vector <int>` bất kì, iterator `it2` có chức năng trỏ vào phần tử của một `deque <char>` bất kì.

### b. Các toán tử
- `it` - trả về giá trị mà iterator `it` đang trỏ vào.
- `it++` hay `++it` - di chuyển iterator `it` đến phần tử tiếp theo trong CTDL dạng container.
- `it--` hay `--it` - di chuyển iterator `it`đến phần tử trước đó trong CTDL dạng container.
- `==` và `!=` - so sánh vị trí 2 phần tử được trỏ vào bởi 2 iterator.
- `=` - gán vị trí trỏ vào cho iterator.

### c. Các hàm
- `container_name.begin()` - trả về iterator trỏ đến phần tử **đầu tiên** trong CTDL dạng container có tên `container_name`.
- `container_name.end()` - trả về iterator trỏ đến phần tử **ngay sau** phần tử **cuối cùng** trong CTDL dạng container có tên `container_name`.
- `container_name.rbegin()` - trả về iterator trỏ đến phần tử **cuối cùng** trong CTDL dạng container có tên `container_name`.
- `container_name.rend()` - trả về iterator trỏ đến phần tử **ngay trước** phần tử **đầu tiên** trong CTDL dạng container có tên `container_name`.
+ Ví dụ:

    #include <bits/stdc++.h>
    using namespace std;

    int main()
    {
        vector <int> v = {1, 2, 3, 4};

        cout << *v.begin() << "\n"; //output ra 1
        cout << *v.end() << "\n"; //output ra 0
        cout << *v.rbegin() << "\n"; //output ra 4
        cout << *v.rend() << "\n"; //output ra 0
        return 0;
    }

+ Từ ví dụ trên ta có thể thấy `*v.end()` và `*v.rend()` trả về giá trị `0` vì `v.end()` và `v.rend()` trỏ vào các phần tử không nằm trong `v`.
- `advance(it, x)` - di chuyển iterator `it` đến phần tử tiếp theo `x` lần (nếu `x` dương) hoặc đến phần tử trước đó `x` lần (nếu `x` âm) trong CTDL dạng container.
- `next(it)` - di chuyển iterator `it` đến phần tử tiếp theo trong CTDL dạng container.
- `prev(it)` - di chuyển iterator `it`đến phần tử trước đó trong CTDL dạng container.

# Cách duyệt qua một CTDL dạng container bằng vòng lặp `for`
## 1. Sử dụng chỉ số (index) *(chỉ sử dụng cho CTDL dạng sequential container)*
**Cú pháp:**

for (int index_name = 0; index_name < container_name.size(); index_name++)

- `container_name` - tên của CTDL dạng container.
- `index_name` - chỉ số của các phần tử trong `container_name`.
- `container_name[index_name]` - giá trị của phần tử tại chỉ số `index_name` trong `container_name`.

**Ví dụ:**

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector <int> v = {2, 3, 5, 7, 11, 13};
    for (int i = 0; i < v.size(); i++)
    {
        // logic code
    }
}

## 2. Sử dụng vòng lặp for-each *(chỉ sử dụng từ C++ 11 trở lên)*
**Cú pháp:**

for (type element_name : container_name)

- `container_name` - tên của CTDL dạng container.
- `type` - kiểu dữ liệu của phần tử trong `container_name`.
- `element_name` - giá trị của phần tử trong `container_name`.

**Ví dụ:**

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector <int> v = {2, 3, 5, 7, 11, 13};
    for (int i : v)
    {
        // logic code
    }
}

## 3. Sử dụng iterator (con trỏ)
**Cú pháp:**

for (container <type>::iterator iterator_name = container_name.begin(); iterator_name != container_name.end(); iterator_name++)

- `container_name` - tên của CTDL dạng container.
- `iterator_name` - con trỏ trỏ vào phần tử của `container_name`.
- `*iterator_name`: giá trị của phần tử trong `container_name`.

**Ví dụ:**

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector <int> v = {2, 3, 5, 7, 11, 13};
    for (vector <int>::iterator it = v.begin(); it != v.end(); it++)
    {
        // logic code
    }
}

# Vector (mảng động)
## 1. Cấu trúc và cơ chế hoạt động
Như chúng mình đã giới thiệu trong bài viết *[Những kiến thức cơ bản (Phần 2)](/j6sPIVN8RrWbRb4HXVpPjQ)*, **vector** hoạt động tương tự như một mảng thông thường nhưng không cần khai báo trước kích thước và nó có thể **thêm vào** hay **xoá đi** phần tử ở **vị trí cuối**.

Ngoài cách truy cập các phần tử chứa trong vector bằng **chỉ số (index)**, ta còn có thể truy cập bằng **con trỏ (iterator)**.

## 2. Các cú pháp và hàm thông dụng
- `vector <int> v` - khai báo vector `v` với kiểu dữ liệu int, tức là các phần tử trong vector `v` có kiểu dữ liệu là int.
- `v[x]` - truy cập phần tử ở **vị trí `x`** của vector `v`.

### a. Các hàm có độ phức tạp O(1)
- `v.push_back(x)` - **thêm** phần tử `x` vào **vị trí cuối** của vector `v`.
- `v.back()` - trả về **giá trị** của phần tử ở **vị trí cuối** của vector `v`.
- `v.front()` - trả về **giá trị** của phần tử ở **vị trí đầu** của vector `v`.
- `v.pop_back()` - **xoá đi** phần tử nằm ở **vị trí cuối** của vector `v`.
- `v.empty()` - trả về **true** nếu vector `v` **rỗng** (không có phần tử nào) và **false** nếu vector `v` có **ít nhất 1 phần tử**.
- `v.size()` - trả về **kích thước** (số lượng phần tử) của vector `v`.

### b. Các hàm có độ phức tạp O(logN)
*($N$ là kích thước của vector `v`)*
- `lower_bound(v.begin(), v.end(), x)`
+ Trả về **iterator** trỏ vào phần tử có giá trị **nhỏ nhất** mà **$\ge$** `x` trong vector `v` (nếu vector `v` được sắp xếp **tăng dần**).
+ Trả về **iterator** trỏ vào phần tử có giá trị **lớn nhất** mà **$\le$** `x` trong vector `v` (nếu vector `v` được sắp xếp **giảm dần**).
- `upper_bound(v.begin(), v.end(), x)`
+ Trả về **iterator** trỏ vào phần tử có giá trị **nhỏ nhất** mà **$>$** `x` trong vector `v` (nếu vector `v` được sắp xếp **tăng dần**).
+ Trả về **iterator** trỏ vào phần tử có giá trị **lớn nhất** mà **$<$** `x` trong vector `v` (nếu vector `v` được sắp xếp **giảm dần**).

### c. Các hàm có độ phức tạp O(N)
*($N$ là kích thước của vector `v`)*
- `v.clear()` - **xoá toàn bộ** phần tử của vector `v`.

### d. Các hàm có độ phức tạp O(N * logN)
*($N$ là kích thước của vector `v`)*
- `sort(v.begin(), v.end())` - **sắp xếp** các phần tử trong vector `v` theo thứ tự **tăng dần**.
- `sort(v.begin(), v.end(), greater <int>())` - **sắp xếp** các phần tử trong vector `v` theo thứ tự **giảm dần**.

## 3. Một số lưu ý khi sử dụng vector
- Khi vector đang **rỗng** mà ta **truy cập** vào phần tử ở vị trí đầu hoặc cuối 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 hoặc cuối của vector ta cần kiểm tra xem nó có rỗng không.
- Khi vector chỉ chứa **1** phần tử duy nhất thì `vector.front()` và `vector.back()` trả về giá trị của **cùng 1** phần tử.

# Deque (hàng đợi hai đầu)
## 1. Cấu trúc và cơ chế hoạt động
**Deque** là viết tắt của **d**ouble-**e**nded **que**ue.

Mới nghe qua cái tên thì deque có vẻ giống một phiên bản dung hợp giữa **stack** và **queue** *(đọc về stack và queue tại [Standard Template Library (STL) (Phần 1: Container adapters)](/RLY9TS8CTGOsj3734L4z4A))* vì nó có khả năng **lấy giá trị**, **thêm vào** và **xoá đi** phần tử ở **vị trí đầu** lẫn **vị trí cuối**.

*(Ảnh gốc: GeeksforGeeks)*

Tuy nhiên, ta còn có thể truy cập các phần tử trong deque bằng **chỉ số (index)** hay **con trỏ (iterator)**, thậm chí là **sắp xếp** deque và **tìm kiếm nhị phân** trên nó. Chính vì vậy, deque giống với một **vector hai đầu** hơn.

## 2. Các cú pháp và hàm thông dụng
- `deque <int> dq` - khai báo deque `dq` với kiểu dữ liệu int, tức là các phần tử trong deque `dq` có kiểu dữ liệu là int.
- `dq[x]` - truy cập phần tử ở **vị trí `x`** của deque `dq`.

### a. Các hàm có độ phức tạp O(1)
- `dq.push_back(x)` - **thêm** phần tử `x` vào **vị trí cuối** của deque `dq`.
- `dq.push_front(x)` - **thêm** phần tử `x` vào **vị trí đầu** của deque `dq`.
- `dq.back()` - trả về **giá trị** của phần tử ở **vị trí cuối** của deque `dq`.
- `dq.front()` - trả về **giá trị** của phần tử ở **vị trí đầu** của deque `dq`.
- `dq.pop_back()` - **xoá đi* phần tử nằm ở **vị trí cuối** của deque `dq`.
- `dq.pop_front()` - **xoá đi** phần tử nằm ở **vị trí đầu** của deque `dq`.
- `dq.empty()` - trả về **true** nếu deque `dq` **rỗng** (không có phần tử nào) và **false** nếu deque `dq` có **ít nhất 1 phần tử**.
- `dq.size()` - trả về **kích thước** (số lượng phần tử) của deque `dq`.

### b. Các hàm có độ phức tạp O(logN)
*($N$ là kích thước của deque `dq`)*
- `lower_bound(dq.begin(), dq.end(), x)`
+ Trả về **iterator** trỏ vào phần tử có giá trị **nhỏ nhất** mà **$\ge$** `x` trong deque `dq` (nếu deque `dq` được sắp xếp **tăng dần**).
+ Trả về **iterator** trỏ vào phần tử có giá trị **lớn nhất** mà **$\le$** `x` trong deque `dq` (nếu deque `dq` được sắp xếp **giảm dần**).
- `upper_bound(dq.begin(), dq.end(), x)`
+ Trả về **iterator** trỏ vào phần tử có giá trị **nhỏ nhất** mà **$>$** `x` trong deque `dq` (nếu deque `dq` được sắp xếp **tăng dần**).
+ Trả về **iterator** trỏ vào phần tử có giá trị **lớn nhất** mà **$<$** `x` trong deque `dq` (nếu deque `dq` được sắp xếp **giảm dần**).

### c. Các hàm có độ phức tạp O(N)
*($N$ là kích thước của deque `dq`)*
- `dq.clear()` - **xoá toàn bộ** phần tử của deque `dq`.

### d. Các hàm có độ phức tạp O(N * logN)
*($N$ là kích thước của deque `dq`)*
- `sort(dq.begin(), dq.end())` - **sắp xếp** các phần tử trong deque `dq` theo thứ tự **tăng dần**.
- `sort(dq.begin(), dq.end(), greater <int>())` - **sắp xếp** các phần tử trong deque `dq` theo thứ tự **giảm dần**.

## 3. Một số lưu ý khi sử dụng deque
- Khi deque đang **rỗng** mà ta **truy cập** vào phần tử ở vị trí đầu hoặc cuối 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 deque ta cần kiểm tra xem nó có rỗng không.
- Khi deque chỉ chứa **1** phần tử duy nhất thì các thao tác với **vị trí đầu** và **vị tri cuối** của deque đều thao tác với cùng **1** phần tử.

## 4. Bài tập ví dụ
### Đề bài (Chủ đề: Tìm max min trên đoạn tịnh tiến)
Cho một dãy $A$ gồm $N$ phần tử được đánh số từ $1$ đến $N$. Phần tử thứ $i$ có giá trị là $A[i]$. Cho $k$ là một số nguyên dương $(k \le N)$. Với mỗi phần tử $i$ $(k \le i \le N)$, tìm giá trị lớn nhất của các phần tử trong đoạn từ $i–k+1$ đến $i$ trên dãy $A$. $maxRange[i] =$ giá trị lớn nhất trong đoạn.

### Input
- Dòng 1: chứa hai số nguyên dương $N≤10^5,k≤N$ cách nhau bởi dấu cách
- Dòng 2: chứa N số nguyên dương $A_1,A_2,…,A_N$ $(∀i:A_i≤10^9)$ cách nhau bởi dấu cách
### Output
In ra $N - k + 1$ dòng:
- Dòng thứ $i$ in ra giá trị lớn nhất $maxRange[i]$ của các phần tử trong đoạn từ $i−k+1$ đến $i$.

### Sample input

8 3 
1 3 5 7 4 5 9 5

### Sample Output

5
7
7
7
9
9

### Lời giải
#### Thuật toán "trâu bò"
- Đơn giản là đề nói gì chúng ta làm nấy, với mỗi $i$ từ $1 \rightarrow n - k + 1$ ta duyệt $j$ từ $i \rightarrow i + k - 1$ để tìm max và in ra kết quả.

#### Thuật toán tối ưu sử dụng deque
- Để đơn giản, ta hãy lấy 1 ví dụ sau: $n = 9, k = 3, a = [7, 3, 1, 2, 8, 6, 4, 1, 0]$.
- Mục đích khi ta sử dụng deque ở đây là làm sao để lưu được phần tử lớn nhất của dãy $k$ phần tử liên tiếp ở đầu hàng đợi (hay cửa sổ $k$).
- Ví dụ như ở cửa sổ $k$ đầu tiên là $[7, 3, 1]$, ta thấy được rằng ở cửa sổ này, kết quả sẽ là $7$, vậy $dq = [7]$. Thế nhưng liệu số $3, 1$ có còn là vô dụng? Hãy xem xét qua cửa sổ thứ $2$ là $[3, 1, 2]$, đáp án lúc này là $3$. Vậy nên ta nhận xét rằng $3, 1$ lúc này còn có thể là đáp án của một cửa sổ khác, ta cần lưu $3, 1$ này vào $dq$ hiện tại ($dq = [7, 3, 1]$).
- Tiếp theo đó, ta xét ở cửa sổ thứ 2 ($[3, 1, 2]$). Ta sẽ loại bỏ phần tử ở đầu đi vì nó là kết quả của cửa sổ trước đó ($dq = [3, 1]$). Trước khi thêm $2$ vào deque, ta cần để ý một điều rằng, liệu $1$ có cần thiết cho các cửa sổ sau đó hay không? Câu trả lời là không, bởi vì tất cả các cửa sổ sau đó chứa $1$ thì đều sẽ chứa $2$, mà $1$ thì không thể là max vì $1 < 2$. Vậy nên lúc này ta sẽ loại $1$ ra khỏi deque và thêm $2$ vào deque ($dq = [3, 2]$).
- Tương tự như vậy với các cửa sổ sau đó...
- **Vậy nên ta kết luận lại như sau:**
- Với mỗi $i$, nếu $dq$ đang trống (đồng nghĩa với việc không tồn tại một max nào trước đó và $a_i$ là max) ta đẩy $i$ vào $dq$.
- Ta lần lượt loại bỏ các phần tử $\le a_i$ trong $dq$ và thêm $i$ vào $dq$.
- Nếu phần tử ở đầu $dq$ có vị trí nằm ngoài cửa sổ thứ $i$ hiện tại (nằm ngoài đoạn $[i - k + 1, i]$) thì ta xoá phần tử ở đầu đi.

:::spoiler **Code mẫu**

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 1e5 + 5;
int a[maxn];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    deque<int> dq;
    // Ta thêm cửa sổ đầu tiên vào hàng đợi
    for (int i = 1; i <= k; i++) {
        // Nếu deque không rỗng và phần tử ở cuối hàng đợi nhỏ hơn hoặc bằng phần tử hiện tại thì ta loại bỏ phần tử ở cuối hàng đợi
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
    }
    // Kết quả của cửa sổ đầu tiên
    cout << a[dq.front()] << endl;
    
    // Thêm các cửa sổ tiếp theo vào hàng đợi
    for (int i = k + 1; i <= n; i++) {
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        // Nếu phần tử ở đầu hàng đợi có vị trí nằm ngoài đoạn [i - k + 1, i] thì ta loại bỏ
        if (dq.front() < i - k + 1) dq.pop_front();
        // Kết quả của cửa sổ thứ i - k + 1
        cout << a[dq.front()] << endl;
    }
    
    return 0;
}

:::

# Bài tập áp dụng
## [Bài 1](https://cses.fi/problemset/task/1644)
Cho dãy số nguyên a gồm $N$ phần tử và hai số nguyên dương $L, R \le N$. Bạn được yêu cầu tìm dãy con liên tiếp có tổng lớn nhất sao cho độ dài của nó nằm trong đoạn $[L, R]$.

### Input
- Dòng đầu chứa ba số nguyên $N, L, R$ $(L \le R \le N \le 10^5)$.
- Dòng thứ hai chứa $N$ số nguyên miêu tả dãy $a$. $(|a_i| \le 10^9)$.

### Output
Một số nguyên – Tổng lớn nhất tìm được.

### Sample input

9 2 3
40 -39 0 3 -5 0 3 0 1

### Sample output

4

## [Bài 2](https://oj.vnoi.info/problem/qbrect)
Cho một bảng kích thước $M \times N$, được chia thành lưới ô vuông đơn vị $M$ dòng $N$ cột $(1 \le M, N \le 1000)$

Trên các ô của bảng ghi số $0$ hoặc $1$. Các dòng của bảng được đánh số $1, 2, ..., M$ theo thứ tự từ trên xuống dưới và các cột của bảng được đánh số $1, 2, ..., N$ theo thứ tự từ trái qua phải.

**Yêu cầu:** Hãy tìm một hình chữ nhật gồm các ô của bảng thoả mãn các điều kiện sau:
- Hình chữ nhật đó chỉ gồm các số $1$.
- Cạnh hình chữ nhật song song với cạnh bảng.
- Diện tích hình chữ nhật là lớn nhất có thể.

### Input
- Dòng $1$: Ghi hai số $M,N$
- Dòng thứ $i$ trong $M$ dòng tiếp theo: Ghi $N$ số mà số thứ $j$ là số ghi trên ô $(i, j)$ của bảng

### Output
Gồm $1$ dòng duy nhất ghi diện tích của hình chữ nhật tìm được

### Sample Input

11 13
0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 1 1 1 1 0 0
0 1 1 1 1 1 1 1 1 1 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0 0 1 1
0 0 0 0 0 1 0 0 0 0 0 1 1

### Sample Output

49

# Nguồn tham khảo
:::info
[1] https://www.geeksforgeeks.org/the-c-standard-template-library-stl/
[2] https://www.geeksforgeeks.org/iterators-c-stl/
[3] https://cplusplus.com/reference/iterator/
[4] https://cplusplus.com/reference/vector/vector/
[5] https://cplusplus.com/reference/deque/deque/
[6] https://vnoi.info/wiki/algo/data-structures/deque-min-max.md
:::