Cómo cargar / guardar instancia de clase C ++ (usando contenedores STL) en el disco

Question

Tengo una clase de C ++ que representa un árbol de datos organizados jerárquicamente, que es muy grande (~ Gb, básicamente tan grande como pueda salirse con la suya en la memoria). Se utiliza una lista de STL para almacenar la información en cada nodo más iteradores a otros nodos. Cada nodo tiene un solo padre, pero los niños de 0-10. Abstraído, se ve algo como:

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

Me gustaría aplicar la carga () y save () en el disco, y que debe ser bastante rápido, sin embargo los problemas obvios son:

1. No sé el tamaño de antemano;

2. Los datos contienen los iteradores, las cuales son volátiles;

3. Mi ignorancia de C ++ es prodigioso.

¿Alguien podría sugerir una solución de C ++ puro por favor?

Answer 1

Parece que se podía guardar los datos en la siguiente sintaxis:

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

Es decir, cuando se serializa el nodo raíz contiene todos los nodos, ya sea directamente (niños) o indirectamente (otros descendientes). Escribir el formato es bastante sencillo: sólo tienen una función de escritura recursiva empezando por el nodo raíz.

La lectura no es mucho más difícil. iteradores std::list<node> son estables. Una vez que haya insertado el nodo raíz, el iterador no cambiará, ni siquiera cuando la inserción de sus hijos. Por lo tanto, cuando estás leyendo cada nodo ya se puede establecer el iterador de los padres. Por supuesto, esto le deja con los iteradores niño, pero los que son triviales: cada nodo es un hijo de sus padres. Así, después de haber leído todos los nodos que va a arreglar el iteradores niño. Comenzar con el segundo nodo, el primer hijo (el primer ganglio fue la raíz) e iterar hasta el último niño. Entonces, por cada hijo C, obtener su padre y el niño a la colección de su padre. Ahora bien, esto significa que se tienen que establecer los ID int niño a un lado mientras se lee, pero se puede hacer eso en un simple std :: vector paralelo a la std::list<node>. Una vez que haya parcheado todos los ID de los niños en los respectivos padres, se puede descartar el vector.

Answer 2

Puede utilizar la biblioteca boost.serialization. Esto ahorraría estado entero de su contenedor, incluso los iteradores.

Answer 3

boost.serialization es una solución, o en mi humilde opinión, puede utilizar patrón de SQLite + Visitante para cargar y guardar estos nodos, pero no va a ser fácil como suena.

Answer 4

La serialización Boost ya se ha sugerido, y es ciertamente una posibilidad razonable.

Una gran parte depende de cómo se va a utilizar los datos - el hecho de que está utilizando un árbol de múltiples en la memoria no significa que usted tiene que guardar como un árbol de múltiples en el disco. Puesto que usted es (aparentemente) ya empujar los límites de lo que puede almacenar en la memoria, la pregunta obvia es si que eres solo está interesado en la serialización de los datos para que pueda volver a constituir el mismo árbol cuando necesitaba, o si desea algo así como una base de datos para que pueda cargar partes de la información en la memoria, según sea necesario, y actualizar registros, según sea necesario.

Si desea que el último, algunas de sus opciones también dependen de cómo la estructura estática es. Por ejemplo, si un nodo particular tiene N hijos, es que el número constante o es sujeto a cambio? Si se trata de sujetos a cambio, ¿existe un límite en el número máximo de niños?

Si usted quiere ser capaz de atravesar la estructura en el disco, una posibilidad obvia sería como se escribe a cabo, sustituir el desplazamiento de los datos apropiados en lugar del iterador que está utilizando en la memoria de archivos.

Por otra parte, ya que parece que (al menos la mayoría) de los datos en un nodo individual tiene un tamaño fijo, puede crear una base de datos similar a la estructura de los registros de tamaño fijo, y en cada registro Registro los números de registro de la padres / hijos.

Saber el tamaño total de antemano no es particularmente importante (improviso, no puedo pensar en ninguna manera me gustaría usar el tamaño incluso si se conoce de antemano).

Answer 5

En realidad, creo que su mejor opción es mover toda la estructura de datos en tablas de bases de datos. De esta manera se obtiene el beneficio de la gente mucho más inteligente entonces usted (o yo) Tras haber abordado cuestiones de serialización. Sino que también le impide tener que preocuparse de si la estructura puede caber en la memoria.

Answer 6

He contestado algo como esto en el SO antes, así que voy a resumir:
1. Usar una base de datos.
2. Los desplazamientos de archivo sustituto de enlaces (punteros).
3. Almacenar los datos sin la estructura de árbol, en registros, como lo haría una base de datos .
4. Uso de XML para crear la estructura de árbol, utilizando nombres de nodo en lugar de enlaces.
5. Este sería tan mucho más fácil si Se utiliza una base de datos como SQLite o MySQL .

Cuando usted pasa mucho tiempo en la "serialización" y menos en el objetivo principal de su proyecto, es necesario utilizar un base de datos .