如何在迭代通用列表时删除元素？

Question

我正在寻找更好的模式来处理一组元素，每个元素都需要处理，然后根据结果从列表中移除。在foreach(var element in X)循环中不能使用.Remove(element)，因为它会导致“集合已修改；可能不执行枚举操作。”异常......您也不能使用for(int i=0;i

有没有一种优雅的方式来实现这个？

- InvertedAcceleration

Answer 1

使用for循环倒序迭代列表：

for (int i = safePendingList.Count - 1; i >= 0; i--)
{
    // some code
    // safePendingList.RemoveAt(i);
}

示例：

var list = new List<int>(Enumerable.Range(1, 10));
for (int i = list.Count - 1; i >= 0; i--)
{
    if (list[i] > 5)
        list.RemoveAt(i);
}
list.ForEach(i => Console.WriteLine(i));

另外，您可以使用RemoveAll 方法与断言进行测试：

safePendingList.RemoveAll(item => item.Value == someValue);

下面是一个简化示例用于演示：

var list = new List<int>(Enumerable.Range(1, 10));
Console.WriteLine("Before:");
list.ForEach(i => Console.WriteLine(i));
list.RemoveAll(i => i > 5);
Console.WriteLine("After:");
list.ForEach(i => Console.WriteLine(i));

- Ahmad Mageed

---

对于来自Java的人来说，C#的List类似于ArrayList，插入/删除的时间复杂度为O(n)，通过索引检索的时间复杂度为O(1)。这不是传统的链表。C#使用"List"这个词来描述这种数据结构似乎有点不幸，因为它让人想起经典的链表。 - Jarrod Smith

“List”这个名称并没有明确表示它是“LinkedList”。来自Java以外语言背景的人可能会感到困惑，因为它看起来像是一个链表。 - GolezTrol

我是通过 vb.net 搜索最终来到这里的，所以如果有人想要 RemoveAll 的 vb.net 等效语法，可以使用以下代码：list.RemoveAll(Function(item) item.Value = somevalue)。 - pseudocoder

我进行了一项性能测试，结果表明 RemoveAll() 的时间比反向 for 循环慢三倍。所以我肯定会坚持使用循环，至少在关键部分是如此。 - Crusha K. Rool

区别在于使用的时候。 在使用 foreach 迭代同一集合进行 .Remove() 操作时，就会出现此错误。而使用 for 循环并以相反的顺序使用 RemoveAt(...) 允许我们在保持索引跟踪以避免越界的同时删除一个元素。而在使用 RemoveAll() 时，不会在循环中使用，因此不存在修改集合本身的问题，因为我们没有对其进行迭代。 - Ahmad Mageed

Answer 2

 foreach (var item in list.ToList()) {
     list.Remove(item);
 }

如果你在列表（或LINQ查询结果）后面添加".ToList()"，那么你可以直接从"list"中删除"item"，而不会出现可怕的"Collection was modified; enumeration operation may not execute."错误。编译器会复制"list"，使你能够安全地在数组上进行删除。

虽然这种模式并不是超级高效的，但它有一种自然的感觉，并且足够灵活以应对几乎任何情况，比如当你想将每个"item"保存到数据库并且只有在数据库保存成功后才从列表中删除它时。

- Greg Little

---

如果效率不是至关重要的话，这是最好的解决方案。 - IvanP

这种方法既更快速，也更易读: list.RemoveAll(i => true); - santiago arizti

我明白你的意思了吗，当你添加ToList（）时，编译器会遍历复制的集合，但会从原始集合中删除吗？ - Pyrejkee

@Pyrejkee 是的，这是因为如果你通过原始列表进行迭代，在删除一个项目时会出现错误，说集合已被修改，因此foreach循环将崩溃。使用列表的副本，项目不会从副本中删除，而只会从原始列表中删除，从而允许循环完成并修改原始列表。 - NiallMitch14

谢谢分享，这正是我在寻找的。 - user2217057

Answer 3

一个简单直接的解决方案：

在您的集合上使用标准的for循环，并倒序运行它，使用RemoveAt(i)删除元素。

- user169390

---

请注意，如果您的列表包含许多项目，则逐个删除项目不是高效的方法。 它可能会成为O(n^2)。 想象一下一个拥有20亿个项目的列表，其中恰好前10亿个项目都被删除了。每次删除将强制复制所有后面的项目，因此您最终需要将10亿个项目每个复制10亿次。这不是因为反向迭代，而是因为逐个删除。 RemoveAll确保每个项目最多只被复制一次，因此是线性的。 逐个删除可能慢上10亿倍。 O(n)与O(n^2)相比。 - Bruce Dawson

@BruceDawson，这个结论是基于对RemoveAll内部的观察得出的吗？ - AaA

@AaA - 我的观察并不是基于查看RemoveAll内部，而是基于我对C#列表实现方式的理解。它只是一个项目数组，删除单个项目必然需要将后面的所有项目向下移动一个位置。因此，这里建议的算法将具有O(n^2)的性能。这是不必要的。有简单的算法可以在O(n)时间内完成此任务，可能快了数百万倍。我相信remove_if是正确的函数。它仅复制每个项目一次，而不是最多n次。 - Bruce Dawson

@BruceDawson 如果使用列表逐个删除不够高效，是否有其他集合可以代替使用？ - BenKoshy

你可以使用不同类型的集合（如链表）来避免这种情况，但我认为那是错误的解决方案。正确的解决方案是使用正确的算法。使用谓词的.RemoveAll 可以高效地删除项目。它被编写成每个项目只被访问一次（删除或移动）。 - Bruce Dawson

Answer 4

当你想在遍历集合时移除元素时，应该首先考虑反向迭代。

幸运的是，有一种更加优雅的解决方案，可以避免编写需要大量打字且容易出错的for循环。

ICollection<int> test = new List<int>(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10});

