Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

CKTIS / C++

std::ranges::equal_range — rozsah ekvivalentních prvků

std::ranges::equal_range najde polouzavřený rozsah prvků ekvivalentních hledané hodnotě podle komparátoru. Podporuje rozsahy, dvojice iterátor–sentinel a projekce; data musejí být vhodně rozdělena, což zajišťuje jejich seřazení.

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

Syntaxe

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 deklarované v <algorithm> určí rozsah [lower_bound, upper_bound) bez změny dat. Ekvivalence znamená, že obě porovnání comp(proj(element), value) a comp(value, proj(element)) jsou nepravdivá; nemusí odpovídat operator==. Pokud žádná shoda neexistuje, výsledkem je prázdný rozsah na pozici, kam by se hodnota vložila.

Volání přijímá dvojici iterátor–sentinel nebo celý rozsah. Jsou vyžadovány alespoň forward iterátory a comp musí splňovat požadavky na striktní slabé uspořádání. Výchozí hodnoty jsou std::ranges::less a std::identity. Projekce transformuje prvky, nikoli hledanou hodnotu. Data musejí být rozdělena tak, aby booleovské výsledky každého z výrazů comp(proj(element), value) a !comp(value, proj(element)) tvořily nejprve pravdivý prefix a poté nepravdivý suffix. Seřazení pomocí stejného komparátoru a projekce stačí; porušení předpokladů vede k nedefinovanému chování.

Varianta s iterátory vrací std::ranges::subrange<I>, zatímco varianta s rozsahem vrací std::ranges::borrowed_subrange_t<R>. U dočasného rozsahu, který nesplňuje borrowed_range, je druhý typ std::ranges::dangling, nikoli použitelný podrozsah. Výsledek neukládá kopie prvků: data musejí nadále existovat a jejich iterátory musejí zůstat platné.

Pro N prvků je nejvýše 2 * log2(N) + O(1) porovnání a projekcí; bez iterátorů s náhodným přístupem může být počet posunů iterátorů lineární. Příklad hledá klíče přes &Item::key: tři shody mají indexy [1, 4), zatímco klíč 3 vrátí prázdný výsledek. Příklad je určen pro konfiguraci sestavení C++23; kompatibilita běhu v produkčním prostředí není potvrzena.

Příklady

#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';
}

Výsledek

count=3
begin=1
end=4
missing=1

Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.

Zdroje