c++ - 应用了数据修改堆栈的缓冲区的高效查找

Question

我正在尝试编写一个 C++11 库作为更广泛项目的一部分，该项目实现了在原始缓冲区之上实现的一堆更改(修改、插入和删除)。然后，目的是能够快速“透视”更改并将修改后的数据取出。

我目前的做法是:

• 维护一个有序的变更列表，按变更开始的偏移量排序
• 同时维护一堆相同的更改，因此它们可以按顺序回滚
• 新的变化被压入栈中并插入到列表的正确位置
• 如果更改与其他人交互，则可以修改偏移量更改列表
  • 例如，对字节 5-10 的修改会使之前从 8-12 开始的修改无效
  • 此外，插入或删除更改会更改在它们之后发生的数据的表观偏移量(删除字节 5-10 意味着以前的字节 20 现在位于 15)
• 要查找修改后的数据，您可以查看列表中适用的更改(以及适用的更改中的偏移量 - 另一个更改可能会使其中的一些无效)，或者在原始数据中找到正确的偏移量，如果没有变化触及那个偏移量
  • 此处的目的是加快查找速度 - 添加更改可能会花费一些精力来弄乱列表，但稍后查找(这将大大超过修改)在有序列表中应该非常简单。
  • 此外，您不需要不断复制数据 - 每次更改的数据都会保留，原始数据不会受到影响
• 然后通过从堆栈中弹出最后一个更改并回滚此更改的添加对其所做的任何更改来实现撤消。

这似乎是一项相当困难的任务 - 有很多事情要处理，我正在快速堆积复杂的代码!

我确信这一定是其他软件中已经处理过的问题，但是环顾各种十六进制编辑器等并没有为我指出有用的实现。是否有这个问题的名称(“数据撤消堆栈”， friend 们还没有让我走得太远!)，或者可以使用的库，甚至作为引用，用于这种事情？

Answer 1

我相信最常见的方法(我过去曾成功使用过的方法)是简单地存储原始状态，然后将每个更改操作(正在完成的操作 + 参数)放在撤消堆栈上。然后，要到达特定的先前状态，您从原始状态开始并应用所有更改，但您想要撤消的更改除外。

这比尝试识别数据的哪些部分发生了变化要容易得多，而且它运作良好，除非操作本身非常耗时(因此“重放”到原始状态的速度很慢)。