实现撤销/重做的好方案集合？

Question

我在寻找撤销/重做技术方面的技巧，我理解它应该如何实现（我觉得很直观）。

然而，我正在考虑应该用作历史记录的集合，

许多人使用堆栈，但是C#堆栈是作为数组实现的，这是一个问题： 如果我使用“有限”的历史记录（例如，对于2000个命令），当达到限制时，我没有办法从堆栈的末尾删除项目，如果我找到一种方法来做到这一点，我必须移动数组的所有元素（每次执行命令都要这样做）。

LinkedList看起来不错，但浪费了很多内存。

我的最后选择是自定义SingleLinkedList的实现。 此列表的节点包括Value属性和NextNode指针属性，因此对于每个项目，我使用了双倍的内存（但除了使用小于“sizeof(void*)”的内容之外，没有更多）。

我还在集合中存储对第一个元素和最后一个元素的指针。

我可以轻松地将命令添加到历史记录中，并以这种方式将它们移动到redohistory中，但是我无法创建“有限”的历史记录，因为不允许RemoveLast（我必须遍历整个集合以删除最后一个项目）。

所以我的问题是： 我应该使用LinkedList还是我的自定义SingleLinkedList？

更新1：

谢谢目前的答案，在我的情况下，我没有内存问题，好吧，我不知道我在针对谁，我正在创建一个实用程序，并且在我的“实用程序”概念中，它们应该尽可能地浪费最少的cpu /内存（显然不要告诉我“写成c ++”，因为有很大的区别）。

在我看来，单链表效果很好，我真的不喜欢限制历史记录，我在考虑Photoshop，您的历史记录是“无限制”的。

我只担心当撤消历史记录变得非常大时会发生什么，例如使用8小时。 这就是为什么我考虑通过LinkedList限制它的原因。

正如其他人所述，如果我将LinkedList限制在一个大型大小左右，约为60000个命令（我认为它们应该足够），那么与singlelinkedlist相比，我只浪费了很少的内存（4字节* 60000）。

话虽如此，我想我会使用LinkedList，但是为了确保，如果我使用无限制的历史记录，那也可以吗？

更新2：

@ Akash Kava 好吧，你说的很重要，但你误解了我为什么想使用LinkedList以及为什么不想使用堆栈。堆栈的主要问题是必须限制其大小，并且在达到此限制时没有快速删除旧命令的方法（它是一个数组，每次将其维度加倍并不是我们想要的）。

一个单向链表（考虑如何构建）像栈一样快（所有栈操作都是O(1)），而且没有限制。然而在这种情况下，需要不设限制，否则我们会有和栈相同的问题，我们没有快速地删除我们单向链表的最后一个元素（它行为像一个栈），因为我们不知道最后一个节点的前一个节点元素。

在这种情况下，思考具有Previous指针的LinkedList就很容易了。

然而，对于我们“堆栈”（这次是通过链表构建的）的每个元素，我们使用2个额外的指针，这就像使用比存储Command所需内存多3倍的内存（使用数组我们可以获得普通的内存使用，单向链表的内存使用量是2倍，而LinkedList的内存使用量是3倍）。

所以，我基本上询问的是，实现撤销-重做模式的“最佳”集合是什么。

你的答案让我想到，即使我在一个程序中创建了60000个命令，它也只占用程序中约5MB的内存，这并不算太多。

基本上，如果你想限制你的撤消/重做历史记录，你需要使用LinkedList，否则SingleLinkedList更好。

- Francesco Belladonna

---

不是确切的答案，但你是否看过Undo Framework实现：http://undo.codeplex.com/？ - Nick Martyshchenko

请看一下备忘录设计模式。- http://www.codeproject.com/KB/cs/generic_undo_redo.aspx - Mr Shoubs

Answer 1

链表是第一次尝试，但启用/禁用按钮和维护状态会变得有点复杂，所以我找到了更好的方法。

Stack<Action> undoStack;
Stack<Action> redoStack;

撤销/重做的条件很简单

undoStack.Count > 0 (We can undo)
redoStack.Count > 0 (We can redo)

在修改过程中，我们必须清除redoStack，因为在活动文档中修改任何内容时，您可以在VS中清晰地注意到这一点，当您编辑任何内容时，重做将被禁用。

redoStack.Clear() <-- important step
undoStack.Push(action);

撤销操作时

Action action = undoStack.Pop();
redoStack.Push(action); <-- necessary...

重新做的同时，我们需要考虑以下几点：

Action action = redoStack.Pop();
undoStack.Push(action);

使用链表也可以实现相同的功能，但是管理头和尾以及维护当前指针会变得复杂。

阅读您的观点后，我认为您可以使用单向链表来实现撤销和重做栈，因为您只需要一个方向的指针。我只是给出了一种不同的解决方法，使用堆栈（单向链表）来减少内存使用并且没有状态相关问题。

- Akash Kava

---

我在问题中回答了你（我写了一个长回答）。 - Francesco Belladonna

