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

我不需要什么

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

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

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

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

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

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

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

谢谢您的帮助！