Würde vector<T, std::allocator<T>>::clear() O(1) sein, wenn T trivial zerstörbar ist?
gcc in bits/stl_vector.h ruft std::_Destroy ( bits/stl_construct.h ) auf. Diese Implementierung, die für den Fall optimiert wird, dass T durch Tag-Dispatching auf std::is_trivially_destructible<T> trivial zerstörbar ist.
Bei der Durchsicht der Implementierung von llvm (3.5.0) ruft vector::clear std::allocator<T>::destroy für jedes Element auf, das wiederum den Destruktor aufruft.
Würde dies am Ende optimiert werden, indem vector::clear() O(1) in libc ++ ebenfalls gemacht wird?
Im Allgemeinen kann eine konforme Implementierung std::vector::clear in O (1) für Typen mit nicht-trivialen Destruktoren nicht implementieren.
C ++ 11 [container.anforderungen.general] / 3 Zustände:
Für die von dieser Subklausel betroffenen Komponenten, die einen allocator_type deklarieren, müssen in diesen Komponenten gespeicherte Objekte mit der Funktion
allocator_traits<allocator_type>::constructerstellt und mit der Funktionallocator_traits<allocator_type>::destroy(20.6.8.2) zerstört werden.
Da clear size() Elemente zerstören muss, muss es unbedingt O (N) Aufrufe an die Funktion destroy des zugeordneten Zuordners machen. Das Endergebnis kann jedoch effektiv eine konstante Zeit benötigen, wenn jeder dieser Aufrufe null Zeit benötigt, um abgeschlossen zu werden (d. H. Nichts tut).
Ein kurzer Blick auf die Implementierung von _Destroy in Die aktuelle Revision von libstdc ++ 's bits / stl_construct.h zeigt, dass sie versucht, diese Optimierung nur dann auszuführen, wenn der Standardzuordner verwendet wird:
, aber leider nicht ganz richtig, da der Standard die Spezialisierung von Vorlagen im Namensraum std zulässt, die von benutzerdefinierten Typen abhängen ([namespace.std] / 1). Zum Beispiel, dieses Programm:
sollte ausgeben:
%Vor% (die Reihenfolge der Elementzerstörung ist nicht spezifiziert, so dass die "zerstörenden" Zeilen in beliebiger Reihenfolge sein können, aber alle vorhanden sein müssen.) libstdc ++ "optimiert" fälschlicherweise die Aufrufe von allocator<mytype>::construct und allocator<mytype>::destroy , aber natürlich libc ++ macht es richtig ( DEMO ).