Konzept: Speichern von Referenzen/Verweise

Dravere

Grüsse zusammen,

Ich habe mehrere Listen von Objekten unterschiedlicher Klassen. Es kann vorkommen, muss aber nicht, dass ein Objekt eine Referenz/Zeiger auf ein anderes Objekt aus einer anderen Liste bekommt.

Wenn ich jetzt all diese Objekte abspeichern will, speichere ich natürlich die Listen ab, in dem ich jedes einzelne Objekt in die Datei schreibe. Doch wie speichere ich nun am besten die Referenz ab, so dass beim laden, die Verbindung wieder aufgebaut werden kann?

Grundsätzlich fallen mir bis anhin nur zwei Lösungen ein, welche mir aber beide nicht gefallen.

1. Ich gebe jedem Objekt eine ID. Beim speichern der Referenz wird nur die ID abgespeichert. Beim laden wird diese ID dann genommen, um in der Liste nach dem Objekt mit dieser ID zu suchen.
Negativ: Längere Ladezeit, wegen der Suche nach der ID.

2. Das gleiche, nur schaue ich darauf, dass die Sache sortiert bleibt. ID 0 ist auch an der Stelle 0 in der Liste.
Negativ: Längere Zeiten beim erstellen, löschen, bearbeiten der Objekte. Zudem möchte man die Liste womöglich nach etwas anderem sortiert haben, so müsste man die ID ändern, was seltsame Abhängigkeiten und Funktionen ergibt.

Negativ zu beiden:
- Die anderen Objekte müssen bereits geladen sein, sonst geht es natürlich nicht.
- Die Ladefunktion muss eine Referenz zum Objekt bekommen, welches die Listen hat (wohl ein übergeordnetes Objekt).
- Doppelte Referenz, also beide Objekte haben jeweilse eine Referenz zum anderen, geht so nicht. Bzw. die Referenzen müssten am Ende neu aufgebaut werden und können nicht direkt in der Klasse selbst erledigt werden, sondern es muss übergeordnet passieren.
- Grundsätzlich auch Speicherverschwendung, da womöglich nicht alle IDs verwendet werden.
- Es muss auch eine ID Verwaltung rein, also es muss geprüft werden, dass keine ID doppelt vorkommt.
- Irgendwie stimmt dann doch auch etwas mit der Klasse nicht mehr, denn die ID wird nur zum speichern verwendet und nichts anderes. Mit dem Objekt selbst hat die ID dagegen nichts zu tun.

Mir gefallen somit beide Lösungen gar nicht und ich rätsle jetzt schon seit ein paar Tagen über eine bessere Lösung, finde aber keine oder noch nicht.

Wie speichert ihr sowas, bzw. wie würdet ihr sowas speichern?

Vielen Dank für eure Meinungen!

Grüssli

SideWinder

Mit welcher Programmiersprache arbeitest du? Die Begriffe die du verwendest dueten stark auf Java oder C# hin - bei beidem sind diese Überlegungen umsonst, da das Framework bereits die Serialisierung von Objekten beherrscht.

Oder geht es dir um eine Art objektrelationale DB die du da implementieren willst? Dann beachte meinen Hinweis einfach nicht und schau dir z.B. die Implementierungen von gängigen OS-OODBs an.

MfG SideWinder

Dravere

SideWinder schrieb:

Mit welcher Programmiersprache arbeitest du? ...

Hmmm, dachte zuerst das sei nicht so wichtig, aber jetzt sehe ich schon ein wenig, dass es vielleicht nicht schlecht wäre das anzugeben. Grundsätzlich arbeite ich mit C++. Als API die WinAPI, bzw. die MFC, aber die kann man bei der Lösungssuche wohl wirklich vernachlässigen.

Grüssli

SideWinder

Dann vergiss was ich gesagt habe, die C++-Std-Library und die in weiten Teilen (COM zählt zur WinAPI?) nicht-objektorientierte WinAPI werden dir dabei nicht behilflich sein.

Habe mich mit dem Thema auhc noch nicht näher beschäftigt, rate aber nochmals dazu eine OpenSource OODB aufzusuchen und deren Implementierung anzusehen. In der Schule stellte jemand mal http://en.wikipedia.org/wiki/Db4objects vor, ist zwar für Java/.NET aber die müssen die Objekte auch irgendwie auf die Platte speichern

