C++ Boost - Gibt es einen Container, der wie eine Warteschlange mit direktem Schlüsselzugriff funktioniert?

Question

Ich habe mich über einen queueähnlichen Container gewundert, der aber wie eine Karte einen Schlüsselzugriff hat. Mein Ziel ist einfach: Ich möchte eine FIFO-Warteschlange, aber wenn ich ein Element einfügen und ein Element mit einem bestimmten Schlüssel bereits in der Warteschlange ist, möchte ich das neue Element ersetzt die bereits in der Warteschlange. Zum Beispiel würde eine nach Einfügezeit sortierte Karte funktionieren.

Wenn es keinen Container wie diesen gibt, glauben Sie, dass er sowohl mit einer Warteschlange als auch mit einer Karte implementiert werden kann?

Answer 1

Boost multi-index bietet diese Art von Container.

Um es selbst zu implementieren, würde ich wahrscheinlich für eine map gehen, deren Werte bestehen aus einem verknüpften Listenknoten plus eine Nutzlast. Der Listenknoten könnte von Hand gerollt werden oder könnte Boost intrusive lauten.

Beachten Sie, dass der Hauptpunkt des queue Adapters ist, die meisten der Schnittstelle von Sequence zu verbergen, aber Sie wollen mit den Details, die es verbirgt, durcheinander bringen. Also denke ich, dass Sie versuchen sollten, die Schnittstelle queue (leicht modifiziert mit Ihrer geänderten Semantik für push) zu reproduzieren, anstatt sie tatsächlich zu benutzen.

Answer 2

Ich sehe einfachen Weg, dies mit einer Warteschlange und optional einer Karte zu tun.

Definieren Sie eine Art == Operator für Ihre Elemente.

Dann haben Sie einfach eine Warteschlange und suchen Sie jedes Mal nach Ihrem Element, wenn Sie es einfügen möchten.

Sie können dies optimieren, indem Sie eine Zuordnung von Elementpositionen zu Elementen vornehmen, anstatt die Warteschlange jedes Mal zu durchsuchen.

Answer 3

Offensichtlich was Sie wollen, kann einfach mit der Warteschlange-wie Container durchgeführt werden, aber Sie müssten O(n) Zeit bei jeder Einfügung ausgeben, um festzustellen, ob das Element bereits vorhanden ist. Wenn Sie Ihre Warteschlange basierend auf etwas wie std::vector implementieren, können Sie die binäre Suche verwenden und im Grunde Ihre Einfügung zu O(log n)beschleunigen (das würde noch O(n) Operationen erfordern, wenn die Speicherumleitung vorgenommen wird).

Wenn das in Ordnung ist, bleiben Sie einfach dabei. Die Variante mit zusätzlichen Containern könnte Ihnen eine Leistungssteigerung bringen, aber es ist wahrscheinlich auch fehleranfällig zu schreiben und wenn die erste Lösung ausreicht, verwenden Sie sie einfach.

---

Im zweiten Szenario, das Sie Ihre Elemente möchten vielleicht zweimal in verschiedenen Behältern speichern - die ursprünglichen Warteschlange und so etwas wie eine Karte (oder manchmal ein hashmap kann eine bessere Leistung). Die Karte wird nur verwendet, um festzustellen, ob das Element bereits im Container vorhanden ist oder nicht - und wenn JA, müssen Sie es in Ihrer Warteschlange aktualisieren.

Grundsätzlich das gibt uns O(1) Komplexität für hashmap Lookups (in der realen Welt könnte dies aufgrund der Kollisionen hässlichen bekommen - Hashmaps sind nicht wirklich gut für die Bestimmung Element Existenz) und O(1) Einführungszeit für den Fall, wenn kein Update erforderlich und O(n) Einfügezeit für das Fallupdate ist erforderlich.

Basierend auf dem Prozentsatz der tatsächlichen Aktualisierungsvorgänge kann die tatsächliche Einfügungsleistung von O(1) bis O(n) variieren, aber dieses Schema wird definitiv die erste übertreffen, wenn die Anzahl der Aktualisierungen klein genug ist.

Noch müssen Sie Ihre Elemente in zwei Containern gleichzeitig einfügen und das gleiche sollte getan werden, wenn das Element gelöscht wird und ich würde zweimal überlegen "Brauche ich wirklich diesen Leistungsschub?".