Comparator-Vertrag für std::map / std::set

1. Warum map/set einen Comparator braucht

Wenn Sie zuvor einen Comparator als „Ding zum Sortieren“ angesehen haben, dann ist seine Rolle in map/set deutlich gewichtiger. Diese Container speichern Elemente in geordneter Form: intern halten sie eine Suchbaum-ähnliche Datenstruktur. Genau der Comparator sagt dem Baum, wohin er beim Suchen oder Einfügen „abbiegen“ soll: nach links oder nach rechts.

Die offizielle Spezifikation der Standardbibliothek formuliert das so, dass die Elemente des Containers bezüglich des comp (Vergleichers) sortiert sind. Sogar der Ausdruck „sorted with respect to comp“ taucht in den Formulierungen zu assoziativen Containern auf.

Praktische Konsequenz: der Comparator ist keine „Formatierungsoption“, sondern ein Teil der Logik der Korrektheit. Ein falscher Comparator verwandelt den Baum in ein Labyrinth, in dem Schilder „rechts zum Ausgang“ manchmal gegen eine Wand führen.

std::sort vs std::set: Ordnung und Einzigartigkeit

Hier ein wichtiger Punkt, der oft verwechselt wird. Beim Sortieren sind „Duplikate“ zulässig: man kann einen Vektor so sortieren, dass zwei verschiedene Elemente gemäß Comparator „äquivalent“ sind (z. B. Strings gleicher Länge). Der std::vector bricht deswegen nicht zusammen: er erhält einfach eine der gültigen Ordnungen.

Bei std::set (und bei std::map bezüglich des Schlüssels) definiert der Comparator nicht nur die Ordnung, sondern auch das Kriterium, ob der Container zwei Schlüssel als „gleich“ betrachtet. In den Dokumenten und Diskussionen des Standards wird dafür der Begriff „equivalent keys“ (äquivalente Schlüssel) verwendet.

In der „Schulformel“ wird das üblicherweise so erklärt:

Die Schlüssel `a` und `b` gelten für `map/set` als äquivalent, wenn gleichzeitig
`comp(a, b) == false` und `comp(b, a) == false`.

Der Container fragt also nicht nach a == b. Er fragt: „Ist es wirklich so, dass weder a kleiner als b noch b kleiner als a?“

Warum ist das so? Weil der Suchbaum mit der Logik „kleiner/größer“ arbeitet, und genau diese versteht er am besten.

2. Strict weak ordering: der Vertrag des Comparators

Der Begriff strict weak ordering klingt wie ein Zauberspruch aus der Akademie der Zauberer, in der Praxis ist es jedoch eine Menge gesunder Regeln, die den Vergleich „wie ein normales <“ aussehen lassen.

Um nicht in Formalismen zu versinken, fassen wir die Bedeutung durch drei Ideen zusammen: Strenge, Konsistenz und angemessene Äquivalenz.

Nachfolgend eine nützliche „Spickzettel“-Tabelle. Sie ersetzt nicht den Standard, erklärt aber gut, warum manche Comparatoren jahrelang funktionieren und andere bis zum ersten Deadlinedrama.

Und hier erscheint eine nützliche alltagsnahe Interpretation.

Stellen Sie sich vor, der Comparator ist ein Drehkreuz, das entscheidet, wen es „zuerst“ in die Warteschlange lässt. Strict weak ordering bedeutet: das Drehkreuz darf seine Stimmung nicht ändern, darf eine Person nicht „vor sich selbst“ einordnen und darf keine Zyklen erzeugen wie „A vor B, B vor C, C vor A“. Sonst wird die Schlange zur Küchenstreiterei: „Nein, du zuerst!“, „Nein, du!“, „Ich wohne sowieso im anderen Haus“.

4. Wie man set kaputtmacht: Mini-Beispiele

Jetzt folgen einige kurze Beispiele. Sie sind bewusst klein gehalten, damit Sie die Idee mit den Augen erfassen und nicht in Infrastruktur ertrinken.

