By InvertedAcceleration


2009-10-17 14:12:35 8 Comments

I am looking for a better pattern for working with a list of elements which each need processed and then depending on the outcome are removed from the list.

You can't use .Remove(element) inside a foreach (var element in X) (because it results in Collection was modified; enumeration operation may not execute. exception)... you also can't use for (int i = 0; i < elements.Count(); i++) and .RemoveAt(i) because it disrupts your current position in the collection relative to i.

Is there an elegant way to do this?

26 comments

@Gambitier 2019-11-01 09:22:49

I would do like this

using System.IO;
using System;
using System.Collections.Generic;

class Author
    {
        public string Firstname;
        public string Lastname;
        public int no;
    }

class Program
{
    private static bool isEven(int i) 
    { 
        return ((i % 2) == 0); 
    } 

    static void Main()
    {    
        var authorsList = new List<Author>()
        {
            new Author{ Firstname = "Bob", Lastname = "Smith", no = 2 },
            new Author{ Firstname = "Fred", Lastname = "Jones", no = 3 },
            new Author{ Firstname = "Brian", Lastname = "Brains", no = 4 },
            new Author{ Firstname = "Billy", Lastname = "TheKid", no = 1 }
        };

        authorsList.RemoveAll(item => isEven(item.no));

        foreach(var auth in authorsList)
        {
            Console.WriteLine(auth.Firstname + " " + auth.Lastname);
        }
    }
}

OUTPUT

Fred Jones
Billy TheKid

@Sasha1296 2019-09-21 02:53:18

Just wanted to add my 2 cents to this in case this helps anyone, I had a similar problem but needed to remove multiple elements from an array list while it was being iterated over. the highest upvoted answer did it for me for the most part until I ran into errors and realized that the index was greater than the size of the array list in some instances because multiple elements were being removed but the index of the loop didn't keep track of that. I fixed this with a simple check:

ArrayList place_holder = new ArrayList();
place_holder.Add("1");
place_holder.Add("2");
place_holder.Add("3");
place_holder.Add("4");

for(int i = place_holder.Count-1; i>= 0; i--){
    if(i>= place_holder.Count){
        i = place_holder.Count-1; 
    }

// some method that removes multiple elements here
}

@Roberto Mutti 2019-09-10 10:02:44

Trace the elements to be removed with a property, and remove them all after process.

using System.Linq;

List<MyProperty> _Group = new List<MyProperty>();
// ... add elements

bool cond = true;
foreach (MyProperty currObj in _Group)
{
    if (cond) 
    {
        // SET - element can be deleted
        currObj.REMOVE_ME = true;
    }
}
// RESET
_Group.RemoveAll(r => r.REMOVE_ME);

@andrew pate 2019-06-02 14:09:18

In C# one easy way is to mark the ones you wish to delete then create a new list to iterate over...

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

or even simpler use linq....

list.RemoveAll(p=>p.Delete);

but it is worth considering if other tasks or threads will have access to the same list at the same time you are busy removing, and maybe use a ConcurrentList instead.

@Lijo 2018-03-19 12:40:19

foreach(var item in list.ToList())

{

if(item.Delete) list.Remove(item);

}

