Best way to remove multiple items matching a predicate from a .NET Dictionary?

Question

I need to remove multiple items from a Dictionary. A simple way to do that is as follows :

  List<string> keystoremove= new List<string>();
  foreach (KeyValuePair<string,object> k in MyCollection)
     if (k.Value.Member==foo)
        keystoremove.Add(k.Key);
  foreach (string s in keystoremove)
        MyCollection.Remove(s);

The reason why I can't directly Remove the items in the foreach block is that this would throw an Exception ("Collection was modified...")

I'd like to do the following :

 MyCollection.RemoveAll(x =>x.Member==foo)

But the Dictionary<> class doesn't expose a RemoveAll(Predicate<> Match) method, like the List<> Class does.

What's the best way (both performance wise and elegant wise) to do that?

Answer 1

Here's an alternate way

foreach ( var s in MyCollection.Where(kv => kv.Value.Member == foo).ToList() ) {
  MyCollection.Remove(s.Key);
}

Pushing the code into a list directly allows you to avoid the "removing while enumerating" problem. The .ToList() will force the enumeration before the foreach really starts.

Answer 2

you can create an extension method:

public static class DictionaryExtensions
{
    public static void RemoveAll<TKey, TValue>(this IDictionary<TKey, TValue> dict, 
        Func<TValue, bool> predicate)
    {
        var keys = dict.Keys.Where(k => predicate(dict[k])).ToList();
        foreach (var key in keys)
        {
            dict.Remove(key);
        }
    }
}

...

dictionary.RemoveAll(x => x.Member == foo);

Answer 3

Instead of removing, just do the inverse. Create a new dictionary from the old one containing only the elements you are interested in.

public Dictionary<T, U> NewDictionaryFiltered<T, U>
(
  Dictionary<T, U> source,
  Func<T, U, bool> filter
)
{
return source
  .Where(x => filter(x.Key, x.Value))
  .ToDictionary(x => x.Key, x => x.Value);
}

Answer 4

Modified version of Aku's extension method solution. Main difference is that it allows the predicate to use the dictionary key. A minor difference is that it extends IDictionary rather than Dictionary.

public static class DictionaryExtensions
{
    public static void RemoveAll<TKey, TValue>(this IDictionary<TKey, TValue> dic,
        Func<TKey, TValue, bool> predicate)
    {
        var keys = dic.Keys.Where(k => predicate(k, dic[k])).ToList();
        foreach (var key in keys)
        {
            dic.Remove(key);
        }
    }
}

. . .

dictionary.RemoveAll((k,v) => v.Member == foo);

Answer 5

Starting from the .NET 3.0, it's now allowed to remove items from a Dictionary<TKey,TValue> while enumerating it. According to the documentation:

.NET Core 3.0+ only: The only mutating methods which do not invalidate enumerators are Remove and Clear.

Here is the GitHub issue where this change was proposed and approved: Allow Dictionary<K,V>.Remove during enumeration

So the RemoveAll extension method can be implemented simply like this:

/// <remarks>.NET Core 3.0+ only.</remarks>
public static void RemoveAll<TKey, TValue>(this Dictionary<TKey, TValue> source,
    Predicate<KeyValuePair<TKey, TValue>> predicate)
{
    foreach (var pair in source)
        if (predicate(pair))
            source.Remove(pair.Key);
}

Usage example:

myDictionary.RemoveAll(e => e.Value.Member == foo);

Answer 6

The fastest way to remove would be either:

public static void RemoveAll<TKey, TValue>(this IDictionary<TKey, TValue> idict, Func<KeyValuePair<TKey, TValue>, bool> predicate)
    {
        foreach (var kvp in idict.Where(predicate).ToList())
        {
            idict.Remove(kvp.Key);
        }
    }

or

public static void RemoveAll<T>(this ICollection<T> icollection, Predicate<T> predicate)
{
    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);
    }
}

depending on whether you have more cases of predicate returning true or not. Both are O(N) in nature, but 1st approach will be faster if you have very less cases of "removal/lookup", and the second one faster if items in collection matches the condition majority of the times.

Answer 7

Can you just change your loop to use an index (i.e. FOR instead of FOREACH)? You'd have to loop backwards, of course, i.e. count-1 down to zero.

Answer 8

Instead of removing just do the inverse (create a new dictionary from the old one containing only the elements you are interested in) and let the garbage collector take care of the old dictionary:

var newDictionary = oldDictionary.Where(x => x.Value != foo);

Answer 9

It's simple using LINQ. Just do the following :)

MyCollection = MyCollection.Where(mc => !keystoremove.Contains(mc.Key))
.ToDictionary(d => d.Key, d => d.Value);