In meiner C ++ - Anwendung habe ich ein Problem, bei dem ich drei Dinge zuordnen und sie nachschlagen oder über eine einzelne Spalte iterieren muss.
Nehmen wir an, ich habe 3 Klassen A, B, C, und ein A kann zwei oder drei Kombinationen von B / C-Paaren sein. Ich möchte in der Lage sein, alle As zu finden, die zu B gehören, alle B-C-Paare für jedes A oder jedes B für ein gegebenes A und C.
Das ist für mich nicht offensichtlich, außer dass ich einen Vektor von std :: tuple habe und linear über die ganze Liste iteriere, aber ich hätte lieber Hash-Table-ähnlichen Zugriff. Eine andere Methode, an die ich gedacht habe, ist einfach, mehrere Hashtabellen von A -> vector<pair<B,C>> , B -> vector<pair<A,C> , so etwas zu machen, aber es scheint ein Kopfzerbrechen zu sein.
Ich habe Code geschrieben, um ein potentiell ähnliches Problem vorher zu lösen, und ich habe es so gemacht, das (soweit) gut funktioniert hat.
In einer Klasse:
Sie könnten ein vector von tuple s wie:
Und Maps für den Hash-Zugriff, die einfach auf den Tupel-Index zeigen:
%Vor% Im Konstruktor der Klasse können Sie die Mappings ziemlich einfach ableiten. Dies setzt voraus, dass A s, B s und C s sortiert oder gehashed werden können.
Mit dieser Datenstruktur können Sie alle Abfragemethoden schreiben, die Sie für diese Klasse benötigen, und die Implementierung sollte immer anständig einfach und schnell sein.
Das Hinzufügen eines neuen Elements zum Tupel-Array ist einfach. Die Zuordnungen sind im Wesentlichen nur Zwischenspeicher, die eine schnelle Suche ermöglichen. Die Dinge werden ein wenig komplizierter, wenn eine Instanz A , B oder C in mehreren Tupeln liegen kann, müssen Sie möglicherweise eine vector von size_t zuordnen.
Das Hinzufügen von D ist in diesem Design auch ziemlich geradlinig.
Wenn Sie einige Beziehungen benötigen, um keine der Klassen zu haben, können Sie tuple durch variant potenziell ersetzen.
Die Boost-Multi-Index-Container-Bibliothek scheint sehr nahe zu sein was du willst. Von der Einleitung:
Die Boost Multi-Index-Container-Bibliothek stellt eine Klassenvorlage mit dem Namen multi_index_container zur Verfügung, die die Konstruktion von Containern ermöglicht, die einen oder mehrere Indizes mit unterschiedlichen Sortier- und Zugriffssemantiken verwalten.
. . .
Die Vielseitigkeit von Boost.MultiIndex ermöglicht die Spezifikation eines breiten Spektrums verschiedener Datenstrukturen. Im Folgenden finden Sie mögliche Anwendungsbeispiele, die in der Dokumentation entwickelt wurden:
Sie können eine std::list der Tripel beibehalten. Dann fügen Sie drei std::unordered_map<std::reference_wrapper<>, std::list::iterator> oben in der Liste hinzu.
Der Vorteil der Verwendung von list über vector besteht darin, dass Sie damit die Sammlung effizient einfügen / löschen / aktualisieren können.
Der Vorteil der Verwendung von std::reference_wrapper<> als Schlüssel besteht darin, dass Sie die A / B / C-Werte nicht doppelt speichern.
Der Vorteil der Verwendung von list::iterator ist der direkte Zugriff auf ein Triple. Da list zeigerbasiert ist, bleiben die verbleibenden list::iterators nach dem Einfügen / Löschen einiger Listenelemente weiterhin gültig.