Cấu trúc dữ liệu trong C/C++

Mảng động và std::vector trong C, C++

Trong bài học này, bạn sẽ tự cài đặt một mảng động có thể tự mở rộng khi thêm phần tử trong C, rồi so sánh với std::vector của C++.

Giới thiệu

Mảng động (dynamic array) là mảng có thể tăng kích thước khi cần. Nó phân biệt hai khái niệm: số phần tử đang chứa (size) và dung lượng đã cấp phát (capacity). Khi mảng đầy, chương trình cấp phát một vùng nhớ lớn hơn, thường gấp đôi, rồi chuyển dữ liệu sang đó.

Những điểm quan trọng

  • Xác định những điều kiện luôn phải đúng (invariant) của cấu trúc dữ liệu trước khi viết các thao tác.
  • Xử lý đầy đủ các trường hợp rỗng, đầy và cấp phát bộ nhớ thất bại.
  • Đánh giá cả độ phức tạp lẫn cách quản lý vùng nhớ của từng thao tác.

Xem cách hoạt động

Nhấn push_back nhiều lần. Khi mảng đầy, nó cấp phát vùng nhớ lớn gấp đôi và sao chép mọi phần tử sang.

Code ví dụ bằng C và C++

C
Chạy code →
main.c
#include <stdio.h>
#include <stdlib.h>

int main(void) {
    size_t size = 0, capacity = 2;
    int *values = malloc(capacity * sizeof *values);
    if (!values) return 1;
    for (int value = 1; value <= 5; ++value) {
        if (size == capacity) {
            capacity *= 2;
            int *grown = realloc(values, capacity * sizeof *values);
            if (!grown) {
                free(values);
                return 1;
            }
            values = grown;
        }
        values[size++] = value * value;
    }
    printf("size=%zu capacity=%zu last=%d\n",
           size, capacity, values[size - 1]);
    free(values);
}
Kết quả khi chạy
size=5 capacity=8 last=25
C++
Chạy code →
main.cpp
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values;
    for (int value = 1; value <= 5; ++value) {
        values.push_back(value * value);
    }
    std::cout << "size=" << values.size()
              << " last=" << values.back() << '\n';
}
Kết quả khi chạy
size=5 last=25

So sánh C và C++

Trong phiên bản C, khi size bằng capacity, chương trình nhân đôi capacity và gọi realloc để mở rộng vùng nhớ. Kết quả của realloc được gán cho một con trỏ tạm grown để nếu cấp phát thất bại, vùng nhớ cũ vẫn có thể được giải phóng. std::vector của C++ đóng gói đúng chiến lược tăng trưởng này, đồng thời tự giải phóng vùng nhớ, hỗ trợ iterator và an toàn khi có ngoại lệ.

C

Dữ liệu (struct) và các thao tác thường tách rời, bộ nhớ được cấp phát và giải phóng thủ công.

C++

Class và container có thể tự bảo vệ tính đúng đắn của dữ liệu và tự quản lý tài nguyên.

Bài tập mở rộng

Hãy chạy cả hai phiên bản, sau đó thử thay đổi code để quan sát sự khác biệt về mức độ an toàn mà mỗi ngôn ngữ mang lại.

  • Thêm kiểm thử cho trạng thái rỗng và khi đạt giới hạn dung lượng.
  • Viết phần giải phóng bộ nhớ và kiểm tra rò rỉ bộ nhớ.
  • So sánh độ phức tạp với container tương ứng của thư viện chuẩn.

Luyện tập với thử thách

Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.

Tất cả thử thách