c – 具有历史记录的搜索结构(持久性)

前端之家收集整理的这篇文章主要介绍了c – 具有历史记录的搜索结构(持久性)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我需要一个类似于地图的数据结构(在C中)来存储具有以下功能的对(Key,T):

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

我不需要什么

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

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

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

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

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

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

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

谢谢您的帮助!

解决方法

我认为你要找的是一张不变的地图.功能(或功能启发)编程语言(如 HaskellScala)具有您在STL中找到的大多数容器的不可变版本.插入/移除等操作然后返回包含您请求的修改的副本的地图副本(保留原件).在设计数据结构方面已经做了大量工作,以便副本能够指向尽可能多的原始数据结构,以减少每个操作的时间和内存复杂性.

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

原文链接:https://www.f2er.com/c/117899.html

猜你在找的C&C++相关文章