搜索结构与历史（持久性）
我需要一个类似地图的数据结构（在C ++中）用于存储具有以下功能的对（Key，T）：
我不需要的
换句话说，你有一些你可以建立的搜索结构，但是在任何时候你都可以跳过历史，并以不同的方式展开早期/不同版本的结构。 稍后，您可能会在这些不同版本之间跳转。
在我的项目中，Key和T可能是整数或指针值，但不是字符串。
主要目标是减少时间复杂性; 空间消费是次要的（但也应该是合理的）。 为了说明一下，对我来说，log（N）+ log（S）（其中N个元素的数量，S个快照数量）就足够了，尽管更快更好:)
我有一些大概的想法 - 例如：作为二叉搜索树的结构，插入新元素可以克隆从根到插入位置的路径，同时保持树的其余部分不变。 切换树版本将等同于选取不同版本的根节点，对此，某些更改根本不可见。
然而，为了使这个自定义树有效（例如自平衡），它将需要一些额外的努力和仔细的编码。 当然，我可以自己做，但也许已经有现成的图书馆来做到这一点？
另外，这种数据结构可能有一个我根本不知道的名称，这使得我的Google搜索（或SO搜索）失败了......
感谢您的帮助！
我认为你正在寻找的是一张不可改变的地图。 函数式（或功能上的启发式）编程语言（如Haskell或Scala）具有您在STL中找到的大多数容器的不可变版本。 诸如插入/移除等操作然后将包含您所请求的修改的副本返回到地图的副本（保留原件）。 在设计数据结构方面做了大量工作，以便副本能够指向尽可能多的原始数据结构，以减少每个操作的时间和内存复杂性。
你可以在这本书中找到更多的细节：http://www.amazon.co.uk/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504。
在搜索一些持久搜索树库时，我偶然发现了这一点：
http://cg.scs.carleton.ca/~dana/pbst/
虽然它不具备所需的完全相同的功能，但它似乎非常接近它。 我会调查。
（在这里张贴，因为有人可能会发现它也很有用） 链接地址: http://www.djcxy.com/p/60763.html