Dynamic array và std::vector
Dynamic array tách logical size khỏi allocated capacity và tăng capacity theo cấp số nhân.
Dynamic array và std::vector là gì?
Dynamic array tách logical size khỏi allocated capacity và tăng capacity theo cấp số nhân.
Mở rộng contiguous storage khi append dữ liệu.
Điểm quan trọng
- Xác định invariant trước khi cài đặt operation.
- Xử lý trường hợp rỗng, đầy và cấp phát thất bại.
- Đánh giá đồng thời complexity và ownership.
Code ví dụ bằng C và C++
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);
}
size=5 capacity=8 last=25C++
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';
}
size=5 last=25So sánh C và C++
C tự kiểm tra realloc và cập nhật capacity; std::vector đóng gói growth, destructor, iterator và exception safety.
C
Struct và operation thường tách rời, cấp phát được quản lý thủ công.
C++
Class và container có thể bảo vệ invariant và tự quản lý tài nguyên.
Bài tập mở rộng
Chạy cả hai phiên bản rồi thay đổi để quan sát khác biệt về bảo đảm của từng ngôn ngữ.
- Thêm test cho trạng thái rỗng và capacity boundary.
- Cài đặt cleanup rồi kiểm tra memory leak.
- So sánh complexity với standard container.