C++ - 具有结构共享/不变性的类 map 数据结构

Question

函数式编程语言通常处理不可变数据结构，但通过结构共享保持高效。例如。你在一些信息 map 上工作，如果你插入一个元素，你不会修改现有的 map ，而是创建一个新的更新版本。为避免大量复制和内存使用， map 将(尽可能好地)在两个实例之间共享未更改的数据。

如果存在一些模板库为 C++ 提供类似数据结构的映射，我会很感兴趣。我搜索了一下，除了 LLVM 中的内部类之外什么也没找到。

Answer 1

A Copy On Write b+tree 听起来像您要找的东西。它基本上每次被修改时都会创建一个新的自身快照，但它会在版本之间共享未修改的叶节点。我见过的大多数实现都倾向于烘焙成仅附加数据库日志文件。 CouchDB 对它们有很好的描述。然而，就 map 数据结构而言，它们“相对容易”实现。