Editing dictionary values in a foreach loop

Question

I am trying to build a pie chart from a dictionary. Before I display the pie chart, I want to tidy up the data. I'm removing any pie slices that would be less than 5% of the pie and putting them in a "Other" pie slice. However I'm getting a Collection was modified; enumeration operation may not execute exception at runtime.

I understand why you can not add or remove items from a dictionary while iterating over them. However I don't understand why you can't simply change a value for an existing key within the foreach loop.

Any suggestions re: fixing my code, would be appreciated.

Dictionary<string, int> colStates = new Dictionary<string,int>();
// ...
// Some code to populate colStates dictionary
// ...

int OtherCount = 0;

foreach(string key in colStates.Keys)
{

    double  Percent = colStates[key] / TotalCount;

    if (Percent < 0.05)
    {
        OtherCount += colStates[key];
        colStates[key] = 0;
    }
}

colStates.Add("Other", OtherCount);

Answer 1

Setting a value in a dictionary updates its internal "version number" - which invalidates the iterator, and any iterator associated with the keys or values collection.

I do see your point, but at the same time it would be odd if the values collection could change mid-iteration - and for simplicity there's only one version number.

The normal way of fixing this sort of thing is to either copy the collection of keys beforehand and iterate over the copy, or iterate over the original collection but maintain a collection of changes which you'll apply after you've finished iterating.

For example:

Copying keys first

List<string> keys = new List<string>(colStates.Keys);
foreach(string key in keys)
{
    double percent = colStates[key] / TotalCount;    
    if (percent < 0.05)
    {
        OtherCount += colStates[key];
        colStates[key] = 0;
    }
}

Or...

Creating a list of modifications

List<string> keysToNuke = new List<string>();
foreach(string key in colStates.Keys)
{
    double percent = colStates[key] / TotalCount;    
    if (percent < 0.05)
    {
        OtherCount += colStates[key];
        keysToNuke.Add(key);
    }
}
foreach (string key in keysToNuke)
{
    colStates[key] = 0;
}

Answer 2

Call the ToList() in the foreach loop. This way we dont need a temp variable copy. It depends on Linq which is available since .Net 3.5.

using System.Linq;

foreach(string key in colStates.Keys.ToList())
{
  double  Percent = colStates[key] / TotalCount;

    if (Percent < 0.05)
    {
        OtherCount += colStates[key];
        colStates[key] = 0;
    }
}

Answer 3

You are modifying the collection in this line:

colStates[key] = 0;

