Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

std::ranges::equal_range — raspon ekvivalentnih elemenata

std::ranges::equal_range pronalazi poluotvoreni raspon elemenata ekvivalentnih traženoj vrijednosti prema komparatoru. Podržava raspone, parove iterator–sentinel i projekcije; podaci moraju biti prikladno particionirani, što osigurava sortiranje.

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

Sintaksa

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, deklariran u <algorithm>, određuje raspon [lower_bound, upper_bound) bez mijenjanja podataka. Ekvivalentnost znači da su obje usporedbe comp(proj(element), value) i comp(value, proj(element)) netočne; ne moraju se podudarati s operator==. Ako nema podudaranja, rezultat je prazan raspon na mjestu umetanja vrijednosti.

Poziv prihvaća par iterator–sentinel ili cijeli raspon. Potrebni su barem forward iteratori, a comp mora zadovoljavati zahtjeve stroge slabe uređenosti. Zadane su vrijednosti std::ranges::less i std::identity. Projekcija transformira elemente, a ne traženu vrijednost. Podaci moraju biti particionirani tako da logički rezultati svakog od izraza comp(proj(element), value) i !comp(value, proj(element)) najprije tvore istiniti prefiks, a zatim neistiniti sufiks. Sortiranje istim komparatorom i projekcijom dovoljno je; kršenje preduvjeta uzrokuje nedefinirano ponašanje.

Preopterećenje s iteratorima vraća std::ranges::subrange<I>, a ono s rasponom vraća std::ranges::borrowed_subrange_t<R>. Za privremeni raspon koji ne zadovoljava borrowed_range, potonji je tip std::ranges::dangling, a ne upotrebljiv podraspon. Rezultat ne pohranjuje kopije elemenata: podaci moraju i dalje postojati, a iteratori ostati valjani.

Za N elemenata ima najviše 2 * log2(N) + O(1) usporedbi i projekcija; bez iteratora s nasumičnim pristupom broj pomaka iteratora može biti linearan. Primjer traži ključeve putem &Item::key: tri podudaranja zauzimaju indekse [1, 4), dok ključ 3 daje prazan rezultat. Primjer je namijenjen konfiguraciji prevođenja C++23; kompatibilnost izvođenja u produkciji nije potvrđena.

Primjeri

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

Rezultat

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

Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.

Izvori