Simply create an entirely new list from the first one. I say "Easy" rather than "Right" as creating an entirely new list probably comes at a performance premium over the previous method (I haven't bothered with any benchmarking.) I generally prefer this pattern, it can also be useful in overcoming Linq-To-Entities limitations.

for(i = list.Count()-1;i>=0;i--)

{

item=list[i];

if (item.Delete) list.Remove(item);

}

This way cycles through the list backwards with a plain old For loop. Doing this forwards could be problematic if the size of the collection changes, but backwards should always be safe.

@Hüseyin Yağlı 2017-10-29 15:32:29

The best way to remove items from a list while iterating over it is to use RemoveAll(). But the main concern written by people is that they have to do some complex things inside the loop and/or have complex compare cases.

The solution is to still use RemoveAll() but use this notation:

var list = new List<int>(Enumerable.Range(1, 10));
list.RemoveAll(item => 
{
    // Do some complex operations here
    // Or even some operations on the items
    SomeFunction(item);
    // In the end return true if the item is to be removed. False otherwise
    return item > 5;
});

@Timothy Gonzalez 2017-09-24 09:00:57

Copy the list you are iterating. Then remove from the copy and interate the original. Going backwards is confusing and doesn't work well when looping in parallel.

var ids = new List<int> { 1, 2, 3, 4 };
var iterableIds = ids.ToList();

Parallel.ForEach(iterableIds, id =>
{
    ids.Remove(id);
});

@testing 2017-08-18 14:40:54

My approach is that I first create a list of indices, which should get deleted. Afterwards I loop over the indices and remove the items from the initial list. This looks like this:

var messageList = ...;
// Restrict your list to certain criteria
var customMessageList = messageList.FindAll(m => m.UserId == someId);

if (customMessageList != null && customMessageList.Count > 0)
{
    // Create list with positions in origin list
    List<int> positionList = new List<int>();
    foreach (var message in customMessageList)
    {
        var position = messageList.FindIndex(m => m.MessageId == message.MessageId);
        if (position != -1)
            positionList.Add(position);
    }
    // To be able to remove the items in the origin list, we do it backwards
    // so that the order of indices stays the same
    positionList = positionList.OrderByDescending(p => p).ToList();
    foreach (var position in positionList)
    {
        messageList.RemoveAt(position);
    }
}

@Jan 2009-10-17 14:25:05

A simple and straightforward solution:

Use a standard for-loop running backwards on your collection and RemoveAt(i) to remove elements.

@Bruce Dawson 2019-07-08 03:57:31

Be aware that removing items one at a time is not efficient if your list contains many items. It has the potential to be O(n^2). Imagine a List with two billion items where it just happens that the first billion items all end up being deleted. Each removal forces all later items to be copied, so you end up copying a billion items a billion times each. This isn't because of the reverse iteration, it is because of the one-at-a-time removal. RemoveAll ensures that each item is copied at most once so it is linear. One-at-a-time removal may be a billion times slower. O(n) versus O(n^2).

@bcmpinc 2016-10-09 21:12:43

Using Remove or RemoveAt on a list while iterating over that list has intentionally been made difficult, because it is almost always the wrong thing to do. You might be able to get it working with some clever trick, but it would be extremely slow. Every time you call Remove it has to scan through the entire list to find the element you want to remove. Every time you call RemoveAt it has to move subsequent elements 1 position to the left. As such, any solution using Remove or RemoveAt, would require quadratic time, O(n²).

Use RemoveAll if you can. Otherwise, the following pattern will filter the list in-place in linear time, O(n).

// Create a list to be filtered
IList<int> elements = new List<int>(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10});
// Filter the list
int kept = 0;
for (int i = 0; i < elements.Count; i++) {
    // Test whether this is an element that we want to keep.
    if (elements[i] % 3 > 0) {
        // Add it to the list of kept elements.
        elements[kept] = elements[i];
        kept++;
    }
}
// Unfortunately IList has no Resize method. So instead we
// remove the last element of the list until: elements.Count == kept.
while (kept < elements.Count) elements.RemoveAt(elements.Count-1);

@supercat 2016-04-18 17:29:01

The cost of removing an item from the list is proportional to the number of items following the one to be removed. In the case where the first half of the items qualify for removal, any approach which is based upon removing items individually will end up having to perform about N*N/4 item-copy operations, which can get very expensive if the list is large.

A faster approach is to scan through the list to find the first item to be removed (if any), and then from that point forward copy each item which should be retained to the spot where it belongs. Once this is done, if R items should be retained, the first R items in the list will be those R items, and all of the items requiring deletion will be at the end. If those items are deleted in reverse order, the system won't end up having to copy any of them, so if the list had N items of which R items, including all of the first F, were retained, it will be necessary to copy R-F items, and shrink the list by one item N-R times. All linear time.

@CodesInChaos 2014-12-22 11:32:26

If the function that determines which items to delete has no side effects and doesn't mutate the item (it's a pure function), a simple and efficient (linear time) solution is:

list.RemoveAll(condition);

If there are side effects, I'd use something like:

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

