Why can't we change values of a dictionary while enumerating its keys?

Question

class Program
{
    static void Main(string[] args)
    {
        var dictionary = new Dictionary<string, int>()
        {
            {"1", 1}, {"2", 2}, {"3", 3}
        };

        foreach (var s in dictionary.Keys)
        {
            // Throws the "Collection was modified exception..." on the next iteration
            // What's up with that?

            dictionary[s] = 1;  
        }
    }
}

I completely understand why this exception is thrown when enumerating a list. It seems reasonable to expect that during enumeration the structure of the enumerated object does not change. However, does changing a value of a dictionary also changes its structure? Specifically, the structure of its keys?

Geoid

Answer 1

I see where you're coming from, actually. What most of the answers here fail to notice is that you are iterating across the list of Keys, and not the Dictionary's Items themselves. If the .NET framework programmers wanted to, they could fairly easily differentiate between changes made to the structure of the dictionary and changes made to the values in the dictionary. Nevertheless, even when people iterate across the keys of a collection, they usually end up getting the values out anyway. I suspect the .NET framework designers figured that if you're iterating across those values, you'll want to know if something is changing them out from under you, just as much as with any List. Either that or they didn't see it as an important enough issue to merit the programming and maintenance that would be required to differentiate between one kind of change and another.

Fabricant

Thanks for pointing it out. Although this is an old answer, I'd like to point out something as well. The most confusing thing is, that in the VS debugger, one could drill into Object.Dictionary.List (I hope I describe it clear enough) and see there same list of values, as in Object.Dictionary.Items. No wonder, we then tend to loop through wrong collection... – Selfaggrandizement

Answer 2

Because the values and keys are stored as a pair. There is not a separate structure for keys and values but instead a single structure which stores both as a set of pair values. When you change a value it necessitates changing the single underlying structure which contains both keys and values.

Does changing a value necessarily change the order of the underlying structure? No. But this is an implementation specific detail and the Dictionary<TKey,TValue> class, correctly, deemed not to reveal this by allowing modification of values as part of the API.

Karlenekarlens

Correct answer, the items are of type KeyValuePair<TKey, TValue>, the enumerator iterations the items, not the keys. – Slung

As far as I know, a dictionary is implemented as a hash table, meaning it is not stored as a List of key value pairs. And even if it were, the Value is just a Parasite hanging on to the key- its the keys that are organized in a tricky sophisticated structure. – Geoid

@Geoid I was very careful to not say List in my answer for a reason. The underlying structure implementation is somewhat irrelevant other than keys and values are seen as a pair. Changing one affects the other because they are considered part of the same object. – Karlenekarlens

I think that the assumption that they are considered part of the same object is not trivial (unless you have seen the code already). The fact is that most implementations of a hash table I am familiar with, do not store keys and values as pairs. And the structure does enable changing values without altering the key structure. – Geoid

Jared - I would argue completely the opposite; throwing the exception IS exposing the implementation detail. A proper abstraction would not tell you the .Keys collection has changed when in fact it hasn't. – Lands

Wrong answer. The behavior was just an unfortunate design choice, perhaps just based on how easily the conditions of the enumeration could be optimized by the coders. Once an element has been produced in the sequence, it shouldn't matter if it gets changed. – Tirza

Answer 3

Thanks to Vitaliy I went back and looked at the code some more and it looks like it is a specific implementation decision to disallow this (see snippet below). The Dictionary keeps a private value called verrsion which is incremented when changing the value of an existing item. When the enumerator is created it makes a note of the value at that time, then checks on each call to MoveNext.

for (int i = this.buckets[index]; i >= 0; i = this.entries[i].next)
{
    if ((this.entries[i].hashCode == num) && this.comparer.Equals(this.entries[i].key, key))
    {
        if (add)
        {
            ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
        }
        this.entries[i].value = value;
        this.version++;
        return;
    }
}

I don't know of a reason why this would be necessary. You are still free to modify the properties of the value, just not assign it to a new value:

public class IntWrapper
{
  public IntWrapper(int v) { Value = v; }
  public int Value { get; set; }
}

class Program
{
  static void Main(string[] args)
  {
    var kvp = new KeyValuePair<string, int>("1",1);
    kvp.Value = 17;
    var dictionary = new Dictionary<string, IntWrapper>(){
      {"1", new IntWrapper(1)}, 
      {"2", new IntWrapper(2)}, 
      {"3", new IntWrapper(3)} };

    foreach (var s in dictionary.Keys)
    {
      dictionary[s].Value = 1;  //OK
      dictionary[s] = new IntWrapper(1); // boom
    }
  } 
}

Volcanology

