14
Was ist der schnellste Weg herauszufinden, ob ein unordered_map Container ein Element mit einem bestimmten Schlüssel hat?unordered_map: welcher ist schneller find() oder count()?
A
Antwort
13
Sie werden etwa gleiche Leistung haben. Sie sollten den Algorithmus verwenden, der am besten ausdrückt, was Sie zu tun versuchen.
Um dies näher auszuführen, wird im Allgemeinen count() unter Verwendung von find() implementiert. Zum Beispiel in libcxx wird count() implementiert als return (find(__k) != end());
1
Ich denke, die Suche ist die beste Option hier, keine Notwendigkeit, weiter zu gehen.
http://www.cplusplus.com/reference/unordered_map/unordered_map/find/
1
find() und count() zu viele Behälter in C++ anwendbar sind.
Für Maps, Sets usw. wird find immer eine konstante Ausführungszeit haben, da es nur den Hash berechnet und einen Iterator an das erste gefundene Element zurückgibt (end() falls nicht gefunden).
count() auf der anderen Seite hat eine konstante Ausführungszeit O (e), wobei e die Anzahl der Male ist, die der angegebene Schlüssel gefunden wird. Der schlimmste Fall ist eine Sammlung, in der alle Mitglieder die gleichen sind, so count eine Komplexität O (n)
map oder unordered_map erlauben keine Duplikate, damit ihre asymptotische Laufzeit wäre das gleiche, haben könnte.
Die Auswahl hängt von der Semantik in Ihrem Code ab. Wenn Sie nur überprüfen möchten, ob ein Schlüssel vorhanden ist, können Sie einfach count verwenden. Wenn Sie überprüfen möchten, ob ein Schlüssel vorhanden ist, und dessen Wert verwenden, gehen Sie zu find, da Sie bereits einen Iterator haben, der auf dieses Element zeigt.
'unordered_map' weiß, dass es eindeutige Schlüssel hat, also' count() 'stoppt bei der ersten Übereinstimmung (es sei denn, die Implementierung ist kaputt, aber Sie sollten davon ausgehen, dass es nicht ist) –