Welcher Weg, um einer Karte Werte zuzuweisen, ist am effizientesten? Oder sind sie alle auf den gleichen Code optimiert (bei den meisten modernen Compilern)?
%Vor%(Ich weiß, dass ich die Ausgabe des Compilers vergleichen und überprüfen könnte, aber diese Frage ist jetzt entstanden und das einzige, was ich in der Nähe habe, ist mein Handy ... hehe)
Erstens gibt es semantische Unterschiede zwischen [] und insert :
[] ersetzt den alten Wert (falls vorhanden) insert wird den neuen Wert ignorieren (wenn bereits ein alter Wert vorhanden ist) daher ist der Vergleich der beiden im allgemeinen nutzlos.
Zu den Einfügungsversionen:
std::map<std::string, int>::value_type ist std::pair<std::string const, int> , also kein (wichtiger) Unterschied zwischen 3 und 4 std::make_pair("Bar", 12345) ist billiger als std::pair<std::string, int>("Bar", 12345) , weil der std::string -Typ eine vollwertige Klasse mit Operationen ist, die auf Kopie auszuführen sind, und "Bar" ist nur ein String-Literal (also nur eine Zeigerkopie); Da Sie am Ende jedoch std::string erstellen müssen, hängt dies von der Qualität Ihres Compilers ab
Im Allgemeinen würde ich empfehlen:
[] für die Aktualisierung insert(std::make_pair()) für das Ignorieren von Duplikaten std::make_pair ist nicht nur kürzer, es respektiert auch die DRY-Richtlinie: Wiederhole dich nicht selbst.
Der Vollständigkeit halber wäre jedoch die schnellste (und einfachste) emplace (C ++ 11 aktiviert):
Sein Verhalten ist das von insert , aber es baut das neue Element direkt auf.
1) möglicherweise etwas langsamer als die anderen Methoden, weil std::map::operator[] first default - das Objekt erstellt, wenn es noch nicht existiert, und gibt dann einen Verweis zurück, den Sie operator= verwenden können, um Ihren gewünschten Wert festzulegen zwei Operationen.
2-4) sollte äquivalent sein, da map::value_type ein typedef zu std::pair für die gleichen Typen ist und daher auch make_pair gleichwertig ist. Der Compiler sollte diese identisch behandeln.
Beachten Sie auch, dass die Leistung weiter gesteigert werden kann, wenn Sie sowohl die Existenz prüfen müssen (zB um spezielle Logik durchzuführen, abhängig davon, ob sie existiert), als auch map::lower_bound , um zuerst einen Hinweis zu erhalten wo das Element sein sollte, also muss map::insert nicht nochmal das ganze map durchsuchen:
Ihre erste Möglichkeit: Foo["Bar"] = 12345; hat eine etwas andere Semantik als die anderen - es fügt ein neues Objekt ein, wenn keines existiert (wie die anderen), aber überschreibt den aktuellen Inhalt, wenn keiner existiert ( wo die anderen, die insert verwenden, fehlschlagen werden, wenn dieser Schlüssel bereits vorhanden ist).
Was die Geschwindigkeit anbelangt, hat sie das Potenzial, langsamer zu sein als die anderen. Wenn Sie ein neues Objekt einfügen, erstellt es ein Paar mit dem angegebenen Schlüssel und einem standardkonstruierten value_type und weist anschließend den korrekten value_type zu. Alle anderen konstruieren das Paar mit dem richtigen Schlüssel und Wert und fügen dieses Objekt ein. Fairerweise bin ich jedoch der Meinung, dass der Unterschied selten signifikant ist (bei älteren Compilern war er signifikanter, bei den neueren aber ziemlich minimal).
Die nächsten beiden sind einander gleichwertig. Sie verwenden nur zwei verschiedene Möglichkeiten, um denselben Typ zu benennen. Nach der Laufzeit gibt es keinen Unterschied zwischen ihnen.
Der vierte verwendet eine Template-Funktion (make_pair), die theoretisch könnte eine zusätzliche Ebene von Funktionsaufruf beinhalten. Ich wäre ziemlich überrascht, einen wirklichen Unterschied zu sehen, außer (möglicherweise) wenn Sie sorgfältig darauf achten, dass der Compiler absolut keine Optimierung (insbesondere Inlining) durchgeführt hat.
Unterm Strich: Der erste wird oft etwas langsamer sein als der Rest (aber nicht immer und nicht viel). Die anderen drei werden fast immer gleich sein (wie in: normalerweise erwarten, dass jeder vernünftige Compiler für alle drei identische Codes erzeugt), obwohl es eine theoretische Begründung dafür gibt, dass die vierte langsamer ist.
Wenn sich an dieser Schlüsselposition kein Objekt befindet, dann:
std::map::emplace ist am effizientesten. insert ist die zweite (aber wird sehr nahe). [] ist am wenigsten effizient.
[] , wenn es dort kein Objekt gibt, konstruiert trivial eins. Es ruft dann operator= auf.
insert führt einen Aufruf des Kopierkonstruktors für das Argument std::pair durch.
Im Fall von Karten ist map.insert( make_pair( std::move(key), std::move(value) ) ) jedoch in der Nähe von map.emplace( std::move(key), std::move(value) ) .
Wenn sich an der Schlüsselposition ein Objekt befindet, ruft [] operator= auf, während insert / emplace das alte Objekt zerstört und ein neues erstellt. [] könnte in diesem Fall leicht billiger sein.
Letztendlich hängt es davon ab, was Ihre operator= vs Kopie-Konstrukt vs. trivial-Konstrukt vs Destruktor Kosten für Ihren Schlüssel und Wert sind.
Die eigentliche Arbeit, die in der Baumstruktur von std::map aufgeht, wird so ähnlich sein, dass sie nicht lustig ist.
Der dritte ist die beste Wahl (IMHO), aber 2, 3 und 4 sind gleich.
%Vor% Warum ich denke, dass die dritte die beste Wahl ist: Sie führen nur eine Operation aus, um den Wert einzufügen: einfach einfügen (nun, es gibt auch eine Suche) und Sie können wissen, ob der Wert wurde eingefügt, indem das second -Member des Rückgabewerts und die Implementierungs-Berechtigungen überprüft wurden, um den Wert nicht zu überschreiben.
Die Verwendung von value_type hat auch Vorteile: Sie müssen den zugeordneten Typ oder Schlüsseltyp nicht kennen, was bei der Vorlagenprogrammierung nützlich ist.
Das Schlimmste (IMHO) ist das erste:
%Vor% Sie rufen das std::map::operator[] auf, das ein Objekt erstellt und einen Verweis darauf zurückgibt, dann wird das zugeordnete Objekt operator = aufgerufen. Sie machen zwei Operationen für die Insertion: zuerst die Insertion, dann die Asignation.
Und es hat ein anderes Problem: Sie wissen nicht, ob der Wert eingefügt oder überschrieben wurde.
Auch wenn es schon einige gute Antworten gegeben hat, dachte ich, ich könnte auch einen schnellen Benchmark machen. Ran jede 5 Millionen mal und verwendet C ++ 11's Chrono, um die Zeit zu messen, die es dauerte.
Heres der Code:
%Vor%Die Ausgabe für 5 Millionen Iterationen lautet:
%Vor%GCC-Version:
%Vor%Mein Gerät:
%Vor%EDIT1: Der Code wurde korrigiert und der Benchmark neu erstellt.
EDIT2: Matthieu M.'s Vorschlag für C ++ 11's Platz hinzugefügt und er hat recht, emplace ist am schnellsten