如何有效地从List <T>中删除(C#)？

Question

如果我理解正确(如果我错了请纠正我),列表是由.NET中的数组实现的,这意味着列表中每个项目的删除都会导致重新分配所有列表(这意味着O(n)).

我正在开发一款游戏,在游戏中我有许多子弹在任何给定时刻在空中飞行,让我们说100个子弹,每帧我移动几个像素并检查与游戏中物体的碰撞,我需要删除从列表中每个碰撞的子弹.

所以我在另一个临时列表中收集了碰撞的子弹,然后执行以下操作:

foreach (Bullet bullet in bulletsForDeletion)
    mBullets.Remove(bullet);

因为循环是O(n)和删除O(n),我花费O(n^2时间删除.

有没有更好的方法来删除它,或更合适的集合使用？

Answer 1

集合和链接列表都具有恒定的时间删除.你能使用这些数据结构吗？

没有办法避免从中移除O(N)成本List<T>.如果这对您来说是个问题,您将需要使用不同的数据结构.它可能会使计算bulletsToRemove的代码感觉更好.

ISet<T> 有很好的方法来计算对象集之间的差异和交叉点.

你使用套装丢失了订单,但鉴于你正在使用子弹,我猜这不是问题.你仍然可以在恒定的时间内枚举它.

在您的情况下,您可能会写:

mBullets.ExceptWith(bulletsForDeletion);

Answer 2

创建一个新列表：

var newList = `oldList.Except(deleteItems).ToList()`.

尽量使用功能性习语。不要修改现有的数据结构，创建新的。

由于散列，该算法是 O(N)。