Dynamic Array: mảng động và cách tự cài đặt

Giới thiệu

Mảng động là vùng nhớ liên tục có dự trữ chỗ trống. Hết chỗ thì cấp vùng gấp đôi và sao chép sang. Bài này chỉ học một thứ: tự cài đặt Dynamic Array.

Kiến thức cần nhớ

Size vs capacity

• size: số phần tử đang dùng.
• capacity: số ô đã cấp phát.
• size == capacity khi push → phải cấp phát lại.

Vì sao nhân đôi

Cấp vùng mới gấp đôi, copy toàn bộ, rồi mới thêm. Nhờ dự trữ dư nên n lần push chỉ tốn $O(1)$ trung bình.

Bảng độ phức tạp

Khung struct

// C
typedef struct {
  int *data;
  size_t size;
  size_t capacity;
} DynamicArray;

// C++: class DynamicArray với data_, size_, capacity_ + destructor

Quy tắc bắt buộc:

• realloc qua con trỏ tạm, thất bại thì mảng cũ còn nguyên.
• Mọi get/set/insert/erase/pop kiểm tra biên, không crash.
• destroy free đúng 1 lần, gán NULL, không leak.

Ví dụ

DynamicArray a; da_init(&a, 2);
da_push(&a, 1); da_push(&a, 2); da_push(&a, 3);
// capacity: 2 -> 4, size = 3
da_get(&a, 1);    // = 2
da_insert(&a, 1, 9); // 1, 9, 2, 3
da_erase(&a, 1);     // 1, 2, 3
da_pop(&a);          // 1, 2
da_destroy(&a);

💻 Bài tập

Ngôn ngữ: C cho Bài 1-2, C++ cho Bài 3. Nộp vào thư mục day-001/ trong repo của bạn.

Bài 1: Cài đặt Dynamic Array bằng C

Viết dynamic_array.h và dynamic_array.c. Mảng lưu phần tử kiểu int.

typedef struct {
  int *data;
  size_t size;      // số phần tử đang dùng
  size_t capacity;  // số ô đã cấp phát
} DynamicArray;

API bắt buộc. Mọi hàm trả bool đều trả false khi lỗi và giữ mảng nguyên trạng.

Ràng buộc

• Chỉ dùng malloc, realloc, free, memmove. Không dùng thư viện container.
• realloc luôn qua con trỏ tạm. Cấp phát thất bại thì dữ liệu cũ còn nguyên.
• Thư viện không printf. Lỗi báo qua giá trị trả về.

Test mẫu. Viết trong test_da.c bằng assert.

init(cap=2); push 1, 2, 3        -> size=3, capacity=4, [1, 2, 3]
get(1)                           -> true, out=2
insert(1, 9)                     -> [1, 9, 2, 3]
insert(4, 7)                     -> [1, 9, 2, 3, 7]   (chèn cuối hợp lệ)
erase(1)                         -> [1, 2, 3, 7]
pop                              -> true, out=7, [1, 2, 3]
get(5) / set(5, 0) / erase(5)    -> false, mảng không đổi
insert(9, 0)                     -> false
pop 3 lần, rồi pop tiếp          -> lần thứ 4 trả false
reserve(100); shrink_to_fit      -> capacity 100, rồi về 1

Bài 2: Đo vết capacity và chi phí copy

Thêm vào struct biến đếm size_t copies: tổng số phần tử bị sao chép khi cấp phát lại.

1. Khởi tạo cap = 1, push 10 phần tử. In ra mỗi lần capacity đổi. Kết quả phải là 1 -> 2 -> 4 -> 8 -> 16.
2. Viết thêm 2 chiến lược tăng: +1 ô và x1.5. Chọn chiến lược qua tham số ở da_init.
3. Với mỗi chiến lược, push $n = 10^5$ phần tử rồi in bảng:

chien_luoc   n        copies      copies/n
x2           100000   ...         ...
x1.5         100000   ...         ...
+1           100000   ...         ...

Kiểm tra: nhân đôi cho copies < 2n. Chiến lược +1 cho copies xấp xỉ $n^2/2$. Viết 3 dòng trong README.md giải thích kết quả.

Bài 3: Bản C++ Vec<T> (nâng cao)

Viết class template Vec<T> trong vec.hpp, tự quản lý bộ nhớ. Không dùng std::vector.

Test mẫu: dùng Vec<std::string>. Push 1000 chuỗi, copy sang Vec khác, sửa bản copy, kiểm tra bản gốc không đổi. Move sang biến mới, kiểm tra nguồn có size() == 0.

✅ Tiêu chí hoàn thành

• Toàn bộ test assert của Bài 1 pass.
• Build với gcc -Wall -Wextra -g -fsanitize=address,undefined không có cảnh báo, không lỗi runtime.
• valgrind --leak-check=full ./test_da báo 0 bytes in 0 blocks bị leak.
• Bảng đo Bài 2 có số thật và 3 dòng giải thích.
• Nói được bằng lời: vì sao nhân đôi cho push $O(1)$ trung bình, còn +1 cho tổng $O(n^2)$.

❓ Câu hỏi ôn tập

• size khác capacity ở điểm nào? Khi nào phải cấp phát lại?
• Vì sao push cuối là $O(1)$ trung bình nhưng insert giữa là $O(n)$?
• Vì sao realloc phải qua con trỏ tạm?
• Khi nào dùng reserve, khi nào dùng shrink_to_fit?

🌕 Bạn đã xong ngày 1. Cài đặt xong Dynamic Array chạy sạch thì sang Day 2.