Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

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.

Źródła