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

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?

Nein, das ist nicht möglich. Um eine effiziente Suche zu erhalten, muss der Container den Inhalt so anordnen, dass eine effiziente Suche möglich ist. Bei std::map ist das eine Art von sortierter Reihenfolge; bei std::unordered_map ist das eine Reihenfolge, die auf dem Hash des Schlüssels basiert.

In beiden Fällen ist die Reihenfolge anders als die Reihenfolge, in der sie hinzugefügt wurden.

Answer 2

Zuallererst, std::map garantiert O(log n) Nachschlagezeit. Sie denken dabei vielleicht an std::tr1::unordered_map . Damit wird aber definitionsgemäß jede Ordnung geopfert, um die zeitlich konstante Suche zu erhalten.

Man muss schon etwas Zeit darauf verwenden, aber ich denke, man kann die boost::multi_index_container zu tun, was Sie wollen.

Answer 3

Wie wäre es mit der Verwendung eines vector für die Schlüssel in der ursprünglichen Reihenfolge und eine map für den schnellen Zugriff auf die Daten?

Etwa so:

vector<string> keys;
map<string, Data*> values;

// obtaining values
...
keys.push_back("key-01");
values["key-01"] = new Data(...);
keys.push_back("key-02");
values["key-02"] = new Data(...);
...

// iterating over values in original order
vector<string>::const_iterator it;
for (it = keys.begin(); it != keys.end(); it++) {
    Data* value = values[*it];
}

Answer 4

Die Artikel werden bestellt nach operator< (standardmäßig), wenn sie auf den Schlüssel angewendet wird.

PS. std::map garantiert keine konstante Zeit für das Nachschlagen.
Es garantiert eine maximale Komplexität von O(ln(n))

Answer 5

Ich werde tatsächlich... rückwärts gehen.

Wenn Sie die Reihenfolge, in der die Elemente eingefügt wurden, beibehalten oder allgemein die Reihenfolge kontrollieren wollen, benötigen Sie eine Reihenfolge, die Sie kontrollieren können:

• std::vector (ja, es gibt noch andere, aber standardmäßig wird dieser verwendet)

Sie können die std::find Algorithmus (von <algorithm> ), um nach einem bestimmten Wert im Vektor zu suchen: std::find(vec.begin(), vec.end(), value); .

Oh ja, sie hat lineare Komplexität O(N) aber für kleine Sammlungen sollte das keine Rolle spielen.

Andernfalls können Sie sich unter Boost.MultiIndex wie bereits vorgeschlagen, aber für einen Anfänger wird es wahrscheinlich etwas schwierig sein.

Lassen Sie also die Komplexität erst einmal beiseite und denken Sie sich etwas aus, das funktioniert. Sie werden sich über die Geschwindigkeit Gedanken machen, wenn Sie mit der Sprache besser vertraut sind.