Best way to remove items from a collection

What is the best way to approach removing items from a collection in C#, once the item is known, but not it's index. This is one way to do it, but it seems inelegant at best.

//Remove the existing role assignment for the user.
int cnt = 0;
int assToDelete = 0;
foreach (SPRoleAssignment spAssignment in workspace.RoleAssignments)
{
    if (spAssignment.Member.Name == shortName)
    {
        assToDelete = cnt;
    }
    cnt++;
}
workspace.RoleAssignments.Remove(assToDelete);

What I would really like to do is find the item to remove by property (in this case, name) without looping through the entire collection and using 2 additional variables.

If RoleAssignments is a List<T> you can use the following code.

workSpace.RoleAssignments.RemoveAll(x =>x.Member.Name == shortName);

If you want to access members of the collection by one of their properties, you might consider using a Dictionary<T> or KeyedCollection<T> instead. This way you don't have to search for the item you're looking for.

Otherwise, you could at least do this:

foreach (SPRoleAssignment spAssignment in workspace.RoleAssignments)
{
    if (spAssignment.Member.Name == shortName)
    {
        workspace.RoleAssignments.Remove(spAssignment);
        break;
    }
}

@smaclell asked why reverse iteration was more efficient in in a comment to @sambo99.

Sometimes it's more efficient. Consider you have a list of people, and you want to remove or filter all customers with a credit rating < 1000;

We have the following data

"Bob" 999
"Mary" 999
"Ted" 1000

If we were to iterate forward, we'd soon get into trouble

for( int idx = 0; idx < list.Count ; idx++ )
{
    if( list[idx].Rating < 1000 )
    {
        list.RemoveAt(idx); // whoops!
    }
}

At idx = 0 we remove Bob, which then shifts all remaining elements left. The next time through the loop idx = 1, but list[1] is now Ted instead of Mary. We end up skipping Mary by mistake. We could use a while loop, and we could introduce more variables.

Or, we just reverse iterate:

for (int idx = list.Count-1; idx >= 0; idx--)
{
    if (list[idx].Rating < 1000)
    {
        list.RemoveAt(idx);
    }
}

All the indexes to the left of the removed item stay the same, so you don't skip any items.

The same principle applies if you're given a list of indexes to remove from an array. In order to keep things straight you need to sort the list and then remove the items from highest index to lowest.

Now you can just use Linq and declare what you're doing in a straightforward manner.

list.RemoveAll(o => o.Rating < 1000);

---

For this case of removing a single item, it's no more efficient iterating forwards or backwards. You could also use Linq for this.

int removeIndex = list.FindIndex(o => o.Name == "Ted");
if( removeIndex != -1 )
{
    list.RemoveAt(removeIndex);
}

If it's an ICollection then you won't have a RemoveAll method. Here's an extension method that will do it:

    public static void RemoveAll<T>(this ICollection<T> source, 
                                    Func<T, bool> predicate)
    {
        if (source == null)
            throw new ArgumentNullException("source", "source is null.");

        if (predicate == null)
            throw new ArgumentNullException("predicate", "predicate is null.");

        source.Where(predicate).ToList().ForEach(e => source.Remove(e));
    }

Based on: http://phejndorf.wordpress.com/2011/03/09/a-removeall-extension-for-the-collection-class/

For a simple List structure the most efficient way seems to be using the Predicate RemoveAll implementation.

Eg.

 workSpace.RoleAssignments.RemoveAll(x =>x.Member.Name == shortName);

The reasons are:

1. The Predicate/Linq RemoveAll method is implemented in List and has access to the internal array storing the actual data. It will shift the data and resize the internal array.
2. The RemoveAt method implementation is quite slow, and will copy the entire underlying array of data into a new array. This means reverse iteration is useless for List

If you are stuck implementing this in a the pre c# 3.0 era. You have 2 options.

• The easily maintainable option. Copy all the matching items into a new list and and swap the underlying list.

Eg.

List<int> list2 = new List<int>() ; 
foreach (int i in GetList())
{
    if (!(i % 2 == 0))
    {
        list2.Add(i);
    }
}
list2 = list2;

Or

• The tricky slightly faster option, which involves shifting all the data in the list down when it does not match and then resizing the array.

If you are removing stuff really frequently from a list, perhaps another structure like a HashTable (.net 1.1) or a Dictionary (.net 2.0) or a HashSet (.net 3.5) are better suited for this purpose.

What type is the collection? If it's List, you can use the helpful "RemoveAll":

int cnt = workspace.RoleAssignments
                      .RemoveAll(spa => spa.Member.Name == shortName)

(This works in .NET 2.0. Of course, if you don't have the newer compiler, you'll have to use "delegate (SPRoleAssignment spa) { return spa.Member.Name == shortName; }" instead of the nice lambda syntax.)

Another approach if it's not a List, but still an ICollection:

   var toRemove = workspace.RoleAssignments
                              .FirstOrDefault(spa => spa.Member.Name == shortName)
   if (toRemove != null) workspace.RoleAssignments.Remove(toRemove);

This requires the Enumerable extension methods. (You can copy the Mono ones in, if you are stuck on .NET 2.0). If it's some custom collection that cannot take an item, but MUST take an index, some of the other Enumerable methods, such as Select, pass in the integer index for you.

Here is a pretty good way to do it

http://support.microsoft.com/kb/555972

        System.Collections.ArrayList arr = new System.Collections.ArrayList();
        arr.Add("1");
        arr.Add("2");
        arr.Add("3");

        /*This throws an exception
        foreach (string s in arr)
        {
            arr.Remove(s);
        }
        */

        //where as this works correctly
        Console.WriteLine(arr.Count);
        foreach (string s in new System.Collections.ArrayList(arr)) 
        {
            arr.Remove(s);
        }
        Console.WriteLine(arr.Count);
        Console.ReadKey();

