c++ - C++ - 具有结构共享/不变性的类似地图的数据结构

Question

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

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

Answer 1

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

Answer 2

您可以使用普通地图，但用时间戳或“地图版本号”标记每个元素。如果您也想删除元素，请使用两个标记。如果您可能重新插入已删除的元素，那么您需要一个值列表和每个元素的标记对。

例如，您搜索键“foo”，您发现它在版本 0 到 3（包括）中具有值 5，然后它被“删除”，然后在版本 9 到当前中它具有值 -8 .

不过，这会占用大量内存和时间。