序列化和反序列化

“序列化”到底是什么？

它允许您获取一个或一组对象，将它们存入磁盘或通过有线或无线传输机制发送，然后在稍后，可能在另一台计算机上，反转此过程：复活原始对象。基本机制是将对象扁平化为一维比特流，并将该比特流重新转换为原始对象。

就像《星际迷航》中的传送器一样，它就是将复杂的东西转化为一串扁平的1和0，然后将这串1和0（可能在另一个地方，可能在另一个时间）重构为原始的复杂“东西”。

如何选择最佳的序列化技术？

有非常非常多（和非常多）的如果、和、但是，实际上存在一个具有许多维度的技术连续体。因为我的时间有限（翻译：我做这些没有报酬），我将其简化为在人类可读（“文本”）格式和非人类可读（“二进制”）格式之间做出决定，然后列出五种技术，大致按复杂性递增的顺序排列。

当然，您不限于这五种技术。您最终可能会混合使用多种技术中的思想。当然，您总是可以使用比实际需要更复杂（编号更高）的技术。事实上，如果您认为未来的变化将需要更高的复杂性，那么使用比最低限度需要更复杂的技术可能是明智的。因此，将此列表仅仅视为一个好的起点。

这里有很多内容，请准备好！

1. 在人类可读（“文本”）格式和非人类可读（“二进制”）格式之间做出决定。权衡并非微不足道。后续的常见问题将展示如何在文本格式中写入简单类型以及如何在二进制格式中写入简单类型。
2. 当要序列化的对象不属于继承层次结构（即，当它们都属于同一类）并且不包含指向其他对象的指针时，使用最简单的解决方案。
3. 当要序列化的对象属于继承层次结构，但它们不包含指向其他对象的指针时，使用第二级复杂度的解决方案。
4. 当要序列化的对象包含指向其他对象的指针，但这些指针形成没有循环和没有连接的树时，使用第三级复杂度的解决方案。
5. 当要序列化的对象包含指向其他对象的指针，并且这些指针形成没有循环，并且只有叶子节点处有连接的图时，使用第四级复杂度的解决方案。
6. 当要序列化的对象包含指向其他对象的指针，且这些指针形成的图可能存在循环或连接时，使用最复杂的解决方案。

以下是相同信息，以算法形式排列

1. 第一步是在文本格式和二进制格式之间做出明智的决定。
2. 如果您的对象不属于继承层次结构且不包含指针，请使用解决方案 #1。
3. 否则，如果您的对象不包含指向其他对象的指针，请使用解决方案 #2。
4. 否则，如果您的对象内部的指针图既不包含循环也不包含连接，请使用解决方案 #3。
5. 否则，如果您的对象内部的指针图不包含循环，并且唯一的连接只在终端（叶子）节点处，请使用解决方案 #4。
6. 否则使用解决方案 #5。

请记住：您可以随意混合搭配，添加到上述列表中，并且，如果您可以证明增加的开销是合理的，可以使用比最低要求更复杂的技术。

还有一件事：继承问题和对象内部的指针问题在逻辑上是无关的，所以理论上#2没有理由比#3-5复杂程度低。然而，在实践中，情况往往（并非总是）如此。所以请不要认为这些类别是神圣的——它们有些武断，您应该根据您的情况混合搭配解决方案。序列化这个领域有远比几个问题/答案能涵盖的变体和灰色地带。

如何决定序列化为人类可读（“文本”）格式还是非人类可读（“二进制”）格式？

仔细斟酌。

这个问题没有“正确”答案；它真正取决于您的目标。以下是人类可读（“文本”）格式与非人类可读（“二进制”）格式的一些优缺点对比：

