Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

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.

Viri