By doing so, you are essentially deleting and reinserting something at that point (as far as IEnumerable is concerned anyways.

If you edit a member of the value you are storing, that would be OK, but you are editing the value itself and IEnumberable doesn't like that.

The solution I've used is to eliminate the foreach loop and just use a for loop. A simple for loop won't check for changes that you know won't effect the collection.

Here's how you could do it:

List<string> keys = new List<string>(colStates.Keys);
for(int i = 0; i < keys.Count; i++)
{
    string key = keys[i];
    double  Percent = colStates[key] / TotalCount;
    if (Percent < 0.05)    
    {        
        OtherCount += colStates[key];
        colStates[key] = 0;    
    }
}

Answer 4

You can't modify the keys nor the values directly in a ForEach, but you can modify their members. E.g., this should work:

public class State {
    public int Value;
}

...

Dictionary<string, State> colStates = new Dictionary<string,State>();

int OtherCount = 0;
foreach(string key in colStates.Keys)
{
    double  Percent = colStates[key].Value / TotalCount;

    if (Percent < 0.05)
    {
        OtherCount += colStates[key].Value;
        colStates[key].Value = 0;
    }
}

colStates.Add("Other", new State { Value =  OtherCount } );

Answer 5

How about just doing some linq queries against your dictionary, and then binding your graph to the results of those?...

var under = colStates.Where(c => (decimal)c.Value / (decimal)totalCount < .05M);
var over = colStates.Where(c => (decimal)c.Value / (decimal)totalCount >= .05M);
var newColStates = over.Union(new Dictionary<string, int>() { { "Other", under.Sum(c => c.Value) } });

foreach (var item in newColStates)
{
    Console.WriteLine("{0}:{1}", item.Key, item.Value);
}

Answer 6

If you're feeling creative you could do something like this. Loop backwards through the dictionary to make your changes.

Dictionary<string, int> collection = new Dictionary<string, int>();
collection.Add("value1", 9);
collection.Add("value2", 7);
collection.Add("value3", 5);
collection.Add("value4", 3);
collection.Add("value5", 1);

for (int i = collection.Keys.Count; i-- > 0; ) {
    if (collection.Values.ElementAt(i) < 5) {
        collection.Remove(collection.Keys.ElementAt(i)); ;
    }

}

Certainly not identical, but you might be interested anyways...

Answer 7

You need to create a new Dictionary from the old rather than modifying in place. Somethine like (also iterate over the KeyValuePair<,> rather than using a key lookup:

int otherCount = 0;
int totalCounts = colStates.Values.Sum();
var newDict = new Dictionary<string,int>();
foreach (var kv in colStates) {
  if (kv.Value/(double)totalCounts < 0.05) {
    otherCount += kv.Value;
  } else {
    newDict.Add(kv.Key, kv.Value);
  }
}
if (otherCount > 0) {
  newDict.Add("Other", otherCount);
}

colStates = newDict;

Answer 8

Starting with .NET 4.5 You can do this with ConcurrentDictionary:

using System.Collections.Concurrent;

var colStates = new ConcurrentDictionary<string,int>();
colStates["foo"] = 1;
colStates["bar"] = 2;
colStates["baz"] = 3;

int OtherCount = 0;
int TotalCount = 100;

foreach(string key in colStates.Keys)
{
    double Percent = (double)colStates[key] / TotalCount;

    if (Percent < 0.05)
    {
        OtherCount += colStates[key];
        colStates[key] = 0;
    }
}

colStates.TryAdd("Other", OtherCount);

Note however that its performance is actually much worse that a simple foreach dictionary.Kes.ToArray():

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

public class ConcurrentVsRegularDictionary
{
    private readonly Random _rand;
    private const int Count = 1_000;

    public ConcurrentVsRegularDictionary()
    {
        _rand = new Random();
    }

    [Benchmark]
    public void ConcurrentDictionary()
    {
        var dict = new ConcurrentDictionary<int, int>();
        Populate(dict);

        foreach (var key in dict.Keys)
        {
            dict[key] = _rand.Next();
        }
    }

    [Benchmark]
    public void Dictionary()
    {
        var dict = new Dictionary<int, int>();
        Populate(dict);

        foreach (var key in dict.Keys.ToArray())
        {
            dict[key] = _rand.Next();
        }
    }

    private void Populate(IDictionary<int, int> dictionary)
    {
        for (int i = 0; i < Count; i++)
        {
            dictionary[i] = 0;
        }
    }
}

public class Program
{
    public static void Main(string[] args)
    {
        BenchmarkRunner.Run<ConcurrentVsRegularDictionary>();
    }
}

Result:

              Method |      Mean |     Error |    StdDev |
--------------------- |----------:|----------:|----------:|
 ConcurrentDictionary | 182.24 us | 3.1507 us | 2.7930 us |
           Dictionary |  47.01 us | 0.4824 us | 0.4512 us |

Answer 9

You can't modify the collection, not even the values. You could save these cases and remove them later. It would end up like this:

Dictionary<string, int> colStates = new Dictionary<string, int>();
// ...
// Some code to populate colStates dictionary
// ...

int OtherCount = 0;
List<string> notRelevantKeys = new List<string>();

foreach (string key in colStates.Keys)
{

    double Percent = colStates[key] / colStates.Count;

    if (Percent < 0.05)
    {
        OtherCount += colStates[key];
        notRelevantKeys.Add(key);
    }
}

foreach (string key in notRelevantKeys)
{
    colStates[key] = 0;
}

colStates.Add("Other", OtherCount);

Answer 10

In .NET 5 the dictionary items can be changed while the dictionary is enumerated.

The Pull Request is: Allow Dictionary overwrites during enumeration and the issue is Consider removing _version++ from overwrites in Dictionary<TKey, TValue>.

Now you can:

foreach (var pair in dict)
    dict[pair.Key] = pair.Value + 1;

Answer 11

Disclaimer: I don't do much C#

You are trying to modify the DictionaryEntry object which is stored in the HashTable. The Hashtable only stores one object -- your instance of DictionaryEntry. Changing the Key or the Value is enough to change the HashTable and cause the enumerator to become invalid.

You can do it outside of the loop:

if(hashtable.Contains(key))
{
    hashtable[key] = value;
}

by first creating a list of all the keys of the values you wish to change and iterate through that list instead.

Answer 12

You can make a list copy of the dict.Values, then you can use the List.ForEach lambda function for iteration, (or a foreach loop, as suggested before).

new List<string>(myDict.Values).ForEach(str =>
{
  //Use str in any other way you need here.
  Console.WriteLine(str);
});

Answer 13

Along with the other answers, I thought I'd note that if you get sortedDictionary.Keys or sortedDictionary.Values and then loop over them with foreach, you also go through in sorted order. This is because those methods return System.Collections.Generic.SortedDictionary<TKey,TValue>.KeyCollection or SortedDictionary<TKey,TValue>.ValueCollection objects, which maintain the sort of the original dictionary.

Answer 14

This answer is for comparing two solutions, not a suggested solution.

Instead of creating another list as other answers suggested, you can used a for loop using the dictionary Count for the loop stop condition and Keys.ElementAt(i) to get the key.

for (int i = 0; i < dictionary.Count; i++)
{
    dictionary[dictionary.Keys.ElementAt(i)] = 0;
}

At firs I thought this would be more efficient because we do not need to create a key list. After running a test I found that the for loop solution is much less efficient. The reason is because ElementAt is O(n) on the dictionary.Keys property, it searches from the beginning of the collection until it gets to the nth item.

Test:

int iterations = 10;
int dictionarySize = 10000;
Stopwatch sw = new Stopwatch();

Console.WriteLine("Creating dictionary...");
Dictionary<string, int> dictionary = new Dictionary<string, int>(dictionarySize);
for (int i = 0; i < dictionarySize; i++)
{
    dictionary.Add(i.ToString(), i);
}
Console.WriteLine("Done");

Console.WriteLine("Starting tests...");

// for loop test
sw.Restart();
for (int i = 0; i < iterations; i++)
{
    for (int j = 0; j < dictionary.Count; j++)
    {
        dictionary[dictionary.Keys.ElementAt(j)] = 3;
    }
}
sw.Stop();
Console.WriteLine($"for loop Test:     {sw.ElapsedMilliseconds} ms");

// foreach loop test
sw.Restart();
for (int i = 0; i < iterations; i++)
{
    foreach (string key in dictionary.Keys.ToList())
    {
        dictionary[key] = 3;
    }
}
sw.Stop();
Console.WriteLine($"foreach loop Test: {sw.ElapsedMilliseconds} ms");

Console.WriteLine("Done");

Results:

Creating dictionary...
Done
Starting tests...
for loop Test:     2367 ms
foreach loop Test: 3 ms
Done