I am skeptical that a dictionary is implemented with an array of KeyValue pairs. Especially considering the fact that two different keys can be mapped to the same numerical hash code. So each key is actually mapped to multiple values. Hence the need to override Equals. – Geoid

If you are skeptical you can go grab a copy of .Net Reflector and disassemble the code yourself. – Volcanology

Well, I viewed the implementation, and whilst a dictionary does have a collection of entries, it is not obvious why the value cannot be changed. Although a KeyValuePair is a struct, it is not immutable by nature, as you stated, thus its Value property Can be changed. Moreover, considering whichever reason that with the given implementation throws when a value is changed during enumeration, This behavior is not intuitive and breaks encapsulation by exposing implementation details. Some would say thats just plain bad API design! – Geoid

I was too quick in reading the implementation. My other answer talks about the mechanism, though I still can't think of a good reason why. – Volcanology

@Volcanology That was a good example. I agree there is no good reason to disallow changing properties of an element. – Tirza

Answer 4

It's possible that you've just inserted a new key into the dictionary, which would indeed change dictionary.Keys. Even though in this specific loop that will never happen, the [] operation in general can change the list of keys so this is flagged as a mutation.

Hepato

Answer 5

Indexer on Dictionary is potentially an operation that can change the structure of the collection, since it will add a new entry with such key if one doesn't exist already. This obviously isn't the case here, but I expect that Dictionary contract is deliberately kept simple in that all operations on the object are divided into "mutating" and "non-mutating", and all "mutating" operations invalidate enumerators, even if they don't actually change anything.

Raposa

Answer 6

From the documentation (Dictionary.Item Property):

You can also use the Item property to add new elements by setting the value of a key that does not exist in the Dictionary. When you set the property value, if the key is in the Dictionary, the value associated with that key is replaced by the assigned value. If the key is not in the Dictionary, the key and value are added to the dictionary. In contrast, the Add method does not modify existing elements.

So, as John indicates, there is no way for the framework to know that you haven't altered the contents of the list, so it assumes that you have.

Kearse

I disagree. The framework does know that you have accessed the indexer property. It is trivial to check whether the structure of the keys was invalidated, and issue an exception only in that case. – Geoid

@Geoid Not only is it trivial, .net has to do it for the Add method and in fact it already does. – Ce

Answer 7

For those interested in how to get around this problem, here's a modified version of Vitaliy's code that works:

class Program
{
    static void Main(string[] args)
    {
        var dictionary = new Dictionary<string, int>()
        {
            {"1", 1}, {"2", 2}, {"3", 3}
        };

        string[] keyArray = new string[dictionary.Keys.Count];
        dictionary.Keys.CopyTo(keyArray, 0);
        foreach (var s in keyArray)
        {
            dictionary[s] = 1;
        }
    }
}

The answer is to copy the keys out into another enumerable then iterate over that collection. For some reason there is no KeyCollection.ToList method to make things easy. Instead you need to use the KeyCollection.CopyTo method, which copies the keys out into an array.

Lundy

This doesn't solve the issue, partner. You still get the Collection Modified error. Nice try but not cigar. – Nelsen

@ObiWan: No error for me in a .NET 4.5 console application written in VS 2013. What version of .NET are you using? – Lundy

At the time I was using 4.6.1 I probably did not do exactly what you did. I apologize for my cynical comment which I made because I was frustrated. It seems ridiculous to me that I cannot simply iterate the keys collection and modify the values as long as I don't change the key collection. This entire issue is because of bad design IMO of the Dictionary class not to allow this. – Nelsen

@ObiWan: No problems, I wasn't offended. It was fair enough to raise the issue if you couldn't reproduce my results. Cheers. – Lundy

Answer 8

The short answer is that you are modifying the dictionary collection, even though you're not actually changing any of its keys. So the next iteration that accesses the collection after your update throws an exception that indicates that the collection was modified since your last access (and rightly so).

To do what you want, you need a different way of iterating through the elements, so that changing them won't trigger an iterator exception.

Triforium

Answer 9

It's because they designed .Net with the ability to iterate a collection in multiple threads. So you either gotta allow the iterator be multithreaded or prevent that and allow the modification of the collection during the iteration which would require limiting the object to be itereated in a single thread. Can't have both.

In fact the answer to your question is that the code you type in actually results in a compiler generated ([CompilerGenerated]) state machine that allows for iterators to maintain the collection state in order to provide the yield magic. Thats why if you dont synchronize your collections and you iterate in one thread and manipulate in another thread, you;ll get some funky shit going on.

Check out: http://csharpindepth.com/articles/chapter6/iteratorblockimplementation.aspx

Also: http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentHashMap.html "iterators are designed to be used by only one thread at a time."

Coolth