Ansonsten würde ich die Objekte nicht auf der Platte sortiert halten, das ist meistens mit viel Kopieren verbunden. Warum nicht die Objekte auf die Platte schreiben und einen Index aufbauen wie er bei Datenbanken üblich ist.

MfG SideWinder

Dravere

SideWinder schrieb:

... aber die müssen die Objekte auch irgendwie auf die Platte speichern

Hmmm, ich weiss nicht ob du mich richtig verstanden hast, wenn ich den Satz lese. Ein Objekt zu speichern ist nicht das Problem, das Problem ist die Referenz. Hier mal ein Beispiel code:

#include <fstream>
#include <vector>

class ClassB;

class ClassA
{
    ClassB* m_pB;

public:
    ClassA(ClassB* pB = 0) : m_pB(pB) { };

    void setReference(ClassB* pB) { m_pB = pB; };

    void store(std::ofstream& ofs) { /* Wie speicher ich nun den Zeiger m_pB, wenn ein gültiger Zeiger vorhanden ist? */ };
    void load(std::ifstream& ifs) { /* Und natürlich muss der wieder initialisiert werden. */};
};

class ClassB
{
    void store(std::ofstream& ofs); // Speichern
    void load(std::ifstream& ifs); // Laden
};

class ClassC
{
    std::vector<ClassA> m_vecClassA;
    std::vector<ClassB> m_vecClassB;

public:
    ClassC()
    {
        // m_vecClassA und m_vecClassB werden mit Objekten gefüllt.
    }

    // Diese Funktion kann ganz unterschiedlich oft aufgerufen werden.
    void foo(int iIndexA, int iIndexB)
    {
        m_vecClassA[iIndexA].setReference(m_vecClassB[iIndexB]);
    }

    void store(std::ofstream& ofs)
    {
        // Durch m_vecClassA und m_vecClassB durch iterieren und jeweils store aufrufen.
    }

    void load(std::ifstream& ifs)
    {
        // Durch m_vecClassA und m_vecClassB durch iterieren und jeweils load aufrufen.
    }
};

Nun, wie speichere ich den Zeiger sinnvoll ab, damit ich ihn beim Laden wieder initialisieren kann? Komplexer wird es wohl, wenn ClassB auch noch einen Zeiger auf ClassA aufnehmen könnte. Wie könnte man diese Beziehung sinnvoll abspeichern?

Grüssli

SideWinder

Meines Erachtens ist der Weg mit der ID schon der Richtige. Nur statt die Objekte dann nach ID sortiert zu halten würde ich eher einen Index empfehlen.

Du solltest allerdings über die Möglichkeit einer Level-Beschränkung in die Tiefe nachdenken (sonst bist du vom Kunden plötzlich bei den bestellten Bleistiften...)

Ich kann nochmals nur empfehlen dir eine OS-OODB anzusehen.

MfG SideWinder

rüdiger

Du solltest dir vielleicht mal anschauen, ob nicht ein B-Tree für das ID<->Objekt-Mapping ideal wäre.

Apollon

Dravere schrieb:

Nun, wie speichere ich den Zeiger sinnvoll ab, damit ich ihn beim Laden wieder initialisieren kann? Komplexer wird es wohl, wenn ClassB auch noch einen Zeiger auf ClassA aufnehmen könnte. Wie könnte man diese Beziehung sinnvoll abspeichern?

