📚 Bài giảng HTML tương tác

VECTOR trong C++

Vector là mảng động của thư viện STL, giúp lưu trữ dữ liệu linh hoạt, tự thay đổi kích thước và rất hay dùng trong bài toán mảng, đồ thị, quy hoạch động.

1. Linh hoạt

Không cần biết trước chính xác số phần tử. Có thể thêm/xóa trong lúc chạy chương trình.

2. Truy cập nhanh

Truy cập phần tử bằng chỉ số như mảng: v[i], độ phức tạp O(1).

3. Dễ dùng với STL

Kết hợp tốt với sort, reverse, lower_bound, đồ thị danh sách kề.

Đặt vấn đề: vì sao cần vector?

Giả sử một bài toán có nhiều hàng dữ liệu, mỗi hàng có số phần tử khác nhau. Nếu dùng mảng tĩnh quá nhỏ thì thiếu ô nhớ; nếu khai báo quá lớn thì dễ tràn bộ nhớ.

Không nên: khai báo mảng quá lớn như char a[1000001][1000001], vì số ô nhớ có thể lên tới 1012.
Nên dùng: vector hoặc vector<vector<T>> để cấp phát đúng theo dữ liệu thực tế.

Khái niệm

Vector là mảng động trong C++. Các phần tử của vector nằm liên tiếp trong bộ nhớ, có thể truy cập bằng chỉ số và có thể tự mở rộng khi thêm phần tử mới.

Tiêu chíMảng tĩnhVector
Kích thướcCố định sau khi khai báoCó thể thay đổi khi chạy
Thêm phần tửKhó, phải tự quản lýDùng push_back(x)
Xóa phần tử cuốiPhải tự giảm biến đếmDùng pop_back()
Truy cậpa[i]v[i] hoặc v.at(i)

Khai báo và khởi tạo vector

Ví dụ khai báo vector 1 chiều
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v1;              // vector rỗng
    vector<int> v2 = {10, 2, 10, 5};
    vector<int> v3(5);           // 5 phần tử, mặc định bằng 0
    vector<int> v4(5, 7);        // 5 phần tử, mỗi phần tử bằng 7

    return 0;
}
Cú pháp tổng quát: vector<kiểu_dữ_liệu> tên_vector;

Nhập và xuất vector 1 chiều

Ta có thể nhập từng giá trị rồi dùng push_back(x) để đưa vào cuối vector.

Nhập n số vào vector và in ra
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a;
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        a.push_back(x); // thêm x vào cuối vector
    }

    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }

    return 0;
}
Lưu ý: vector đánh số từ 0. Phần tử đầu tiên là a[0], phần tử cuối là a[a.size()-1].

Duyệt vector bằng iterator

begin() trỏ tới phần tử đầu tiên, end() trỏ tới vị trí sau phần tử cuối.

Duyệt bằng iterator
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a = {4, 7, 2, 9};

    for (auto it = a.begin(); it != a.end(); ++it) {
        cout << *it << " ";
    }

    return 0;
}
Cách ngắn hơn: dùng vòng lặp for-each for (int x : a).
Duyệt bằng for-each
for (int x : a) {
    cout << x << " ";
}

Vector 2 chiều

Vector 2 chiều có thể hiểu là vector mà mỗi phần tử của nó lại là một vector.

Khai báo vector 2 chiều n × m
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 4, m = 5;

    // n hàng, mỗi hàng có m phần tử int, ban đầu bằng 0
    vector<vector<int>> vec(n, vector<int>(m));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            vec[i][j] = i + j + 1;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << vec[i][j] << " ";
        }
        cout << '\n';
    }

    return 0;
}

Vector 2 chiều có số phần tử mỗi hàng khác nhau

Nhập n hàng, mỗi hàng m phần tử
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> a(n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int x;
            cin >> x;
            a[i].push_back(x);
        }
    }

    for (int i = 0; i < n; i++) {
        for (int x : a[i]) {
            cout << x << " ";
        }
        cout << '\n';
    }

    return 0;
}

Một số hàm thành viên quan trọng

HàmÝ nghĩaĐộ phức tạp thường gặp
v.size()Trả về số lượng phần tử trong vectorO(1)
v.empty()Kiểm tra vector có rỗng khôngO(1)
v[i]Truy cập phần tử thứ i, không kiểm tra lỗi chỉ sốO(1)
v.at(i)Truy cập phần tử thứ i, có kiểm tra lỗi chỉ sốO(1)
v.front()Lấy phần tử đầu tiênO(1)
v.back()Lấy phần tử cuối cùngO(1)
v.push_back(x)Thêm x vào cuối vectorO(1) trung bình
v.pop_back()Xóa phần tử cuối cùngO(1)
v.insert(pos, x)Chèn x trước vị trí iterator posO(n)
v.erase(pos)Xóa phần tử tại vị trí iterator posO(n)
Ví dụ các hàm thường dùng
vector<int> v = {1, 2, 1};

cout << v.size();   // 3
cout << v.empty();  // 0, vì vector không rỗng
cout << v[1];       // 2
cout << v.at(2);    // 1

cout << v.front();  // 1
cout << v.back();   // 1

v.push_back(8);             // v = {1, 2, 1, 8}
v.insert(v.begin(), 5);     // v = {5, 1, 2, 1, 8}
v.insert(v.begin() + 1, 6); // v = {5, 6, 1, 2, 1, 8}
v.erase(v.begin());         // v = {6, 1, 2, 1, 8}
v.pop_back();               // v = {6, 1, 2, 1}

Ứng dụng vector trong đồ thị: danh sách kề

Với đồ thị có n đỉnh, ta thường dùng vector<int> adj[MAXN] hoặc vector<vector<int>> adj(n+1) để lưu danh sách các đỉnh kề.

