6

我有一个 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++ 解决方案吗？

4

7 回答 7

1

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

于 2010-04-26T14:58:36.717 回答
1

boost.serialization 是一个解决方案，或者恕我直言，您可以使用 SQLite + Visitor 模式来加载和保存这些节点，但这听起来并不容易。

于 2010-04-26T15:02:33.990 回答
1

实际上，我认为您最好的选择是将整个数据结构移动到数据库表中。这样一来，您就可以比您（或我）处理序列化问题更聪明地受益于人们。它还可以让您不必担心结构是否适合内存。

于 2010-04-26T16:12:57.367 回答
1

看来您可以使用以下语法保存数据：

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

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

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

于 2010-04-26T15:12:51.847 回答
1

Boost Serialization 已经被提出，这当然是一个合理的可能性。

很大程度上取决于您将如何使用数据——您在内存中使用多路树这一事实并不意味着您必须将其作为多路树存储在磁盘上。由于您（显然）已经突破了您可以在内存中存储的内容的限制，显而易见的问题是您是否只是对序列化数据感兴趣，以便在需要时重新构建同一棵树，或者您是否想要一些东西就像数据库一样，因此您可以根据需要将部分信息加载到内存中，并根据需要更新记录。

如果您想要后者，您的一些选择还取决于结构的静态程度。例如，如果一个特定的节点有 N 个孩子，这个数字是恒定的还是会发生变化？如果可能发生变化，孩子的最大人数是否有限制？

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

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

提前知道整体尺寸并不是特别重要（即兴发挥，我想不出任何方式我会使用这个尺寸，即使它是事先知道的）。

于 2010-04-26T15:15:38.747 回答
0

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

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

于 2010-04-26T16:55:19.143 回答
-1

如果您这样做是为了持久化，那么您可以从网络上使用几种解决方案，即谷歌“persist std::list”，或者您可以使用 mmap 创建一个文件支持的内存区域。

于 2020-07-28T20:40:33.680 回答