Warum benutzt libC++ diese Karte?

Question

#if __cplusplus >= 201103L 

template <class _Key, class _Tp> 
union __value_type 
{ 
    typedef _Key          key_type; 
    typedef _Tp          mapped_type; 
    typedef pair<const key_type, mapped_type>  value_type; 
    typedef pair<key_type, mapped_type>    __nc_value_type; 

    value_type __cc; 
    __nc_value_type __nc; 

    template <class ..._Args> 
    _LIBCPP_INLINE_VISIBILITY 
    __value_type(_Args&& ...__args) 
     : __cc(std::forward<_Args>(__args)...) {} 

    _LIBCPP_INLINE_VISIBILITY 
    __value_type(const __value_type& __v) 
     : __cc(__v.__cc) {} 

    _LIBCPP_INLINE_VISIBILITY 
    __value_type(__value_type& __v) 
     : __cc(__v.__cc) {} 

    _LIBCPP_INLINE_VISIBILITY 
    __value_type(__value_type&& __v) 
     : __nc(std::move(__v.__nc)) {} 

    _LIBCPP_INLINE_VISIBILITY 
    __value_type& operator=(const __value_type& __v) 
     {__nc = __v.__cc; return *this;} 

    _LIBCPP_INLINE_VISIBILITY 
    __value_type& operator=(__value_type&& __v) 
     {__nc = std::move(__v.__nc); return *this;} 

    _LIBCPP_INLINE_VISIBILITY 
    ~__value_type() {__cc.~value_type();} 
}; 

#else 
// definition for C++03... 

Es sieht aus wie der Zweck auch zu machen __value_type belegbare und beweglich ist, während in der Lage, den Inhalt als pair<const key_type, mapped_type> (das ist der Wert Art von Iteratoren ist und so weiter) zu belichten. Aber ich sehe nicht, warum es zuweisbar oder beweglich sein muss, da ich keinen Grund sehe, warum die Implementierung jemals Knoten innerhalb einer Karte kopieren oder verschieben müsste oder irgendetwas anderes tun würde, als sie zu konstruieren und zu zerstören - Platziere Zeiger und konfiguriere sie neu.

Answer 1

Wenn Sie einen benutzerdefinierten Zuordner verwenden, ist es möglicherweise erforderlich, die Zuordnung (und deren Inhalt) in einen neuen Ressourcenpool zu verschieben. In diesem Fall liefert diese Überlastung beweglichen Zugang zu den Tasten:

__value_type(__value_type&& __v) 
    : __nc(std::move(__v.__nc)) {} 

Es spielt keine Rolle, dass die Schlüssel haben-von verschoben worden, da das nächste, was alles passiert die Knoten ist zu befreien.

Hinweis: Diese Verwendung kann zu undefiniertem Verhalten führen. Sie können im Allgemeinen nicht ein Mitglied einer Union schreiben und dann ein anderes lesen. Clang und libC++ können dies tun, solange sie intern garantieren können, dass es kein Problem (oder Fehlerdiagnose) verursacht.

Sie haben es wahrscheinlich auch so gemacht, weil es keine gute konforme Alternative gibt. Zumindest kann ich nicht an einen denken. Der Standard erfordert, dass value_type::first_type ist wirklich const qualifiziert, so dass auch eine const_cast nicht zulässig ist.

Der Trick ist, in dem Fall entspricht, dass key_type und mapped_type sind sowohl Standard-Layout, so dass std::pair<key_type, mapped_type> und std::pair<key_type const, mapped_type> Layout-kompatibel sind, per [class.mem] §9.2/16. Es sieht hier etwas seltsam aus, da sich die Funktion auf die unmittelbaren Elemente __cc und __nc der Union bezieht, so dass es dem Konstruktor überlassen bleibt, auf die gemeinsame Teilsequenz zuzugreifen, die first und second umfasst. Die requirements für Standard-Layout-Typen sind etwas restriktiv, aber viele gemeinsame Schlüssel und Werttypen (z. B. std::string) können sie möglicherweise erfüllen.

