Wörter ordnen

Die Sortierung von Buchstaben und Wörtern ist äußerst sprachabhängig. Zwar sie grundlegend zum Beispiel für alle Sprachen mit dem lateinischen Alphabet gleich, aber selbst da kommen kleine Abweichungen, wie Umlaute oder Buchstaben mit Akzent vor. Zeit mal wieder für eine weitere Facette.

Video

Quelltext

#include <iostream>
#include <locale>
#include <vector>
#include <string>
#include <algorithm>

int main()
{
    std::locale de("de_DE.UTF-8");

    auto &c_c = std::use_facet<std::collate<char>>(std::locale::classic());
    auto &de_c = std::use_facet<std::collate<char>>(de);

    auto w1 = "Hallo";
    auto w2 = "Äh";

    std::cout << "classic: " << c_c.compare(w1, w1+5, w2, w2+2) << std::endl;
    std::cout << "de: " << de_c.compare(w1, w1+5, w2, w2+2) << std::endl;
    
    std::vector<std::string> words { "Die", "Wörter", "werden", "manchmal", 
                                    "unerwartet", "sortiert" };
    std::sort(words.begin(), words.end(), de);
    std::cout << "[";
    for (auto w : words) {
        std::cout << w << ", ";
    }
    std::cout << "]\n";

    std::vector<std::string> words2 { "Die", "Wörter", "werden", "manchmal", 
                                      "unerwartet", "sortiert" };
    std::sort(words2.begin(), words2.end(), std::locale::classic());
    std::cout << "[";
    for (auto w : words2) {
        std::cout << w << ", ";
    }
    std::cout << "]\n";
    
    auto result = de_c.transform(w1, w1+5);
    for (auto c : result) {
        std::cout << static_cast<int>(c) << ", ";
    }
    std::cout << std::endl;
    auto result2 = de_c.transform(w2, w2+2);
    for (auto c : result2) {
        std::cout << static_cast<int>(c) << ", ";
    }
    std::cout << std::endl;
}

Erklärung

Um die sprachabhängige Sortierung von Buchstaben zu kapseln bietet der C++-Standard die Facette std::collate<>. Da es wieder mal um die Verarbeitung von Zeichen geht, ist sie wieder als Template ausgelegt, welches für den passenden Zeichentyp instanziiert werden muss. Das Interface der Facette ist übersichtlich: eine Methode zum Vergleich von Zeichenketten, eine Methode zum Berechnen von Hashes (hier nicht gezeigt) und eine zur Umwandlung in eine besondere Darstellung (dazu später mehr).

Die Methode compare() vergleicht zwei Zeichenketten (gegeben jeweils als Anfangs- und Endpointer) unter den Sortierregeln eingestellten Sprache miteinander. Ähnlich wie das Comparable-Interface in Java liefert sie eine negative Zahl, wenn die erste Zeichenkette vor der zweite einzusortieren wäre, eine positive, wenn sie dahinter käme und 0, wenn beide Zeichenketten gleich sind. Im Beispiel oben wird der Vergleich in Zeile 17 eine negative Zahl liefern (-1 auf meiner Plattform), da die Classic-Locale nur die reinen ASCII (bzw. UTF-8)-Werte der Zeichenketten vergleicht. Unter diesen Bedingungen kommt der Buchstabe H vor dem Ä und damit wird auch das Wort Hallo vor Äh einsortiert. Der Vergleich unterscheidet auch zwischen Groß- und Kleinbuchstaben und sortiert erstere vor letzteren ein (Z kommt also vor a, wie an der Sortierung in Zeile 31 zu sehen ist). Anders hingegen die deutsche Locale: hier wird Ä vor H einsortiert und damit gilt auch Hallo > Äh, compare liefert also eine positive Zahl (1 auf meinem System).

Aus Bequemlichkeitsgründen wird die compare-Schnittstelle vom std::locale-Objekt nochmal verpackt. Dieses definiert einen operator(), ist also ein Funktionsobjekt. Der Operator nimmt zwei Strings und vergleicht diese mittels der in der Locale gespeicherten std::collate<>-Facette. Daher kann das Locale-Objekt als Vergleichsoperator bspw. bei std::sort übergeben werden (vgl. Zeilen 22 und 31).

Eine etwas ungewöhnliche Funktionalität stellt std::collate<>::transform bereit. Diese Funktion wandelt eine übergebene Zeichenkette (wieder als Anfangs- und Endpointer übergeben) in eine implementierungsabhängige Darstellung um, die mittels eine lexikografischen Vergleichs verglichen werden kann. Im Beispiel werden die Wörter Äh und Hallo unter der deutschen Locale umgewandelt. Die resultierenden Zeichenketten liefern beim einfachen lexikografischen (also zeichenweisen) Vergleich das gleiche Ergebnis, wie std::collate<>::compare liefern würde. Auf meinem System beginnt bspw. die Umwandlung von "Hallo" mit dem Wert 19, während "Äh" mit 12 beginnt. Damit ist schon im ersten Zeichen klar, dass Äh vor Hallo einzusortieren ist. Würde die gleiche Umwandlung bspw. unter der classic-Locale stattfinden, wäre das anders (diese muss den Eingabestring unverändert zurückliefern).