c++ std::map Frage zur Reihenfolge der Iteratoren

Question

Ich bin ein C++-Neuling, der versucht, eine Map zu verwenden, damit ich konstante Zeitabfragen für die find()-Methode erhalten kann.

Das Problem ist, dass, wenn ich einen Iterator verwende, um die Elemente in der Karte zu durchlaufen, die Elemente nicht in der gleichen Reihenfolge erscheinen, in der sie in der Karte platziert wurden.

Gibt es eine Möglichkeit, die Iteration in der Reihenfolge zu erreichen, ohne eine weitere Datenstruktur zu pflegen, und dabei die Fähigkeit zum Nachschlagen in konstanter Zeit beizubehalten?

Bitte lassen Sie es mich wissen.

Danke! jbu

edit: Danke für den Hinweis, dass map::find() keine konstante Zeit ist.

Answer 1

Zunächst einmal, std::map nicht konstant nachschlagen. Es ist O(log n). Ich dachte nur, ich sollte das klarstellen.

In jedem Fall müssen Sie Ihre eigene Vergleichsfunktion angeben, wenn Sie eine andere Reihenfolge verwenden wollen. Es gibt keine eingebaute Vergleichsfunktion, die nach der Einfügezeit ordnen kann, aber wenn Ihr Objekt ein Zeitstempelfeld enthält, können Sie den Zeitstempel zum Zeitpunkt der Einfügung festlegen und einen Vergleich nach Zeitstempel verwenden.

Answer 2

Map ist nicht dafür gedacht, Elemente in eine bestimmte Reihenfolge zu bringen - verwenden Sie dafür einen Vektor.

Wenn Sie etwas in der Karte finden wollen, sollten Sie nach dem Schlüssel "suchen", indem Sie [den Operator

Wenn Sie beides brauchen: Iteration und Suche nach Schlüssel, siehe dies Thema

Answer 3

Ja, man kann eine solche Datenstruktur erstellen, aber nicht mit der Standardbibliothek... der Grund dafür ist, dass Standardcontainer verschachtelt werden können, aber nicht gemischt werden können.

Es ist kein Problem, z. B. eine Map-Datenstruktur zu implementieren, bei der alle Knoten ebenfalls in einer doppelt verketteten Liste in der Reihenfolge des Einfügens stehen, oder eine Map, bei der alle Knoten in einem Array stehen. Es scheint mir, dass eine dieser Strukturen das sein könnte, wonach Sie suchen (je nachdem, welche Operation Sie als schnell bevorzugen), aber keine von beiden ist trivial mit Standardcontainern zu bauen, weil jeder Standardcontainer ( vector , list , set , ...) soll die einzige Möglichkeit sein, auf enthaltene Elemente zuzugreifen.

Zum Beispiel fand ich es in vielen Fällen nützlich, Knoten zu haben, die gleichzeitig in mehreren doppelt verknüpften Listen waren, aber das kann man nicht mit std::list .