Removing elements from a Dictionary

  • Article

The topic of removing elements from a dictionary came up recently on an internal mailing list.  Someone was iterating through all the elements of a collection and wanting to remove some of them. The problem with that is that modifying the collection underlying the enumerator throws.  He had the following pseudo code:

 void RemoveSomeElements(Dictionary<string, int> dict){    foreach (var e in dict)    {        if (e.Value < 35)        {            // Remove e!        }    }}

Several people replied that he could just create a list of elements to be removed and then iterate that afterwards:

 var keysToRemove = new List<string>();foreach (var e in dict){    if (e.Value < 35)    {        keysToRemove.Add(e.Key);    }}foreach (var key in keysToRemove){    dict.Remove(key);}

That works, but it’s pretty verbose.  Someone suggested a more functional way to do it that’s pretty nice:

 dict.ToList().Where(pair => pair.Value < 35).ToList().ForEach(pair => dict.Remove(pair.Key));

At this point I decided to show off, and make it more efficient by using an “Apply” extension method instead of the .ForEach method that shipped on List<T> in .Net 2.0.  I came up with this:

 dict.Where(pair => pair.Value < 35).Apply(pair => dict.Remove(pair.Key)).Apply();

 

Along with the code to Apply:

 public static class ApplyExtensions{    public static IEnumerable<T> Apply<T>(this IEnumerable<T> source, Action<T> action)    {        Argument.NotNull(source, () => () => source);        Argument.NotNull(action, () => () => action);        return ApplyInternal(source, action);    }    internal static IEnumerable<T> ApplyInternal<T>(IEnumerable<T> source, Action<T> action)    {        foreach (var e in source)        {            action(e);            yield return e;        }    }    public static void Apply<T>(this IEnumerable<T> source)    {        foreach (var e in source)        {            // do nothing, just make sure the elements are enumerated.        }    }}

Here I thought I was doing right by C# 3.0, and showing people how to use lazily chained iterators.  Unfortunately, this code drops us right back to the original problem!  Because of lazy iteration, we’re actually still iterating the dictionary when we try to remove the elements, and so we invalidate the first iterator in our chain. 

It’s a simple fix, but still a reminder that the semantics of delayed execution can be tricky to reason about sometimes:

 dict.Where(pair => pair.Value < 35).ToArray().Apply(pair => dict.Remove(pair.Key)).Apply();

The “ToArray” call finishes the iteration of the dictionary, but uses less space than the original “.ForEach” solution, since we only realize a collection of the elements to be removed, instead of all of the elements in the dictionary.