c++ - 如何跟踪列表的更改

Question

我有一个不可变的基本项目列表，我想对其执行多种操作:编辑、添加、删除、读取。实际操作将排队并在其他地方执行(发送到服务器，然后将发送一个新列表)，但我想要表示当前操作集应用于基本列表时列表的外观。

我当前的实现保留了一个范围 vector 及其映射到的位置。因此，未经编辑的列表具有从 0 到直接映射到基本列表的长度的一个范围。如果在索引 5 中执行添加，那么我们有 3 个范围:0-4 映射到基本列表 0-4。 5 映射到新项目，6-(length+1) 映射到 5-length。这是有效的，但是随着大量的添加和删除，读取会降级为 O(n)。

我曾考虑过使用散列图，但插入和删除可能发生的范围变化带来了挑战。是否有某种方法可以实现这一点，以便读取仍然在 O(1) 左右？

Answer 1

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

如果您有很多重复读取和少量修改，您可能会通过保留自上次修改以来读取结果的 HashMap 并在修改时清除它来获益。