• 文本格式更容易“桌面检查”。这意味着您不必编写额外的工具来调试输入和输出；您可以用文本编辑器打开序列化输出，查看它是否正确。
• 二进制格式通常使用更少的 CPU 周期。然而，这仅在您的应用程序受限于 CPU 且您打算在内部循环/瓶颈处进行序列化和/或反序列化时才相关。请记住：90% 的 CPU 时间花在 10% 的代码上，这意味着除非您的“CPU 仪表”固定在 100%，并且您的序列化和/或反序列化代码消耗了那 100% 的很大一部分，否则不会有任何实际的性能优势。
• 文本格式允许您忽略像 sizeof 和小端与大端这样的编程问题。
• 二进制格式允许您忽略相邻值之间的分隔，因为许多值具有固定长度。
• 当大多数数字较小且需要以文本方式编码二进制结果（例如 uuencode 或 Base64）时，文本格式可以生成更小的结果。
• 当大多数数字较大或不需要以文本方式编码二进制结果时，二进制格式可以生成更小的结果。

您可能还会想到其他要添加的内容……重要的是要记住，一刀切不适合所有情况——在这里做出仔细的决定。

还有一件事：无论您选择哪种格式，您可能都希望在每个文件/流的开头加上一个“魔术”标签和版本号。版本号将指示格式规则。这样，如果您决定对格式进行彻底更改，您仍然有望能够读取旧软件生成的输出。

如何序列化/反序列化数字、字符、字符串等简单类型？

答案取决于您关于人类可读（“文本”）格式与非人类可读（“二进制”）格式的决定

• 以下是如何在人类可读（“文本”）格式中序列化/反序列化简单类型。
• 以下是如何在非人类可读（“二进制”）格式中序列化/反序列化简单类型。

这些常见问题中讨论的基本类型将是本节中大多数其他常见问题所必需的。

如何在人类可读（“文本”）格式中精确读写简单类型？

在阅读此内容之前，请务必评估人类可读格式和非人类可读格式之间的所有权衡。权衡并非微不足道，因此您应该抵制膝跳反射式地采用上次项目中的做法——一刀切不适合所有情况。

在您做出明智的决定使用人类可读（“文本”）格式后，您应该记住以下要点：

• 您可能希望使用 iostream 的 >> 和 << 运算符，而不是它的 read() 和 write() 方法。>> 和 << 运算符更适合文本模式，而 read() 和 write() 更适合二进制模式。
• 存储数字时，您可能希望添加一个分隔符以防止项目混淆。一个简单的方法是在每个数字前总是添加一个空格（' '），这样数字1后面跟着数字2就不会混淆并看起来像12。由于前导空格会自动被>>运算符吸收，因此您不必在读取代码中显式提取前导空格。
• 字符串数据很棘手，因为您必须明确知道字符串主体何时停止。如果某些字符串可能包含'\n'、'"'甚至'\0'这些字符，您就不能明确地用它们来终止所有字符串。您可能希望使用C++源代码转义序列，例如，当您看到换行符时写入'\'后跟'n'等。经过这种转换后，您可以让字符串一直到行尾（意味着它们由'\n'分隔）或者用'"'分隔它们。
• 如果您对字符串数据使用类似于 C++ 的转义序列，请务必在 '\x' 和 '\u' 之后始终使用相同数量的十六进制数字。我通常分别使用 2 和 4 位数字。原因：如果您写入较少的十六进制数字，例如，如果您只是使用 stream << "\\x" << hex << unsigned(theChar)，那么当字符串中的下一个字符恰好是十六进制数字时，您会遇到错误。例如，如果字符串包含 '\xF' 后跟 'A'，您应该写入 "\x0FA"，而不是 "\xFA"。
• 如果您不使用某种转义序列来处理像 '\n' 这样的字符，请小心操作系统不要弄乱您的字符串数据。特别是，如果您在没有 std::ios::binary 的情况下打开 std::fstream，某些操作系统会转换行尾字符。
• 字符串数据的另一种方法是在字符串数据前加上一个整数长度，例如将 "now is the time" 写成 15:now is the time。请注意，这可能会使人们难以读取/写入文件，因为紧随其后的值可能没有可见的分隔符，但您可能仍然觉得它有用。

请记住，这些是您需要在本节中其他常见问题解答中使用的基本操作。

如何在非人类可读（“二进制”）格式中精确读写简单类型？