This is still linear time, assuming the hash is good. But it has an increased memory use due to the hashset.

Finally if your list is only an IList<T> instead of a List<T> I suggest my answer to How can I do this special foreach iterator?. This will have linear runtime given typical implementations of IList<T>, compared with quadratic runtime of many other answers.

@S.W. 2015-11-06 14:10:19

myList.RemoveAt(i--);

simples;

@Denny 2017-05-24 11:36:37

What does simples; do here?

@S.W. 2018-02-13 15:41:33

its a delegate.. it downvotes my answer every time it runs

@Martin Liversage 2009-10-17 14:23:21

I would reassign the list from a LINQ query that filtered out the elements you didn't want to keep.

list = list.Where(item => ...).ToList();

Unless the list is very large there should be no significant performance problems in doing this.

@yoyo 2015-02-18 21:37:36

You can't use foreach, but you could iterate forwards and manage your loop index variable when you remove an item, like so:

for (int i = 0; i < elements.Count; i++)
{
    if (<condition>)
    {
        // Decrement the loop counter to iterate this index again, since later elements will get moved down during the remove operation.
        elements.RemoveAt(i--);
    }
}

Note that in general all of these techniques rely on the behaviour of the collection being iterated. The technique shown here will work with the standard List(T). (It is quite possible to write your own collection class and iterator that does allow item removal during a foreach loop.)

@Greg Little 2015-01-08 23:34:56

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

If you add ".ToList()" to your list (or the results of a LINQ query), you can remove "item" directly from "list" without the dreaded "Collection was modified; enumeration operation may not execute." error. The compiler makes a copy of "list", so that you can safely do the remove on the array.

While this pattern is not super efficient, it has a natural feel and is flexible enough for almost any situation. Such as when you want to save each "item" to a DB and remove it from the list only when the DB save succeeds.

@IvanP 2016-06-02 11:54:43

This is the best solution if efficiency is not crucial.

@santiago arizti 2016-07-07 00:42:33

this is faster and more readable too: list.RemoveAll(i => true);

@Pyrejkee 2019-01-17 10:56:40

@Greg Little , did I understand you correctly - when you add ToList() compiler goes through copied collection but removes from original?

@Ahmad 2014-12-22 10:58:23

As any remove is taken on a condition you can use

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

@CodesInChaos 2014-12-22 11:24:56

That's the best solution if the processing does not mutate the item and has no side effects.

@roeesha 2014-07-30 09:28:05

By assuming that predicate is a Boolean property of an element, that if it is true, then the element should be removed:

        int i = 0;
        while (i < list.Count())
        {
            if (list[i].predicate == true)
            {
                list.RemoveAt(i);
                continue;
            }
            i++;
        }

@FrankKrumnow 2018-02-01 11:06:09

I gave this an upvote as sometimes it could be more efficient to move through the List in order (not reverse order). Perhaps you could stop when finding the first item not to remove because the list is ordered. (Imagine a 'break' where the i++ is in this example.

@warrens 2013-12-07 14:10:03

I wish the "pattern" was something like this:

foreach( thing in thingpile )
{
    if( /* condition#1 */ )
    {
        foreach.markfordeleting( thing );
    }
    elseif( /* condition#2 */ )
    {
        foreach.markforkeeping( thing );
    }
} 
foreachcompleted
{
    // then the programmer's choices would be:

    // delete everything that was marked for deleting
    foreach.deletenow(thingpile); 

    // ...or... keep only things that were marked for keeping
    foreach.keepnow(thingpile);

    // ...or even... make a new list of the unmarked items
    others = foreach.unmarked(thingpile);   
}

This would align the code with the process that goes on in the programmer's brain.

@Dan Bechard 2014-07-17 13:50:47

Easy enough. Just create a boolean flag array (use a 3-state type, e.g. Nullable<bool>, if you want to allow unmarked), then use it after the foreach to remove/keep items.

@Paul Nelson Baker 2013-09-19 05:24:54

I found myself in a similar situation where I had to remove every nth element in a given List<T>.

for (int i = 0, j = 0, n = 3; i < list.Count; i++)
{
    if ((j + 1) % n == 0) //Check current iteration is at the nth interval
    {
        list.RemoveAt(i);
        j++; //This extra addition is necessary. Without it j will wrap
             //down to zero, which will throw off our index.
    }
    j++; //This will always advance the j counter
}

@StuartQ 2013-08-08 10:52:43

Using .ToList() will make a copy of your list, as explained in this question: ToList()-- Does it Create a New List?

By using ToList(), you can remove from your original list, because you're actually iterating over a copy.

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

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

     }

