Xóa Một Phần Tử Khỏi Mảng Động

Năm ngoái tôi từng giới thiệu giao diện mô-đun mảng động mà mình triển khai trong một dự án. Trên thực tế, mô-đun này còn hỗ trợ nhiều thao tác phong phú hơn, ví dụ như chức năng xóa phần tử được chỉ định bởi một trình lặp (iterator):

1

void array_erase(struct array *, seqi iter);

Theo thiết kế ban đầu, hàm array_erase sẽ xóa phần tử mà tham số iter trỏ đến. Tuy nhiên, điều này đặt ra một câu hỏi quan trọng: sau khi xóa, iter có nên tiếp tục duy trì tính hợp lệ hay không?
Về mặt lý thuyết, sau khi thực hiện xóa, iter nên trở thành một trình lặp vô hiệu vì phần tử mà nó trỏ đến đã bị hủy bỏ. Trên thực tế, khi duyệt mảng để xóa các phần tử thỏa mãn điều kiện nào đó, việc làm mất hiệu lực của tất cả iterator hiện tại sẽ khiến người dùng gặp nhiều bất tiện.

Mảng động này thực chất được xây dựng dựa trên cấu trúc hàng đợi hai đầu (deque). Để giải quyết vấn đề trên, tôi đã áp dụng một kỹ thuật thông minh: thay vì xóa trực tiếp phần tử tại vị trí iter, hàm sẽ hoán đổi nó với phần tử ở đầu hàng đợi, sau đó loại bỏ phần tử đầu tiên thông qua thao tác pop.
Với cách làm này, trình lặp iter vẫn giữ nguyên vị trí vật lý trong mảng, dù giá trị mà nó trỏ tới đã bị thay thế bằng phần tử đã duyệt qua trước đó. Điều này cho phép vòng lặp tiếp tục thực thi mà không gặp lỗi.

Tuy nhiên, hôm nay tôi phát hiện một tình huống đặc biệt: Nếu iter ban đầu trỏ chính xác vào vị trí đầu deque, sau khi pop thực thi, iter sẽ trỏ vào một vị trí không hợp lệ. Dù đây không phải lỗi kỹ thuật, nhưng kết quả này tạo cảm giác khó chịu cho người dùng. Sau khi cân nhắc, tôi quyết định điều chỉnh lại định nghĩa của array_erase.

Phiên bản mới của array_erase sẽ thực hiện hai nhiệm vụ:

1. Xóa phần tử được trỏ bởi iter
2. Tiến iter đến vị trí kế tiếp (nếu iter đang ở cuối mảng thì sẽ biến thành tham chiếu rỗng)

Nhân tiện, trong C++ vấn đề này được xử lý theo cách đặc biệt: Thuật toán remove không trực tiếp xóa phần tử mà đẩy các phần tử thỏa mãn điều kiện về cuối container, sau đó dùng erase để xóa hàng loạt. Cách tiếp cận này giúp tránh mâu thuẫn khi thao tác với iterator. Tuy nhiên, cá nhân tôi không ưa chuộng kiểu viết remove/remove_if này - trong ngôn ngữ hàm (functional language), cách làm này tự nhiên như nước chảy, nhưng ở C++ với hỗ trợ lập trình hàm còn hạn chế, việc lạm dụng các template method kiểu này khiến đoạn mã trở nên gượng ép và khó đọc.