foreach (int myInt in test.Reverse<int>())
{
    if (myInt % 2 == 0)
    {
        test.Remove(myInt);
    }
}

- jedesah

---

这对我非常有效。简单而优雅，并且只需要对我的代码进行最小限度的更改。 - Stephen MacDougall

这简直是天才吗？我同意@StephenMacDougall的观点，我不需要使用那些C++风格的for循环，而是直接使用预期的LINQ。 - Piotr Kula

我认为用简单的foreach循环没有任何优势： foreach (int myInt in test.ToList()) { if (myInt % 2 == 0) { test.Remove(myInt); } } 你仍然需要为Reverse分配一份副本，并且它会引入困惑的时刻——为什么要用Reverse。 - jahav

是的，Reverse<T>()创建了一个迭代器，用于反向遍历列表，但是它需要分配额外的缓冲区，大小与列表本身相同（http://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,792）。`Reverse<T>不仅仅是反向遍历原始列表（不需要分配额外的内存）。因此，ToList()和Reverse()两者的内存消耗相同（都创建副本），但是ToList()不对数据做任何修改。对于Reverse<int>()`，我会想知道为什么要反转列表，出于什么目的。 - jahav

@jahav 我理解你的观点。实现 Reverse<T>() 创建一个新缓冲区，这确实令人失望，我不太明白为什么需要这样做。在我看来，根据 Enumerable 的底层结构，至少在某些情况下应该能够实现反向迭代而不分配线性内存。 - jedesah

Answer 5

在泛型列表上使用ToArray()可以让您在泛型列表中执行Remove(item)操作：

        List<String> strings = new List<string>() { "a", "b", "c", "d" };
        foreach (string s in strings.ToArray())
        {
            if (s == "b")
                strings.Remove(s);
        }

- Etienne Brouillard

---

这并没有错，但我必须指出，这绕过了创建第二个“存储”列表来删除所需项目的需要，代价是将整个列表复制到一个数组中。手动挑选元素的第二个列表可能会更少。 - Ahmad Mageed

Answer 6

选择你想要的元素，而不是尝试删除你不想要的元素。这样做会更容易（通常也更有效率），比起删除元素。

var newSequence = (from el in list
                   where el.Something || el.AnotherThing < 0
                   select el);

我想把这个回答作为对Michael Dillon留下的评论的回复发表，但它太长了，而且在我的回答中也可能很有用：

个人而言，我永远不会一个一个地删除元素。如果确实需要删除，请调用使用谓词的RemoveAll函数，它只会重新排列内部数组一次，而Remove函数则会针对每个删除的元素执行Array.Copy操作。RemoveAll效率大大提高。

当你在列表上反向迭代时，你已经知道要删除的元素的索引，所以调用RemoveAt会更加高效，因为Remove首先会遍历列表以查找要删除的元素的索引，而你已经知道该索引。

总之，在for循环中，我没有看到任何理由需要调用Remove。如果可能的话，最好使用上面的代码根据需要从列表中流出元素，这样就完全不需要创建第二个数据结构。

- JulianR

---

要么这样做，或者将不需要的元素的指针添加到第二个列表中，然后在循环结束后，迭代删除列表并使用它来删除元素。 - Michael Dillon

这是一个很酷的解决方案，实际上它更加高效。 - Seyedraouf Modarresi

Answer 7

使用.ToList()将会复制你的列表，正如这个问题所解释的那样：

ToList()-- Does it Create a New List?

通过使用ToList()，你可以从原始列表中删除元素，因为你实际上是在迭代一个副本。

foreach (var item in listTracked.ToList()) {    

        if (DetermineIfRequiresRemoval(item)) {
            listTracked.Remove(item)
        }

     }

- StuartQ

---

但从性能角度来看，您正在复制列表，这可能需要一些时间。这是一个很好且简便的方法，但性能不太好。 - Florian K

Answer 8

如果决定要删除哪些项的函数没有副作用并且不改变这些项（即为纯函数），则一个简单而高效（线性时间）的解决方案是：

list.RemoveAll(condition);

如果有副作用，我会使用类似以下的方式：

var toRemove = new HashSet<T>();
foreach(var item in items)
{
     ...
     if(condition)
          toRemove.Add(item);
}
items.RemoveAll(toRemove.Contains);

假设哈希函数良好，这仍然是线性时间。但由于哈希集的存在，它会增加内存使用。

最后，如果您的列表只是IList<T>而不是List<T>，我建议参考我的回答 How can I do this special foreach iterator? 。这将具有线性运行时，与许多其他答案的二次运行时相比。

- CodesInChaos

Answer 9

只要符合条件，就可以进行任何删除操作。

list.RemoveAll(item => item.Value == someValue);

- Ahmad

---

如果处理不改变项目并且没有副作用，那么这是最好的解决方案。 - CodesInChaos

Answer 10

List<T> TheList = new List<T>();

TheList.FindAll(element => element.Satisfies(Condition)).ForEach(element => TheList.Remove(element));

- Mauricio Ramalho