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!

This sounds like crazy talk, what exactly is removing the items while you are processing them? Something running on a different thread? — musefan, Jul 17 '14 at 15:36
So its it the act of removing an item that can cause the list to be modified at other locations? or is the issue access to the list from other threads? — Alex K., Jul 17 '14 at 15:37
It this for real or just a puzzle? Some of those constraints are bizarre. — D Stanley, Jul 17 '14 at 15:41
What does “XL problem” maen? Do you mean [XY problem](http://meta.stackexchange.com/q/66377/130186)? — svick, Jul 17 '14 at 15:43
@Eve: It's still confusing.. but what about making a copy/clone of the original list, iterate over the clone, then if you need to remove an item, just check if the original list contains the item before you remove it (this part may require a unique id of some sort for the item to test equality though) — musefan, Jul 17 '14 at 15:43
The iteration will be repeated quite often, but every object must have exactly one turn? One turn per iteration, or one turn, regardless of how many times the iteration is repeated? — cf_en, Jul 17 '14 at 15:44
In order to be answerable, you're going to need to provide a lot more information about the desired behavior of your application. For example, if you're iterating over the list, and you invoke some method on the second element, which removes elements 1 and 3 from the list, do you want element 3 to be visited still, even though it's been removed? Are there constraints preventing you from creating a copy of your list? Are they real constraints, or is this just a thought problem? — StriplingWarrior, Jul 17 '14 at 15:49
"Multiple and random items can be removed while 1 item is being processed." and "all single threaded here" seems contradictory. — Alex, Jul 17 '14 at 15:51
@Alex Imagine the code in the body of a `foreach` loop removing items from the collection that it is iterating over. Only one thread is involved, but from the point of view of the iterator, it's being mutated from "somewhere else" while it's trying to iterate over the collection. This is simple enough to create: `foreach(var item in list) list.RemoveAt(random.Next(list.Count));` — Servy, Jul 17 '14 at 16:01

score 6 · Accepted Answer · edited May 23 '17 at 12:05

6

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.

edited May 23 '17 at 12:05

Community

1
1

answered Jul 17 '14 at 15:53

Servy

202,030
26
332
449

1

It amazes me how many ways there are to solve a problem. Great code piece. – Measurity Jul 17 '14 at 15:58
1

Shouldn't you also remove the delegate after iterating (ideally inside `finally`)? Otherwise, I think this is a memory leak. – svick Jul 17 '14 at 15:59
*(I'm not in that corner of C#)* If I don't use this as extension and add event listeners to my observable list instead (like `list.CollectionChanged += ...;`), does it have the same solving effect then, when all done correctly ? – Bitterblue Jul 17 '14 at 16:26
1

@Eve If you wanted to you could use all of this code but instead of yielding the item, just do whatever you would have otherwise done in the body of your `foreach` loop, yes. This makes that solution reusable and allows you to abstract away the abstract concept of having an iterator that can effectively iterate a collection being mutated from the code that actually mutates a collection while iterating it. Even if I only ever used this code once, I'd find separating these concerns to be an improvement of the code. – Servy Jul 17 '14 at 16:29
Just for performance reasons I'm also writing another List-variant that notifies me about list changes. I benchmarked `ObservableCollection` against `List` and it was **36x slower** at setting items. – Bitterblue Jul 18 '14 at 10:23
1

@Eve It's not really meaningful to think of it as a relative speedup/slowdown. If what you're doing inside of the loop itself is very fast, then slowing down the overhead of iterating the list can have a meaningful relative impact on the loop, but if the loop itself is doing a lot adding a fair bit of overhead to the loop itself becomes much less meaningful. – Servy Jul 18 '14 at 14:00

score 3 · Answer 2 · answered Jul 17 '14 at 15:53

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).

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

2 Answers2

Linked