具有数据修改堆栈的缓冲区高效查找

Question

我试图编写一个C++11库，作为实现在原始缓冲区之上实现的一系列更改(修改、插入和删除)的更广泛项目的一部分。然后，目标是能够快速“查看”更改并获取修改后的数据。

我目前的做法是：

• 维护更改的有序列表，按更改开始的偏移进行排序。
• 还可以维护相同更改的堆栈，以便按顺序回滚更改。
• 将新的更改推送到堆栈上，并在正确的位置插入到列表中。
• 如果更改与其他交互，则按偏移量更改列表可能会被修改。
  • 例如，字节5-10的修改会使早期修改从8-12开始无效。
  • 此外，插入或删除更改将改变在它们之后发生的数据的表观偏移量(删除字节5-10意味着以前的字节20现在在15)。

​

• 要查找修改过的数据，您可以查看应用更改的列表(以及所应用的更改中的偏移量--另一项更改可能使其中一些更改无效)，或者如果没有任何更改触及偏移量，则在原始数据中找到正确的偏移量。
  • 这里的目标是快速查找--添加一个更改可能需要一些精力来处理列表，但是在一个有序列表中进行查找(这将大大超过修改的数量)应该是非常简单的。
  • 另外，您也不需要不断地复制数据--每个更改的数据都与其一起保存，原始数据不受影响。

​

• 然后，通过从堆栈中弹出最后一个更改并回滚此更改的添加对其所做的任何更改来实现撤销。

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

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

Answer 1

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

这比试图识别数据的哪些部分更改要容易得多，而且除非操作本身非常耗时(因此很慢地“重放”到原始状态)，否则它工作得很好。

Answer 2

我会研究持久的数据结构，比如structure和http://www.toves.org/books/persist/#s2，或者从这些结构中搜索术语。我想你可以用一棵持久耐用的树来做这件事，因为它的叶子上有短串。