C++ 中的备忘录模式

引言

Memento 模式 是一种行为设计模式，用于捕获和外部化对象的内部状态，以便在不违反封装的情况下稍后将对象恢复到该状态。当您需要在应用程序中实现撤销机制、检查点或历史记录管理时，此模式特别有用。

方法 1：基本方法

程序

输出

 
Text after undo: Hello, World!   

说明

• TextMemento 类
  此类在 Memento 模式中表示 memento。它保存了 TextEditor 对象在某个时间点的状态。在此示例中，它仅存储一个表示文本内容的字符串。
• TextEditor 类 (Originator)
  此类在 Memento 模式中表示 originator。它是需要保存和恢复状态的对象。在此示例中，TextEditor 具有一个名为 text 的成员变量，表示文本内容。它提供了设置和获取文本内容的方法，以及创建和恢复 memento 的方法。
• UndoManager 类 (Caretaker)
  此类负责管理 memento。它保存了 TextMemento 对象的集合。它提供了添加 memento 和根据索引检索 memento 的方法。
• 主函数
  创建了 TextEditor 和 UndoManager 的实例。
  TextEditor 的文本内容设置为“Hello, World!”。
  使用 TextEditor 的 createMemento() 方法创建一个表示 TextEditor 当前状态的 memento。然后将此 memento 添加到 UndoManager 中。
  TextEditor 的文本内容更改为“Goodbye, World!”。
  最后，通过使用 getMemento() 方法从 UndoManager 中检索 memento，并将其传递给 TextEditor 的 restoreMemento() 方法来恢复 TextEditor 的先前状态。然后打印 TextEditor 的文本内容，显示状态已成功恢复。

复杂度分析

时间复杂度

创建 memento（TextMemento 对象）涉及复制 TextEditor 的文本内容，其时间复杂度为 O(n)，其中 n 是文本的长度。

将 memento 添加到 UndoManager 涉及将元素附加到 vector，平均时间复杂度为 O(1)。

通过索引从 UndoManager 检索 memento 的时间复杂度也为 O(1)。

恢复 memento 涉及将文本内容从 memento 复制回 TextEditor，其时间复杂度为 O(n)。

空间复杂度

创建 memento（TextMemento 对象）的空间复杂度为 O(n)，其中 n 是要存储的文本的长度。

UndoManager 中存储 memento 的空间复杂度取决于存储的 memento 数量。如果存在 m 个 memento，则空间复杂度为 O(m * n)，其中 n 是每个 memento 中文本的平均长度。

总体而言，实现的总体空间复杂度由 UndoManager 中存储 memento 所需的空间决定。

方法 2：使用序列化/反序列化

引言

而不是创建单独的 TextMemento 类来保存 TextEditor 的状态，您可以直接将 TextEditor 对象的状态序列化为字符串或二进制格式。序列化是将对象转换为字节流的过程，而反序列化是相反的过程。

为了创建 memento，将 TextEditor 对象的状态序列化为字符串或二进制格式并进行存储。

为了恢复状态，将序列化的状态反序列化回 TextEditor 对象。

程序

输出

 
Text after undo: Hello, World!   

说明

• TextEditor 类 (Originator)
  TextEditor 类代表 Memento 模式中的 originator。
  它有一个私有的成员变量 text，用于存储文本内容。
  setText() 方法允许设置文本内容，getText() 方法检索当前文本内容。
  而不是创建单独的 memento 类，createMemento() 方法直接将状态（文本内容）序列化为字符串并返回。
  restoreMemento() 方法接受序列化的状态（字符串）作为参数，并将其反序列化回 TextEditor 的文本内容。
• 主函数
  创建了 TextEditor 的实例。
  使用 setText() 方法将 TextEditor 的文本内容设置为“Hello, World!”。
  调用 TextEditor 的 createMemento() 方法来保存当前状态。序列化的状态存储在名为 memento 的字符串变量中。
  使用 setText() 方法将 TextEditor 的文本内容更改为“Goodbye, World!”。
  使用序列化的状态（memento）作为参数调用 TextEditor 的 restoreMemento() 方法来恢复先前状态。
  最后，打印撤销后 TextEditor 的文本内容。

复杂度分析

时间复杂度

将 TextEditor 对象的状态序列化为字符串涉及复制文本内容，其时间复杂度为 O(n)，其中 n 是文本的长度。

将序列化的状态反序列化回 TextEditor 对象也涉及复制文本内容，时间复杂度为 O(n)。

设置和获取 TextEditor 对象文本内容是直接操作，时间复杂度为 O(1)。

总体而言，此方法中操作的时间复杂度主要取决于文本内容的长度。

