How to iterate over list while removing items at the same time?

Question

I'm trying to find an elegant way to iterate over a list while items are removed at the same time.
I know this solution. But my conditions are something harder:

• all single-threaded here
• Iteration must be forward.
• Every item must be processed exactly once.
• Multiple and random items can be removed while 1 item is being processed.
• Items are complex and smart objects. They execute a custom method and it can decide that some items (0 to all) shall be removed.
• (add and insert can happen too, but just now this is not important, in case there is a way to handle this at the same time, that would be great)

Question: Is this possible ? If yes, how ?

---

I have the idea of marking the objects as removed / inactive. When I iterate again later, I will remove them without calling them to do things. The iteration will be repeated quite often, that's why every object must have exactly 1 turn at each iteration. Would that work ?

---

This is how I handle things now. It's not perfect but gives you the hint what is asked I hope.

Pseudo-code:

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();
    }
}

---

(This is not an XY Problem. I'm sure. I have this sitting on my mind for years now and I decided to finally find a solid solution. I'm working in C# for this. This is not a prank. I'm sorry if it seams like it.)

Thanks for any help!

Answer 1

What you can do is use an ObservableCollection here so that the code that is iterating over the collection has a way of detecting when and how the collection is mutated while it is iterating. By using an ObservableCollection the iterating code can increment the index when an item is added before the current index, or decriment it when an item is removed from before the current index.

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;
    }
}

The code is taken from this other answer of mine. It contains additional tangential information about the consequences of iterating a sequence while mutating it, as well as some additional explanation about this code and the implications of its design decisions.

Answer 2

I have the idea of marking the objects as removed / inactive.

Yes, I think something like this is a reasonable approach. What I would do is to first collect all the items to remove and then remove them all at once. In code, it could look something like:

var toRemove = new HashSet<Item>();

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

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

The nice thing about this approach is that it should be fast (O(n)), because while removing a single item from a List<T> is O(n), removing multiple items from it at the same time is also O(n).