Welcher STL-Container für geordnete Daten mit Schlüsselzugriff?

Lassen Sie uns sagen, dass ich eine Sammlung von Person Objekte, von denen jedes wie folgt aussieht:Welcher STL-Container für geordnete Daten mit Schlüsselzugriff?

class Person 
{ 
    string Name; 
    string UniqueID; 
}

Nun müssen die Objekte in einem Behälter aufbewahrt werden, die mir sie bestellen ermöglicht so, dass ich Artikel gegeben kann X leicht Finde den Gegenstand X + 1 und X-1.

Ich brauche aber auch schnellen Zugriff basierend auf der UniqueID, da die Sammlung groß sein wird und eine lineare Suche wird es nicht schneiden.

Meine aktuelle 'Lösung' ist die Verwendung einer std :: list in Verbindung mit einer std :: map. Die Liste enthält die Personen (für den geordneten Zugriff) und die Karte wird verwendet, um UniqueID einem Verweis auf den Listeneintrag zuzuordnen. Das Aktualisieren des 'Containers' beinhaltet typischerweise das Aktualisieren sowohl der Karte als auch der Liste.

Es funktioniert, aber ich denke, es sollte eine klügere Art, es zu tun, vielleicht boost:bimap. Vorschläge?

EDIT: Es gibt einige Verwirrung über meine Anforderung für "Bestellung". Zur Erklärung werden die Objekte nacheinander aus einer Datei gestreamt, und die 'Reihenfolge' der Objekte im Container sollte der Reihenfolge der Dateien entsprechen. Die Reihenfolge bezieht sich nicht auf die IDs.

Quelle

2010-07-12 Roddy

Was meinen Sie mit 'X + 1' und' X-1'? Ich habe das Gefühl, dass es sich nicht auf das 'UniqueID'-Feld bezieht, also was ist es? Auf welche Reihenfolge beziehen Sie sich? –

Ich beziehe mich auf die Bestellung innerhalb des Containers. (unter der Annahme eines Vektors) Array [X], [X-1] und [X + 1] – Roddy

Was ist die Reihenfolge im Container? Ich denke, das ist es, was Matthieu versucht festzuhalten. – Joel

boost:bimap ist die naheliegendste Wahl. bimap basiert auf boost::multi_index, aber bimap hat vereinfachte Syntax. Persönlich bevorzuge ich boost::multi_index über boost::bimap, weil es in der Zukunft leicht weitere Indizes zur Person Struktur hinzufügen kann.

Quelle

2010-07-12 11:35:33

Übrigens, Frage an Muttersprachler: 'Indizes' oder' Indizes'? –

'Indices' ist das technisch korrekte Plural Nomen.Aber jeder würde 'Indizes' verstehen ... – Roddy

Danke. frustrierend fand ich heraus, dass meine Toolchain (C++ Builder 2010) boost :: multi_index oder bimap nicht unterstützt, aber hey, zumindest weiß ich, was ich * benutzen sollte. – Roddy

Es gibt keinen Standardbibliothekscontainer, der Ihre Anforderungen erfüllt - Sie müssen also zwei Container oder die Boost-Lösung verwenden. Wenn ich zwei Container verwende, würde ich normalerweise unter fast allen Umständen einen Vektor oder eine Deque über einer Liste bevorzugen.

Quelle

2010-07-12 11:37:51

@Neil, Danke. Die Verwendung eines Vektors würde bedeuten, dass das Löschen oder Einfügen eines Elements möglicherweise ALLE Referenzen in meiner Map ungültig machen würde. Daher die Liste. – Roddy

@Roddy: Ich bin unsicher, Ihre Anforderungen, aber ich habe eine Idee, dass Sie Ihre Liste als Warteschlange verwenden. Wenn ich falsch liege, dann zögern Sie nicht, mich zu korrigieren, aber wenn ich recht habe, dann macht Neils "Deque" -Lösung Sinn. –

@Matthieu, leider nicht: Ich brauche immer noch zufällige einfügen/löschen, die Orte aller anderen Elemente nicht ungültig werden. – Roddy

Warum nicht zwei Karten verwenden, eine mit Person als Schlüssel und eine andere mit UniqueId als Schlüssel, aber das erfordert die Aktualisierung von beiden.

Sie können eine Callback-Funktion erstellen, die beide Karten aktualisiert, wenn sich Änderungen ergeben.

Quelle

2010-07-12 12:35:24 anand

"Sie können eine Callback-Funktion erstellen ..." Ah - wie mache ich das ?? – Roddy

Indem ich den Bimap neu erfinde :) –

Welcher STL-Container für geordnete Daten mit Schlüsselzugriff?

Antwort

Verwandte Themen