Extension methods Dictionary<TKey,TValue>.RemoveAll? Is it possible?

Question

I've been trying to write an extension method to mimic List.RemoveAll(Predicate).

So far I've got this:

public static void RemoveAll<TKey,TValue>(this Dictionary<TKey,TValue> dict, 
                                     Predicate<KeyValuePair<TKey,TValue>> condition)
{
    Dictionary<TKey,TValue> temp = new Dictionary<TKey,TValue>();

    foreach (var item in dict)
    {
        if (!condition.Invoke(item))
            temp.Add(item.Key, item.Value);
    }

    dict = temp;
}

Any pointers? Is this a completely naive implementation?

Solution 1

Your code will not work because you are passing the Dictionary class by value. This means the final assignment (dict = temp) will not be visible to a calling function. It is not legal in C# to pass extension method targets by ref or out (in VB it's legal to do ByRef).

Instead you will need to modify the Dictionary inline. Try the following

public static void RemoveAll<TKey,TValue>(this Dictionary<TKey,TValue> dict, 
                                     Func<KeyValuePair<TKey,TValue>,bool> condition)
{
    foreach ( var cur in dict.Where(condition).ToList() ) {
      dict.Remove(cur.Key);
    }
}

EDIT

Swapped the order of Where and ToList to reduce the size of the allocated memory of the list. It will now only allocate a list for the items that are to be removed.

Solution 2

public static void RemoveAll<TKey,TValue>(
    this Dictionary<TKey,TValue> dict, 
    Predicate<KeyValuePair<TKey,TValue>> condition)
{
    var toRemove = new List<TKey>();

    foreach (var item in dict)
    {
        if (!condition(item))
            toRemove.Add(item);
    }
    foreach (var key in toRemove)
    {
        dict.Remove(key);
    }
}

If the number of keys to remove is small relative to the dictionary size this will be faster (if the number removed is likely to be zero you can make this even faster by lazily creating the toRemove list as well.

This boils down to the same as Jared's updated answer but allows you to defer the creation of the removal list if you so desire. If this is not an issue (and you have no reason to break point part way through the process) then Jared's is cleaner and simpler.

Solution 3

That method won't work because the "dict" parameter is not passed by reference, and in fact cannot be because ref is not supported as the first parameter of an extension method.

public static void RemoveAll<TKey,TValue>(this Dictionary<TKey,TValue> dict, 
                                 Predicate<KeyValuePair<TKey,TValue>> condition)
{
    var temp = new List<TKey>();

    foreach (var item in dict)
    {
        if (!condition(item))
            temp.Add(item.Key);
    }

    foreach (var itemKey in temp)
      dict.Remove(itemKey)
}

I'd like to see RemoveAllByKey and RemoveAllByValue implementations as well.

Comments

[ShuggyCoUk]

Has the disadvantage of allocating enough memory for the key list everytime. but certainly simple

[JaredPar]

@Rob how so? Works fine for sample data I've used

[Dustin Campbell]

@Rob Stevenson-Leggett sure it does.

[Rob Stevenson-Leggett]

Wouldn't compile for me, changed it to the editted version and it works. Was giving me: Type args cannot be inferred from usage.

[JaredPar]

@Rob, there was a slight typo in the first version.

[Lucero]

It is not recommended to modify the collection while iterating over it. In fact, many iterators will throw an exception if you do this.

[tina Miller]

@Lucero, he's not looping over it, he's looping over a list which is a projection of it. @Rob Stevenson-Leggett, I'm surprised you accepted this answer, because it alters the signature of your desired function (which was aimed at replicating List.RemoveAll). You could replace Func<> condition with Predicate<> match, then .Where(x => match(x))

[base2]

No need to call the condition.Invoke(...) method on the condition, because, it is already a delegate. You can just call condition directly, e.g. condition(item).

[ShuggyCoUk]

@base2 I was just replicating the original users style. I agree it's better without the Invoke though, I'll change it