在阅读此内容之前，请务必评估人类可读格式和非人类可读格式之间的所有权衡。权衡并非微不足道，因此您应该抵制膝跳反射式地采用上次项目中的做法——一刀切不适合所有情况。

在您做出明智的决定使用非人类可读（“二进制”）格式后，您应该记住以下要点：

• 确保您使用 std::ios::binary 打开输入和输出流。即使您在 Unix 系统上，也要这样做，因为这很容易做到，它记录了您的意图，并且减少了一个在将来定位和更改的不可移植性。
• 您可能希望使用 iostream 的 read() 和 write() 方法，而不是它的 >> 和 << 运算符。read() 和 write() 更适合二进制模式；>> 和 << 更适合文本模式。
• 如果二进制数据可能被不同于写入它的计算机读取，请非常小心字节序问题（小端与大端）和 sizeof 问题。处理这个问题的最简单方法是将这两种格式之一指定为官方的“网络”格式，并创建一个包含机器依赖项的头文件（我通常称之为 machine.h）。该头文件应该定义像 readNetworkInt(std::istream& istr) 这样的 inline 函数来读取“网络 int”，并以此类推用于读取和写入所有基本类型。您可以根据需要定义这些格式。例如，您可以将“网络 int”定义为精确的 32 位小端格式。无论如何，machine.h 中的函数将进行任何必要的字节序转换、sizeof 转换等。您最终会在每种机器架构上得到一个不同的 machine.h，或者您的 machine.h 中会包含大量的 #ifdef，但无论哪种方式，所有这些丑陋都将隐藏在一个头文件中，而您的其余代码将保持简洁（更简洁）。注意：浮点差异是最微妙和最难处理的。这可以做到，但您必须小心处理像 NaN、溢出和下溢、尾数或指数中的位数等问题。
• 当空间成本是一个问题时，例如将序列化形式存储在小型内存设备中或通过慢速链路发送时，您可以压缩流和/或进行一些手动技巧。最简单的方法是将小数字存储在更少的字节中。例如，要在一个具有 8 位字节的流中存储一个无符号整数，您可以劫持每个字节的第 8 位来指示是否还有另一个字节。这意味着您每字节获得 7 个有意义的位，因此 0...127 适合 1 个字节，128...16384 适合 2 个字节，等等。如果平均数字小于大约 5 亿，这将比将每个四字节无符号数存储在四个 8 位字节中占用更少的空间。此主题还有许多其他变体，例如，有序数字数组可以存储每个数字之间的差异，以一元格式存储极小值等。
• 字符串数据很棘手，因为您必须明确知道字符串主体何时停止。如果某些字符串可能包含'\0'字符，您就不能明确地用'\0'来终止所有字符串；请记住std::string可以存储'\0'。最简单的解决方案是在字符串数据之前写入整数长度。确保整数长度以“网络格式”写入，以避免sizeof和字节序问题（参见前面要点中的解决方案）。

请记住，这些是您需要在本节中其他常见问题解答中使用的基本操作。

如何序列化不属于继承层次结构且不包含指向其他对象的指针的对象？

这是最不复杂的问题，不出所料，它也是最不复杂的解决方案

• 每个类都应该处理自己的序列化和反序列化。您通常会创建一个成员函数，将对象序列化到某个目标（例如 std::ostream），以及另一个分配 new 对象或可能更改现有对象，根据从某个源（例如 std::istream）读取的内容设置成员数据。
• 如果您的对象物理地包含另一个对象，例如，一个 Car 对象可能有一个 Engine 类型的成员变量，那么外部对象的 serialize() 成员函数应该简单地调用与成员对象相关的适当函数。
• 使用前面描述的原语来读写文本或二进制格式的简单类型。
• 如果类的P数据结构将来可能会改变，该类应该在对象序列化输出的开头写入一个版本号。除非您绝对确定数据结构在未来任何时候都不会改变，否则请现在就包含版本号。从一开始就放入版本号比在数据结构意外改变后才添加要容易得多。版本号仅仅代表序列化格式；它不应该仅仅因为类的行为改变而增加。这意味着版本号不需要花哨——它们通常不需要主版本号和次版本号。

