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.