我需要一个具有尽可能快的功能更新的类似数组的数据结构。我见过一些不同的灵活数组实现，它们为我提供了此属性（Braun，随机访问列表），但我想知道是否有一个实现专门针对我们对追加或前置不感兴趣的情况进行优化- 只是更新。
让·克里斯托夫·菲利亚特 (Jean-Christophe Filliatre)一个非常好的实现持久数组，详见报纸链接在同一页面（这是关于持久联合查找，其中持久数组是核心组件）。代码可以直接获取there.
这个想法是数组的“最后版本”被表示为一个普通的数组，O(1) access and更新操作和以前的版本表示为最后一个版本，加上差异列表。如果您尝试访问该结构的先前版本，该数组将“重新定位”以应用差异列表并再次向您提供有效的表示形式。
当然，这在所有工作流程下都不会是 O(1)（如果你不断地访问和修改结构的不相关版本，你将频繁地付出重新root的成本），但对于主要使用一个版本，偶尔回溯到的常见工作流程来说，旧版本再次成为“最后版本”并获取更新，这是非常有效的。隐藏在观察纯接口下的可变性的一个非常好的使用。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
