在迭代时从列表中删除/添加项目

Question

首先,我知道由于显而易见的原因,这不可能开箱即用.

foreach(string item in myListOfStrings) {
    myListOfStrings.Remove(item);
}

上面的剪辑是我见过的最可怕的事情之一.那么,你如何实现呢？您可以使用向后遍历列表for,但我也不喜欢这个解决方案.

我想知道的是:是否有一个方法/扩展从当前列表返回IEnumerable,类似浮动副本？LINQ有很多扩展方法可以做到这一点,但你总是要对它做一些事情,比如过滤(where,take ......).

我期待着这样的事情:

foreach(string item in myListOfStrings.Shadow()) {
   myListOfStrings.Remove(item);
}

其中.Shadow()是:

public static IEnumerable<T> Shadow<T>(this IEnumerable<T> source) {
    return new IEnumerable<T>(source);
    // or return source.Copy()
    // or return source.TakeAll();
}

例

foreach(ResponseFlags flag in responseFlagsList.Shadow()) {
    switch(flag) {
        case ResponseFlags.Case1:
            ...
        case ResponseFlags.Case2:
            ...
    }
    ...
    this.InvokeSomeVoidEvent(flag)
    responseFlagsList.Remove(flag);
}

---

解

这就是我解决它的方式,它就像一个魅力:

public static IEnumerable<T> Shadow<T>(this IEnumerable<T> source) where T: new() {
    foreach(T item in source)
        yield return item;
}

它不是那么超快(显然),但它是安全的,正是我打算做的.

Answer 1

由于列表的实现方式,逐个从列表中删除多个元素是C#反模式.

当然,它可以用for循环(而不是foreach)完成.或者可以通过制作列表的副本来完成.但这就是为什么不应该这样做的原因.在100000个随机整数列表中,我的机器需要2500毫秒:

       foreach (var x in listA.ToList())
            if (x % 2 == 0)
                listA.Remove(x);

这需要1250毫秒:

        for (int i = 0; i < listA.Count; i++)
            if (listA[i] % 2 == 0)
                listA.RemoveAt(i--);

而这两个分别需要5和2毫秒:

        listB = listB.Where(x => x % 2 != 0).ToList();

        listB.RemoveAll(x => x % 2 == 0);

这是因为当您从列表中删除元素时,实际上是从数组中删除,这是O(N)时间,因为您需要将删除元素后面的每个元素向左移动一个位置.平均而言,这将是N/2个元素.

删除(元素)还需要在删除之前找到该元素.所以Remove(element)实际上总是需要N步 - elementindex找到元素的N - elementindex步骤,删除它的步骤 - 总共N步.

RemoveAt(index)不必查找元素,但它仍然必须移动底层数组,因此平均而言,RemoveAt是N/2步.

最终结果是O(N ^ 2)复杂度,因为您要删除多达N个元素.

相反,你应该使用Linq,它将在O(N)时间内修改整个列表,或者自己滚动,但是你不应该在循环中使用Remove(或RemoveAt).

Answer 2

为什么不这样做:

foreach(string item in myListOfStrings.ToList()) 
{
    myListOfStrings.Remove(item);
}

要创建原始副本并用于迭代,请从现有中删除.

如果你真的需要你的扩展方法,你可以创建一些对用户更具可读性的东西,例如:

 public static IEnumerable<T> Shadow<T>(this IEnumerable<T> items)
 {
     if (items == null)
        throw new NullReferenceException("Items cannot be null");

     List<T> list = new List<T>();
     foreach (var item in items)
     {
         list.Add(item);
     }
     return list;
 }

这基本上是一样的.ToList().

呼叫:

foreach(string item in myListOfStrings.Shadow())