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?

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

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

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

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

Solution 5

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.

View more solutions

Comments

[Jim Mischel]

Good answer, but I don't think the ToList() is required. Is it?

[Brann]

Good answer, but If I'm not mistaking, s is an instance of the Value type, so the ending s.key won't compile, or will it?

[Brann]

You can't iterate through a Dictionary with FOR.

[Brann]

This would potentially lead to terrible performance, wouldn't it?

[Chris Ammerman]

With the var keyword in there, would this not give newDictionary a type of IEnumerable<KeyValuePair<TKey, TValue>>, rather than Dictionary<TKey, TValue> ?

[aku]

@JaredPar, please fix your answer, it is funny to see that most voted answer won't even compile. Also it is not necessary to query over values, you can get keys directly

[Amy B]

Enumerable.Select does not do filtering.

[Brann]

I'm waiting for someone with editing rights to fix this before I mark this post as the accepted answer.

[JaredPar]

@Jim, the .ToList is absolutely necessary here. The foreach body modifies the underlying collection. Without the .ToList() the Where clause will be operating against a modified collection. Using .ToList() forces the query to complete before any remove occurs

[JaredPar]

@aku, fixed the typo. I originally coded it a different way and then later came back and wanted to use KeyValuePairs. I forgot to update the selection.

[JaredPar]

@Princess, this unfortunately is just life with the implementation of IEnumerable. Yes it's a bit awkward the first time you see it but once you hit the pattern once it's not as bad.

[Geoff]

Sorry, I thought the extension .ElementAt(index) would allow this, at least in .net 3.5.

[Offler]

@brann oh, you can using linq. for (int index = 0; index < MyCollection.Count; index++) { var kvp = MyCollection.ElementAt(index); var kvp = item.Key; var kvp = item.Value; }

[Lyubomir Velchev]

From where filter came from? Can you explain what is it?

[wimh]

I rolled back a change by Community because it did not include ToList() causing the "removing while enumerating" problem.

[supercat]

@Geoff: Suppose the dictionary contains three keys: "Moe", "Larry", and "Curly". }; one wants to delete all keys not starting with "C". The first call to ElementAt(2) will enumerate all three items and return Curly, who should not be deleted. Then ElementAt(1) will enumerate two items, and return Larry. Deleting Larry may arbitrarily resequence the items, so ElementAt(0) might return Moe or Curly. If it happens to return Curly, then Moe will not end up getting processed. ElementAt may be legal, but that doesn't mean it will work usefully.

[Machtyn]

I like it. I threw it into my set of Dictionary extensions. public static T RemoveUnwanted<T,K,V>(this T me, params V[] values) where T : IDictionary<K,V>, new() { foreach (V v in values) { foreach (KeyValuePair<K, V> kvp in me.Where(p => p.Value.Equals(v)).ToList()) { me.Remove(kvp.Key); } } return me; } Use it like myDict = myDict.RemoveUnwanted(myObj1, myObj2, ... myObjn);

[Ulf Åkerstedt]

Thanks for the inspiration Jerome. In addition to this and @Aku's answer I created extension overloads for Func<TKey, bool> and Func<KeyValuePair<TKey, TValue>> that all work along side each other (except if TKey and TValue are of the same type when the compiler obviously can't choose between the Func<TKey, bool> or the Func<TValue, bool>). If someone interested can't figure out how to implement them, ping me here and I'll post them. :-)

[Gerard]

You'll likely need to add using System.Linq; to make this work.

[Nick Allan]

Works a treat. Thanks!

[Theodor Zoulias]

If you want the value for the predicate, then why are you enumerating the keys, and you don't enumerate the dict directly in order to get the key-value pairs? By querying the dictionary for each key, you are losing some efficiency for no apparent reason.

[Brain2000]

Would ToArray( ) be lighter than ToList( )?