Does C# Have a Way of Giving Me an Immutable Dictionary

Does C# have a way of giving me an immutable Dictionary?

No, but a wrapper is rather trivial:

public class ReadOnlyDictionary<TKey, TValue> : IDictionary<TKey, TValue>
{
    IDictionary<TKey, TValue> _dict;

    public ReadOnlyDictionary(IDictionary<TKey, TValue> backingDict)
    {
        _dict = backingDict;
    }

    public void Add(TKey key, TValue value)
    {
        throw new InvalidOperationException();
    }

    public bool ContainsKey(TKey key)
    {
        return _dict.ContainsKey(key);
    }

    public ICollection<TKey> Keys
    {
        get { return _dict.Keys; }
    }

    public bool Remove(TKey key)
    {
        throw new InvalidOperationException();
    }

    public bool TryGetValue(TKey key, out TValue value)
    {
        return _dict.TryGetValue(key, out value);
    }

    public ICollection<TValue> Values
    {
        get { return _dict.Values; }
    }

    public TValue this[TKey key]
    {
        get { return _dict[key]; }
        set { throw new InvalidOperationException(); }
    }

    public void Add(KeyValuePair<TKey, TValue> item)
    {
        throw new InvalidOperationException();
    }

    public void Clear()
    {
        throw new InvalidOperationException();
    }

    public bool Contains(KeyValuePair<TKey, TValue> item)
    {
        return _dict.Contains(item);
    }

    public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
    {
        _dict.CopyTo(array, arrayIndex);
    }

    public int Count
    {
        get { return _dict.Count; }
    }

    public bool IsReadOnly
    {
        get { return true; }
    }

    public bool Remove(KeyValuePair<TKey, TValue> item)
    {
        throw new InvalidOperationException();
    }

    public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
    {
        return _dict.GetEnumerator();
    }

    System.Collections.IEnumerator 
           System.Collections.IEnumerable.GetEnumerator()
    {
        return ((System.Collections.IEnumerable)_dict).GetEnumerator();
    }
}

Obviously, you can change the this[] setter above if you want to allow modifying values.

Constructing immutable dictionary with inner immutable dictionary

You just need to convert each of the internal dictionaries into immutable dictionaries as well, and then make a new ImmutableDictionary from those.

ImmutableDictionary<Type, ImmutableDictionary<Type, Action>> immutableDict = dict
    .ToImmutableDictionary(e => e.Key, e => e.Value.ToImmutableDictionary());

Why would you use an immutable value in a dictionary?

Second question's answer is that the member variables are still settable without the readonly keyword - only within the class itself, but it is still possible.

BTW, this class seems like a solid candidate for a struct.

How can I create a new instance of ImmutableDictionary?

You can't create immutable collection with a collection initializer because the compiler translates them into a sequence of calls to the Add method. For example if you look at the IL code for var d = new Dictionary<string, int> { { "a", 1 }, { "b", 2 } }; you'll get

