Tôi có cần realloc sau khi memmove khi loại bỏ một phần tử từ mảng động?

Question

Tôi đang làm việc về triển khai ArrayList trong C. ArrayList lưu trữ con trỏ (void *), điều đó có nghĩa ArrayList là một mảng động của con trỏ. Dưới đây như thế nào để loại bỏ một phần tử từ ArrayList:

typedef struct 
{ 
    void* ptr; // pointer of array (beginning) 
    int length; // pointer count 
}ArrayList; 

void ArrayList_Remove(ArrayList *list, int index) 
{ 
    memmove(
     list->ptr + (sizeof(void*) * index), 
     list->ptr + (sizeof(void*) * (index + 1)), 
     (list->length - index) * sizeof(void*) 
    ); 
    list->length--; 
    // Do I need to realloc list->ptr to free space? 
    // list->ptr = realloc(list->ptr, list->length * sizeof(void*)); 
} 

Như tôi đã nhận xét trong mã, tôi cần phải realloc list->ptr hoặc memmove sẽ làm điều đó?

Answer 1

Điều đầu tiên: memmove không liên quan đến việc cấp phát bộ nhớ. Nó chỉ làm những gì nó nên, di chuyển (có khả năng chồng chéo) các bộ phận của bộ nhớ.

Trong ví dụ của bạn, không cần thiết phải thực hiện lại mảng. Nó chủ yếu phụ thuộc nếu có quá nhiều phần tử được loại bỏ sẽ có một số lượng không gian trống có liên quan để tái sử dụng. Nếu bạn cảm thấy rằng điều này thực sự có liên quan, tuyên bố realloc của bạn bên dưới có vẻ chính xác. Nhưng hãy ghi nhớ rằng không gian chưa được phân bổ có thể không sử dụng được nếu chỉ một vài phần tử bị xóa trên mỗi mảng do các vấn đề phân mảnh heap.

Answer 2

memmove() sẽ không giải phóng bộ nhớ.

Bạn có thể sử dụng realloc() hoặc có thể chỉ để trống thêm không gian trong trường hợp bạn cần thêm/chèn một mục. Điều đó sẽ cần thêm một thành viên trong cấu trúc của bạn để theo dõi kích thước được phân bổ.

Ngoài ra, nếu bạn có kế hoạch để động thêm hoặc chèn mục, bạn có thể muốn phát triển bộ đệm của bạn trong khối lớn hơn để tránh tình trạng phải gọi realloc() mỗi lần. Thông thường, điều này được thực hiện với hai giá trị đến một kích thước nhất định (ví dụ 16 - 32 - 64 - 1024). Sau đó, mở rộng bộ đệm với kích thước cố định mỗi lần.