Anti-Pattern: <= statt < verwenden

Wichtig: der Comparator für set/map muss die Frage „strictly less?“ beantworten. Daher ist <= fast immer ein Fehler.

#include <set>

struct BadCompare {
    bool operator()(int a, int b) const {
        return a <= b; // Fehler: a <= a ist true
    }
};

int main() {
    std::set<int, BadCompare> s;
    s.insert(1);
    s.insert(2);
}

Warum ist das schlecht? Weil bei a == a der Comparator sagt „ja, a ist kleiner als a“. Das bricht die Strenge: comp(x, x) muss false sein.

„Verkleben“ verschiedener Schlüssel: Vergleich nur nach einem Datenbestandteil

Angenommen, wir wollen Strings in einem set speichern, aber „nach Länge sortieren“. Klingt logisch… bis man zwei verschiedene Strings gleicher Länge einfügt.

#include <set>
#include <string>

struct ByLenOnly {
    bool operator()(const std::string& a, const std::string& b) const {
        return a.size() < b.size(); // kein Tie-Breaker
    }
};

int main() {
    std::set<std::string, ByLenOnly> s;
    s.insert("cat");
    s.insert("dog"); // wird nicht hinzugefügt: äquivalent zu "cat" nach Comparator
}

Der Container betrachtet hier "cat" und "dog" als äquivalent, weil keine der beiden kürzer ist. Und er erfüllt ehrlich den Vertrag des set: er speichert eindeutige Elemente… nach seiner eigenen Definition von Einzigartigkeit.

Richtige Variante: Tie-Breaker hinzufügen

Ein Tie-Breaker ist ein Ausweichkriterium, das greift, wenn das Hauptkriterium „unentschieden“ ergibt. Im String-Beispiel: zuerst nach Länge vergleichen, und falls die Längen gleich sind, lexikografisch vergleichen.

#include <set>
#include <string>

struct ByLenThenLex {
    bool operator()(const std::string& a, const std::string& b) const {
        if (a.size() != b.size()) return a.size() < b.size();
        return a < b; // Tie-Breaker
    }
};

int main() {
    std::set<std::string, ByLenThenLex> s;
    s.insert("cat");
    s.insert("dog"); // wird jetzt hinzugefügt
}

5. Interne Logik von set: Einfügen und Prüfung des Comparators

Wie set beim Einfügen „denkt“

Um zu verstehen, warum der Comparator so wichtig ist, hilft es sich vorzustellen, dass das set Ihrem Comparator bei jedem Einfügevorgang viele Fragen stellt: „Ist das links oder rechts?“.

flowchart TD
    A["insert(x)"] --> B["wir vergleichen mit dem aktuellen Knoten y"]
    B --> C{"comp(x, y)?"}
    C -->|ja| L["gehen in den linken Teilbaum"]
    C -->|nein| D{"comp(y, x)?"}
    D -->|ja| R["gehen in den rechten Teilbaum"]
    D -->|nein| E["äquivalent => wir nehmen an, der Schlüssel ist bereits vorhanden"]

Gerade dieser dritte Fall — „beide Male false“ — ist der Grund, warum ein Tie-Breaker Ihre Daten vor „zufälligem Verschwinden“ bewahrt.

Wie man den Comparator auf Tauglichkeit prüft

Beim Schreiben eines Comparators möchte man gerne einen einfachen „Gesunden Menschenverstand“-Check. Formale Beweise verlangt keiner, aber ein paar praktische Prüfungen retten oft.

Ein guter Anfang sind drei Fragen an konkrete Werte:

Erstens: „Kann comp(x, x) jemals true zurückgeben?“ Wenn ja — sehr wahrscheinlich ein Fehler (oft wegen <=).