如何序列化属于继承层次结构但不包含指向其他对象的指针的对象？

假设您想序列化一个“形状”对象，其中 Shape 是一个抽象类，派生类有 Rectangle、Ellipse、Line、Text 等。您将在 Shape 类中声明一个纯虚函数 serialize(std::ostream&) const，并确保每个覆盖的第一个动作是写入类的标识。例如，Ellipse::serialize(std::ostream&) const 将写入标识符 Ellipse（可能是一个简单的字符串，但下面讨论了几种替代方案）。

反序列化对象时会变得有点棘手。您通常从基类中的 static 成员函数开始，例如 Shape::unserialize(std::istream& istr)。它被声明为返回 Shape* 或可能是一个智能指针，例如 Shape::Ptr。它读取类名标识符，然后使用某种创建模式来创建对象。例如，您可能有一个从类名映射到该类对象的表，然后使用虚构造函数习语来创建对象。

这是一个具体示例：在基类 Shape 中添加一个纯虚方法 create(std::istream&) const，并定义每个覆盖为一个单行代码，使用 new 分配适当派生类的对象。例如，Ellipse::create(std::istream& istr) const 将是 { return new Ellipse(istr); }。添加一个 static std::map 对象，它将类名映射到相应类的代表（又称原型）对象；例如，"Ellipse" 将映射到 new Ellipse()。函数 Shape::unserialize(std::istream& istr) 将读取类名，如果不在映射中则抛出异常（if (theMap.count(className) == 0) throw ...something...），然后查找相关的 Shape* 并调用其 create() 方法：return theMap[className]->create(istr)。

这个映射通常在静态初始化期间填充。例如，如果文件 Ellipse.cpp 包含派生类 Ellipse 的代码，它也会包含一个 static 对象，该对象的构造函数会将该类添加到映射中：theMap["Ellipse"] = new Ellipse()。

注意事项和警告

• 如果 Shape::unserialize() 将类名传递给 create() 方法，则会增加一点灵活性。特别是，这将允许派生类以两个或更多名称使用，每个名称都有自己的“网络格式”。例如，派生类 Ellipse 可以用于 "Ellipse" 和 "Circle"，这可能有助于节省输出流中的空间或其他原因。
• 在反序列化期间处理错误通常最简单的方法是抛出异常。您也可以返回 NULL，但这需要将读取输入流的代码从派生类的构造函数移到相应的 create() 方法中，最终结果通常是您的代码更复杂。
• 您必须小心，避免在 Shape::unserialize() 使用的映射中出现静态初始化顺序问题。这通常意味着对映射本身使用首次使用时构造习语。
• 对于Shape::unserialize()使用的映射，我个人更喜欢命名构造函数习语，而不是虚构造函数习语——它简化了一些步骤。具体细节：我通常在Shape内部定义一个typedef，例如typedef Shape* (*Factory)(std::istream&)。这意味着Shape::Factory是一个“指向函数的指针，该函数接受一个std::istream&并返回一个Shape*。”然后我将映射定义为std::map。最后，我使用如下行填充该映射：theMap["Ellipse"] = Ellipse::create（其中Ellipse::create(std::istream&)现在是类Ellipse的static成员函数，即命名构造函数习语）。您将函数Shape::unserialize(std::istream& istr)中的return值从theMap[className]->create(istr)更改为theMap[className](istr)。
• 如果您可能需要序列化 NULL 指针，这通常很简单，因为您已经写入了类标识符，因此您可以同样轻松地写入一个伪类标识符，例如 "NULL"。您可能需要在 Shape::unserialize() 中添加一个额外的 if 语句，但如果您选择了上一条中我的偏好，您可以通过定义 static 成员函数 Shape* Shape::nullFactory(istream&) { return NULL; } 来消除这种特殊情况（并通常保持代码简洁）。您可以像添加其他函数一样将该函数添加到映射中：theMap["NULL"] = Shape::nullFactory;。
• 如果您对类名标识符进行标记化，可以使序列化形式更小、更快。例如，只有在第一次看到类名时才写入它，对于后续使用，只写入相应的整数索引。一个像 std::map unique 这样的映射可以轻松实现这一点：如果类名已在映射中，则写入 unique[className]；否则设置变量 unsigned n = unique.size()，写入 n，写入类名，并设置 unique[className] = n。（注意：务必将其复制到单独的变量中。不要写 unique[className] = unique.size()！您已被警告！原因：编译器可能会在 unique.size() 之前评估 unique[className]，如果是这样，unique[className] 将预先增加大小。）反序列化时，使用 std::vector unique，读取数字 n，如果 n == unique.size()，则读取一个名称并将其 add 到 vector 中。无论哪种方式，名称都将是 unique[n]。您还可以使用最常见的 N 个名称预填充这些表中的前 N 个槽，这样流就不需要包含任何这些字符串。

