Effizienz von Iteratoren in unordered_map (C++)

Question

Ich kann keine Informationen zu diesem Thema finden, also wende ich mich Stackoverflow zu. Wie effizient sind die Iteratoren von std :: tr1 :: unordered_map in C++? Vor allem im Vergleich zu beispielsweise Iteratoren. Wäre es sinnvoll, eine Wrapper-Klasse zu erstellen, die auch alle Schlüssel in einer Liste enthält, um eine effiziente Iteration zu ermöglichen (mein Code verwendet viele Iterationen über die Schlüssel in einer ungeordneten Map). Für diejenigen, die Boost empfehlen, kann ich es nicht benutzen (aus welchen Gründen auch immer).

Answer 1

Der unordered_map-Iterator muss im Grunde nur über die interne Baumstruktur der Hashtabelle gehen. Dies bedeutet nur, dass einige Zeiger folgen und daher ziemlich effizient sein sollten. Wenn Sie eine unordered_map häufig durchlaufen, verwenden Sie möglicherweise die falsche Datenstruktur. In jedem Fall ist die Antwort darauf wie bei allen Leistungsfragen, dass Sie Ihren spezifischen Code zeitlich festlegen, um zu sehen, ob er schnell genug ist.

Answer 2

Ich habe nicht TR1 geprüft, aber N3035 (C++ 0x Entwurf) sagt dieser:

Alle Kategorien von Iteratoren erfordern nur die Funktionen, die realisierbar für eine bestimmte Kategorie in konstant sind Zeit (amortisiert). Daher haben Anforderungstabellen für die Iteratoren keine Komplexitätsspalte.

Der Standard wird nicht andere eine Effizienz-Garantie zu geben, als in Bezug auf die Komplexität, so haben Sie keine Garantie Vergleich von list und unordered_map außer, dass sie beide konstante Zeit amortisiert (dh lineare Zeit für eine vollständige Iteration über den Container).

In der Praxis würde ich ein unordered_map Iterator zu erwarten zumindest in der Nähe von list, es sei denn, Ihre hashmap ist sehr dünn besiedelt ist. In der Komplexität der vollständigen Iteration könnte ein O-Begriff (Anzahl der Buckets) enthalten sein. Aber ich habe noch nie eine Implementierung speziell von unordered_map für C++ angeschaut, also weiß ich nicht, welche Verzierungen auf einer simplen "Array von verketteten Listen" zu erwarten sind. Wenn Sie eine "typische" Plattform testen, wenn Sie versuchen, Code zu schreiben, der auf allen C++ - Implementierungen auf jeden Fall die schnellste ist, dann können Sie das nicht ;-)

Answer 3

Leider können Sie ' Ich sage mit Sicherheit, ob etwas effizient genug ist, es sei denn, du hast es ausprobiert und die Ergebnisse gemessen. Ich kann Ihnen sagen, dass die Klassen Standard Library, TR1 und Boost viele Augen auf sie hatten. Sie sind wahrscheinlich so schnell, wie sie für die häufigsten Anwendungsfälle erhalten werden. Ein Container zu gehen ist sicherlich ein häufiger Anwendungsfall.

Mit all das gesagt, müssen Sie sich ein paar Fragen stellen:

1. Was ist der klarste Weg, zu sagen, was ich will? Es kann sein, dass das Schreiben einer Wrapper-Klasse Ihrem Code unnötige Komplexität hinzufügt. Machen Sie es zuerst richtig, dann machen Sie es schnell.

2. Kann ich mir den zusätzlichen Speicher und die Zeit leisten, um eine list parallel zur unordered_map zu verwalten?

3. Ist unordered_map wirklich die richtige Datenstruktur? Wenn Ihr häufigster Anwendungsfall das Traversieren von Anfang bis Ende ist, sollten Sie besser mit vector umgehen, da der Speicher garantiert zusammenhängend ist.

Answer 4

von den Benchmarks Beantwortet hier https://stackoverflow.com/a/25027750/1085128 unordered_map ist teilweise zwischen Vektor und für Iteration abzubilden. Es ist deutlich schneller als die Karte.