This is my generic solution

public static IEnumerable<T> Remove<T>(this IEnumerable<T> items, Func<T, bool> match)
    {
        var list = items.ToList();
        for (int idx = 0; idx < list.Count(); idx++)
        {
            if (match(list[idx]))
            {
                list.RemoveAt(idx);
                idx--; // the list is 1 item shorter
            }
        }
        return list.AsEnumerable();
    }

It would look much simpler if extension methods support passing by reference ! usage:

var result = string[]{"mike", "john", "ali"}
result = result.Remove(x => x.Username == "mike").ToArray();
Assert.IsTrue(result.Length == 2);

EDIT: ensured that the list looping remains valid even when deleting items by decrementing the index (idx).

There is another approach you can take depending on how you're using your collection. If you're downloading the assignments one time (e.g., when the app runs), you could translate the collection on the fly into a hashtable where:

shortname => SPRoleAssignment

If you do this, then when you want to remove an item by short name, all you need to do is remove the item from the hashtable by key.

Unfortunately, if you're loading these SPRoleAssignments a lot, that obviously isn't going to be any more cost efficient in terms of time. The suggestions other people made about using Linq would be good if you're using a new version of the .NET Framework, but otherwise, you'll have to stick to the method you're using.

A lot of good responses here; I especially like the lambda expressions...very clean. I was remiss, however, in not specifying the type of Collection. This is a SPRoleAssignmentCollection (from MOSS) that only has Remove(int) and Remove(SPPrincipal), not the handy RemoveAll(). So, I have settled on this, unless there is a better suggestion.

foreach (SPRoleAssignment spAssignment in workspace.RoleAssignments)
{
    if (spAssignment.Member.Name != shortName) continue;
    workspace.RoleAssignments.Remove((SPPrincipal)spAssignment.Member);
    break;
}

To do this while looping through the collection and not to get the modifying a collection exception, this is the approach I've taken in the past (note the .ToList() at the end of the original collection, this creates another collection in memory, then you can modify the existing collection)

foreach (SPRoleAssignment spAssignment in workspace.RoleAssignments.ToList())
{
    if (spAssignment.Member.Name == shortName)
    {
        workspace.RoleAssignments.Remove(spAssignment);
    }
}

Similar to Dictionary Collection point of view, I have done this.

Dictionary<string, bool> sourceDict = new Dictionary<string, bool>();
sourceDict.Add("Sai", true);
sourceDict.Add("Sri", false);
sourceDict.Add("SaiSri", true);
sourceDict.Add("SaiSriMahi", true);

var itemsToDelete = sourceDict.Where(DictItem => DictItem.Value == false);

foreach (var item in itemsToDelete)
{
    sourceDict.Remove(item.Key);
}

Note: Above code will fail in .Net Client Profile (3.5 and 4.5) also some viewers mentioned it is Failing for them in .Net4.0 as well not sure which settings are causing the problem.

So replace with below code (.ToList()) for Where statement, to avoid that error. “Collection was modified; enumeration operation may not execute.”

var itemsToDelete = sourceDict.Where(DictItem => DictItem.Value == false).ToList();

Per MSDN From .Net4.5 onwards Client Profile are discontinued. http://msdn.microsoft.com/en-us/library/cc656912(v=vs.110).aspx

Save your items first, than delete them.

var itemsToDelete = Items.Where(x => !!!your condition!!!).ToArray();
for (int i = 0; i < itemsToDelete.Length; ++i)
	Items.Remove(itemsToDelete[i]);

You need to override GetHashCode() in your Item class.

The best way to do it is by using linq.

Example class:

 public class Product
    {
        public string Name { get; set; }
        public string Price { get; set; }      
    }

Linq query:

var subCollection = collection1.RemoveAll(w => collection2.Any(q => q.Name == w.Name));

This query will remove all elements from collection1 if Name match any element Name from collection2

Remember to use: using System.Linq;

If you have got a List<T>, then List<T>.RemoveAll is your best bet. There can't be anything more efficient. Internally it does the array moving in one shot, not to mention it is O(N).

If all you got is an IList<T> or an ICollection<T> you got roughly these three options:

    public static void RemoveAll<T>(this IList<T> ilist, Predicate<T> predicate) // O(N^2)
    {
        for (var index = ilist.Count - 1; index >= 0; index--)
        {
            var item = ilist[index];
            if (predicate(item))
            {
                ilist.RemoveAt(index);
            }
        }
    }

or

    public static void RemoveAll<T>(this ICollection<T> icollection, Predicate<T> predicate) // O(N)
    {
        var nonMatchingItems = new List<T>();

        // Move all the items that do not match to another collection.
        foreach (var item in icollection) 
        {
            if (!predicate(item))
            {
                nonMatchingItems.Add(item);
            }
        }

        // Clear the collection and then copy back the non-matched items.
        icollection.Clear();
        foreach (var item in nonMatchingItems)
        {
            icollection.Add(item);
        }
    }

or

    public static void RemoveAll<T>(this ICollection<T> icollection, Func<T, bool> predicate) // O(N^2)
    {
        foreach (var item in icollection.Where(predicate).ToList())
        {
            icollection.Remove(item);
        }
    }

Go for either 1 or 2.

1 is lighter on memory and faster if you have less deletes to perform (i.e. predicate is false most of the times).

2 is faster if you have more deletes to perform.

3 is the cleanest code but performs poorly IMO. Again all that depends on input data.

For some benchmarking details see https://github.com/dotnet/BenchmarkDotNet/issues/1505