C# 从 List<T> 移除空元素的优化例子

代码评审中偶尔会发现一些通用的性能问题，在此作记录分享。
需求

我们有时候需要延迟删除 List<T> 中的元素，那时候会先把元素设为 null，最后才一次移除所有空元素。

优化前

static void RemoveNull<T>(List<T> list) {
    for (int i = list.Count - 1; i >= 0; i--)
        if (list[i] == null)
            list.RemoveAt(i); // O(n)
}

 由于 RemoveAt() 是 时间的操作，整个函数是 。但这个问题只需要 时间。

优化后

只要把第一个空元素之后的非空元素往前移，就能实现。

static void RemoveNull<T>(List<T> list) {
    // 找出第一个空元素 O(n)
    int count = list.Count;
    for (int i = 0; i < count; i++)
        if (list[i] == null) {
            // 记录当前位置
            int newCount = i++;

            // 对每个非空元素，复制至当前位置 O(n)
            for (; i < count; i++)
                if (list[i] != null)
                    list[newCount++] = list[i];

            // 移除多余的元素 O(n)
            list.RemoveRange(newCount, count - newCount);
            break;
        }
}

 List<T> 实际上也提供 RemoveAll(Predicate<T>) 的接口（参考实现），可以 完成相同工作。但在目前 Unity 的 IL2CPP 下，因 delegate 的调用成本，自行实现会稍快一些。

C++ 可用 std::remove, std::remove_if，因为支持内联不需考虑调用成本。