如何在删除列表项的同时遍历列表？

Question

我正尝试找到一种优雅的方法来在列表上进行迭代，同时删除项目。
我知道这个解决方案。但我的条件更为苛刻:

• 此处全部是单线程
• 迭代必须向前进行。
• 每个项目必须仅处理一次
• 多个和随机的项目可以在处理1个项目时被删除。
• 项目是复杂和智能对象。它们执行一个自定义方法，并且该方法可以决定是否应该删除某些项目（从0到全部）。
• （添加和插入也可能发生，但目前不重要，如果有办法同时处理这个问题，那就太好了）

问题:这可能吗？如果是，如何实现？

---

我有一个想法，可以将对象标记为“已删除”/“非活动”。当我稍后再次迭代时，我将删除它们而不调用它们执行任何操作。迭代会经常重复，这就是为什么每个对象必须在每次迭代中恰好有1个轮换的原因。这样行得通吗？

---

这是我现在处理事情的方式。它并不完美，但希望能给你提供提示，了解需要的内容。

伪代码：

class Foo
{
    public void DoStuff()
    {
        // do other stuff

        if (condition)
            Kill(x); // should result in list.RemoveAt(x) somehow
    }
}

class Program
{
    [STAThread]
    static void Main(string[] args)
    {
        List<Foo> list = new List<Foo>();
        for (int i = 0; i < 15; i++)
            list.Add(new Foo());

        for (int i = 0; i < list.Count; i++)
            list[i].DoStuff();

        Console.ReadKey();
    }
}

感谢任何帮助！

（这不是一个XY问题。我确定。这个问题已经困扰我多年了，现在我决定找到一个可靠的解决方案。我在C#中工作。这不是一个恶作剧。如果看起来像是，我很抱歉。）

- Bitterblue

---

这听起来像是疯言疯语，移除正在处理的项目是什么意思？是在不同的线程上运行吗？ - musefan

那么，是删除项目的行为会导致列表在其他位置被修改？还是问题在于其他线程访问列表？ - Alex K.

这是真的还是只是一个谜题？其中一些限制条件很奇怪。 - D Stanley

为了能够回答这个问题，您需要提供更多关于应用程序期望行为的信息。例如，如果您正在遍历列表，并在第二个元素上调用某个方法，该方法会从列表中删除元素1和3，那么即使已经被删除，您是否仍希望访问元素3？是否有限制阻止您创建列表的副本？这些限制是真实存在的，还是只是思考问题？ - StriplingWarrior

@Alex 想象一下，在 foreach 循环体中的代码正在从正在迭代的集合中删除项目。只涉及一个线程，但从迭代器的角度来看，它正在尝试在迭代集合时从“其他地方”进行变异。这很容易创建：foreach(var item in list) list.RemoveAt(random.Next(list.Count)); - Servy

Answer 1

你可以在这里使用一个ObservableCollection，这样迭代集合的代码就有一种检测集合何时以及如何被改变的方法。通过使用ObservableCollection，迭代代码可以在当前索引之前添加一个项目时递增索引，或者在当前索引之前删除一个项目时递减索引。

public static IEnumerable<T> IterateWhileMutating<T>(
    this ObservableCollection<T> list)
{
    int i = 0;
    NotifyCollectionChangedEventHandler handler = (_, args) =>
    {
        switch (args.Action)
        {
            case NotifyCollectionChangedAction.Add:
                if (args.NewStartingIndex <= i)
                    i++;
                break;
            case NotifyCollectionChangedAction.Move:
                if (args.NewStartingIndex <= i)
                    i++;
                if (args.OldStartingIndex <= i) //note *not* else if
                    i--;
                break;
            case NotifyCollectionChangedAction.Remove:
                if (args.OldStartingIndex <= i)
                    i--;
                break;
            case NotifyCollectionChangedAction.Reset:
                i = int.MaxValue;//end the sequence
                break;
            default:
                //do nothing
                break;
        }
    };
    try
    {
        list.CollectionChanged += handler;
        for (i = 0; i < list.Count; i++)
        {
            yield return list[i];
        }
    }
    finally
    {
        list.CollectionChanged -= handler;
    }
}

这段代码来自我之前的另一个回答。它包含了在迭代过程中对序列进行变异的后果以及关于这个代码的额外解释和其设计决策的影响等相关信息。

- Servy

---

令我惊奇的是，解决问题的方法有很多种。优秀的代码片段。 - Measurity

你不应该在迭代完成后（最好在finally块内）移除委托吗？否则，我认为这会导致内存泄漏。 - svick

如果我不使用这个作为扩展，并且将事件监听器添加到我的可观察列表中（例如 list.CollectionChanged += ...;），那么当所有操作都正确完成时，它是否具有相同的解决效果？但是我不在 C# 的那个角落里。 - Bitterblue

@Eve 如果你想的话，你可以使用所有这些代码，但是不要yield item，而是在foreach循环的主体中执行任何你本来想做的操作。这使得该解决方案可重用，并允许你将能够有效迭代被从实际改变集合的代码抽象出来，而不是在迭代时实际改变集合的代码。即使我只使用过这个代码一次，我也会发现将这些问题分开处理是代码的一个改进。 - Servy

出于性能原因，我还编写了另一个列表变体，以通知我有关列表更改的信息。我对ObservableCollection和List进行了基准测试，发现在设置项目方面，ObservableCollection比List慢了36倍。 - Bitterblue

@Eve，将其视为相对加速度/减速度并没有真正意义。如果循环内部正在执行的操作非常快，则减慢迭代列表的开销可能会对循环产生显着的相对影响，但是如果循环本身正在执行许多操作，则在循环本身中添加大量开销的意义变得不那么重要。 - Servy

Answer 2

我有一个想法，可以将物品标记为已删除/不活跃。

是的，我认为这样做是一个合理的方法。我会先收集所有要删除的项目，然后一次性将它们全部删除。在代码中，它可能看起来像这样：

var toRemove = new HashSet<Item>();

foreach (var item in list)
{
    toRemove.UnionWith(item.GetItemsToRemove());
}

list.RemoveAll(item => toRemove.Contains(item));

这种方法的好处是它应该很快（O(n)），因为虽然从List中删除单个项是O(n)，但同时从中删除多个项也是O(n)。

- svick