std::sort Problem mit Reihenfolge



  • Hallo,

    ich hab ein Problem mit einer selbst geschriebenen Sortier-funktion welche momentan nicht das macht was ich will. Und zwar habe ich einen string vektor den ich gerne folgendermaßen sortieren will:

    • Die Elemente bestehen nur aus Zahlen, Buchstaben und/oder underscore
    • Zahlen haben Priorität vor allem, sollen also ganz nach oben sortiert werden
    • Dann Buchstaben
    • Als letztes underscore
    • Die Reihenfolge ist dabei "natürlich", also '1' hat Priorität vor '2' oder 'a' hat Priorität vor 'b'
    • Die Sortierung soll Nicht Case-Sensitiv sein
    • Kürzere Wörter haben Priorität vor längeren Wörtern wenn sie ansonsten exakt übereinstimmen

    Bis auf den letzten Punkt hab ich das auch schon alles hingekriegt. Meine Funktion sieht so aus:

    bool sort_method(const std::string &first, const std::string &second)
    {
    	for (std::string::const_iterator fi = first.begin(), si = second.begin(), efi = first.end(), esi = second.end(); fi != efi && si != esi; ++fi, ++si) {
    		char c_first = tolower(*fi), c_second = tolower(*si); // Case-Insensitive
    
    		// Bewertung des undescore anpassen
    		if (c_first == '_')
    			c_first = 123; 
    		if (c_second == '_')
    			c_second = 123;
    
    		if (c_second > c_first)
    			return true;
    		if (c_second < c_first)
    			return false;
    	}
    	// Hier ist das Problem
    	if (first.size() > second.size())
    		return true;
    	return false;
    }
    

    Als Beispiel Vektor habe ich dann mal sowas:

    Int
    Int2String
    Abs

    Sortiert sollte das Ganze dann so aussehen:

    Abs
    Int
    Int2String

    Leider kommt aber sowas raus:

    Abs
    Int2String
    Int

    Also Wörter die übereinstimmen, aber sich in der Lände unterscheiden wie Int und Int2String werden nicht korrekt sortiert. Daran ändert sich leider auch nichts wenn ich in dem

    if (first.size() > second.size())

    das Größerzeichen umdrehe...

    Was läuft hier schief?



  • struct Comparator
    {
        bool operator()(char c1, char c2) const
        { 
            // Bewertung des undescore anpassen
            if (c1== '_')
                c1 = 123;
            if (c2== '_')
                c2 = 123;
    
            return (tolower(c1)<tolower(c2));
        }
    };
    
    bool sort_method(const std::string &first, const std::string &second)
    {
        return std::lexicographical_compare(first.begin(), first.end(), second.begin(), second.end(), Comparator());
    }
    

    Nicht getestet. Ich hoffe, das ist so alles richtig.



  • Ok, das klappt schonmal, vielen Dank! 👍

    Hab allerdings noch ne Frage, im Debug Mode ist das Sortieren schon extrem langsam... Also da merkt man ein Ruckeln von ca. 1 Sekunde bei jedem Sortiervorgang.

    Im Release Mode ist das Ruckeln weg, aber mich würde trotzdem mal interessieren was hier den Unterschied zwischen Debug und Release macht? Wieso ist der Unterschied hier so krass, das hatte ich bis jetzt noch nicht?



  • Es gibt keinen Debug- oder Releasemodus im C++-Standard. Dein Compiler/Debugger wird sich da wohl einige Dinge genauer ansehen.



  • Wahrscheinlich werden die iterators in jedem Schritt auf Gültigkeit geprüft, während im Release mode manche iteratoren zu pointern optimiert und der Vergleich "geinlined" wird.



  • Marthog schrieb:

    Wahrscheinlich werden die iterators in jedem Schritt auf Gültigkeit geprüft, während im Release mode manche iteratoren zu pointern optimiert und der Vergleich "geinlined" wird.

    Und das macht so viel aus? 😮

    Kann man das irgendwie deaktivieren, das bremst sonst die Entwicklung relativ krass aus...



  • Teste mit reduziertem Datensatz. Dann dauert das auch nicht so lange.



  • happystudent schrieb:

    Marthog schrieb:

    Wahrscheinlich werden die iterators in jedem Schritt auf Gültigkeit geprüft, während im Release mode manche iteratoren zu pointern optimiert und der Vergleich "geinlined" wird.

    Und das macht so viel aus? 😮

    Offenbar. Mehr können wir ohne kompletten Programmcode nicht sagen.

    Kann man das irgendwie deaktivieren, das bremst sonst die Entwicklung relativ krass aus...

    Ja, kann man. Ist aber vom Compiler abhängig.
    Beim gcc reicht imo #define NDEBUG.
    Du willst das aber nicht deaktivieren. Der Debug-Mode ist zur Fehlersuche da, nicht zum eig. Ausführen des Programmes, um damit zu arbeiten. Und sobald du Probleme mit invalidierten Iteratoren kriegst, biste darüber froh.



  • Ok, dann lass ich es mal so und bau mir nen kleineren Debug-Datensatz zusammen. Im Release-Mode läufts ja Gott sei Dank schnell.

    Danke für die Antworten 🙂



  • Dabei ist auch die Frage was du sortieren willst (klar Vectoren von Strings, aber vielleicht kann man das auch etwas eingrenzen).
    Dann könnte man, je nachdem wann und wie du die Daten bekommst und auch wieder benötigst, sich Gedanken über eine andere Datenstruktur machen, z.B. eine Map, Set oder sonstige sortierende Datenstrukturen. Je nachdem halt was du brauchst.

    Denn immer dran denken, Vectoren von Strings zu sortieren ist wie Vectoren von Vectoren zu sortieren. Da geht die Komplexität im Quadrat hoch. Das ist schon recht aufwendig.



  • Skym0sh0 schrieb:

    Denn immer dran denken, Vectoren von Strings zu sortieren ist wie Vectoren von Vectoren zu sortieren. Da geht die Komplexität im Quadrat hoch. Das ist schon recht aufwendig.

    Hm ja, ich werd mir nochmal Gedanken über die Prinzipielle Struktur machen...

    Hab aber gleich noch eine Frage, wie könnte ich in den Ansatz noch einbauen dass der Vergleich bei einem Delimiter aufhört? Also angenommen meine String sehen eigentlich nicht so:

    Abs
    Int
    Int2String

    sondern so aus:

    Abs?2
    Int?22
    Int2String?7

    Ich würde die Sortierung jetzt gerne so einschränken dass nur die Zeichen vor dem Delimiter "?" berücksichtigt werden. Den Iterator einfach auf first.end() - 2 zu setzen geht leider nicht, da die Info-Strings nach dem Delimiter unterschiedlich lang sein können (0 - 255)...


Log in to reply