函数式编程语言通常处理不可变的数据结构，但通过结构共享保持高效。例如，你在处理一些信息地图，如果你插入一个元素，你不会修改现有的地图，而是创建一个新的更新版本。为了避免大规模复制和内存使用，映射将在两个实例之间共享（尽可能好）未更改的数据。
如果有一些模板库为C++提供类似地图的数据结构，我会很感兴趣。我搜索了一下，除了LLVM中的内部类之外，什么也没找到。
写时复制b+树听起来像您想要的。它基本上每次被修改时都会创建一个自己的新快照，但它在不同版本之间共享未修改的叶节点。我看到的大多数实现都倾向于烘焙到只附加数据库日志文件中。CouchDB有一篇非常好的文章。然而，就地图数据结构而言，它们"相对容易"实现。
您可以使用普通的映射，但用时间戳或"映射版本号"标记每个元素。如果也要删除元素，请使用两个标记。如果可能重新插入已删除的元素，则需要每个元素的值和标记对列表。
例如，您搜索关键字"foo"，发现它在版本0到3（包括在内）中的值为5，然后它被"删除"，然后在版本9到current中它的值为-8。
不过，这消耗了大量的记忆和时间。