CKTIS / C++
std::ranges::equal_range — obseg enakovrednih elementov
std::ranges::equal_range poišče polodprti obseg elementov, ki so po primerjalniku enakovredni iskani vrednosti. Podpira obsege, pare iterator–sentinel in projekcije; podatki morajo biti ustrezno razdeljeni, kar zagotovi razvrščanje.
Različica: 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 v <algorithm>, določi obseg [lower_bound, upper_bound) brez spreminjanja podatkov. Enakovrednost pomeni, da sta obe primerjavi comp(proj(element), value) in comp(value, proj(element)) neresnični; ni treba, da se ujema z operator==. Če ni zadetka, je rezultat prazen obseg na mestu vstavljanja vrednosti.
Klic sprejme par iterator–sentinel ali celoten obseg. Zahtevani so najmanj forward iteratorji, comp pa mora izpolnjevati zahteve stroge šibke urejenosti. Privzeti vrednosti sta std::ranges::less in std::identity. Projekcija preoblikuje elemente, ne iskane vrednosti. Podatki morajo biti razdeljeni tako, da logične vrednosti vsakega od izrazov comp(proj(element), value) in !comp(value, proj(element)) najprej tvorijo resnični predponi, nato pa neresnični priponi. Razvrščanje z istim primerjalnikom in projekcijo zadostuje; kršitev predpogojev povzroči nedefinirano vedenje.
Različica z iteratorji vrne std::ranges::subrange<I>, različica z obsegom pa std::ranges::borrowed_subrange_t<R>. Pri začasnem obsegu, ki ne izpolnjuje borrowed_range, je zadnji tip std::ranges::dangling, ne uporaben podobseg. Rezultat ne hrani kopij elementov: podatki morajo še naprej obstajati, iteratorji pa ostati veljavni.
Za N elementov je največ 2 * log2(N) + O(1) primerjav in projekcij; brez iteratorjev z naključnim dostopom je lahko število premikov iteratorjev linearno. Primer išče ključe prek &Item::key: trije zadetki zasedajo indekse [1, 4), ključ 3 pa da prazen rezultat. Primer je namenjen konfiguraciji gradnje C++23; združljivost izvajanja v produkciji ni potrjena.
Primeri
#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
Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.