WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C++

Partitionierter Suchbereich

`std::lower_bound` braucht keinen vollständig sortierten Bereich: Für den gegebenen Suchschlüssel müssen alle Treffer des Tests vor allen übrigen Elementen stehen.

Version: ISO C++23; implementation support may vary

Syntax

#include <algorithm>

std::lower_bound(first, last, key);
std::lower_bound(first, last, key, comp);
std::ranges::lower_bound(first, last, key, comp, proj);
std::ranges::lower_bound(range, key, comp, proj);

// For this key, the predicate must be true for a prefix and false for the rest.
// Classic: bool(comp(element, key))
// Ranges:  bool(std::invoke(comp, std::invoke(proj, element), key))

Ein Suchbereich [first, last) ist bezüglich des Schlüssels partitioniert, wenn bool(comp(element, key)) zuerst nur true und danach nur false ergibt. Beide Abschnitte dürfen leer sein und müssen intern nicht sortiert sein. Das klassische std::lower_bound aus <algorithm> liefert den ersten Iterator, an dem der Test falsch ist, oder last, falls es keinen solchen gibt. Das Ergebnis muss nicht dem Schlüssel entsprechen. Ist die Partitionierungsbedingung verletzt, ist das Verhalten undefiniert.

Die klassische Überladung mit Komparator vergleicht nur in Richtung Element zu Schlüssel. Daher genügt eine Lambda-Funktion [](const Sale& row, int key), die row.sales > key prüft; [] erfasst nichts. std::ranges::lower_bound (seit C++20) akzeptiert ein Iterator-Sentinel-Paar oder einen Bereich. Der Komparator muss für projizierte Elemente und Schlüssel indirect_strict_weak_order erfüllen; mit &Sale::sales werden Ganzzahlen verglichen. Beide Varianten benötigen mindestens Vorwärtsiteratoren und logarithmisch viele Vergleiche, doch ohne wahlfreien Zugriff kann die Zahl der Iteratorschritte linear sein. Die Bereichsüberladung liefert bei einem temporären Bereich, der kein Borrowed Range ist, std::ranges::dangling. Iteratoren am Ende oder ungültig gewordene Iteratoren dürfen nicht dereferenziert werden.

std::nth_element und std::partial_sort benötigen Iteratoren mit wahlfreiem Zugriff und eine strikte schwache Ordnung: comp(x, x) muss falsch sein; sowohl der Vergleich als auch die durch zwei falsche Vergleiche definierte Äquivalenz müssen transitiv sein. Für ganzzahlige Verkaufszahlen erfüllt a.sales > b.sales diese Regeln, >= hingegen nicht. nth_element platziert das Element am gewählten Rang und trennt beide Seiten, ohne sie zwingend zu sortieren. partial_sort sortiert das gewünschte Präfix; die Reihenfolge des Rests ist nicht festgelegt. Keines garantiert eine Partitionierung des gesamten Bereichs für beliebige Schlüssel. Für wiederholte Suchen mit wechselnden Schlüsseln sollte der ganze Bereich nach derselben Ordnung sortiert werden.

Beispiele

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

struct Sale {
    int sales;
};

int main() {
    const std::vector<Sale> rows{{95}, {120}, {70}, {85}, {60}};
    const int key = 90;
    const auto before_key = [](const Sale& row, int key) {
        return row.sales > key;
    };

    const auto classic = std::lower_bound(rows.begin(), rows.end(), key, before_key);
    const auto ranged = std::ranges::lower_bound(rows, key, std::ranges::greater{}, &Sale::sales);

    if (classic != rows.end() && ranged != rows.end()) {
        std::cout << classic->sales << '\n' << ranged->sales << '\n';
    }
}

Ergebnis

70
70

Für `90` geben beide Aufrufe `70` aus, den ersten Wert, der die Schwelle nicht überschreitet. Der Bereich ist dabei nicht absteigend sortiert. Für `100` ergibt `95` bereits `false`, bevor `120` `true` ergibt; deshalb ist keiner der beiden Aufrufe mit `100` auf diesem Bereich zulässig.

Zugehörige Lektionen

  • C++ · Lektion 23 · Fortgeschritten · Version: 3

Quellen