Lambda-Funktion in std::qsort



  • Hallo,
    ich bekomme es gerade nicht hin, dass der Compiler (VS 2017) meine Lambda-Funktion akzeptiert. Folgendes Codestück (bitte nicht dran stören, dass in den Arrays nichts sinnvolles steht, das ist nur das auf ein Mimimum heruntergebrochene Beispiel):

    void Test()
    {
        int * myarray = new int[20];
        int * indices = new int[20];
        std::qsort (indices, 10, sizeof (indices[0]),
                    [myarray] (const void * a, const void * b)
                    {
                        int va = myarray[*static_cast <const int *> (a)];
                        int vb = myarray[*static_cast <const int *> (b)];
                        return va < vb ? -1 : va > vb ? 1 : 0;
                    }
        );
    }
    

    liefert den Fehler

    error C2664: "void qsort(void *,size_t,size_t,_CoreCrtNonSecureSearchSortCompareFunction)" : Konvertierung von Argument 4 von "Test::<lambda_0cd77753173ed5da466825239fd6681f>" in "_CoreCrtNonSecureSearchSortCompareFunction" nicht möglich
    

    Merkwürdig ist noch, dass es ohne Capturen des "myarray" ohne Fehler compiliert:

    void Test()
    {
        int * myarray = new int[20];
        int * indices = new int[20];
        std::qsort (indices, 10, sizeof (indices[0]),
                    [] (const void * a, const void * b)
                    {
                        int va = *static_cast <const int *> (a);
                        int vb = *static_cast <const int *> (b);
                        return va < vb ? -1 : va > vb ? 1 : 0;
                    }
        );
    }
    

    Ich verstehe gerade nicht, was er hier für ein Problem mit dem Capture-Parameter hat. [&] oder [=] funktionieren auch nicht. Eingestellt ist der C++17-Standard.

    Danke schonmal, viele Grüße
    Holger



  • @Lutex sagte in Lambda-Funktion in std::qsort:

    Ich verstehe gerade nicht, was er hier für ein Problem mit dem Capture-Parameter hat.

    [expr.prim.lambda.closure]/7:

    The closure type for a non-generic lambda-expression with no lambda-capture whose constraints (if any) are satisfied has a conversion function to pointer to function with C++ language linkage having the same parameter and return types as the closure type's function call operator. [...]

    Umkehrschluss: Mit lambda-capure gibts keine Conversion in einen Function Pointer.

    Nimm std::sort().


  • Mod

    Bevor man sich darüber Gedanken macht, was genau diesen speziellen Fehler auslöst: Da ist ja alles falsch, was falsch sein könnte! Daher lieber gleich richtig machen, anstatt versuchen, den Fehler weg zu hacken.

    Die Vergleichsfunktion bekommt keine Indizes übergeben, sondern die Werte. Daher ist der ganze Ansatz mit dem Capturing falsch. Und daher funktioniert dein zweiter Ansatz auch.

    Aber: Wieso std::qsort statt des intuitiverem std::sort? Wieso dynamischer Speicher für statische Felder? Und wenn schon dynamischer Speicher dann bitte mit std::vector, niemals mit new! Das Problem löst sich wahrscheinlich ganz von alleine, wenn du vector und sort benutzt. Dann brauchst du auch gar keine eigene Vergleichsfunktion, denn der Vergleich mittels < ist dort schon Standard (und die anderen üblichen Vergleichsfunktionen sind recht trivial übergebbar, da schon vordefiniert in functional)

    Zusammengefasst: Du mischt irgendwie C (qsort) mit Java (dein Objekthandling), aber das ergibt kein C++. Mit C++ wäre das nicht passiert.



  • @SeppJ sagte in Lambda-Funktion in std::qsort:

    Die Vergleichsfunktion bekommt keine Indizes übergeben, sondern die Werte.

    Mein Verständnis war, daß er die Werte in indices nach den Werten in myarray sortieren will, nicht myarray selbst.


  • Mod

    @Swordfish sagte in Lambda-Funktion in std::qsort:

    @SeppJ sagte in Lambda-Funktion in std::qsort:

    Die Vergleichsfunktion bekommt keine Indizes übergeben, sondern die Werte.

    Mein Verständnis war, daß er die Werte in indices nach den Werten in myarray sortieren will, nicht myarray selbst.

    Ahh! Jetzt macht so einiges mehr Sinn.

    Nun, da das tatsächlich ein bisschen weniger trivial ist als nur std::sort aufzurufen machen wir es mal vor, wie es richtig geht:

    #include <algorithm>
    #include <iostream>
    #include <numeric>
    #include <vector>
    using namespace std;
    
    int main() {
    	vector<int> values = {7, 5, 8, 2, 6, 8, 10};
    	vector<int> indices(values.size());
    	iota(indices.begin(), indices.end(), 0);
    	cout << "vorher:\n";
    	for (auto i: indices)
    		cout << i << '(' << values[i] << ") ";
    	
    	std::sort(indices.begin(), indices.end(), 
                      [values](int a, int b) {return values[a] < values[b];}  );
    	
    	cout << "\nnachher:\n";
    	for (auto i: indices)
    		cout << i << '(' << values[i] << ") ";
    	
    	return 0;
    }
    

    Wie man sieht, ist nicht das Capture an sich problematisch, man muss es nur richtig machen. Man notiere auch den Vector und die Nutzung dazu passender Behilfsfunktionen für fehlerfreie und ausdrucksstarke Programmierung. Ohne das viele Rauschen für Casting von void und das Interface von qsort ist auch unmittelbar klar, was der Vergleichsausdruck erreichen soll.
    PS: https://ideone.com/6Sqgfo



  • @SeppJ sagte in Lambda-Funktion in std::qsort:

    Wie man sieht, ist nicht das Capture an sich problematisch, man muss es nur richtig machen.

    Würde man nicht [&values] capturen statt den vector zu kopieren?


  • Mod

    @wob sagte in Lambda-Funktion in std::qsort:

    @SeppJ sagte in Lambda-Funktion in std::qsort:

    Wie man sieht, ist nicht das Capture an sich problematisch, man muss es nur richtig machen.

    Würde man nicht [&values] capturen statt den vector zu kopieren?

    Ja, das wär 'ne Idee 🙂



  • Dann machst Du noch

    @SeppJ sagte in Lambda-Funktion in std::qsort:

    using namespace std;
    

    weg und alles wird gut.



  • Warum? Damit der Code dann so mit std:: verunstaltet und unleserlich ist, wie in deinem Code .txt Datei einlesen und in Vectoren speichern???



  • Ok, vielen Dank für die Erläuterungen. Das Beispiel mit std::qsort und Lambda-Funktion (ohne Capture) steht so sogar auf [https://en.cppreference.com/w/cpp/algorithm/qsort] . Mir war nicht klar, dass das hier nur für den Spezialfall ohne Capturing funktioniert, die Verwendung der Lambda-Syntax im Beispiel statt eines "normalen" C-Funktionspointers ist da schon verwirrend.
    Diese Einschränkung betrifft dann also alle Funktionen, die ursprünglich von C kommen und in <cstdlib> statt <algorithm> stehen?


  • Mod

    Um das mal genauer zu erklären: Ein Lambda ohne Capture ist nur eine ganz normale Funktion, die mit etwas anderer Syntax definiert wurde und keinen Namen hat. Daher gibt es eine ganz natürliche und automatische Konvertierung von solchen Lambdas hin zu einem Zeiger auf diese Funktion.

    Ein Lambda mit Capture ist hingegen ein funktionsartiges Objekt. Das trägt einen inneren Zustand (nämlich den Kontext, den es captured). Ein Verweis auf solch ein Lambda kann kein einfacher Funktionszeiger mehr sein, denn es muss sowohl irgendwie der Code als auch sein Kontext referenziert werden, wenn man das Lambda aufrufen möchte. Früher hat man solche funktionsartigen Objekte oft "Functor" genannt, aber heutzutage ist das halt einfach ganz normal und selbstverständlich in C++, dass Funktionen auch funktionsartige Objekte sein können, daher ist es lange her, dass ich jemanden gehört habe, der auf die Unterscheidung Wert legt. .

    Bei der C-Schnittstelle von qsort ist diese Unterscheidung dann aber doch wichtig. Denn die kann nur C-Funktionszeiger und ist überfordert mit allem was anders ist. Daher hat man früher auch mehr von Functors geredet, weil es da noch häufiger solche Schnittstellen gab und es noch neu war, dass man einer modernen Schnittstelle auch etwas anderes mitgeben kann. Entsprechend kommt std::sort damit ganz selbstverständlich klar, man muss nichts spezielles dafür tun, siehe mein Code.

    Du darfst davon ausgehen, dass alle der C-Funktionen solche Macken haben, wenn es um Zusammenarbeit mit C++ geht. Die sind zur Abwärtskompatibilität da, und sollten andernfalls nicht benutzt werden. Wenn man sich ganz genau auskennt, dann kann man ihnen vorsichtig beibringen, mit ausgewählten C++-Strukturen zusammen zu arbeiten. Hier hast du versucht, einen Vector zu sortieren, und das hätte auch funktioniert. Ich hoffe, du weißt auch warum das funktioniert hätte, denn zum Beispiel eine deque (die nahezu das gleiche Interface hat wie ein vector) hätte nicht funktioniert. Und auch ein Lambda hätte funktioniert, solange es kein Capture gehabt hätte.



  • @Lutex sagte in Lambda-Funktion in std::qsort:

    Diese Einschränkung betrifft dann also alle Funktionen, die ursprünglich von C kommen und in <cstdlib> statt <algorithm> stehen?

    Um es noch mehr auf den Punkt zu bringen: Alle Funktionen (egal woher) die "nur" einen Function Pointer nehmen kannst Du nicht mit einem Lambda füttern das captured (grausiges Wort).



  • Ok, jetzt hab ich's verstanden. Herzlichen Dank nochmal für Eure Mühe!



  • @Swordfish

    ... captured (grausiges Wort)

    Du kannst ja "kapturieren" statt dessen verwenden 😆


Log in to reply