IL_0000: newobj instance void class [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::.ctor()
IL_0005: dup
IL_0006: ldstr "a"
IL_000b: ldc.i4.1
IL_000c: callvirt instance void class [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::Add(!0, !1)
IL_0011: dup
IL_0012: ldstr "b"
IL_0017: ldc.i4.2
IL_0018: callvirt instance void class [mscorlib]System.Collections.Generic.Dictionary`2<string, int32>::Add(!0, !1)

Obviously this violates the concept of immutable collections.

Both your own answer and Jon Skeet's are ways to deal with this.

// lukasLansky's solution
var d = new Dictionary<string, int> { { "a", 1 }, { "b", 2 } }.ToImmutableDictionary();

// Jon Skeet's solution
var builder = ImmutableDictionary.CreateBuilder<string, int>();
builder.Add("a", 1);
builder.Add("b", 2);   
var result = builder.ToImmutable();

Why is the .NET DictionaryTKey, TValue immutable?

The dictionary itself is not immutable. But you cannot change the dictionary while enumerating it in the foreach-loop.

Here a link for further reading: Why is The Iteration Variable in a C# foreach statement read-only?

What's the difference between a ReadOnlyDictionary and an ImmutableDictionary?

• A ReadOnlyDictionary can be initialized once via constructor, then you can't add or remove items from it (they throw NotSupportedExceptions). It's useful if you want to ensure that it won't be modified while it's sent across multiple layers of your application.
• An ImmutableDictionary has methods to modify it like Add or Remove, but they will create a new dictionary and return that, the original one remains unchanged and the copy of the new immutable dictionary is returned.

Note that:

• You initialize the ReadOnlyDictionary by passing another dictionary instance to the constructor. That explains why a ReadOnlyDictionary is mutable (if the underlying dictionary is modified). It's just a wrapper that is protected from direct changes.
• You can't use a constructor for ImmutableDictionary: How can I create a new instance of ImmutableDictionary?

That also explains why the ReadOnlyDictionary is not thread-safe (better: it's as thread-safe as the underlying dictionary). The ImmutableDictionary is thread-safe because you can't modify the original instance (neither directly nor indirectly). All methods that "modify" it actually return a new instance.

But if you need a thread-safe dictionary and it's not necessary that it's immutable, use a ConcurrentDictionary instead.

Immutable Dictionary Vs Dictionary Vs C5

The standard dictionary is already quite well optimized. All it really does when you do a lookup is calculate the hash of the provided key (the speed of which depends on the type of the key and how it implements GetHashCode), a modulo operation on the hash value to find the right bucket and then it iterates through the contents of the bucket until it finds the right value (the speed of which depends on the quality of the GetHashCode function, so if the buckets are well balanced and don't contain too many items, and the speed of the Equals method for the type).

All in all, it doesn't do that much for lookups, so I don't think you'll be able to find a significantly faster generic data structure. However, it's possible that depending on how you plan to use the dictionaries, you're able to build a more specialized solution. For example, I needed a really fast lookup where the key was a type. Instead of using a dictionary and doing dictionary[typeof(T)], I made a generic class like so:

class ValueStore<T> 
{
  public static T Value;
}

So I could just do ValueStore<T>.Value with pretty much zero lookup overhead.

Whether or not you could do something similar (and whether it's worth it) really depends on your usecase; how many items the structure would hold, how often it's being read and written to, whether it needs to be threadsafe, how important write speed is, etc. For example, if write speed didn't matter at all but if thread safety was required, you would need to do a copy-on-write, where the data structure is never written to but instead copied, ensuring thread safety and lockless (thus: fast) reads, at the cost of write speeds. Specializing it could go as far as reordering the structure on writes to optimize it so the hash buckets don't contain more than N items.

PS: if you were really desperate for speed but couldn't build a more specialized data structure then you could perhaps get small gains from copying Dictionary<TKey,TValue> and removing the various sanity checks (null checks and such) and virtual/interface method calls. However, I doubt this would give you any more than 20% gain, if that.

Unchangeable Dictionary

I think that you'll need a class that wraps a Dictionary like the ReadOnlyCollection wraps a List.

While you will not find a default class that does this, you'll find an implementation in one of the answers to this question.

The BCL Extras Project also contains such an implementation. It supports the creation of a proxy object which implements IDictionary and can be used in its place.

f# dictionary, immutability and performance

The System.Collections.Generic.Dictionary class is identical between F# and C# (it's the exact same thing). If that works for you in C#, it should work perfectly well for you in F#, using precisely the same method calls. This interoperability with other .NET languages is a good aspect of F#. F# for Fun and Profit has some info on porting from C# to F#.

The confusion likely arises because you are looking at discussions of F#'s built-in Map type, which does much the same thing but is F#-specific and 'immutable' (I'm pretty sure it is a persistent data structure, meaning that you don't have to entirely chuck out the old one to create a new version).

See here and here for a bit more of a Dictionary vs Map discussion - turns out there's actually C# dictionaries, F# dictionaries and F# maps, apparently.

All this being said, using strings as keys in a dictionary doesn't sound like a particularly great idea to me in performance terms, though I'm failing to come up with a suitable replacement if there is a potentially unbounded set of keys possible.

---

Related Topics