Zweitens: „Wenn ich zwei verschiedene Objekte a und b habe, kann es passieren, dass comp(a, b) und comp(b, a) beide false sind?“ Wenn ja — das ist nicht immer ein Fehler, aber Sie sollten bewusst entscheiden: ‚Ja, ich möchte, dass diese Schlüssel äquivalent sind.‘ Wenn Sie das nicht wollen — fügen Sie einen Tie-Breaker hinzu.

Drittens: „Kann der Comparator einen Zyklus erzeugen?“ Zum Beispiel vergleichen Sie Strings nach a[0] < b[0], aber bei leeren Strings machen Sie einen merkwürdigen Hack. Zyklen entstehen oft aus Sonderfällen, die der Hauptlogik widersprechen.

6. Der Comparator muss „sauber“ sein

Es ist verlockend, einen „intelligenten“ Comparator zu implementieren: etwa je nach globaler Flagge mal aufsteigend, mal absteigend sortieren. Bei normaler Sortierung ist das bereits riskant, aber manchmal noch zu umgehen. In set/map ist das fast garantiert katastrophal.

Das Problem: der Baum wird nach einer festen Ordnung aufgebaut. Wenn der Comparator „unterwegs die Schuhe wechselt“, hat der Baum keinen Mechanismus, sich selbst neu aufzubauen. Er denkt weiter, dass „links/rechts“ eine bestimmte Bedeutung hat, während der Comparator plötzlich etwas anderes behauptet.

Mini-Anti-Beispiel (nicht so machen):

#include <set>

bool g_reverse = false;

struct WeirdCompare {
    bool operator()(int a, int b) const {
        if (!g_reverse) return a < b;
        return b < a; // die Ordnung wurde "on the fly" gewechselt
    }
};

int main() {
    std::set<int, WeirdCompare> s;
    s.insert(1);
    s.insert(2);

    g_reverse = true; // jetzt ist der Comparator "eine andere Person"
}

Die Regel ist einfach: ein Container lebt mit genau einer festen Ordnung.

7. Beispiel: Aufgaben nach Priorität in std::set

Wir machen eine praktische Verbindung zu unserer kleinen Übungsanwendung. Angenommen, wir haben ein einfaches Aufgabenmodell: id, title, priority. Früher konnten wir Aufgaben in einem std::vector speichern und beim Ausgeben sortieren. Jetzt möchten wir, dass die Aufgaben immer „nach Priorität“ verfügbar sind, ohne jedes Mal neu zu sortieren.

Dazu verwenden wir std::set, aber wichtig: wenn wir nur priority vergleichen, „verkleben“ alle Aufgaben mit gleicher Priorität. Deshalb fügen wir einen Tie-Breaker anhand der id hinzu.

Modell und Comparator

#include <string>

struct Task {
    int id{};
    std::string title;
    int priority{}; // je kleiner, desto wichtiger
};

struct TaskByPriority {
    bool operator()(const Task& a, const Task& b) const {
        if (a.priority != b.priority) return a.priority < b.priority;
        return a.id < b.id; // Tie-Breaker: verschiedene Aufgaben nicht verkleben
    }
};

Beachten Sie: wir haben den Comparator deterministisch und „streng“ gemacht. Er benutzt nicht <=, und bei a == a liefert er false.

Aufgaben in std::set speichern und „in Prioritätsreihenfolge“ ausgeben

#include <iostream>
#include <set>

int main() {
    std::set<Task, TaskByPriority> tasks;

    tasks.insert(Task{1, "Write report", 2});
    tasks.insert(Task{2, "Fix bug", 1});
    tasks.insert(Task{3, "Buy coffee", 2});

    for (const auto& t : tasks) {
        std::cout << t.priority << " | " << t.id << " | " << t.title << '\n';
        // 1 | 2 | Fix bug
        // 2 | 1 | Write report
        // 2 | 3 | Buy coffee
    }
}

Hier werden zwei Dinge deutlich. Erstens: die Reihenfolge wird wirklich vom Comparator bestimmt. Zweitens: Aufgaben mit priority == 2 existieren beide im Container, weil der Tie-Breaker sie anhand der id unterscheidet.

