Comment charger / enregistrer l'instance de classe C (en utilisant des conteneurs STL) sur le disque

Question

J'ai une classe C ++ qui représente un arbre de données hiérarchisées qui est très grand (~ Gb, essentiellement aussi grand que je peux sortir avec en mémoire). Il utilise une liste STL pour stocker des informations à chaque nœud plus itérateurs à d'autres nœuds. Chaque noeud n'a qu'un seul parent, mais les enfants 0-10. Abstraite, il ressemble à quelque chose comme:

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

Je voudrais mettre en œuvre la charge () et enregistrer () sur le disque, et il devrait être assez rapide, mais les problèmes évidents sont:

1. Je ne sais pas la taille à l'avance;

2. Les données contiennent des itérateurs, qui sont volatils;

3. Mon ignorance de C ++ est prodigieuse.

Quelqu'un pourrait-il proposer une solution C ++ pur s'il vous plaît?

Answer 1

Il semble que vous pouvez enregistrer les données dans la syntaxe suivante:

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

C'est-à-dire quand sérialisé le nœud racine contient tous les nœuds, soit directement (enfants) ou indirectement (autres descendants). Écrit le format est assez simple: il suffit d'avoir une fonction d'écriture récursive à partir du nœud racine.

La lecture est beaucoup plus difficile. itérateurs std::list<node> sont stables. Une fois que vous avez inséré le nœud racine, son iterator ne changera pas, même pas lors de l'insertion de ses enfants. Par conséquent, lorsque vous lisez chaque nœud, vous pouvez déjà définir la iterator mère. Bien sûr, cela vous laisse avec l'enfant itérateurs, mais ce sont triviales: chaque nœud est un enfant de ses parents. Donc, après avoir lu tous les nœuds vous Rénovez des itérateurs enfants. Commencez par le deuxième noeud, le premier enfant (Le premier noeud un était la racine) et itérer au dernier enfant. Ensuite, pour chaque enfant C, obtenir son parent et l'enfant à la collection de son parent. Maintenant, cela signifie que vous devez définir les ID enfant int côté pendant la lecture, mais vous pouvez le faire dans un simple std :: vecteur parallèle à la std::list<node>. Une fois que vous avez patché tous les ID enfants chez les parents respectifs, vous pouvez jeter le vecteur.

Answer 2

Vous pouvez utiliser la bibliothèque de boost.serialization. Cela permettrait d'économiser l'état entier de votre conteneur, même les itérateurs.

Answer 3

boost.serialization est une solution, ou à mon humble avis, vous pouvez utiliser SQLite + modèle visiteur pour charger et enregistrer ces nœuds, mais il ne sera pas facile que cela puisse paraître.

Answer 4

Boost sérialisation a déjà été suggéré, et il est certainement une possibilité raisonnable.

Une grande partie dépend de la façon dont vous allez utiliser les données - le fait que vous utilisez un arbre multivoies en mémoire ne pas vous dire nécessairement stocker sous forme d'un arbre multivoies sur le disque. Puisque vous êtes (apparemment) poussant déjà les limites de ce que vous pouvez stocker dans la mémoire, la question évidente est que vous soyez juste intéressé à la sérialisation des données afin que vous puissiez reconstituer le même arbre lorsque besoin, ou si vous voulez quelque chose comme une base de données de sorte que vous pouvez charger une partie des informations dans la mémoire selon les besoins, et mettre à jour les dossiers au besoin.

Si vous voulez que celui-ci, certains de vos choix dépendra aussi de la façon dont la structure statique est. Par exemple, si un nœud particulier a N enfants, est que constante de nombre ou est-ce sujet au changement? Si elle est sujet au changement, est-il une limite sur le nombre maximum d'enfants?

Si vous voulez être en mesure de traverser la structure sur le disque, une possibilité évidente serait que vous l'écrire, remplacer le fichier décalage des données appropriées à la place de l'itérateur que vous utilisez dans la mémoire.

Sinon, car il ressemble à (au moins la plupart) les données dans un noeud individuel a une taille fixe, vous pouvez créer une base de données comme la structure des dossiers de taille fixe, et dans chaque enregistrement d'enregistrement des numéros d'enregistrement du parents / enfants.

La connaissance de la taille globale à l'avance est pas particulièrement importante (désinvolture, je ne peux pas penser à quelque façon que j'utiliser la taille même si elle était connue à l'avance).

Answer 5

En fait, je pense que la meilleure option est de déplacer l'ensemble de la structure de données dans des tables de base de données. De cette façon, vous obtenez le bénéfice des gens beaucoup plus intelligents que vous (ou moi) ayant traité des questions de sérialisation. Il sera également vous empêcher d'avoir à se soucier de savoir si la structure peut tenir dans la mémoire.

Answer 6

J'ai répondu quelque chose comme ça sur le SO avant, donc je vais résumer:
1. Utiliser une base de données. 2. décalages de fichiers de remplacement pour les liens (pointeurs).
3. Conserver les données sans la structure des arbres, dans les dossiers, comme base de données serait .
4. Utilisez XML pour créer l'arborescence, en utilisant les noms de nœuds au lieu de liens.
5. Ce serait tellement plus facile si vous utilisé une base de données comme MySQL ou SQLite .

Lorsque vous passez trop de temps sur la « sérialisation » et moins sur l'objectif principal de votre projet, vous devez utiliser une base de données .