CKTIS / C++
std::ranges::equal_range — przedział równoważnych elementów
std::ranges::equal_range znajduje półotwarty przedział elementów równoważnych szukanej wartości według komparatora. Obsługuje zakresy, parę iterator–wartownik i projekcje; wymaga odpowiedniego podziału danych, który zapewnia ich posortowanie.
Wersja: C++23; repository compiler flag, production runtime not attested
Składnia
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 z nagłówka <algorithm> wyznacza przedział [lower_bound, upper_bound) bez zmiany danych. Równoważność oznacza, że oba porównania comp(proj(element), value) i comp(value, proj(element)) są fałszywe; nie wymaga zgodności z operator==. Gdy nie ma dopasowania, wynik jest pustym przedziałem w miejscu wstawienia wartości.
Dostępne są wywołania z parą iterator–wartownik oraz z całym zakresem. Wymagane są co najmniej iteratory typu forward, a comp musi spełniać wymagania ścisłego słabego porządku. Domyślne argumenty to std::ranges::less i std::identity. Projekcja przekształca elementy, nie szukaną wartość. Dane muszą być podzielone tak, by wartości logiczne każdego z wyrażeń comp(proj(element), value) oraz !comp(value, proj(element)) tworzyły najpierw część prawdziwą, potem fałszywą. Posortowanie według tego samego komparatora i projekcji wystarcza; naruszenie warunków wstępnych powoduje niezdefiniowane zachowanie.
Wariant iteratorowy zwraca std::ranges::subrange<I>, a zakresowy — std::ranges::borrowed_subrange_t<R>. Dla tymczasowego zakresu, który nie spełnia borrowed_range, ten drugi typ to std::ranges::dangling, nie użyteczny podzakres. Wynik nie przechowuje kopii elementów: dane muszą nadal istnieć, a iteratory pozostać ważne.
Dla N elementów liczba porównań i projekcji wynosi najwyżej 2 * log2(N) + O(1); bez iteratorów swobodnego dostępu liczba przesunięć iteratorów może być liniowa. Przykład wyszukuje klucz przez &Item::key: trzy dopasowania zajmują indeksy [1, 4), a klucz 3 daje pusty wynik. To przykład dla konfiguracji kompilacji C++23; zgodność środowiska produkcyjnego nie została potwierdzona.
Przykłady
#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';
}
Wynik
count=3 begin=1 end=4 missing=1
Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.