如何序列化包含指向其他对象的指针，但这些指针形成没有循环和没有连接的树的对象？

在我们开始之前，您必须明白“树”这个词不意味着对象存储在某种树状数据结构中，例如 std::set。它只是意味着您的对象彼此指向，“没有循环”部分意味着如果您不断地从一个对象沿着指针指向下一个对象，您永远不会回到更早的对象。您的对象不在“内部”一棵树；它们就是一棵树。如果您不理解这一点，那么您确实应该在继续阅读之前阅读术语常见问题。

其次，如果图将来可能包含循环或连接，请不要使用此技术。

没有循环也没有连接的图非常常见，即使是“递归组合”的设计模式，如组合（Composite）或装饰（Decorator）。例如，表示 XML 文档或 HTML 文档的对象可以表示为没有连接或循环的图。

序列化这些图的关键是忽略节点的身份，而只关注其内容。一个（通常是递归的）算法遍历树，并在遍历过程中写入内容。例如，如果当前节点恰好有一个整数a，一个指针b，一个浮点数c，和另一个指针d，那么您首先写入整数a，然后递归地进入b指向的子节点，然后写入浮点数c，最后递归地进入d指向的子节点。（您不必按照声明顺序写入/读取它们；唯一的基本规则是读取器的顺序与写入器的顺序一致。）

反序列化时，您需要一个接受 std::istream& 的构造函数。上述对象的构造函数将读取一个整数并将其结果存储在 a 中，然后将分配一个对象存储在指针 b 中（并将 std::istream 传递给构造函数，以便它也能读取流的内容），读取一个 float 到 c 中，最后将分配一个对象存储在指针 d 中。请务必在您的对象中使用智能指针，否则如果在读取第一个指向对象以外的任何内容时抛出异常，您将会出现内存泄漏。

在分配这些对象时，使用命名构造函数习语通常很方便。这样做的好处是您可以强制使用智能指针。要在类 Foo 中执行此操作，请编写一个 static 方法，例如 FooPtr Foo::create(std::istream& istr) { return new Foo(istr); }（其中 FooPtr 是指向 Foo 的智能指针）。细心的读者会注意到这与上一篇常见问题中讨论的技术是多么一致——这两种技术是完全兼容的。

如果一个对象可以包含可变数量的子对象，例如，一个 std::vector 指针，那么通常的方法是在递归进入第一个子对象之前写入子对象的数量。反序列化时，只需读取子对象的数量，然后使用循环分配适当数量的子对象。

如果子指针可能是NULL，请务必在写入和读取时都进行处理。如果您的对象使用继承，这应该不是问题；请参阅该解决方案获取详细信息。否则，如果对象中序列化的第一个字符有一个已知范围，则使用该范围之外的字符。例如，如果序列化对象的第一个字符始终是数字，则使用非数字字符（如'N'）表示NULL指针。反序列化可以使用std::istream::peek()来检查'N'标签。如果第一个字符没有已知范围，请强制指定一个；例如，在每个对象之前写入'x'，然后使用其他字符（如'y'）表示NULL。

