是否存在C#的开源不可变字典,具有快速"With/Without"方法？

Question

我正在寻找一个适当的C#immutable字典,使用快速更新方法(创建一个略有变化的字典的部分副本).我自己实现了一个,使用拉链来更新红黑树,但它并不是特别快.

通过'不可变字典',我不只是指readonly或const.我想要一些具有相当快速的"With"和"Without"或类似方法的东西,这些方法可以在不修改原始内容的情况下稍微修改一些东西.

另一种语言的示例是Scala中的地图

Answer 1

有一些基于只读二叉AVL树的不可变字典的实现。

\n\n

/**\n * To modify, use the InsertIntoNew and RemoveFromNew methods\n * which return a new instance with minimal changes (about Log C),\n * so this is an efficient way to make changes without having\n * to copy the entire data structure.\n */\n

\n\n

请看一下方法InsertIntoNew()：

\n\n

/** Return a new tree with the key-value pair inserted\n * If the key is already present, it replaces the value\n * This operation is O(Log N) where N is the number of keys\n */\npublic ImmutableDictionary<K,V> InsertIntoNew(K key, V val)\n{ ... }\n

\n\n

方法RemoveFromNew()：

\n\n

/** Try to remove the key, and return the resulting Dict\n * if the key is not found, old_node is Empty, else old_node is the Dict\n * with matching Key\n */\npublic ImmutableDictionary<K,V> RemoveFromNew(K key, out ImmutableDictionary<K,V> old_node)\n{ ... }\n

\n\n

另外，还有另一种实现：C# 中的 Immutable AVL Tree。它具有相同的 O(log N) 查找和插入时间。

\n\n

其他参考资料

\n\n

\n
• 似乎是一个镜像：brunet/ImmutableDictionary.cs at master \xc2\xb7 johnynek/brunet \xc2\xb7 GitHub。
\n
• 似乎很相似：ImmutableCollections/ImmutableDictionary.cs at master \xc2\xb7 mono/ImmutableCollections \xc2\xb7 GitHub。
\n

\n