Warum verwendet C++ std :: map :: operator [] nicht inplace new?

Question

Wenn Sie C++ std :: maps (und andere Container) mit Werttypen verwenden, werden Sie feststellen, dass das Einfügen in die Map den Destruktor für Ihren Elementtyp aufruft. Dies liegt daran, die Umsetzung des Operators [] durch die C++ Spezifikation erforderlich ist äquivalent dazu sein:

(*((std::map<>::insert(std::make_pair(x, T()))).first)).second 

Er ruft den Standardkonstruktor Ihrer Art, um das Paar zu bauen. Dieser temporäre Wert wird dann in die Karte kopiert und dann zerstört. Bestätigung davon kann in this stackoverflow post und here on codeguru gefunden werden.

Was ich seltsam finde ist, dass dies ohne die temporäre Variable implementiert werden könnte und immer noch gleichwertig ist. Es gibt eine Funktion von C++, die "inplace new" genannt wird. Die std :: map und andere Container können leeren Speicherplatz für das Objekt zuweisen und dann explizit den Standardkonstruktor des Elements für den zugewiesenen Speicherplatz aufrufen.

Meine Frage: Warum keine der Implementierungen von std :: map, die ich gesehen habe, inplace new verwenden, um diese Operation zu optimieren? Es scheint mir, dass es die Leistung dieser Low-Level-Operation erheblich verbessern würde. Aber viele Augen haben die STL-Code-Basis studiert, also denke ich, dass es einen Grund geben muss, warum es so gemacht wird.

Answer 1

Im Allgemeinen ist es eine gute Idee, eine Operation auf höherer Ebene wie [] in Bezug auf niedrigere Ebenen anzugeben.

Vor C++ 11 wäre es schwierig ohne insert[] zu tun.

In C++ 11, die Zugabe von std::map<?>::emplace und ähnliche Zeug für std::pair gibt uns die Möglichkeit, dieses Problem zu vermeiden. Wenn Sie es neu definieren, also eine solche In-Place-Konstruktion verwenden, würde die zusätzliche (hoffentlich entfernte) Objekterstellung verschwinden.

Ich kann nicht einen Grund denken, dies nicht zu tun. Ich würde Sie ermutigen, es zur Standardisierung vorzuschlagen.

#include <map> 
#include <iostream> 

struct no_copy_type { 
    no_copy_type(no_copy_type const&)=delete; 
    no_copy_type(double) {} 
    ~no_copy_type() { std::cout << "destroyed\n"; } 
}; 
int main() { 
    std::map< int, no_copy_type > m; 
    m.emplace(
    std::piecewise_construct, 
    std::forward_as_tuple(1), 
    std::forward_as_tuple(3.14) 
); 
    std::cout << "destroy happens next:\n"; 
} 

live example - wie Sie sehen können, ist keine vorübergehende erzeugt:

Um kopier weniger Einsetzen in eine std::map, wir tun können, die folgende demonstrieren. So

wenn wir ersetzen

(*((std::map<>::insert(std::make_pair(x, T()))).first)).second 

mit

(* 
    (
    (
     std::map<>::emplace(
     std::piecewise_construct, 
     std::forward_as_tuple(std::forward<X>(x)), 
     std::forward_as_tuple() 
    ) 
).first 
).second 

keine temporären geschaffen würde (Leerzeichen hinzugefügt, so kann ich den Überblick über () s).

Answer 2

First off, operator[<key>] für std::map ist nur äquivalent zu einem Einfügevorgang wenn die angeforderte <key> nicht gefunden wird. In diesem Fall wird nur ein Verweis auf den Schlüssel benötigt und nur ein Verweis auf den gespeicherten Wert erzeugt.

Zweitens, wenn das neue Element eingefügt wird, gibt es keine Möglichkeit zu wissen, ob eine Kopieroperation folgen wird. Sie könnten map[_k] = _v; haben, oder Sie könnten _v = map[_k]; haben.Letzteres hat natürlich die gleichen Anforderungen wie es außerhalb einer Zuweisung, d. H. map[_k].method_call();, tut aber nicht Verwenden Sie den Kopierkonstruktor (es gibt keine Quelle zu konstruieren von). In Bezug auf die Einfügung erfordern alle oben genannten, dass der Standardkonstruktor des value_type aufgerufen werden muss und dass Speicherplatz für es zugewiesen werden muss. Selbst wenn wir wissen würden, dass wir operator[] geschrieben haben, waren wir im Anwendungsfall der Zuweisung, wir konnten wegen der Reihenfolge der Operationen nicht "inplace new" verwenden. Der value_type-Konstruktor müsste zuerst aufgerufen werden, gefolgt von value_type::operator=, was den Aufruf des Kopierkonstruktors erforderlich macht.

Schönes Denken obwohl.