Cross-Reference oder std::map

Tag zusammen,

ich frage mich für ein konkretes Problem gerade, ob ich lieber eine Cross-Reference oder eine std::map mit Verknüpfungen wählen soll. Folgende Situation:

Es gibt die Klassen Entity und Room.

- Eine Room-Instanz ganz beliebig viele Zeiger auf Entity-Instanzen haben (1:n-Relation).
- Von jeder Entity-Instanz muss ich wissen, welcher Room-Instanz diese zugeordnet ist.

Dafür gibt's zwei Möglichkeiten:
- Entity-Instanz erhält einen Zeiger auf die Room-Instanz, in der sie liegt.
- Es gibt irgendwo eine std::map<Entity*, Room*>.

Die erste Möglichkeit wollte ich eigentlich vermeiden, weil Entity-Instanzen *selbst* nichts von irgendeinem Raum wissen müssen. Notwendig wird die Information für andere Klassen.

Die zweite Möglichkeit finde ich designtechnisch gut, allerdings treibt das 1. den Speicher etwas nach oben (es kann enorm viele Entity-Instanzen geben) und 2. fordert das einen weiteren Such-Schritt, den ich mit der ersten Möglichkeit umgehen könnte.

Gibt's noch andere Möglichkeiten, die das sauber implementieren?

DocShoe

Irgendwie beisst sich die Katze da doch in den Schwanz. Wenn du zu jedem Entity Objekt wissen musst, welchem Room es zugeordnet brauchst du irgendeine Information, die das Room Objekt identifiziert, sei es ein Pointer oder eine ID (es sei denn du möchstest alle Vektoren aller Rooms durchsuchen, bis du in irgendeinem Room das Entity Objekt wiederfindest und dann auch weißt, zu welchem Room das Entity Objekt gehört.
Was genau willst du denn abbilden? Nach meinem Verständnis haben alle Dinge irgendeinen Aufenthaltsort, daher macht ein Room Element für Entity schon Sinn. Aber ich kenne die Aufgabenstellung ja nicht...

Eine Aufgabenstellung gibt es nicht, ist ein freies Projekt. Von daher ist mir jeder Ansatz lieb.

Was ich im Grunde abbilden möchte ist die Room -> Entity-Relation, eine 1:n-Relation. Dabei muss ein Entity selbst gar nicht wissen, in welchem Raum es ist. Diese Klasse ist für sich völlig unabhängig davon.

Allerdings benötigen andere Klassen diese Information für einige Operationen. Und hier überlege ich, ob ich im Vorfeld schon optimieren soll, damit es später nicht zu (eigentlich unnötigen) Suchläufen kommt.

Wenn ich mir nämlich vorstelle, dass z.B. eine Entity-Instanz im 1000. Room liegt, und eine entsprechende GetRoomOfEntity()-Methode alle 1000 durchiterieren muss, um die zugehörige Room-Instanz zu ermitteln, frage ich mich, ob man das nicht besser lösen kann.

Ein Nachteil der Methode, dass ein Entity-Objekt weiß, wo es reingehört (z.B. durch einen Pointer) ist die, dass ich ständig zwei Verweise aktualisieren muss. Wenn beispielsweise ein Entity-Objekt von Room A nach Room B überführt wird:
- Entity aus Room A entfernen.
- Entity an Room B hängen.
- Room-Pointer im Entity aktualisieren.

Die ersten beiden Operationen sind unausweichlich, das ist klar, denn ein Room-Objekt muss wissen, welche Objekte in ihm rumlungern. Aber die dritte ist dann eigentlich wieder unnötig, weil im Programm schon alle Informationen vorhanden sind, um den Room eines Entity-Objekts ausfindig zu machen (bisher aber eben mit linearer Laufzeitkomplexität, was man ja vermeiden sollte).

Vielleicht sehe ich auch einfach den Wald vor lauter Bäumen nicht oder treibe es mit der Premature Optimization zu wild. Die Frage dabei ist: Es ist weiterhin performant, Room-Objekte in einer std::list zu sichern und Entity-Verweise in Form von Pointern in der Room-Klasse in einem std::set? Hier hätte man doch O(AnzahlRoomObjekte) + O(log AnzahlEntityVerweiseImAktuellen Raum), oder irre ich?

DocShoe

Um irgendeine Redundanz wirst du nicht herumkommen, sei es die Room Information im Entity Objekt oder eine Lookup Table für die Entity->Room Zuordnung.
Ich weiss immer noch nicht, was ein Entity Objekt eigentlich ist, ich nehme mal an, es ist die Basisklasse aller möglichen Objekte, die sich in einem Raum befinden. Wenn das so ist würde ich einen Zeiger auf den Room als Element einfügen, das den Room bestimmt, in dem sich das Entity Objekt befindet. Die Lösung hat noch den Vorteil, dass die Datenhaltung zentral an einer Stelle geführt werden kann, bei einer zusätzlichen Lookup Table muss man immer noch irgendwie an die Tabelle kommen, sei es durch einen zusätzlichen Parameter im Funktionsaufruf oder als Singleton. Intuitiv finde ich die Lösung auch eleganter, weil der Quelltext sich selbst dokumentiert und beim Lesen klar wird, was da eigentlich passiert (auch wenn es etwas mehr Code ist als die LU Tabelle zu pflegen).

// Lösung mit Zeigern
void put_entity( Room& room, Entity& entity )
{
   if( entity.room() )
   {
      entity.room()->remove_entity( entity );
   }
   room.add_entity( entity );
   entity.set_room( room );
}

// Lösung mit Lookup Tabelle
void put_entity( Room& room, Entity& entity )
{
   // Adresse des Rooms für das Entity Objekt eintragen
   GlobalLookupTable[entity.id()] = &room;
}

Edit:
Bugs gefixt

Hm, damit hast du Recht, das scheint wirklich die elegantere UND performantere Lösung zu sein. Zumal es ja wirklich nur ein Verweis ist, mit dem Entity selbst gar nix anstellt.

Und genau der Verweis kann von der verwaltenden Methode aktualisiert werden (ich hätte jetzt z.B. so was wie Room::AddEntity( Entity& ent ) hergenommen, aber das Prinzip bleibt dasselbe).

Übrigens, mit der Annahme, dass ein Entity ein beliebiges Objekt sein kann, liegst du richtig. Es ist zwar keine Basisklasse, weil nicht der C++-Code, sondern Python-Skripte die Funktionalität erweitern, aber auch hier ist das Prinzip dasselbe.

Ich danke Dir vielmals für deine Hilfe.