如何使用STL容器将C++类实例加载/保存到磁盘中

Question

我有一个代表层次化组织数据树的C++类，它非常大（~Gb，基本上尽可能使用内存）。它使用STL列表在每个节点处存储信息以及指向其他节点的迭代器。每个节点仅有一个父节点，但是0-10个子节点。

抽象来看，它类似于：

struct node {
public:
    node_list_iterator parent;              // iterator to a single parent node
    double node_data_array[X];
    map<int,node_list_iterator> children;   // iterators to child nodes
};

class strategy {
private:
    list<node> tree;        // hierarchically linked list of nodes
    struct some_other_data;
public:
    void build();           // build the tree
    void save();            // save the tree from disk
    void load();            // load the tree from disk
    void use();             // use the tree
};

我希望实现对磁盘的load()和save()，并且应该相当快，然而明显存在以下问题：

1. 我事先不知道大小；

2. 数据包含迭代器，这些迭代器是易变的；

3. 我对C++的无知是巨大的。

请问有人能提供一个纯C++的解决方案吗？

- ati

---

你需要多具备未来的可持续性？几年后你还会查看这些数据吗？其他人呢？他们也需要查看吗？这个结构有多容易修改？如果只是一次性工作，那就不同于可维护的数据结构（例如，一个单词文件或其他东西，被许多人在程序的许多版本中使用）。 - mmr

@ "std::list? 呸！:) - Billy ONeal" -- 为什么？ @mmr - 这是一个一次性项目，数据是即时生成的。 - ati

如果您不担心未来的兼容性，那么这些解决方案都可以使用。但是如果您担心未来的兼容性，就必须考虑程序的可扩展性以及需求如何变化。 - mmr

Answer 1

看起来你可以用以下语法保存数据：

File = Meta-data Node
Node = Node-data ChildCount NodeList
NodeList = sequence (int, Node)

也就是说，当序列化根节点时，它包含所有节点，直接（子节点）或间接（其他后代）。编写格式相当简单：只需从根节点开始递归编写函数。

阅读并不那么困难。std::list<node> 迭代器是稳定的。一旦插入根节点，其迭代器将不会改变，即使在插入其子节点时也是如此。因此，当你读取每个节点时，可以已经设置父级迭代器。当然，这还留下了子级迭代器，但那些很简单：每个节点都是其父节点的子代。因此，在读取完所有节点后，您将修复子迭代器。从第二个节点（第一个节点是根节点）开始迭代到最后一个子节点。然后，对于每个子项 C，请获取其父项和其父项集合中的子项。现在，这意味着在读取时必须将 int 子 ID 放置在与 std::list<node> 平行的简单 std::vector 中。一旦在各自的父级中修补了所有子级 ID，您就可以丢弃该向量。

- MSalters

---

不需要显式地指定。您可以从文件中的位置推导出来：跟随其父节点。当您从根节点开始编写时，这很容易实现。而在阅读时，通过反转所有父关系，您可以恢复子关系。 - MSalters

Answer 2

你可以使用boost.serialization库。这将保存容器的整个状态，甚至包括迭代器。

- user283145

---

我认为boost::serialization并没有什么帮助，因为列表的成员包含指向列表内部的迭代器。这会导致大量递归问题 :) - Billy ONeal

只要实现了适当的序列化程序，这就不是问题。 - user283145

boost::serialization 的根本问题在于迭代器。对于 OP 来说，其余部分已经完成了，但是库中没有迭代器的序列化支持，因此必须自定义滚动。在 boost 列表上有关于如何做到这一点的定期闲聊，但我找不到任何实际进展。 - McBeth

Answer 3

boost.serialization是一种解决方案，或者在我看来，你可以使用SQLite + Visitor模式来加载和保存这些节点，但这并不像听起来那么容易。

- baris.aydinoz

Answer 4

Boost Serialization已经被建议过了，这当然是一个合理的选择。

很大程度上取决于您将如何使用数据，将多路树存储在内存中并不意味着您必须将其作为多路树存储在磁盘上。由于您（显然）已经推动了存储在内存中的极限，显然的问题是，您是否仅仅有兴趣将数据序列化以便在需要时重新构造相同的树，还是需要像数据库一样，以便在需要时加载部分信息到内存，并更新记录。

如果您需要后者，那么您的某些选择也将取决于结构的静态性。例如，如果特定节点有N个子节点，那么这个数字是否固定，还是可能会改变？如果它可能会改变，则最大子节点数是否有限制？

如果您确实希望能够在磁盘上遍历该结构，那么一个明显的可能性是，在写出时，用适当数据的文件偏移量代替内存中使用的迭代器。

或者，由于看起来（至少大部分）单个节点中的数据具有固定大小，您可以创建一个类似数据库的结构，其中包含固定大小的记录，并在每个记录中记录父/子记录的记录号。

事先知道总体积并不特别重要（一时之间，我想不出任何方式，即使事先知道了大小，我也会使用它）。

- Jerry Coffin

Answer 5

其实，我认为你最好的选择是将整个数据结构移入数据库表中。这样，你就能享受到比你（或我）聪明得多的人处理序列化问题的好处。它还可以防止你担心结构是否能适应内存。

- Winston Ewert

Answer 6

我之前在SO上回答过类似的问题，所以我会总结一下：
1. 使用数据库。
2. 用文件偏移量替换链接（指针）。
3. 将数据存储为记录，就像数据库一样，而不是树形结构。
4. 使用XML创建树形结构，使用节点名称代替链接。
5. 如果您使用像SqLite或MySQL这样的数据库，这将变得非常容易。

当您在“序列化”上花费太多时间而忽略了项目的主要目的时，您需要使用数据库。

- Thomas Matthews

---

我的应用程序需要在几秒钟内遍历树约10^8次（作为优化的一部分）。因此，我需要将整个树保存在内存中。我可以使用数据库保存和加载，但不在内存中处理树会使我的应用程序变得太慢。 - ati

Answer 7

如果您正在进行持久化操作，那么您可以使用一些网络上的解决方案，例如搜索“persist std::list”或者使用mmap创建一个文件支持的内存区域来自己实现。

- MrMagoo

---

请确保未来提供完整有用的答案，最好附带示例代码。另外，请注意谷歌搜索结果会因国家、搜索历史、活动和其他标准而有所不同。如果您发现了有用的内容，请务必提供链接或更好的总结性回答。如果您投入了精力并且帮助/解决了问题，这将反映在您的声誉上。希望这可以帮到您 - 请编辑您的答案。 - Ingo Mi