1 2 3 4 5 6
Lưu đồ thị bằng vector
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> adj(n + 1);

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); // đồ thị có hướng u -> v
    }

    for (int u = 1; u <= n; u++) {
        cout << "Ke cua " << u << ": ";
        for (int v : adj[u]) cout << v << " ";
        cout << '\n';
    }

    return 0;
}

Lỗi thường gặp khi dùng vector

1
Truy cập khi vector chưa có phần tử.
Ví dụ: vector<int> v; v[0] = 5; là sai vì vector đang rỗng.
2
Nhầm chỉ số từ 1 và từ 0.
Vector đánh số từ 0, nên vòng lặp thường là for (int i=0; i<v.size(); i++).
3
Dùng insert/erase quá nhiều ở giữa vector.
Các thao tác này có thể O(n), nếu làm quá nhiều sẽ chậm.
4
So sánh int với size_t.
v.size() trả về kiểu không âm. Khi cần, có thể ép kiểu: int n = (int)v.size();.

Bài tập luyện tập vector

Các bài dưới đây phù hợp để học sinh luyện cách đọc dữ liệu không cố định, xử lý dãy bằng vector và lưu đồ thị bằng danh sách kề.

📝 Câu 1. DEMSO.CPP

Cho một dãy gồm số lượng số lẻ. Hãy tìm số nằm ở chính giữa dãy.

Dữ liệu: File DEMSO.INP gồm nhiều dòng, mỗi dòng là một số trong đoạn [0, 105]. Số lượng số không quá 106 và luôn là số lẻ.

Kết quả: Ghi ra DEMSO.OUT số nằm ở chính giữa.

DEMSO.INP
1
2
8
6
9
DEMSO.OUT
8

Gợi ý: Đọc đến hết file bằng while(cin >> x), đưa vào vector rồi in a[a.size()/2].

📝 Câu 2. KHACNHAU.CPP

Cho một dãy số, mỗi số nằm trong đoạn từ 0 đến 109. Hãy đếm có bao nhiêu số khác nhau trong dãy.

Dữ liệu: File KHACNHAU.INP gồm một dòng là một dãy số, không quá 106 số.

Kết quả: Ghi ra KHACNHAU.OUT số lượng giá trị khác nhau.

KHACNHAU.INP
1 5 3 4 2 4 5 7 8
KHACNHAU.OUT
7

Gợi ý: Lưu vào vector, sắp xếp, sau đó dùng unique hoặc tự đếm khi giá trị thay đổi.

📝 Câu 3. CANHNHAU.CPP

Cho danh sách các con đường hai chiều giữa các ngôi nhà. Hãy khôi phục danh sách những ngôi nhà kề với từng ngôi nhà.

Dữ liệu: Dòng đầu gồm N, M. M dòng tiếp theo gồm u, v là một con đường hai chiều nối u và v.

Kết quả: In N dòng. Dòng i gồm các ngôi nhà kề với i, kết thúc bằng số 0.

CANHNHAU.INP
5 6
3 5
5 2
3 4
4 1
1 2
5 1
CANHNHAU.OUT
4 2 5 0
5 1 0
5 4 0
3 1 0
3 2 1 0

Gợi ý: Dùng vector<vector<int>> adj(n+1). Với mỗi cạnh u-v, thêm v vào adj[u] và u vào adj[v].

📝 Câu 4. LIENTHONG.CPP

Một đất nước có N khu dân cư và M con đường một chiều. Cần chia các khu dân cư thành số nhóm nhỏ nhất sao cho trong mỗi nhóm, từ một khu bất kỳ có thể đi đến các khu còn lại trong nhóm.

Dữ liệu: Dòng đầu gồm N, M. M dòng sau gồm u, v là đường một chiều từ u đến v. N ≤ 100, M ≤ 200.

Kết quả: Ghi ra số K nhỏ nhất.

LIENTHONG.INP
6 7
1 3
2 1
5 3
3 2
4 6
6 5
6 4
LIENTHONG.OUT
3

Gợi ý: Đây là bài toán đếm số thành phần liên thông mạnh. Có thể dùng Floyd-Warshall với N nhỏ, hoặc Tarjan/Kosaraju.

📝 Câu 5. SEQDIV.CPP

Cho hai số nguyên dương n và k. Hãy đếm số lượng dãy a1, a2, ..., an sao cho mỗi ai nằm trong đoạn [1, k] và với hai phần tử kề nhau, một số chia hết cho số còn lại nhưng không được xảy ra đồng thời hai chiều.

Dữ liệu: File SEQDIV.INP gồm hai số n và k.

Kết quả: Ghi ra SEQDIV.OUT số lượng dãy thỏa mãn, lấy phần dư cho 109+7.

SEQDIV.INP
4 3
SEQDIV.OUT
8

Gợi ý: Dùng quy hoạch động. Gọi dp[i][x] là số dãy độ dài i kết thúc bằng x. Chuyển từ y sang x nếu x và y thỏa điều kiện chia hết một chiều.

Đưa bài giảng vào OJ

Sau khi đưa file này lên server, ví dụ tại:

https://hvojbd.ddns.net/docs/LTBT/VECTOR_LIEN_KET.htm

Trong phần mô tả OJ, dán đoạn sau:

Mã iframe dùng trong OJ
<iframe
src="https://hvojbd.ddns.net/docs/LTBT/VECTOR_LIEN_KET.htm"
width="100%"
height="850px"
frameborder="0">
</iframe>
Bài giảng VECTOR C++ • Thiết kế lại để dùng trực tiếp trong OJ
↑ Đầu trang style> body { user-select: none; }