空间复杂度

将 TextEditor 对象的状态序列化为字符串的空间复杂度为 O(n)，其中 n 是要存储的文本内容的长度。

同样，将序列化的状态反序列化回 TextEditor 对象所需空间复杂度也为 O(n)。

将序列化的状态（memento）存储在字符串变量中的空间复杂度为 O(n)，其中 n 是序列化状态的长度。

TextEditor 对象本身和其他变量的空间复杂度与序列化状态相比可以忽略不计。

总体而言，此方法总体空间复杂度由存储序列化状态所需的空间决定。

方法 3：使用 Command 模式和 Undo Stack

引言

而不是直接保存和恢复 TextEditor 的状态，您可以使用 Command 模式和 undo stack。

每个用户操作（如键入、删除或替换文本）都封装在一个命令对象中。每个命令对象都知道如何执行操作以及如何撤销它。

当用户执行操作时，将创建一个相应的命令对象并执行它。命令对象在执行前的状态可以作为 memento 暗示。

已执行的命令对象存储在 undo stack 中。要撤销操作，将命令对象从 undo stack 中弹出，并调用它们的 undo 方法。

程序

输出

 
Text after undo: Goodbye, World!   

说明

• Command 接口
  Command 接口定义了两个纯虚函数：execute() 和 undo()。此接口表示一个可以执行和撤销的命令。
• 具体命令：SetTextCommand
  SetTextCommand 是 Command 接口的具体实现。
  它封装了在 TextEditor 中设置文本的操作。
  它存储旧文本内容和新文本内容。
  execute() 方法将 TextEditor 的文本内容设置为新文本。
  undo() 方法交换旧文本和新文本内容，从而有效地撤销操作。
• TextEditor 类 (Originator)
  TextEditor 类代表 Memento 模式中的 originator。
  它有一个私有的成员变量 text，用于存储文本内容。
  它维护一个命令堆栈（undoStack），表示已执行的操作。
  setText() 方法创建一个带有旧文本和新文本的 SetTextCommand 对象，执行该命令，并将其推送到 undoStack。
  undo() 方法从 undoStack 中弹出顶部的命令，并调用其 undo() 方法来恢复操作。
• 主函数
  创建了 TextEditor 的实例。
  调用 setText() 方法将文本内容设置为“Hello, World!”。
  再次调用 setText() 将文本内容更改为“Goodbye, World!”。
  调用 undo() 方法来撤销最后一个操作。
  最后，打印撤销后 TextEditor 的文本内容。

复杂度分析

时间复杂度

使用 setText() 方法设置文本涉及创建 SetTextCommand 对象、执行命令（设置文本内容）并将命令推送到 undo stack。这些操作的时间复杂度为 O(1)。

使用 undo() 方法撤销操作涉及从 undo stack 中弹出顶部的命令并调用其 undo() 方法。这两个操作的时间复杂度都为 O(1)。

总体而言，设置文本和撤销操作的时间复杂度是恒定的，与文本内容的长度无关。

空间复杂度

TextEditor 类本身的空间复杂度是恒定的，因为它只存储用于文本内容的字符串和用于撤销命令的堆栈。

undo stack 中存储的每个命令对象都会消耗额外的内存。但是，由于只存储已执行的命令，undo stack 的空间复杂度取决于已执行命令的数量，而不是文本内容的长度。

因此，undo stack 的空间复杂度为 O(k)，其中 k 是已执行命令的数量。

总体而言，此实现的空间复杂度主要由 undo stack 中存储的已执行命令的数量决定。

C++ 中 Memento 模式的属性

Originator

• Originator 是需要保存和恢复状态的对象。它包含需要保留的状态。
• 在 C++ 中，Originator 类通常提供设置和获取其内部状态的方法，以及创建和恢复 memento 的方法。
• 它负责创建捕获其内部状态的 memento，并负责从 memento 恢复其状态。

Memento

• Memento 是保存 Originator 状态的对象。它充当 Originator 在特定时间点的状态快照。
• 在 C++ 中，Memento 类通常提供访问甚至修改其所保存状态的方法，但它不暴露状态的内部表示。
• 它被设计为不可变的，或者防止其状态在创建后被修改，从而确保 Originator 的状态保持不变。

Caretaker

• Caretaker 负责管理 memento。它跟踪 memento 并提供保存和检索它们的操作。
• 在 C++ 中，Caretaker 类可以维护一个 memento 的集合（例如，堆栈或列表），并提供添加、检索以及可能的删除 memento 的方法。
• 它负责决定何时创建 memento 以及何时从 memento 恢复 Originator 的状态。