如果一个对象物理上包含另一个对象，而不是包含指向另一个对象的指针，那么没有任何变化：您仍然递归地深入到子节点，就像它是通过指针一样。

如何序列化包含指向其他对象的指针，但这些指针形成没有循环且只有“平凡”连接的树的对象？

和以前一样，“树”这个词不意味着对象存储在某种树状数据结构中，例如 std::set。它只是意味着您的对象彼此指向，“没有循环”部分意味着您可以从一个对象沿着指针指向下一个对象，并且永远不会回到更早的对象。对象不在“内部”一棵树；它们就是一棵树。如果这说不通，那么您确实应该在继续阅读之前阅读术语常见问题。

如果图包含叶子节点处的连接，但这些连接可以通过简单的查找表轻松重建，则使用此解决方案。例如，像 (3*(a+b) - 1/a) 这样的算术表达式的解析树可能包含连接，因为变量名（如 a）可以出现不止一次。如果您希望图使用完全相同的节点对象来表示该变量的两次出现，那么您可以使用此解决方案。

尽管上述约束与没有连接的解决方案不符，但它们如此接近，以至于您可以将它们压缩到该解决方案中。以下是不同之处：

• 序列化期间，完全忽略连接。
• 在反序列化期间，创建一个查找表，例如 std::map，将变量名映射到相关联的节点。

警告：这假设变量a的所有出现都应该映射到同一个节点对象；如果情况更复杂，也就是说，如果a的一些出现应该映射到一个对象，而另一些应该映射到另一个对象，您可能需要使用更复杂的解决方案。

警告：如果您的对象包含指向某个对象成员而不是对象本身的指针，则需要特别小心。例如，如果指针“p”指向“x.y”，指针“q”指向“x.z”，也就是说，它们指向对象“x”内部的数据成员，而不是对象“x”本身，当您序列化这些指针时，您需要识别两者都指向同一个对象。您需要序列化对象“x”，而不仅仅是“x.y”和“x.z”，并且您需要确保在反序列化时，“p”和“q”再次指向同一个对象。序列化过程可能需要两遍方法，并且序列化后的指针可能需要存储目标对象内的偏移量以及目标对象的ID。

如何序列化包含指向其他对象的指针，且这些指针形成的图可能存在循环或非平凡连接的对象？

警告：“图”这个词不表示对象存储在某种数据结构中。您的对象形成一个图是因为它们彼此指向。它们不是“在”一个图里面；它们就是一个图。如果这说不通，您确实应该在继续阅读之前阅读术语常见问题。

如果图可能包含循环，或者可能包含比处理平凡连接的解决方案允许的更复杂类型的连接时，请使用此解决方案。此解决方案处理两个核心问题：它避免了无限递归，并且它除了写入/读取每个节点的内容外，还写入/读取其身份。

节点的身份通常不必在不同的输出流之间保持一致。例如，如果某个文件使用数字 3 来表示节点 x，则另一个文件可以使用数字 3 来表示不同的节点 y。

有一些巧妙的方法可以序列化图，但最简单的描述是一个两趟算法，它使用一个对象ID映射，例如 std::map oidMap。第一趟填充我们的 oidMap，也就是说，它建立一个从对象指针到表示对象身份的整数的映射。它通过递归遍历图来完成此操作，在每个节点处检查该节点是否已存在于 oidMap 中，如果不存在，则将该节点和一个唯一的整数添加到 oidMap 中，并递归地进入新节点的子节点。唯一的整数通常只是初始的 oidMap.size()，例如 unsigned n = oidMap.size(); oidMap[nodePtr] = n。（是的，我们用两条语句完成了这个操作。您也必须如此。不要将其缩短为一条语句。您已被警告！）

第二遍遍历 oidMap 中的节点，并在每个节点处，写入节点的身份（关联的整数），然后写入其内容。当写入包含指向其他节点的指针的节点内容时，它不深入这些“子”对象，而是简单地写入指向这些节点的指针的身份（关联的整数）。例如，当您的节点包含 Node* child 时，只需写入整数 oidMap[child]。第二遍结束后，oidMap 可以被丢弃。换句话说，从 Node* 到 unsigned 的映射通常不应在任何给定图的序列化结束后继续存在。