Wenn ich den Code richtig verstehe, dann bildest Du (A -> Paare. Solltest Du gleich viele As wie Bs haben und jedem A sei ein eindeutiges B zugeordnet welches nicht auch noch einem anderem A zugeordnet ist, dann ist das doch recht einfach. Du speicherst erst das A und dahinter das zugehoerige B. Also in etwa so: A0 B0; A1 B1; A2 B2; usw. Sollte jetzt auch noch B eine Referenz zurueck haben, so ist die Loesung auch noch Ok. Wenn Du jetzt aber mehrere Referenzen speichern moechtest, dann hast Du einen bipartiten Graphen. Sowas kannst Du als Matrix (Indextabelle) abspeichern. Sie ist dann zwar moeglicherweise duenn besetzt, aber immerhin eine Loesung.

Dravere

@rüdiger,
Ja, B-Trees sind mir bekannt und auch noch die mit der kürzeren Suchzeit, nämlich die B*-Trees. Etwas scheine ich aus der Vorlesung über Datenbanken doch mitgenommen zu haben

@SideWinder,
Ok, so langsam habe ich es glaube ich zumindest oberflächlich begriffen, was es sich mit der Obj-DB auf sich hat. Wir hatten in der Vorlesung leider keine Zeit mehr die Objektdatenbanken anzuschauen. Eindeutig schade! ^^
Allerdings erscheint mir so ein DB-System für mein Problem, ein wenig übertrieben, auch wenn ich es auf das wesentliche reduziere.

Apollon schrieb:

Wenn ich den Code richtig verstehe, dann bildest Du (A -> Paare. Solltest Du gleich viele As wie Bs haben und jedem A sei ein eindeutiges B zugeordnet welches nicht auch noch einem anderem A zugeordnet ist, dann ist das doch recht einfach. Du speicherst erst das A und dahinter das zugehoerige B. Also in etwa so: A0 B0; A1 B1; A2 B2; usw. Sollte jetzt auch noch B eine Referenz zurueck haben, so ist die Loesung auch noch Ok.

Wenn das der Fall wäre, müsste ich womöglich gar nicht mehr alle Bs in der Klasse C auflisten, sondern könnte sie direkt als Member von A machen. Dann würde auch genau so der Speichervorgang aussehen, da im store von A das store von B aufgerufen würde.

leider ...

Apollon schrieb:

Wenn Du jetzt aber mehrere Referenzen speichern moechtest, ...

Ist genau das der Fall

Apollon schrieb:

... dann hast Du einen bipartiten Graphen. Sowas kannst Du als Matrix (Indextabelle) abspeichern. Sie ist dann zwar moeglicherweise duenn besetzt, aber immerhin eine Loesung.

bipartiten Graphen ... ok muss ich noch nachschlagen ...
Als Matrix abspeichern? Kann sein, dass es schon etwas spät ist und ich deshalb jetzt nicht ganz mitkomme, aber wie soll ich das als Matrix speichern? Meinst du die jeweiligen Zusammenhänge, also Index von A und Index von B? Höhe der Matrix als die Menge von Zusammenhängen und breite die maximale Anzahl Referenzen? Tönt interessant, aber man ist dann halt wieder bei den IDs.

Noch eine Frage zum C++ Standard, das konnte ich gerade nicht so finden. Bei einem std::vector, liegen da die Objekte hintereinander auf dem Speicher, bzw. wie sieht das allgemein bei Containern aus? So könnte ich nämlich zumindest die ID über die Zeiger rausfinden, indem ich den aktuellen Zeiger minus den ersten Zeiger rechne. Das wäre eine schnelle Ermittlung der ID und sie wäre eindeutig, also keine Verwaltung der IDs notwendig. Und zum abrufen der Objekte beim laden, wäre natürlich eine ID als Index auch sehr schnell. Allerdings müsste ich dann beim Speichern und Laden immer auf die C Klasse zugreifen, rückwirkend von der A, bzw. B Klasse. Aber zumindest das Geschwindigkeitsproblem wäre behoben.

Grüssli und Danke für die bisherigen Antworten!

Apollon

Dravere schrieb:

Apollon schrieb:

... dann hast Du einen bipartiten Graphen. Sowas kannst Du als Matrix (Indextabelle) abspeichern. Sie ist dann zwar moeglicherweise duenn besetzt, aber immerhin eine Loesung.

bipartiten Graphen ... ok muss ich noch nachschlagen ...
Als Matrix abspeichern? Kann sein, dass es schon etwas spät ist und ich deshalb jetzt nicht ganz mitkomme, aber wie soll ich das als Matrix speichern? Meinst du die jeweiligen Zusammenhänge, also Index von A und Index von B? Höhe der Matrix als die Menge von Zusammenhängen und breite die maximale Anzahl Referenzen? Tönt interessant, aber man ist dann halt wieder bei den IDs.

Dass der Graph bipartit ist, ist uninteresaant. Zu den IDs: die existieren aber nur in der Datei, nicht in den Objekten. Zur Laufzeit sind sie ja implizit durch den Index im vector gegeben. Die Idee ist nun folgende: Du speicherst die As in der Reihenfolge in der Du sie vorliegen hast. Ebenso die Bs. Dann erstellst Du eine As.size() X Bs.size() Matrix von ints. Im Feld a0-b0 speicherst Du dann eine 1, wenn a0 eine Referenz auf b0 haelt, eine 2, wenn b0 eine Referenz auf a0 haelt aber a0 nicht auf b0, und eine 3, wenn sowohl a0 eine Referenz auf b0, als auch b0 eine Referenz auf a0 haelt.

Hoffe es war verstaendlich und hilfreich.