Den Operator [] effizient mit C ++ unordered_map verwenden
Erstens könnte jemand klären, ob in C++ die Verwendung der [] - operator in Verbindung mit einer unordered_map für Suchvorgänge umschließt einen Aufruf der find() Methode, oder über den [] - operator schneller als die find()?
Zweitens, in der das folgende Stück code, ich vermute, dass in den Fällen, wo der Schlüssel ist nicht schon in der unordered_map ich bin der Durchführung einer zweiten look-up durch die Linie map[key] = value
um zu ersetzen Sie den Standardwert erstellt wurde es mit dem [] - operator, wenn ein Schlüssel nicht vorhanden ist.
Ist das wahr und wenn ja gibt es eine Möglichkeit (vielleicht durch die Verwendung von Zeigern oder so), dass ich vielleicht nur ein Blick in jedem Fall (vielleicht durch die Speicherung der Adresse, wo ein Wert/lese einen Wert aus) und immer noch erreichen die gleiche Funktionalität? Offensichtlich wäre dies eine nützliche Verbesserung der Effizienz, wenn dem so ist.
Hier ist der geänderte code-Auszug:
int stored_val = map[key]; //first look up. Does this wrap ->find()??
//return the corresponding value if we find the key in the map - ie != 0
if (stored_val) return stored_val;
//if not in map
map[key] = value;
/* second (unnecessary?) look up here to find position for newly
added key entry */
return value;
InformationsquelleAutor der Frage ComethTheNerd | 2011-08-01
Du musst angemeldet sein, um einen Kommentar abzugeben.
operator[]
fügen Sie einen Eintrag für Sie mit einem default-konstruiert Wert, wenn man nicht bereits vorhanden ist. Es ist gleichwertig, aber wahrscheinlich effizienter umgesetzt werden als:operator[]
kann schneller sein als die Arbeit von Hand mitfind()
undinsert()
weil Sie sparen können, zu re-hash der Schlüssel.Einen Weg, den Sie umgehen können, dass mehrere lookups in Ihrem code, um eine Referenz auf den Wert:
Beachten Sie, dass, wenn der Wert existiert nicht in der Karte
operator[]
wird default-Konstrukt und setzen Sie ein. Während also damit vermeiden Sie, dass mehrere lookups, es könnte in der Tat langsamer, wenn verwendet mit einem Typ, der langsamer ist, Standard-Konstrukt + zuweisen als das kopieren - oder verschieben-Konstrukt.Mit
int
obwohl, die Billig Standard-Konstrukte, die 0, Sie könnten in der Lage sein zu behandeln, 0 magic number Bedeutung leer. Dieses sieht wie es könnte der Fall in deinem Beispiel.Wenn Sie keine solche Magische Zahl, du hast zwei Optionen. Was Sie verwenden sollten, hängt davon ab, wie teuer es ist für Sie zur Berechnung des Wertes.
Erst, als die Vermischung der Schlüssel ist Billig, aber das berechnen der Wert ist teuer,
find()
kann die beste option sein. Diese wird hash-zweimal, aber nur rechnen Sie den Wert bei Bedarf:Aber wenn Sie haben den Wert bereits, Sie können es tun, sehr effizient-vielleicht leicht effizienter als die Verwendung einer Referenz + Magische Zahl wie oben:
Wenn die bool zurückgegeben
map.insert(value_type)
wahr ist, wird das Element eingefügt wurde. Ansonsten, wenn es bereits existierte und keine änderungen vorgenommen wurden. Der iterator zurückgegeben Punkte die eingefügt oder vorhandene Wert in der Karte. Für Ihren einfachen Beispiel kann dies die beste option.InformationsquelleAutor der Antwort Cory Nelson
Können Sie auch überprüfen, ob ein element vorhanden ist, und fügen Sie ein neues element ist, wenn es nicht vorhanden ist, mit dem speziellen
insert
Funktion zurückgibt, die einpair<iterator, bool>
in denen der Boolesche Wert zeigt Ihnen, ob der Wert wurde tatsächlich eingesetzt. Zum Beispiel, der code hier:Den code hier ein, fügt das paar
<'z',200>
in die Karte, wenn es nicht vorhanden ist. Es gibt den iterator, wo es eingefügt, wenn der Wert des zweiten Elementes des Paares zurückgegeben wahr ist, oder gibt es den iterator, wo das element wirklich war, wenn das zweite element des Paares ist falsch.InformationsquelleAutor der Antwort Diego Sevilla
Gibt es keine Regel für. Eine Implementierung von
[]
verwenden könntefind()
ist, könnte es führen Sie die Suche nach sich selbst, oder es könnte delegieren, lookup, um einige private Methode, die auchfind()
intern.Gibt es auch keine Garantie, auf denen man schneller ist.
find()
beinhaltet einen Aufwand in der Erstellung und Rücksendung einen iterator, in der Erwägung, dass[]
wird wahrscheinlich langsamer sein, wenn der Schlüssel nicht vorhanden ist, wie es fügt einen neuen Wert in diesem Fall.Wenn der Schlüssel nicht in der map
[]
wird, legen Sie eine neue Standard-konstruiert Wert, und die return - eine Referenz. Dementsprechend könnte man speichern, die Referenz zu speichern, die zweite-Suche:InformationsquelleAutor der Antwort Ferdinand Beyer