Menu
I'm looking for a proper C# immutable dictionary, with fast update methods (that create a partial copy of the dictionary with slight changes). I've implemented one myself, using zippers to update a red-black tree, but it's not particularly fast.
By 'immutable dictionary' I don't just mean readonly or const. I want something that has reasonably fast 'With' and 'Without', or equivalent, methods that return a thing with slight modifications without modifying the original.
An example from another language is map in Scala
898
The ImmutableDictionary<TKey,TValue> class represents an immutable, unordered collection of keys and values in C#. However, you can't create an immutable dictionary with the standard initializer syntax, since the compiler internally translates each key/value pair into chains of the Add() method.
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.
There is some implementation of the immutable dictionary based on read-only binary AVL tree.
/**
* To modify, use the InsertIntoNew and RemoveFromNew methods
* which return a new instance with minimal changes (about Log C),
* so this is an efficient way to make changes without having
* to copy the entire data structure.
*/
Please take a look at the InsertIntoNew() method:
/** Return a new tree with the key-value pair inserted
* If the key is already present, it replaces the value
* This operation is O(Log N) where N is the number of keys
*/
public ImmutableDictionary<K,V> InsertIntoNew(K key, V val)
{ ... }
The RemoveFromNew() method:
/** Try to remove the key, and return the resulting Dict
* if the key is not found, old_node is Empty, else old_node is the Dict
* with matching Key
*/
public ImmutableDictionary<K,V> RemoveFromNew(K key, out ImmutableDictionary<K,V> old_node)
{ ... }
Also, there is another implementation: Immutable AVL Tree in C#. It has the same O(log N) lookup and insertion times.
172
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