Answer 2

Dies ist zur Unterstützung von Potatoswatter 's Antwort. Ich antworte als Autor dieses libC++ Codes.

Bedenken Sie:

int 
main() 
{ 
    std::map<A, int> m1; 
    m1[A{1}] = 1; 
    m1[A{2}] = 2; 
    m1[A{3}] = 3; 
    std::map<A, int> m2; 
    m2[A{4}] = 4; 
    m2[A{5}] = 5; 
    m2[A{6}] = 6; 
    std::cout << "start copy assignment\n"; 
    m2 = m1; 
    std::cout << "end copy assignment\n"; 
} 

In diesem besonderen Umstand ich die Notwendigkeit, beide recycle Knoten der Karte sah voraus, und die „const“ Schlüssel zuweisen effizient das Recycling von Knoten zu machen. Deshalb

http://cplusplus.github.io/LWG/lwg-defects.html#704

eingefügt, um die folgende Formulierung für das Recycling von map Knoten zu ermöglichen:

Die assoziativen Container erfüllen alle Anforderungen von Allocator-Aware-Containern (23.2.1 [container.requirements .general]), Die Anforderungen an value_type in Tabelle 93 gelten mit Ausnahme der containers map und multimap direkt für key_type und mapped_type. [Hinweis: Zum Beispiel sind key_type und mapped_type manchmal , um CopyAssignable zu sein, obwohl der value_type (pair) nicht CopyAssignable ist.- Endnote]

Dadurch den Containern non-const Zugriff auf die key_type der Karte. Bis heute nutzt nur libC++ dies. Wenn Sie Instrument A im obigen Beispiel Sie für libc bekommen ++:

start copy assignment 
operator=(const A& a) 
operator=(const A& a) 
operator=(const A& a) 
end copy assignment 

Für libstdC++ (gcc-5.2.0)

start copy assignment 
~A() 
A(A const& a) 
~A() 
A(A const& a) 
~A() 
A(A const& a) 
end copy assignment 

Für VS-2015:

start copy assignment 
~A() 
~A() 
~A() 
A(A const& a) 
A(A const& a) 
A(A const& a) 
end copy assignment 

I behaupten, dass, wenn A ein Typ wie int, std::vector oder std::string ist, oder ein Typ, der einen dieser üblichen Standardtypen enthält, es einen Prozess gibt vergeblicher Leistungsvorteil der Zuordnung über Zerstörung gefolgt von Konstruktion. Die Zuweisung kann die vorhandene Kapazität in den lhs ausnutzen, was oft zu einem einfachen memcpy führt, im Gegensatz zu einer Freigabe des Speichers, gefolgt von einer Zuweisung des Speichers.

Beachten Sie, dass über ~A() wahrscheinlich Aufhebung der Zuordnung des ganzen Knotens schon sagt, nicht nur A (wenn auch nicht unbedingt). In jedem Fall ist der Kopierzuweisungsoperator libC++ map hochoptimiert, um Speicher zu recyceln, und die Berechtigung für diese Optimierung wird von den Standards C++ 11 und darüber hinaus unterstützt. Der Gewerkschaftstrick ist eine (nicht notwendigerweise tragbare) Möglichkeit, diese Optimierung zu erreichen.

Eine ähnliche Optimierung wird durch denselben Code für die Bewegung Zuweisungsoperator erhalten, wenn der Zuteiler auf Bewegung Zuordnung propagieren nicht und die beiden Verteilern vergleichen ungleicher:

Klirren/libC++:

start move assignment 
operator=(A&& a) 
operator=(A&& a) 
operator=(A&& a) 
end move assignment 

gcc -5.2.0

start move assignment 
~A() 
A(A const& a) 
~A() 
A(A const& a) 
~A() 
A(A const& a) 
~A() 
~A() 
~A() 
end move assignment 

VS-2015

start move assignment 
~A() 
~A() 
~A() 
A(A const& a) 
A(A const& a) 
A(A const& a) 
end move assignment