Ich brauche einen Container, der die Eigenschaften eines Vektors und einer Liste hat. Ich brauche schnellen wahlfreien Zugriff auf Elemente innerhalb des Containers, aber ich muss auch Elemente in der Mitte des Containers entfernen können, ohne die anderen Elemente zu bewegen. Ich muss auch in der Lage sein, über alle Elemente im Container zu iterieren und auf einen Blick (ohne Iteration) zu sehen, wie viele Elemente sich im Container befinden.
Nach einiger Überlegung habe ich herausgefunden, wie ich einen solchen Container erstellen könnte, indem ich einen Vektor als Basiscontainer verwende und die tatsächlich gespeicherten Daten in eine Struktur einpacke, die auch Felder enthält, um aufzuzeichnen, ob das Element gültig ist Zeiger auf das nächste / vorherige gültige Element im Vektor. Kombiniert mit Überlastung und so, es klingt wie es sollte ziemlich transparent sein und meine Anforderungen erfüllen.
Aber bevor ich tatsächlich an der Erstellung eines weiteren Containers arbeite, bin ich neugierig, ob jemand eine existierende Bibliothek kennt, die genau das implementiert? Ich würde lieber etwas verwenden, das funktioniert, als Zeit damit zu verbringen, eine benutzerdefinierte Implementierung zu debuggen. Ich habe die Boost-Bibliothek durchgesehen (die ich bereits verwende), habe sie aber nicht gefunden.
Wenn die Reihenfolge keine Rolle spielt, würde ich einfach eine Hashtabelle verwenden, die ganze Zahlen auf Zeiger abbildet. std::tr1::unordered_map<int, T *> (oder std::unordered_map<int, unique_ptr<T>> , wenn C ++ 0x OK ist).
Die Elemente der Hashtabelle können sich bewegen, weshalb Sie einen Zeiger verwenden müssen, der jedoch sehr schnelles Einfügen / Suchen / Löschen unterstützt. Iteration ist auch schnell, aber die Elemente werden in einer unbestimmten Reihenfolge herauskommen.
Alternativ, denke ich, können Sie Ihre eigene Idee als eine sehr einfache Kombination von std::vector und std::list implementieren. Behalten Sie einfach einen list<T> my_list und einen vector<list<T>::iterator> my_vector bei. Um ein Objekt hinzuzufügen, schieben Sie es auf die Rückseite von my_list und schieben Sie dann seinen Iterator auf my_vector . (Setzen Sie einen Iterator auf my_list.end() und dekrementieren Sie ihn, um den Iterator für das letzte Element zu erhalten.) Um nachzuschlagen, suchen Sie im Vektor nach und demertieren Sie den Iterator einfach. Um zu löschen, entferne es aus der Liste (was du mit dem Iterator machen kannst) und setze den Ort im Vektor auf my_list.end() .
std::list garantiert, dass die Elemente nicht verschoben werden, wenn Sie sie löschen.
[Update]
Ich fühle mich motiviert. Erster Durchlauf bei einer Implementierung:
%Vor% Es fehlen einige Implementierungsdetails ... Vielleicht möchten Sie mehr Fehler überprüfen (was ist, wenn ich das gleiche Element zweimal lösche?) und vielleicht einige const Versionen von operator[] , begin() ,% Code%. Aber es ist ein Anfang.
Das heißt, für "ein paar tausend" Elemente wird eine Karte wahrscheinlich genauso gut dienen. Eine gute Faustregel lautet: "Optimiere nie etwas, bis dein Profiler es dir sagt".
Sieht so aus, als ob Sie vielleicht eine std :: deque möchten. Das Entfernen eines Elements ist nicht so effizient wie ein std::list , sondern weil Deques typischerweise durch Verwendung von nicht zusammenhängenden Speicherblöcken erzeugt werden, die über ein zusätzliches Zeigerarray / Vektor innerhalb des Containers verwaltet werden (jeder "Block" wäre ein) Array von N Elementen), führt das Entfernen eines Elements innerhalb von deque nicht zu der gleichen Umordnungsoperation, die Sie mit einem Vektor sehen würden.
Bearbeiten: Aber nach ein paar Kommentaren, obwohl ich denke, dass std::deque funktionieren könnte, denke ich, dass ein std::map oder std::unordered_map tatsächlich besser für dich ist da es die Array-Syntax-Indizierung ermöglicht, die Sie möchten, und Ihnen dennoch eine schnelle Entfernung von Elementen ermöglicht.