c – 如何跟踪列表的更改

发布时间：2020-12-16 06:50:03 所属栏目：百科来源：网络整理

导读：我有一个不可变的项目列表,我想对其执行许多操作：编辑,添加,删除,读取.实际操作将排队并在其他地方执行(发送到服务器并将向下发送新列表),但我希望表示列表在应用于基本列表的当前操作集时的样子. 我当前的实现保留了范围向量和它们映射到的位置.因此,未编

我有一个不可变的项目列表,我想对其执行许多操作：编辑,添加,删除,读取.实际操作将排队并在其他地方执行(发送到服务器并将向下发送新列表),但我希望表示列表在应用于基本列表的当前操作集时的样子.

我当前的实现保留了范围向量和它们映射到的位置.因此,未编辑的列表具有从0到长度的一个范围,该范围直接映射到基本列表.如果在索引5中执行添加,则我们有3个范围：0-4映射到基本列表0-4. 5映射到新项目,6-(长度1)映射到5长度.这有效,但是有很多添加和删除,读取会降级为O(n).

我曾想过使用散列图,但插入和删除时可能出现的范围变化带来了挑战.有没有办法实现这一点,以便读取仍然是O(1)？

如果你有一个大致平衡的范围树,每个节点都保留了树中它下面元素总数的记录,你可以在最坏的情况下回答树的深度,这应该是关于log(n) .也许 https://en.wikipedia.org/wiki/Treap将是为此实现的更容易平衡的树之一.

如果您有大量重复读取和少量修改,您可以通过保留自上次修改后读取结果的散列图,并在修改时清除它来获得.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!