動的配列から要素を削除するときにmemmoveの後で再割り当てする必要はありますか？

Question

私はCでArrayListの実装をしています。ArrayListはポインタ（void *）を格納します。つまり、ArrayListはポインタの動的配列です。ここで私は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*)); 
} 

を私はコードにコメントしたように、私はlist->ptrまたはmemmoveはそれを行いますreallocをする必要がありますか？

Answer 1

最初のこと：memmoveはメモリ割り当てにまったく関与していません。それは、メモリの一部（潜在的に重なり合う部分）を動かすだけです。

この例では、アレイを再割り当てする必要はありません。これは、多くの要素が削除されて再利用のために関連する量の空き領域があるかどうかによって主に異なります。これが本当に関連していると思われる場合は、以下のreallocステートメントが正しいように見えます。ただし、ヒープの断片化の問題により、配列ごとにいくつかの要素が削除された場合、未割り当ての領域はまったく使用できない可能性があることに注意してください。

Answer 2

memmove()メモリを解放しません。

realloc()を使用するか、アイテムを追加/挿入する必要がある場合に備えて、余分なスペースを残してください。それは割り当てられたサイズを追跡するために構造体に余分なメンバを必要とします。あなたはを計画している場合

また、動的またはが項目を挿入追加し、毎回realloc()を呼び出すために持っ防ぐために、より大きな塊であなたのバッファを成長させたい場合があります。通常、これは特定のサイズまで2の累乗で実行されます（たとえば16 - 32 - 64 - 1024）。その後、毎回固定サイズのバッファを展開してください。