Wie man eine eingereihte Karte implementiert?

Question

Das Problem: Ich möchte in der Lage sein FIFO ausgehende Nachrichten Warteschlange. Aus Gründen des Updates/Löschens möchte ich auch auf jede Nachricht in der Warteschlange basierend auf einer Objekt-ID zugreifen können.

Ich habe derzeit eine Lösung implementiert, bei der Daten in eine Deque verschoben werden und ein Iterator für diese Daten beibehalten wird. Der Iterator, der durch eine Objekt-ID codiert ist, wird dann in eine Karte eingefügt. Das war gut an dem einen Ort, an dem ich es gemacht habe, aber jetzt will ich das anderswo machen.

Übertreibe ich das Problem? Gibt es da draußen eine Datenstruktur, die das schon macht?

Answer 1

Warum machen Sie nicht die Deque IDs und die Karte eine Karte von ID zu Objekt. Wenn Sie dann auf eine ID in der Deque zugreifen, suchen Sie die ID in der Karte. Wenn die IDs global eindeutig sind, benötigen Sie nur eine Karte, um alle Deques zu bedienen.

Answer 2

Ich würde versuchen, anders herum zu arbeiten. Nutzen Sie die Karte als primäre Datenstruktur. Lassen Sie die Warteschlange Objekt-IDs enthalten, mit denen Sie das Objekt aus der Karte finden können. Sie müssen nicht alle zusätzlichen Informationen bis zu Iteratoren und Ähnlichem im Auge behalten - nur eine Karte Ihrer Daten und eine Warteschlange von Objekt-IDs.

• Editier- Neil schlug mich zu ihm, gehen Requisiten zu ihm :)

Answer 3

I Boost.MultiIndex verwendet habe etwas sehr ähnliches zu tun. Sie können einen Container verwenden, der die Daten nur einmal enthält, aber über zwei (oder mehrere!) Fassaden zugegriffen werden kann: eine, die wie eine Liste aussieht, und eine andere, die sich wie eine Karte verhält. Wenn Sie ein Element unter Verwendung einer Fassade löschen (z. B. Pop von der Liste), wird die andere Ansicht nahtlos aktualisiert.