Geek asks and answers

Is there an immutable open source dictionary for C # with quick "With / Without" methods?

I am looking for a suitable dictionary with an immutable C # dictionary with quick update methods (which create a partial copy of the dictionary with slight modifications). I myself implemented this using lightning bolts to update the red-black tree, but it is not particularly fast.

By "immutable dictionary" I mean not only readonly, but also const. I want something that has fast enough "With" and "Without" methods or equivalent methods that return a thing with little changes without changing the original.

Example from another map language in Scala

+5
source share
1 answer

AVL .

/**
 * 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.
 */

InsertIntoNew():

/** 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)
{ ... }

RemoveFromNew():

/** 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)
{ ... }

, : AVL #. (log N).

+1

More articles:


All Articles