C++ Std :: Map Frage über Iterator Reihenfolge

Question

Ich bin ein C++ - Neuling versucht, eine Karte zu verwenden, damit ich konstante Zeit-Lookups für die find() -Methode bekommen kann.

Das Problem ist, dass, wenn ich einen Iterator verwenden, um über die Elemente in der Karte gehen, Elemente nicht in der gleichen Reihenfolge angezeigt werden, in der sie in der Karte platziert wurden.

Ohne eine andere Datenstruktur zu verwalten, gibt es eine Möglichkeit, in Reihenfolge Iteration zu erreichen, während immer noch die konstante Zeit Lookup-Fähigkeit beibehalten?

Bitte lassen Sie es mich wissen.

Danke, JBU

edit: Danke, dass ich weiß, map :: find() ist nicht konstant Zeit.

Answer 1

Elemente werden nach operator< (standardmäßig) sortiert, wenn sie auf den Schlüssel angewendet werden.

PS. std :: map garantiert keine konstante Zeit nachschlagen.
Es garantiert maximale Komplexität von O (ln (n))

Answer 2

Zunächst einmal std::map ist keine konstante Zeit-Lookup. Es ist O (log n). Ich dachte, ich sollte das klarstellen.

Wie auch immer, Sie müssen Ihre eigene Vergleichsfunktion angeben, wenn Sie eine andere Reihenfolge verwenden möchten. Es gibt keine integrierte Vergleichsfunktion, die nach Einfügezeit sortiert werden kann. Wenn Ihr Objekt jedoch ein Zeitstempelfeld enthält, können Sie den Zeitstempel zum Zeitpunkt des Einfügens festlegen und einen Zeitstempelvergleich verwenden.

Answer 3

Zunächst garantiert std::map O (log n) Nachschlagezeit. Vielleicht denken Sie an std::tr1::unordered_map. Aber das durch Definitionen opfert jede Reihenfolge, um die Suche nach der konstanten Zeit zu bekommen.

Sie müssten einige Zeit darauf verbringen, aber ich denke, Sie können boost::multi_index_container Bash tun, was Sie wollen.

Answer 4

Ohne Aufrechterhaltung einer anderen Datenstruktur, gibt es eine Möglichkeit, in Reihenfolge Iteration zu erreichen, während immer noch die konstante Zeit Lookup-Fähigkeit?

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

In beiden Fällen unterscheidet sich die Reihenfolge von der Reihenfolge, in der sie hinzugefügt wurden.

Answer 5

Karte ist nicht für die Platzierung von Elementen in einer bestimmten Reihenfolge gedacht - verwenden Sie Vektor dafür.

Wenn Sie etwas in der Karte finden Sie mit der Taste [den Operator „suchen“ sollte

Wenn Sie beide benötigen: Iteration und die Suche nach Schlüssel finden Sie in diesem topic

Answer 6

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

Wenn Sie den Auftrag erhalten wollen, in der Elemente eingefügt wurden, oder im allgemeinen die Reihenfolge zu steuern, müssen Sie eine Sequenz, die Sie steuern:

• std::vector (ja, es gibt andere, aber standardmäßig verwenden diese ein)

Sie den std::find Algorithmus (von <algorithm>) können für einen bestimmten Wert in dem Vektor zu suchen: std::find(vec.begin(), vec.end(), value);.

Oh ja, es hat lineare Komplexität O(N), aber für kleine Sammlungen sollte es egal sein.

Sonst können Sie anfangen, Boost.MultiIndex nachzuschlagen, wie bereits vorgeschlagen, aber für einen Anfänger werden Sie wahrscheinlich ein bisschen kämpfen.

Also, scheuen Sie die Komplexität Problem für den Augenblick, und kommen mit etwas, das funktioniert. Sie werden sich Gedanken über die Geschwindigkeit machen, wenn Sie mit der Sprache vertraut sind.

Answer 7

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

Es ist kein Problem, zum Beispiel eine Kartendatenstruktur zu implementieren, bei der alle Knoten auch in einer doppelt verknüpften Liste in der Reihenfolge der Einfügung sind oder beispielsweise eine Karte, in der sich alle Knoten in einem Array befinden. Es scheint mir, dass eine dieser Strukturen das sein könnte, wonach Sie suchen (abhängig davon, welche Operation Sie bevorzugen, schnell zu sein), aber keine von ihnen ist trivial mit Standardcontainern zu bauen, weil jeder Standardcontainer (vector, list, set, ...) möchte die einzige Möglichkeit sein, auf enthaltene Elemente zuzugreifen.

Zum Beispiel fand ich in vielen Fällen nützlich, Knoten zu haben, die zur gleichen Zeit in mehreren doppelt verknüpften Listen waren, aber Sie können das nicht mit std::list tun.

Answer 8

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

Etwas wie folgt aus:

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]; 
}