@Florian K 2017-03-13 15:08:08

But from a performance point of view you are copying your list, which may take some time. Good and easy way to do it, but with a not so good performance

@Mauricio Ramalho 2012-10-24 08:23:03

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

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

@jedesah 2012-05-10 19:39:21

Reverse iteration should be the first thing to come to mind when you want to remove elements from a Collection while iterating over it.

Luckily, there is a more elegant solution than writing a for loop which involves needless typing and can be error prone.

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

@Stephen MacDougall 2013-07-22 17:58:28

This worked perfectly for me. Simple, and elegant, and required minimal changes to my code.

@Piotr Kula 2014-04-29 10:07:54

Is this is just flippin genius? And I agree with @StephenMacDougall , I do not need to use those C++'y for loops and just get on with LINQ as intended.

@jahav 2015-05-25 13:38:17

I don't see any advantage over simple foreach (int myInt in test.ToList()) { if (myInt % 2 == 0) { test.Remove(myInt); } } You still have to allocate a copy for Reverse and it introduces Huh? moment - why is there Reverse.

@jedesah 2015-06-17 00:43:37

@jahav The Reverse<int>() is in order for the iterator to go through the list backwards. If you don't do that, your indexes get screwed up because you are removing elements from the list at the same time (so every element after the removed element's index goes down by one). Since the indexes of the elements before the removed element do not change, by iterating in the reverse order, you are safe against the awful consequences of your own mutations. Btw, this was a long time ago, today I would suggest that if at all possible, you use a language such as Haskell and avoid mutation altogether.

@jahav 2015-06-17 09:00:42

@jedesah Yes, Reverse<T>() creates an iterator that goes through list backwards, but it allocates extra buffer with same size as the list itself for it ( referencesource.microsoft.com/#System.Core/System/Linq/… ). Reverse<T> doesn't just go through the original list in reverse order (w/o allocating extra memory). Therefore both ToList() and Reverse() have same memory consumption (both create copy), but ToList() doesn't do anything to the data. With Reverse<int>(), I would wonder why is list reversed, for what reason.

@jedesah 2015-06-17 17:59:12

@jahav I see your point. That is quite disappointing that the implementation of Reverse<T>() creates a new buffer, I am not quite sure I understand why that is necessary. It seems to me that depending on the underlying structure of the Enumerable, it should at least in some cases be possible to achieve reverse iteration without allocating linear memory.

@JulianR 2009-10-17 14:48:59

Select the elements you do want rather than trying to remove the elements you don't want. This is so much easier (and generally more efficient too) than removing elements.

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

I wanted to post this as a comment in response to the comment left by Michael Dillon below, but it's too long and probably useful to have in my answer anyway:

Personally, I'd never remove items one-by-one, if you do need removal, then call RemoveAll which takes a predicate and only rearranges the internal array once, whereas Remove does an Array.Copy operation for every element you remove. RemoveAll is vastly more efficient.

And when you're backwards iterating over a list, you already have the index of the element you want to remove, so it would be far more efficient to call RemoveAt, because Remove first does a traversal of the list to find the index of the element you're trying to remove, but you already know that index.

So all in all, I don't see any reason to ever call Remove in a for-loop. And ideally, if it is at all possible, use the above code to stream elements from the list as needed so no second data structure has to be created at all.

@Michael Dillon 2009-10-17 18:54:43

Either this, or add a pointer to the unwanted elements into a second list, then after your loop ends, iterate the removal list and use that to remove the elements.

@Etienne Brouillard 2009-10-17 14:46:09

Using the ToArray() on a generic list allows you to do a Remove(item) on your generic List:

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

@Ahmad Mageed 2009-10-17 15:06:03

This isn't wrong but I have to point out that this bypasses the need to create a 2nd "storage" list of the items you want removed at the expense of copying the entire list to an array. A 2nd list of hand-picked elements will probably have less items.

@Ahmad Mageed 2009-10-17 14:31:26

Iterate your list in reverse with a for loop:

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

Example:

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

Alternately, you can use the RemoveAll method with a predicate to test against:

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

Here's a simplified example to demonstrate:

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

@Jarrod Smith 2013-12-19 23:55:10

For those coming from Java, C#'s List is like ArrayList in that insertion/removal is O(n) and retrieval via an index is O(1). This is not a traditional linked list. It seems a bit unfortunate C# uses the word "List" to describe this data structure since it brings to mind the classic linked list.

@GolezTrol 2014-05-01 14:13:02

Nothing in the name 'List' says 'LinkedList'. People coming from other languages than Java might be confused when it would be a linked list.

@pseudocoder 2014-11-06 17:35:47

I ended up here through a vb.net search so in case anyone wants the vb.net equivalent syntax for RemoveAll: list.RemoveAll(Function(item) item.Value = somevalue)

@Autumn Leonard 2015-12-11 15:17:08

This also works in Java with minimal modification: .size() instead of .Count and .remove(i) instead of .removeAt(i). Clever--thanks!

@Crusha K. Rool 2016-11-15 01:40:38

I made a little test for performance and it turned out that RemoveAll() takes three times as much time as the backwards for loop. So I am definitely sticking with the loop, at least in sections where it matters.

@ndm13 2017-09-20 14:53:13

@AutumnLeonard A better solution for Java would be using the Iterator (assuming the remove() method is implemented).

@Karlth 2017-10-11 10:04:17

Brilliant solution, iterating backwards! Clever, clever :)

