c - 从 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²) 解决方案，您可以创建一个循环，使用单个读取和单个写入索引。遍历数组，边走边复制项目:

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

在循环结束时，wr 是数组 中保留的元素数。