WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C++

Sortieren, Vergleiche und Suchbereiche

Korrektes Sortieren erfordert einen Komparator, der eine strikte schwache Ordnung definiert. Für die binäre Suche muss ein Bereich bezüglich der jeweiligen Bedingung partitioniert sein; den gesamten Bereich zu sortieren ist ausreichend, aber nicht immer notwendig.

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

Syntax

std::sort(first, last, comp);
std::lower_bound(first, last, value, comp);

std::sort aus <algorithm> ordnet den halboffenen Bereich [first, last) mit comp: Kein späteres Element steht vor einem früheren. Erfordert werden Random-Access-Iteratoren sowie Elemente, die die Anforderungen an Verschieben und Tauschen erfüllen. Es werden O(N log N) Vergleiche ausgeführt. Die Reihenfolge gleichwertiger Elemente bleibt nicht garantiert erhalten; dafür dient std::stable_sort.

Der Komparator muss eine strikte schwache Ordnung definieren. comp(a, b) bedeutet, dass a vor b steht, und comp(a, a) muss false ergeben. Die Relation muss transitiv sein. Auch die durch !comp(a, b) && !comp(b, a) definierte Gleichwertigkeit muss transitiv sein und muss nicht mit operator== übereinstimmen. Verwende nicht <=: Bei identischen Argumenten verletzt es die Anforderung. Werden die Komparatoranforderungen nicht erfüllt, gelten die Garantien des Algorithmus nicht.

Strikte schwache Ordnung und partitionierte Suchbereiche sind miteinander verbunden, aber unterschiedliche Anforderungen. Bei einem bezüglich eines Prädikats partitionierten Bereich liefern zuerst alle Elemente true, danach alle false; einer der Teile kann leer sein. Für std::lower_bound(first, last, value, comp) lautet das Prädikat comp(e, value). Die Funktion gibt die Grenze zurück: das erste Element mit Ergebnis false oder last. Damit ist nicht festgestellt, ob der gesuchte Wert vorhanden ist; dereferenziere last nicht.

Sortieren mit derselben Ordnung gewährleistet diese Partition für jeden Schlüssel. Für einen einzelnen Schlüssel genügt die Partitionierung allein: [2, 1, 4, 3] erfüllt für value = 3 und den Vergleich < die Vorbedingung von std::lower_bound, obwohl der Bereich nicht sortiert ist. Andere Binärsuchfunktionen haben eigene Partitionsanforderungen. std::lower_bound führt O(log N) Vergleiche aus, kann aber ohne Random-Access-Iteratoren eine lineare Anzahl von Iteratorschritten benötigen.

Das Beispiel sortiert Ganzzahlen und verwendet anschließend dasselbe comp, um Index 3 zu erhalten. Der Inhalt zielt auf C++23; der angegebene Verweis führt zu einem fortlaufend bearbeiteten Arbeitsentwurf, nicht zu einer festgeschriebenen C++23-Veröffentlichung. Die Unterstützung durch Compiler und Produktionslaufzeit ist nicht bestätigt.

Beispiele

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

int main() {
    std::vector<int> values{4, 1, 3, 1, 2};
    const auto comp = [](int a, int b) { return a < b; };

    std::sort(values.begin(), values.end(), comp);
    for (std::size_t i = 0; i < values.size(); ++i) {
        if (i != 0) std::cout << ' ';
        std::cout << values[i];
    }
    std::cout << '\n';

    const auto it = std::lower_bound(values.begin(), values.end(), 3, comp);
    std::cout << "index=" << (it - values.begin()) << '\n';
}

Ergebnis

1 1 2 3 4
index=3

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