@TheXenocide 2018-03-15 13:41:47

@JarrodSmith, it's worth noting that with lists less than massive size, modern hardware architecture gives a massive performance benefit to arrays such that for most practical purposes outside very large data sets (or lists of very large contiguous structures; i.e. non-references, which aren't a Java feature) and some other edge cases, despite the illusion granted by big-O complexity analysis (this is mostly due to processor-localized caching and prefetching). One of many articles on the subject: youthdev.net/en/…

@TheXenocide 2018-03-15 13:42:52

I am, admittedly, rather late to the discussion lol. I also didn't give that article a thorough read as I was only looking for an example of something I've already studied, though it looked relevant enough

@Vinicius Gonçalves 2019-01-17 14:02:40

iterate reverse, just think out of box, simply awesome.

Related Questions

Sponsored Content

45 Answered Questions

[SOLVED] How to make a flat list out of list of lists?

25 Answered Questions

[SOLVED] How do I concatenate two lists in Python?

16 Answered Questions

[SOLVED] How to clone or copy a list?

27 Answered Questions

[SOLVED] How do I check if a list is empty?

  • 2008-09-10 06:20:11
  • Ray Vega
  • 2611983 View
  • 3234 Score
  • 27 Answer
  • Tags:   python list

7 Answered Questions

[SOLVED] How do I get the number of elements in a list?

  • 2009-11-11 00:30:54
  • y2k
  • 3182280 View
  • 1875 Score
  • 7 Answer
  • Tags:   python list

28 Answered Questions

[SOLVED] What is the best way to iterate over a dictionary?

  • 2008-09-26 18:20:06
  • Jake Stewart
  • 1509324 View
  • 2502 Score
  • 28 Answer
  • Tags:   c# dictionary loops

11 Answered Questions

[SOLVED] Getting the last element of a list

  • 2009-05-30 19:28:53
  • Janusz
  • 1909336 View
  • 1920 Score
  • 11 Answer
  • Tags:   python list indexing

7 Answered Questions

[SOLVED] How does PHP 'foreach' actually work?

18 Answered Questions

[SOLVED] How to remove an element from a list by index?

  • 2009-03-09 18:16:11
  • Joan Venge
  • 2457740 View
  • 1411 Score
  • 18 Answer
  • Tags:   python list

19 Answered Questions

[SOLVED] How to Sort a List<T> by a property in the object

Sponsored Content