CKTIS / C++
std::ranges::equal_range — Bereich gleichwertiger Elemente
std::ranges::equal_range findet den halboffenen Bereich der Elemente, die gemäß einem Vergleichsoperator einem Suchwert gleichwertig sind. Unterstützt werden Bereiche, Iterator-Sentinel-Paare und Projektionen; die Daten müssen passend partitioniert sein, was eine Sortierung gewährleistet.
Version: C++23; repository compiler flag, production runtime not attested
Syntax
std::ranges::equal_range(first, last, value)
std::ranges::equal_range(first, last, value, comp)
std::ranges::equal_range(first, last, value, comp, proj)
std::ranges::equal_range(range, value)
std::ranges::equal_range(range, value, comp)
std::ranges::equal_range(range, value, comp, proj)std::ranges::equal_range aus <algorithm> bestimmt den Bereich [lower_bound, upper_bound), ohne die Daten zu verändern. Gleichwertigkeit bedeutet, dass beide Vergleiche comp(proj(element), value) und comp(value, proj(element)) falsch sind; sie muss nicht mit operator== übereinstimmen. Gibt es keinen Treffer, ist das Ergebnis ein leerer Bereich an der Einfügeposition des Werts.
Der Aufruf akzeptiert entweder ein Iterator-Sentinel-Paar oder einen vollständigen Bereich. Erforderlich sind mindestens Forward-Iteratoren, und comp muss die Anforderungen an eine strikte schwache Ordnung erfüllen. Die Standardwerte sind std::ranges::less und std::identity. Die Projektion transformiert Elemente, nicht den Suchwert. Die Daten müssen so partitioniert sein, dass die booleschen Ergebnisse jedes Ausdrucks comp(proj(element), value) und !comp(value, proj(element)) zuerst einen wahren Präfix und danach einen falschen Suffix bilden. Eine Sortierung mit demselben Vergleichsoperator und derselben Projektion genügt; eine Verletzung der Vorbedingungen führt zu undefiniertem Verhalten.
Die Iterator-Überladung gibt std::ranges::subrange<I> zurück, die Bereichs-Überladung std::ranges::borrowed_subrange_t<R>. Bei einem temporären Bereich, der borrowed_range nicht erfüllt, ist der letztere Typ std::ranges::dangling und kein verwendbarer Unterbereich. Das Ergebnis speichert keine Elementkopien: Die Daten müssen weiter existieren und ihre Iteratoren gültig bleiben.
Für N Elemente gibt es höchstens 2 * log2(N) + O(1) Vergleiche und Projektionen; ohne Iteratoren mit wahlfreiem Zugriff kann die Anzahl der Iteratorbewegungen linear sein. Das Beispiel sucht Schlüssel über &Item::key: Drei Treffer liegen an den Indizes [1, 4), während Schlüssel 3 ein leeres Ergebnis liefert. Das Beispiel ist für eine C++23-Build-Konfiguration vorgesehen; die Laufzeitkompatibilität in Produktionsumgebungen ist nicht bestätigt.
Beispiele
#include <algorithm>
#include <array>
#include <iostream>
struct Item {
int key;
};
int main() {
const std::array<Item, 5> items{{{1}, {2}, {2}, {2}, {4}}};
const auto matches = std::ranges::equal_range(items, 2, {}, &Item::key);
std::cout << "count=" << matches.size() << '\n';
std::cout << "begin=" << (matches.begin() - items.begin()) << '\n';
std::cout << "end=" << (matches.end() - items.begin()) << '\n';
const auto missing = std::ranges::equal_range(items, 3, {}, &Item::key);
std::cout << "missing=" << missing.empty() << '\n';
}
Ergebnis
count=3 begin=1 end=4 missing=1
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.