如何高效实现动态长度数组的整块右移？删除元素后保序

架构老林

2026-5-28

优化动态数组删除后整块右移的效率方案

嘿，我完全懂你现在的困扰——在动态数组里删除元素后，挨个移动后续元素的操作，数据量一大就慢得让人头疼，而且还得保证元素顺序不变对吧？咱们来聊聊几个更高效的解决方案，帮你摆脱这种低效的逐个移动模式。

1. 用语言内置的批量内存拷贝/切片操作（最直接的优化）

首先要明确：基于连续内存的动态数组（比如C++的vector、Java的ArrayList、Python的list），本质上内存是连续的，要保持顺序的话，没法完全跳过内存拷贝，但我们可以用底层优化过的批量拷贝工具，代替自己写的循环逐个赋值——这些工具通常会利用CPU的批量指令集，效率比手动循环高几个量级。

举几个不同语言的实例：

C++ 示例

用std::copy或者memmove来批量移动元素，最后截断数组：

#include <vector>
#include <algorithm>

int main() {
    std::vector<int> arr = {1, 2, 3, 4, 5};
    int remove_idx = 2; // 要删除索引为2的元素（值为3）

    // 把remove_idx+1到末尾的元素，批量拷贝到remove_idx起始的位置
    std::copy(arr.begin() + remove_idx + 1, arr.end(), arr.begin() + remove_idx);
    // 移除最后一个重复的元素
    arr.pop_back();

    // 现在arr的内容是 {1, 2, 4, 5}
    return 0;
}

其实vector自带的erase方法内部就是这么实现的，直接用arr.erase(arr.begin() + remove_idx)更省事，底层已经做了优化。

Java 示例

用System.arraycopy批量拷贝，或者直接用ArrayList的remove方法（内部也是基于System.arraycopy实现的）：

import java.util.ArrayList;

public class ArrayShiftOpt {
    public static void main(String[] args) {
        ArrayList<Integer> arr = new ArrayList<>();
        arr.add(1); arr.add(2); arr.add(3); arr.add(4); arr.add(5);
        int removeIdx = 2;

        // 手动调用批量拷贝：从removeIdx+1的位置，拷贝到removeIdx，长度为剩余元素数
        System.arraycopy(arr.toArray(), removeIdx + 1, arr.toArray(), removeIdx, arr.size() - removeIdx - 1);
        arr.remove(arr.size() - 1);

        // 更简单的方式：直接用ArrayList的remove方法，底层已经优化过
        // arr.remove(removeIdx);
    }
}

Python 示例

Python的list切片操作底层是批量实现的，直接拼接切片就能完成删除+右移的效果：

arr = [1, 2, 3, 4, 5]
remove_idx = 2
# 拼接删除位置前后的切片，底层是批量内存操作
arr = arr[:remove_idx] + arr[remove_idx + 1:]
# 结果：[1, 2, 4, 5]

2. 标记删除 + 延迟整理（适合频繁删除的场景）

如果你的业务场景需要频繁执行删除操作，每次删除都做拷贝还是会有累计开销，这时候可以用「标记删除+延迟整理」的思路：

给每个元素加一个“有效标记”，删除时只标记该元素无效，不立即移动其他元素；
当无效元素达到一定比例（比如30%），或者数组需要扩容/缩容时，再一次性把所有有效元素批量拷贝到新的内存区域，完成整理。

伪代码示例：

class EfficientDynamicArray:
    def __init__(self):
        self.data = []
        self.is_valid = []  # 标记对应位置的元素是否有效

    def add(self, value):
        self.data.append(value)
        self.is_valid.append(True)

    def remove(self, idx):
        if 0 <= idx < len(self.data):
            self.is_valid[idx] = False

    def compact(self):
        # 一次性整理所有有效元素
        new_data = []
        for val, valid in zip(self.data, self.is_valid):
            if valid:
                new_data.append(val)
        self.data = new_data
        self.is_valid = [True] * len(self.data)

    def get(self, idx):
        # 访问时跳过无效元素，或者先触发整理
        current_idx = 0
        for i in range(len(self.data)):
            if self.is_valid[i]:
                if current_idx == idx:
                    return self.data[i]
                current_idx += 1
        raise IndexError("Index out of range")

这种方式把删除操作的开销从O(n)降到了O(1)，只有整理的时候才会有一次O(n)的拷贝，适合频繁删除的场景。

3. 换用链表结构（权衡访问效率）

如果你的场景中删除操作远多于随机访问操作，可以考虑用链表（比如Java的LinkedList、C++的std::list）。链表删除元素只需要修改前后节点的指针，不需要移动任何元素，时间复杂度是O(1)（如果已经找到要删除的节点）。

但要注意：链表的随机访问效率很低（O(n)），如果需要频繁按索引访问元素，还是数组更合适。

总结一下：

单次/少量删除：直接用语言内置的批量拷贝/切片操作，比手动循环高效得多；
频繁删除：用标记删除+延迟整理，减少每次操作的即时开销；
删除多、访问少：考虑换用链表结构，权衡性能 trade-off。

内容的提问来源于stack exchange，提问作者J. Joly

如何高效实现动态长度数组的整块右移？删除元素后保序

1. 用语言内置的批量内存拷贝/切片操作（最直接的优化） #

C++ 示例 #

Java 示例 #

Python 示例 #

2. 标记删除 + 延迟整理（适合频繁删除的场景） #