也有一些巧妙的方法可以反序列化图，但这里最简单的描述仍然是一个两趟算法。第一趟用正确类的对象填充一个 std::vector v，但这些对象中的任何子指针都为 NULL。这意味着 v[3] 将指向 ID 为 3 的对象，但该对象内部的任何子指针都将为 NULL。第二趟填充对象内部的子指针，例如，如果 v[3] 有一个名为 child 的子指针，它应该指向 ID 为 5 的对象，第二趟将 v[3].child 从 NULL 更改为 v[5]（显然封装可能会阻止它直接访问 v[3].child，但最终 v[3].child 会更改为 v[5]）。反序列化给定流后，vector v 通常可以被丢弃。换句话说，在序列化或反序列化不同的流时，对象 ID（3、5 等）没有任何意义——这些数字只在给定流内部有意义。

注意：如果您的对象包含多态指针，即可能指向派生类对象的基类指针，那么请使用前面描述的技术。您还需要阅读一些早期处理 NULL、写入版本号等的技术。

注意：您应该认真考虑在递归遍历图时使用访问者模式，因为序列化可能只是进行该递归遍历的众多原因之一，并且它们都需要避免无限递归。

序列化/反序列化对象时有什么注意事项吗？

除了特殊情况，您不想做的事情之一是在遍历过程中对节点数据进行任何更改。例如，有些人觉得他们可以通过简单地将整数作为数据成员添加到 Node 类中来将 Node* 映射到整数。他们有时还会在 Node 对象中添加一个 bool haveVisited 标志作为另一个数据成员。

但是，这会导致许多多线程和/或性能问题。您的 serialize() 方法将不再是 const，因此即使它逻辑上只是节点数据的读取器，并且即使逻辑上允许多个线程同时读取节点，实际算法也会写入节点。如果您完全理解线程和读/写冲突，您最好的希望是使您的代码更复杂、更慢（每当任何线程在图上做任何事情时，您都必须阻塞所有读线程）。如果您（或您之后将维护代码的人！）不完全理解读/写冲突，这种技术会创建非常严重且非常微妙的错误。读/写和写/写冲突是如此微妙，它们经常在测试阶段溜入实际应用中。坏消息。相信我。如果您不相信我，请与您信任的人交谈。但不要偷工减料。

我还可以说很多，比如一些简化和特殊情况，但我已经在这上面花了太多时间。如果您想要更多信息，请花点钱。

关于图、树、节点、循环、连接以及叶子节点与内部节点的连接，这些都是什么意思？

当您的对象包含指向其他对象的指针时，您最终会得到计算机科学家所称的图。并非您的对象存储在树状数据结构中；它们就是一个树状结构。

您的对象对应于图的节点或顶点，而您对象内部的指针对应于图的边。这个图是一种特殊的变体，称为有根、有向图。要序列化的根对象对应于图的根节点，而指针对应于有向边。

如果对象x有一个指向对象y的指针，我们说x是y的父对象和/或y是x的子对象。

图中的一条路径对应于从一个对象开始，沿着指针指向另一个对象，以此类推，直到任意深度。如果从 x 到 z 有一条路径，我们说 x 是 z 的祖先和/或 z 是 x 的后代。

图中的连接（join）意味着有两条或更多条不同的路径通向同一个对象。例如，如果 z 既是 x 的子节点又是 y 的子节点，那么该图就有一个连接，而 z 是一个连接节点。

图中的一个循环意味着存在从一个对象返回到自身的路径：如果x有一个指向自身的指针，或者指向y（y指向x），或者指向y（y指向z，z指向x）等等。如果一个图包含一个或多个循环，则称其为循环图；否则为无环图。

内部节点是指有子节点的节点。叶子节点是指没有子节点的节点。

在本节中，“树”一词指的是有根、有向、无环图。请注意，树中的每个节点也是一棵树。