Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / C++

std::ranges::equal_range — rozsah ekvivalentných prvkov

std::ranges::equal_range nájde polootvorený rozsah prvkov ekvivalentných hľadanej hodnote podľa komparátora. Podporuje rozsahy, dvojice iterátor–sentinel a projekcie; údaje musia byť vhodne rozdelené, čo zabezpečí ich usporiadanie.

Verzia: 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 deklarované v <algorithm> určí rozsah [lower_bound, upper_bound) bez zmeny údajov. Ekvivalencia znamená, že obe porovnania comp(proj(element), value) a comp(value, proj(element)) sú nepravdivé; nemusia sa zhodovať s operator==. Ak sa nenájde zhoda, výsledkom je prázdny rozsah na pozícii vloženia hodnoty.

Volanie prijíma dvojicu iterátor–sentinel alebo celý rozsah. Vyžadujú sa aspoň forward iterátory a comp musí spĺňať požiadavky na striktné slabé usporiadanie. Predvolené hodnoty sú std::ranges::less a std::identity. Projekcia transformuje prvky, nie hľadanú hodnotu. Údaje musia byť rozdelené tak, aby booleovské výsledky každého z výrazov comp(proj(element), value) a !comp(value, proj(element)) tvorili najprv pravdivý prefix a potom nepravdivý suffix. Usporiadanie pomocou toho istého komparátora a projekcie stačí; porušenie predpokladov spôsobí nedefinované správanie.

Verzia s iterátormi vracia std::ranges::subrange<I>, kým verzia s rozsahom vracia std::ranges::borrowed_subrange_t<R>. Pri dočasnom rozsahu, ktorý nespĺňa borrowed_range, je druhý typ std::ranges::dangling, nie použiteľný podrozsah. Výsledok neukladá kópie prvkov: údaje musia naďalej existovať a ich iterátory musia zostať platné.

Pre N prvkov je najviac 2 * log2(N) + O(1) porovnaní a projekcií; bez iterátorov s náhodným prístupom môže byť počet posunov iterátorov lineárny. Príklad vyhľadáva kľúče cez &Item::key: tri zhody majú indexy [1, 4), zatiaľ čo kľúč 3 vráti prázdny výsledok. Príklad je určený pre konfiguráciu zostavenia C++23; kompatibilita behu v produkčnom prostredí nie je potvrdená.

Prí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ýsledok

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

Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.

Zdroje