我知道这个，但是Stack可以通过链表实现，或者你可以考虑使用两个链表，一个用于撤销，一个用于重做。我最近刚刚实现了它，并发现保留一个历史记录存储（链表）会导致一些状态管理问题，所以我将它们分成了两个堆栈或两个链表。由于您永远不需要下一个节点作为其他重做堆栈的一部分，因此可以使用单链表实现堆栈。 - Akash Kava

事实上，我把所有东西都当作堆栈使用，我只是在思考哪种集合更适合用作堆栈，我仍然认为如果你想要无限的撤消/重做堆栈，那么单向链表是最好的选择。 - Francesco Belladonna

Answer 2

现在可以使用LinkedList或任何标准解决方案，但是要注意如何实现它。将所有的撤销/重做操作放在一个良好设计的抽象层后面。然后，如果LinkedList消耗的额外内存真的成为了问题（不太可能），您可以用自己的实现来替换它。

我们经常这样做；将现有功能封装在一个抽象层中，以便我们可以在需要时进行调整，因为有时特定于领域的条件可能会提供额外的效率机会。这就是你在这里的情况；链表将起作用，但是您的问题领域表明，在实现的成本方面可能存在效率问题。

- user236520

---

链表是数据修改控件的首选。因为当您必须提交更改（这些更改不立即应用于数据源）到数据源时，您将不得不将栈转换为队列，以便将所有更改合并到实际数据源中。 - Crypt32

Answer 3

如果你需要一个链表，应该使用LinkedList。为什么要重写已经存在的代码呢？只为了节省16MB的内存吗？

- configurator

Answer 4

我会给出一个奇怪的答案，就是“随便你”，因为这通常不是性能关键的情况，特别是当历史记录仅在达到2000个可撤销操作时开始弹出最旧的条目。

双向链表很好用。双端队列也很好用。像 ArrayList 这样的连续结构，如果每个操作只是存储其中的对象引用，并且需要在线性时间内从前面删除，那么仍然可以正常工作。如果您对可以记录的撤消操作数量有固定限制（在这种情况下，您可以提前调整圆形数组的大小，并在超过一定容量时自动开始覆盖最旧的条目），则循环数组也可以很好地工作。

由于您所做的唯一事情就是一次将整个用户操作推回去，一次将整个撤消操作弹回去，以及如果用户记录操作并且历史记录开始变满或使用太多内存，则可能从前面弹出一个元素。这根本不是性能关键。除非您有一个非常不寻常的情况，即用户每秒可以记录像一万个操作（看到有人点击得如此之快，真的会很惊讶），否则不会发生太多事情，因为它非常受用户输入的限制。

当然，你存储在单个撤销操作中的内容可能非常关键，因此你可能需要一种非常高效的数据表示方法来最小化内存使用（这取决于你在可撤销条目中存储了多少状态）。但外部撤销堆栈/历史记录并不是非常关键，我认为在这种情况下几乎所有选项都是合理的。这是来自一个喜欢减少内存使用以提高性能的人的建议，但在这种情况下，你的撤销堆栈内存是“冷”的。它们中的许多并不经常被访问（例如：不是每帧都访问）- 只有当用户点击撤销按钮或记录新操作时才会访问，除非你的目标硬件非常有限。

但如果你想要压缩内容，虽然我认为这并不是必要的，但是未展开的链表可以很好地工作。它基本上是一个链表，其中每个节点存储多个元素。在这种情况下，链接的内存使用是微不足道的。你可以这样做：

struct Node
{
     Command commands[n];
     Node next;
     Node prev;
     int first;
     int last;
}

当你撤销时，可以减少尾节点的last计数器。如果last == first，则弹出并释放它，并将上一个节点作为新的尾节点。当你记录一个操作时，可以增加last计数器。如果last == n，则分配一个新节点并将其设置为新的尾节点。当你想要开始减小历史记录的大小（即从前面删除撤销条目）时，请增加头节点的first计数器。如果first == last，则释放节点并将下一个节点设置为新的头。这样可以使每次撤销使用的内存非常小（仅需要在每个n撤销条目中存储一次节点数据，而且可以将n设为一个大的数字，如512，将链表开销降低到1/512或~1.95%），从而实现常数时间的后推、后弹和前弹，并提高引用局部性。

- user4842163

Answer 5

正如我所说，也有人建议，每个节点使用1个额外指针而不是数组并不是一个大问题。此外，让我们假设我们的值是另一个指针，在60000个命令的情况下，每个节点有8个字节。480 KB，如果我们考虑到这一点，这是一个非常低的值。

话虽如此，在这种情况下，我认为最好的集合是SingleLinkedList，它允许我们无限制地撤消/重做“堆栈”（围绕SingleLinkedList构建）。

如果必须限制我们的堆栈大小，则需要使用LinkedList。

- Francesco Belladonna

Answer 6

你可以使用一个带有旋转起始索引和结束索引值的数组。在同步类方法中抽象出元素检索和添加过程，这些方法还维护startIndex和endIndex。相比于普通的数组支持的堆栈，这种方法只会增加o(2)的内存消耗。

- arvind