实现撤消/重做的好集合？

Question

我正在阅读撤消/重做技术，我了解应该如何实现它（我发现它很直观）。

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

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

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

我的最后一个选择是链表的自定义实现，即 SingleLinkedList。 该列表的节点由 Value 属性和 NextNode 指针属性组成，因此我为每个项目使用双倍内存（但仅此而已，除非我使用小于“sizeof(void*)”的东西）。

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

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

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

更新1：

感谢您目前的回答，在我的情况下，我没有记忆问题，嗯，我不知道我的目标是谁，我正在创建一个实用程序并在我自己对“实用程序”的想法，他们应该尽可能浪费最少的CPU/内存（显然不要告诉我“用C++编写它”，因为有很大的区别）。

在我看来，singlelinkedlist效果很好，我不太喜欢限制历史记录，我在考虑Photoshop，其中你的历史记录是“无限的”。

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

然而，正如其他人所说，如果我将链表限制为大尺寸，大约 60000 个命令（我认为它们应该足够了），与 singlelinkedlist 相比，我只会浪费少量内存（4 字节 * 60000）。

也就是说，我想我会使用 LinkedList，但是为了确定，如果我无限制地使用历史记录就可以了吗？

更新2：

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

单个链表（想想它是如何构建的）与堆栈一样快（所有堆栈操作都是 O(1)）并且没有限制。然而，在这种情况下，需要没有限制，否则我们会遇到与堆栈相同的问题，我们没有快速的方法来删除 singlelinkedlist 的最后一个元素（其行为类似于堆栈） ，因为我们不知道最后一个节点的前一个节点元素。

在这种情况下，这很容易，所以，考虑一个 LinkedList，其中有 Previous 指针。 然而，我们为“Stack”的每个元素使用了 2 个额外的指针（这次是通过链表构建的），这就像使用比存储命令所需的内存多 3 倍的内存（使用数组，我们拥有正常的内存）使用情况，singlelinkedlist的内存使用量是2倍，linkedlist的内存使用量是3倍）。

所以我基本上问的是哪个是实现撤消重做模式堆栈的“最佳”集合。

你的回答让我觉得即使我在 1 个程序中创建 60000 个命令，程序中的内存也只有 5MB 左右，这并不算多。

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

Answer 1

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

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);

While undoing

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

While redoing

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

相同可以用链表实现，但管理头尾和维护当前指针变得复杂。

读完你的观点后，我认为你可以使用单链表来实现撤消和重做堆栈，因为你只需要一个方向指针。我只是为您提供了一种不同的方法来了解如何使用堆栈（单链表）来解决此问题，该堆栈使用较少的内存并且不存在与状态相关的问题。

Answer 2

现在使用 LinkedList 或任何标准解决方案，但要小心如何实现它。将所有撤消/重做操作置于精心设计的抽象后面。然后，如果 LinkedList 消耗的额外内存确实被证明是一个问题（不太可能），您可以用自己的实现替换它。

我们一直这样做；将现有功能包装在抽象中，以便我们可以在需要时对其进行修改，因为有时特定于领域的条件可能会提供额外效率的机会。这就是你的情况；链接列表可以工作，但是您的问题域表明效率可能会以实施为代价。

Answer 3

如果您想要一个链接列表，您应该使用LinkedList。为什么要重写已经存在的代码？节省 16MB RAM？

Answer 4

正如我所说和其他人建议的那样，每个节点有 1 个上瘾的指针而不是数组并不是一个大问题，同时我们假设我们的值是另一个指针，如果有 60000 个命令，每个节点有 8 个字节。 480 KB，仔细想想，这个值确实很低。

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

如果有必要限制我们的堆栈大小，则需要一个 LinkedList。

Answer 5

我会给出一个奇怪的答案，只是说“无论你想要什么”，因为这通常不是性能关键的情况，特别是在历史记录有限的情况下，当达到 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%）并且改善局部性 参考。

Answer 6

您可以使用具有旋转起始索引和结束索引值的数组。在同步类方法中抽象元素检索和添加过程，这些方法还维护 startIndex 和 endIndex，此方法只会增加 ao(2) 内存而不是普通数组支持的堆栈。