CKTIS / C++
Razvrščanje, primerjave in iskalni obsegi
Pravilno razvrščanje zahteva primerjalnik, ki določa strogo šibko urejenost. Binarno iskanje zahteva obseg, razdeljen glede na ustrezni pogoj; razvrščanje celotnega obsega zadostuje, ni pa vedno nujno.
Različica: C++23; repository compiler flag, production runtime not attested
Sintaksa
std::sort(first, last, comp);
std::lower_bound(first, last, value, comp);std::sort iz <algorithm> uredi polodprti obseg [first, last) po comp: noben poznejši element ni pred zgodnejšim. Zahteva iteratorje z naključnim dostopom in elemente, ki izpolnjujejo zahteve za premikanje in zamenjavo. Izvede O(N log N) primerjav. Ne zagotavlja ohranitve vrstnega reda enakovrednih elementov; za to uporabite std::stable_sort.
Primerjalnik mora določati strogo šibko urejenost. comp(a, b) pomeni, da je a pred b, comp(a, a) pa mora biti neresničen. Relacija mora biti tranzitivna. Tudi ekvivalenca, določena z !comp(a, b) && !comp(b, a), mora biti tranzitivna in ni nujno enaka operator==. Ne uporabljajte <=: pri enakih argumentih krši zahtevo. Če zahteve za primerjalnik niso izpolnjene, jamstva algoritma ne veljajo.
Stroga šibka urejenost in razdeljenost iskalnih obsegov sta povezani, vendar različni zahtevi. V obsegu, razdeljenem glede na predikat, so najprej vsi elementi z rezultatom true, nato vsi z rezultatom false; eden od delov je lahko prazen. Za std::lower_bound(first, last, value, comp) je predikat comp(e, value). Funkcija vrne mejo: prvi element z rezultatom false ali last. To ne potrjuje, da je iskana vrednost prisotna; last ne dereferencirajte.
Razvrščanje po isti urejenosti zagotavlja to razdelitev za vsak ključ. Za en ključ zadošča že razdelitev: [2, 1, 4, 3] izpolnjuje predpogoj za std::lower_bound pri value = 3 in primerjavi <, čeprav ni razvrščen. Druge funkcije za binarno iskanje imajo svoje zahteve glede razdelitve. std::lower_bound izvede O(log N) primerjav, brez iteratorjev z naključnim dostopom pa lahko potrebuje linearno število korakov iteratorja.
Primer razvrsti cela števila in nato z istim comp pridobi indeks 3. Vsebina je namenjena C++23; navedena referenca vodi do sproti razvijajočega se delovnega osnutka, ne do nespremenljive izdaje C++23. Podpora prevajalnika in produkcijskega izvajalnega okolja ni potrjena.
Primeri
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values{4, 1, 3, 1, 2};
const auto comp = [](int a, int b) { return a < b; };
std::sort(values.begin(), values.end(), comp);
for (std::size_t i = 0; i < values.size(); ++i) {
if (i != 0) std::cout << ' ';
std::cout << values[i];
}
std::cout << '\n';
const auto it = std::lower_bound(values.begin(), values.end(), 3, comp);
std::cout << "index=" << (it - values.begin()) << '\n';
}
Rezultat
1 1 2 3 4 index=3
Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.