Objekt Serialisierung bzw. Eigene Baumstruktur abspeichern
-
Hallo liebe Community,
Ich soll/möchte eine eigene Baumstruktur in C++ schreiben. Diese Baumstruktur muss sich speichern und laden lassen.
Dabei soll ein binäres und einem menschenlesbares(humanreadable) Format möglich sein.
Außerdem sollte möglichst wenig Präzisionsverlust entstehen und Portabilität der Daten gegeben sein (Stichwort "most significant bit").
Leider habe ich seit längerem kein C++ mehr programmiert und mich bis jetzt auch wenig mit dem Speichern von Objekten auseinandergesetzt.
Als Ansätze für mein Problem sehe ich, nach schnellem googlen, boost::serialization oder cereal, jeweils in Kombination mit std I/O Filestreams.
Hier stellen sich für mich nun 2 Fragen, derer ich Euch um eine Antwort/Empfehlung bitten möchte.
1. Gehen meine Ansätze in die richtige Richtung? Falls Ja, was könnt Ihr empfehlen boost, cereal oder etwas anderes?
2. Sind (zirkulare) Pointer-Strukturen ein Problem (z.B. Elternknoten hält std::vector von Kindknoten und Kinder halten Pointer auf Elternknoten.) für das serialisieren?
Falls Ja, ergibt es Sinn statt Pointern lieber Indices zuhalten, welche auf einen vector mit allen Knoten verweisen?Vielen Dank für jede Hilfe und viele Grüße
CJack
-
Vielleicht einfach XML benutzen? Das geht einfach, ist portabel und ein bisschen lesbar.
-
CJack schrieb:
1. Gehen meine Ansätze in die richtige Richtung? Falls Ja, was könnt Ihr empfehlen boost, cereal oder etwas anderes?
Ja, das ist die/eine richtige Richtung. Beide Bibliotheken setzen den üblichen Ansatz (salopp ausgedrückt: Eine Datenstruktur gibt sich selber aus, indem sie alle ihre Bestandteile ausgibt. Rekursiv durchführen bis man bei der niedrigsten Struktur angekommen ist) um. Dadurch spart man sich den ganzen Standardcode jedes Mal neu schreiben zu müssen und kann sich auf die für die konkrete Struktur wichtigen Teile konzentrieren.
Mit cereal habe ich noch nie gearbeitet, sondern nur die Anleitung gelesen, daher kann ich boost und cereal nicht vergleichen.Ich möchte noch erwähnen, dass man das natürlich auch selber schreiben kann. Vielleicht ist das gar keine so schlechte Idee, falls es bei dem Projekt in erster Linie um das Lernen neuer Techniken geht. So lernt man, was unter der Haube der Bibliotheken abgeht. Man muss ja kein abstraktes Framework schreiben, das alles und jedes Objekt serialisieren kann (das wäre schwer), sondern man muss bloß eine spezielle Lösung für die eigene Datenstruktur schreiben (das ist machbar).
2. Sind (zirkulare) Pointer-Strukturen ein Problem (z.B. Elternknoten hält std::vector von Kindknoten und Kinder halten Pointer auf Elternknoten.) für das serialisieren?
Falls Ja, ergibt es Sinn statt Pointern lieber Indices zuhalten, welche auf einen vector mit allen Knoten verweisen?Das ist kein Problem, man muss es nur richtig machen. Das heißt, nicht blind jedem Zeiger folgen, wenn es nur ein nicht-besitzender Verweis ist. Das heißt, bei der Serialisierung gibt das Kind zwar aus, wer sein Elternteil ist*, aber es gibt dann nicht sein Elternteil aus. Dafür gibt es an seine eigenen Kinder den Auftrag, sich auszugeben.
Da es gerade ein bisschen komisch klingt, wie du das formuliert hast: Dir ist schon klar, dass es keinen Sinn macht, den Zahlenwert eines Pointers zu speichern?*: Dies ist eine redundante Information, die in deiner Datenstruktur nur gespeichert ist, um bestimmte Aktionen zu optimieren. Beim Einlesen des Baumes ist jedoch klar, welches das Elternobjekt ist und man kann den Zeiger beim Einlesen automatisch richtig setzen, ohne dass diese Information explizit in den gelesenen Daten steht. Ich würde mir daher überlegen, ob man diese Information überhaupt mit abspeichern möchte.
Ähnliches gilt für die gesamte Baumstruktur. Falls die Elemente eine natürliche Ordnung haben, ist die Struktur des Baumes nicht wirklich wichtig. Wenn man einfach alle Inhalte abspeichert (ohne die Baumstruktur) und wieder einliest, bekommt man automatisch den gleichen, oder zumindest einen vergleichbaren, Baum.
-
nwp3 schrieb:
Vielleicht einfach XML benutzen? Das geht einfach, ist portabel und ein bisschen lesbar.
Danke, ja, XML ist z.B. eines der möglichen Ausgabeformate. Das trifft aber nicht ganz meine Frage. Vielleicht hab ich mich ungünstig ausgedrückt, eine (gute) Frage auch gut zustellen, ist leider schwerer als man denkt, einer neuer Versuch. Meine Frage ist eigentlich:
"Objekte eigener Klassen möglichst komfortabel auf Festplatte speichern/davon laden, wie geht das?"
Zusätzlich ist mir dabei wichtig:
- 2 Formate ein binäres(Speicherplatz, Wertgenauigkeit (floats, etc.)) und ein für Menschen lesbares(z.B. xml)(für z.B. Debugging)
- Portabilität der (binär) Daten (little/big endianness bzw. Byte Reihenfolge)SeppJ schrieb:
Ja, das ist die/eine richtige Richtung.
Danke
Das schon mal gut zu wissen.SeppJ schrieb:
Mit cereal habe ich noch nie gearbeitet, sondern nur die Anleitung gelesen, daher kann ich boost und cereal nicht vergleichen.
Ok, trotzdem Danke, vielleicht antwortet ja noch wer, sonst wird selbst getestet.
SeppJ schrieb:
Ich möchte noch erwähnen, dass man das natürlich auch selber schreiben kann. Vielleicht ist das gar keine so schlechte Idee, falls es bei dem Projekt in erster Linie um das Lernen neuer Techniken geht.
Grundsätzlich richtig, dem Aufwand wollte ich in diesem Fall aber aus dem Weg gehen.
SeppJ schrieb:
Da es gerade ein bisschen komisch klingt, wie du das formuliert hast: Dir ist schon klar, dass es keinen Sinn macht, den Zahlenwert eines Pointers zu speichern?
Danke, ja, mir ist klar, dass es keinen Sinn ergibt die Speicheradresse abzuspeichern, genau deswegen die Frage. Die Frage war/ist kann man(/die eingesetzte Bibliothek) mit (zirkularen) Pointer-Strukturen umgehen? Oder wird das Problem einfacher, wenn man auf (echte) Pointer verzichtet und diese durch einen Index auf eine Listenstruktur (z.B. std::vector), welche alle Objekte(Knoten des Baumes) enthält, nachbildet.
Wie ich dich bis jetzt verstanden habe, sind Pointer kein Problem.SeppJ schrieb:
Ähnliches gilt für die gesamte Baumstruktur. Falls die Elemente eine natürliche Ordnung haben, ist die Struktur des Baumes nicht wirklich wichtig. Wenn man einfach alle Inhalte abspeichert (ohne die Baumstruktur) und wieder einliest, bekommt man automatisch den gleichen, oder zumindest einen vergleichbaren, Baum.
Vorsichtig mit solchen Aussagen, dass stimmt nur eingeschränkt.
Beispiel: Binärer Baum(in ausbalanciertem Zustand), Inhalte sortiert weg gespeichert, Inhalte von vorneweg wieder eingelesen und eingefügt.
-> Baum entartet zu linearer Liste und Suchanfragen in logarithmischer Zeit nicht mehr möglich.Viele Grüße
CJack
-
CJack schrieb:
Beispiel: Binärer Baum(in ausbalanciertem Zustand), Inhalte sortiert weg gespeichert, Inhalte von vorneweg wieder eingelesen und eingefügt.
-> Baum entartet zu linearer Liste und Suchanfragen in logarithmischer Zeit nicht mehr möglich.Ich würde von einer guten, selbstbalancierenden Implementierung eines solchen Baums ausgehen. Absichtlich schlecht gemachte Eventualitäten braucht man nicht immer zu berücksichtigen.
