Speicher und Verarbeitung effiziente mehrdimensionale Datenstruktur C++

Question

Was ist der beste Weg, um mehrdimensionale Daten in C++ zu speichern? Ich suche nach einer dynamischen Datenstruktur statt nach statischen mehrdimensionalen Arrays, da die Anzahl der Elemente, die in der Struktur gespeichert werden sollen, nicht vorher festgelegt werden kann.

Darüber hinaus bin ich auf der Suche nach einer Datenstruktur, die die Speicherkosten minimieren und eine schnellere Suche ermöglichen. Gibt es eine fertige Datenstruktur oder muss ich eine mehrdimensionale baumbasierte Datenstruktur implementieren?

Edit: Ich muss mehrdimensionale Stream-Daten in einigen Datenstruktur speichern. Der Datenstrom hat zB die Form: (Schlüssel1, Schlüssel2, Schlüssel3, Wert1), (Schlüssel1, Schlüssel2, Schlüssel3, Wert2), (Schlüssel1, Schlüssel2, Schlüssel3, Wert3), ...

Später würde ich mag die Daten in Bezug auf verschiedene Schlüssel suchen.

Answer 1

Ich muss mehrdimensionale Stream-Daten in einigen Datenstruktur speichern. ZB hat der Datenstrom das folgende Format: (Schlüssel1, Schlüssel2, Schlüssel3, Wert), (Schlüssel1, Schlüssel2, Schlüssel3, Wert), (Schlüssel1, Schlüssel2, Schlüssel3, Wert), ...

Später würde ich mag die Daten in Bezug auf verschiedene Schlüssel suchen.

boost::multiindex ermöglicht das Hinzufügen verschiedener Arten von Indizes zu Ihrem Container.

Es ist eine ziemlich komplexe Bibliothek und kann ein bisschen schmerzhaft sein, sich daran zu gewöhnen. Aber das ist die Mühe wert, weil das Problem, das es löst, ein ziemlich allgemeines ist.

Answer 2

Wenn die schnelle Suche und Speichereffizienz die einzigen Dinge sind, die Sie benötigen, sollten Sie eine Hashtabelle verwenden (z. B. die STL-Datei: std::unordered_set<std::vector<int>>).

Dies ermöglicht Ihnen Insertionen, Löschungen und Nachschlagen in bis zu amortisierten O(1) Zeit unter Verbrauch von O(n) Speicher.

Um std::unordered_set zu verwenden, sollten wir eine Hash-Funktion bereitstellen, und std::hash<std::vector<T>> ist nicht definiert. Das Beispiel der Verwendung dieses Ansatzes (einschließlich einiger nicht schrecklicher Hash-Funktion) kann here gefunden werden.

@BiagioFesta Wie erwähnt, zeigt diese Code Zeitkomplexität von O(D) wo D eine Anzahl der Dimensionen ist, da jede Operation Hash-Berechnung wird, die O(D) Zeit in Anspruch nimmt. Dies kann durch Speichern von Hash innerhalb des Elements beschleunigt werden.