Detail: warum Elemente im set „wie const“ wirken

Wenn Sie versuchen, über ein set zu iterieren und bei einem Element die priority zu ändern, wird der Compiler Ihnen das höchstwahrscheinlich nicht erlauben. Das liegt nicht an der Bosheit der Sprache, sondern daran, dass das Ändern eines feldes, das an der Ordnung beteiligt ist, den Baum zerstört.

Die Logik ist simpel: wenn ein Element „links“ stand und nach der Änderung „rechts“ stehen sollte, merkt der Baum das nicht automatisch. Daher schützt sich das set: die Schlüssel im Inneren kann man nicht direkt ändern.

Wenn Sie die Priorität ändern müssen, ist die korrekte Strategie, die alte Version zu entfernen und eine neue einzufügen (oder die Quelle der Wahrheit separat zu halten und im set nur Schlüssel/Indizes zu speichern — aber das ist ein großes Thema für sich).

8. Typische Fehler beim Schreiben von Comparators für map/set

Fehler Nr.1: <= oder >= statt striktem < verwenden.
Das ist das häufigste Problem: es scheint sicherer, weil man so auch Gleiches berücksichtigt. Aber der Comparator in set/map muss genau auf „strictly less“ antworten. Wenn comp(x, x) true wird, bricht man das grundlegende Prinzip der strict weak ordering, und der Container ist zu nichts mehr verpflichtet.

Fehler Nr.2: denken, Einzigartigkeit der Schlüssel wird durch operator== bestimmt.
Nach Vektoren und std::find ist man an die vertraute Gleichheit gewöhnt. Aber set/map leben vom „kleiner“-Vergleich. Wenn der Comparator zwei verschiedene Schlüssel nicht unterscheidet (beide Vergleiche ergeben false), dann betrachtet der Container sie als äquivalent. Das ist nicht falsch — man muss es sich nur bewusst machen. Der Begriff „equivalent keys“ taucht im Standardkontext assoziativer Container auf.

Fehler Nr.3: nur nach einem Feld vergleichen und dadurch versehentlich verschiedene Schlüssel „verkleben“.
Ein sehr typisches Szenario: man sortiert nach dem „Hauptkriterium“ (z. B. Priorität) und vergisst die anderen Felder. Am Ende „verliert“ das set Elemente beim Einfügen. Die Lösung ist fast immer dieselbe: fügen Sie einen Tie-Breaker hinzu (meistens nach id oder einem zweiten Feld).

Fehler Nr.4: den Comparator abhängig von externem veränderbarem Zustand machen.
Ein Comparator, der ein globales Flag „auf-/absteigend“ liest, wirkt praktisch. Aber der Baum wurde unter einer Ordnung aufgebaut, und ein Wechsel der Vergleichslogik mittendrin macht die Datenstruktur widersprüchlich. Der Container kann anfangen, Dinge nicht mehr zu finden, die eigentlich vorhanden sind.

Fehler Nr.5: Seiteneffekte im Comparator einbauen.
Manchmal will man „sehen, wie oft der Comparator aufgerufen wird“ und greift zu std::cout oder inkrementiert einen Zähler. Das ist gefährlich: Vergleiche werden häufig und zu unerwarteten Zeitpunkten aufgerufen, und die Reihenfolge der Aufrufe ist nicht garantiert „schön“. Der Comparator sollte so rein wie möglich sein: vergleichen — antworten — fertig.

Fehler Nr.6: versuchen, Schlüssel im set inplace zu ändern.
In einem set kann man Elemente de facto nicht einfach so ändern: das Ändern von Feldern, die an der Vergleichsoperation beteiligt sind, zerstört die Ordnung des Baums. Wenn Sie Priorität oder Namen ändern müssen, ist meist das Entfernen des Elements und Einfügen einer neuen Version die richtige Vorgehensweise. Die Idee, dass assoziative Container eine Ordnung bezüglich des comp garantieren, ist in ihren Anforderungen verankert.