搜索结构与历史(持久性)

Question

我需要一个类似于地图的数据结构(在C++中),用于存储具有以下功能的对(Key,T):

• 您可以将新元素(Key,T)插入当前结构中
• 您可以根据当前结构中的Key搜索元素
• 您可以创建当前版本结构的"快照"
• 您可以切换到您拍摄快照的结构版本之一,并从那里继续所有操作
• 完全删除其中一个版本

我不需要什么

• 元素从结构中移除
• 将不同版本的结构合并为一个
• 迭代当前存储在结构中的所有(或部分)元素

换句话说,您可以构建一些搜索结构,但在任何时候您都可以跳过历史记录,并以不同的方式扩展结构的早期/不同版本.稍后您可以在这些不同版本之间跳转.

在我的项目中,Key和T可能是整数或指针值,但不是字符串.

主要目标是减少时间复杂性; 空间消耗是次要的(但也应该是合理的).为了澄清,对我来说log(N)+ log(S)(其中N个元素数量,S个快照数量)就够了,虽然速度更快更好:)

我有一些粗略的想法如何实现它 - 例如:作为二元搜索树的结构,插入新元素可以克隆从根到插入位置的路径,同时保持树的其余部分完好无损.切换树版本等同于选择不同版本的根节点,对于这些版本,某些更改根本不可见.

但是,为了使这种自定义树有效(例如自平衡),需要一些额外的努力和仔细的编码.当然我可以自己做,但也许现有的图书馆可以做到这一点？

此外,我可能根本不知道这种数据结构的正确名称,使我的Google搜索(或SO搜索)完全失败......

谢谢您的帮助!

Answer 1

我认为您正在寻找的是一个不可变的地图。函数式（或受函数式启发）编程语言（例如 Haskell 或 Scala）具有 STL 中大多数容器的不可变版本。然后，插入/删除等操作将返回地图的副本（保留原始版本），该副本包含您请求的修改。我们在设计数据结构方面做了很多工作，以便副本能够指向尽可能多的原始数据结构，以减少每个操作的时间和内存复杂性。

您可以在一本书中找到更多详细信息，例如这本书：http://www.amazon.co.uk/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504。