WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C++

std::stable_sort — stabile Sortierung

std::stable_sort sortiert einen Bereich und bewahrt dabei die relative Reihenfolge von Elementen, die gemäß dem Vergleich gleichwertig sind. So lassen sich Datensätze nach einem Schlüssel ordnen, ohne die bisherige Reihenfolge von Datensätzen mit demselben Schlüssel zu ändern.

Version: C++23; repository compiler flag, production runtime not attested

Syntax

#include <algorithm>

std::stable_sort(first, last);
std::stable_sort(first, last, comp);

std::stable_sort aus <algorithm> ordnet die Elemente im Bereich [first, last) um und gibt void zurück. Die Überladung ohne comp sortiert mit dem Standardvergleich aufsteigend; die Überladung mit comp verwendet den angegebenen Komparator. Anders als std::sort garantiert die Funktion, dass die relative Reihenfolge gleichwertiger Elemente erhalten bleibt.

Gleichwertigkeit bedeutet !comp(a, b) && !comp(b, a), nicht unbedingt a == b. Der Komparator muss eine strikte schwache Ordnung definieren: Insbesondere muss comp(x, x) falsch sein, und sowohl die Ordnung als auch die daraus abgeleitete Gleichwertigkeit müssen transitiv sein. Verwende nicht <= anstelle von < und verändere die verglichenen Elemente nicht.

Erforderlich sind Iteratoren mit wahlfreiem Zugriff sowie Elemente, die Tausch, Move-Konstruktion und Move-Zuweisung unterstützen. Für N = last - first beträgt die Anzahl der Vergleiche O(N log N), wenn ausreichend zusätzlicher Speicher verfügbar ist; andernfalls beträgt sie höchstens O(N log² N). Die Sortierung verändert die Eingabe, garantiert aber keinen konstanten Hilfsspeicherbedarf.

Im Beispiel wird nur key verglichen: B bleibt vor D und A vor C. Das Beispiel ist für die Ausführung mit einem C++23-Compiler-Flag vorgesehen. Der gezeigte Code wurde unverändert in einer isolierten Umgebung ausgeführt, und seine Ausgabe stimmte mit der angegebenen Ausgabe überein. Diese Prüfung bestätigt nicht die Kompatibilität mit der Laufzeitumgebung im Produktivbetrieb. Der verknüpfte aktuelle Arbeitsentwurf kann Erweiterungen enthalten, die über C++23 hinausgehen; die gezeigten Aufrufe benötigen sie nicht.

Beispiele

#include <algorithm>
#include <iostream>
#include <vector>

struct Item {
    int key;
    char id;
};

int main() {
    std::vector<Item> items{{2, 'A'}, {1, 'B'}, {2, 'C'}, {1, 'D'}};

    std::stable_sort(items.begin(), items.end(),
        [](const Item& a, const Item& b) {
            return a.key < b.key;
        });

    for (const Item& item : items) {
        std::cout << item.key << ' ' << item.id << '\n';
    }
}

Ergebnis

1 B
1 D
2 A
2 C

Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.

Quellen