从C中删除数组中大量元素的最快方法

Question

我有动态数组,包含数千个元素甚至更多,为了不消耗大量的内存,我可以从中删除不需要的元素(即元素已被使用,不再需要它们)所以从一开始我通过估计每次删除元素后所需的最大大小,可以分配更小的内存大小.

我用这种方式但是需要很长时间才能完成,有时需要30分钟!

int x, y ;
for (x = 0 ; x<number_of_elements_to_remove ; x++){
    for (y = 0 ; y<size_of_array; y++ ){
            array[y] = array[y+1];
    }
}

有比这更快的方法吗？

Answer 1

您可以创建一个循环，使用单个读取和单个写入索引，而不是一次删除一个元素，使用两个循环来实现 O(n ^{2 ) 解决方案。}遍历数组，同时复制项目：

int rd = 0, wr = 0;
while (rd != size_of_array) {
    if (keep_element(array[rd])) {
        array[wr++] = array[rd];
    }
    rd++;
}

循环结束时wr是 中保存的元素数量array。