Verwendet STL Sortierung Swap oder Binärkopie?

  • Ich habe Probleme, eine gute Antwort darauf zu finden. Aus irgendeinem Grund dachte ich, STL-Sortierung würde mithilfe von Swap implementiert werden, um komplizierte Typen besser zu unterstützen, aber als ich am Ende den Code ein wenig durchforstete, scheint er tatsächlich eine binäre Kopie zu machen. Kann jemand das bestätigen? Ich vermute, binäre Kopie wäre eigentlich der Auslagerung vorzuziehen.

    Nebenfrage : Werden STL-Algorithmen oder Containeroperationen mit Swap implementiert? (Außerhalb von std::swap natürlich.) Ich möchte wissen, wann es ratsam ist, meinen eigenen Swap für komplizierte Typen zu implementieren Sie haben so etwas wie:

     class MyClass {
      vector<int> vec_data;
      int a;
      int b;
    }
    vector<MyClass> my_vec;
    sort(my_vec.begin(), my_vec.end(), MyCustomCompare);
     

    Ich möchte sicherstellen, dass die Sortierung nicht den Kopierkonstruktor der vector, der passieren würde, wenn Sie den Standardkonstruktor für Konstruktionen von MyData aufrufen. Daher ist meine Frage Sortieraufrufe, Kopieren, Zuweisen usw.

    22 November 2011
    Jason T.
4 answers
  • Nein, std::sort aus der C ++ - Standardbibliothek darf keine binären Kopien von Objekten mit nicht trivialen Kopier- / Zuweisungsoperatoren durchführen. Ich kann nicht verstehen, warum es keine binären Kopien von Objekten mit trivialen Kopier- / Zuweisungsoperatoren machen kann. Betrachten Sie dieses Objekt:

     class Explosive {
        Explosive* const self;
    public:
        Explosive() :self(this) {}
        Explosive(const Explosive&) :self(this) {}
        ~Explosive() {assert(this==self);}
        Explosive& operator=(const Explosive& rhs) {
            assert(this==self && rhs.self==&rhs); 
            return *this;
        }
        bool operator<(const Explosive& rhs) const 
        {return std::less<Explosive*>(self,rhs.self);}
    };
     

    Es wird garantiert, dass die C ++ - Algorithmen keine der beiden Assertierungen auslösen, d wäre nicht gültig.

    17 January 2013
    Mooing Duckmoonshadow
  • Ich habe gesehen, dass std::copy in GNU libstdc ++ memmove beschäftigt, abhängig davon, ob der Elementtyp POD has_trivial_assignment_operator ist. Siehe hier :

     template<typename _Tp>
       inline _Tp*
       __copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result)
       {
          std::memmove(__result, __first, sizeof(_Tp) * (__last - __first));
          return __result + (__last - __first);
       }
     

    Zumindest in SGI rotate, reverse, swap_ranges, random_shuffle, partition, next_permutation alle beschäftigen swap.

    Siehe http://www.sgi.com/tech/stl/stl_algo.h

    Auch das C ++ 11 Standarddokument für std::sort wird speziell in § 25.4.1.1 erwähnt:

    Erfordert : RandomAccessIterator muss die Anforderungen von ValueSwappable (17.6.3.2). Der Typ von *first muss den Anforderungen von MoveConstructible (Tabelle 20) und von MoveAssignable (Tabelle 22) genügen.

    Nun enthält § 17.6.3.2 folgendes:

    Ein Objekt t ist mit einem Objekt u nur dann austauschbar, wenn:

    • der Ausdruck s swap(t, u) und d swap(u, t) sind gültig, wenn sie im unten beschriebenen Kontext ausgewertet werden, und
    • diese Ausdrücke haben folgende Auswirkungen:
      • das Objekt, auf das mit t Bezug genommen wird, hat den ursprünglich von u gehaltenen Wert, und
      • das von u bezeichnete Objekt hat den Wert ursprünglich von t gehalten.

    Der Kontext, in dem h swap(t, u) ein d swap(u, t) ausgewertet werden, um sicherzustellen, dass eine binäre Nicht-Member-Funktion mit dem Namen „Swap“ über die Überladungsauflösung (13.3) eines Kandidaten-Sets ausgewählt wird, das Folgendes umfasst:

    • die beiden in (20.2) definierten Swap-Funktionsvorlagen und
    • der Suchsatz, der durch eine argumentabhängige Suche (3.4.2) erzeugt wird.
    22 November 2011
    sehecw.prime
  • Das hängt von Ihrer STL-Implementierung ab. Die die GCC STL-Implementierung verwendet eine Kombination aus mehreren Optionen und Einfügungssortierung. Anscheinend wird std::swap (oder Ihre Spezialisierung) in der Introsort-Schleife aufgerufen, jedoch nicht durch die Einfügungssortierung.

    Wenn Sie keine haben Spezialisierung von std::swap, dann verwendet die Standardimplementierung std::swap eine temporäre Kopie, um den Swap zu implementieren.

    Es wird keine binäre Kopie verwendet (außer bei einigen POD-Typen, die dies können.) tief in den STL-Bibliotheken verborgene Spezialisierungen haben.

    Außerdem scheint es in C ++ 0x wahrscheinlich zu sein, dass die Einfügungssortierung die Bewegungssemantik (Rvalue-Referenzen) verwendet.

    29 November 2011
    Laramie
  • Es wird ausgetauscht, aber da es sich um eine Vorlagenfunktion handelt, kann es dazu kommen, dass der Code ausgetauscht wird. Der Compiler kann einen binären Swap als Optimierung auswählen, wenn es sich um einen einfachen Typ handelt.

    22 November 2011
    Mark Ransom