Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

Sortiranje, usporedbe i rasponi pretraživanja

Ispravno sortiranje zahtijeva komparator koji definira strogi slabi poredak. Binarno pretraživanje zahtijeva raspon podijeljen prema relevantnom uvjetu; sortiranje cijelog raspona dovoljno je, ali nije uvijek nužno.

Verzija: 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> uređuje poluotvoreni raspon [first, last) prema comp: nijedan kasniji element ne prethodi ranijemu. Zahtijeva iteratore s nasumičnim pristupom i elemente koji zadovoljavaju zahtjeve za premještanje i zamjenu. Izvodi O(N log N) usporedbi. Ne jamči očuvanje redoslijeda ekvivalentnih elemenata; za to služi std::stable_sort.

Komparator mora definirati strogi slabi poredak. comp(a, b) znači da a prethodi b, a comp(a, a) mora biti netočno. Relacija mora biti tranzitivna. I ekvivalencija definirana kao !comp(a, b) && !comp(b, a) mora biti tranzitivna i ne mora odgovarati operatoru operator==. Nemojte koristiti <=: krši zahtjev za jednake argumente. Ako zahtjevi za komparator nisu zadovoljeni, jamstva algoritma ne vrijede.

Strogi slabi poredak i podjela raspona za pretraživanje povezani su, ali različiti zahtjevi. U rasponu podijeljenom prema predikatu najprije su svi elementi s rezultatom true, a zatim oni s rezultatom false; bilo koji dio može biti prazan. Za std::lower_bound(first, last, value, comp) predikat je comp(e, value). Funkcija vraća granicu: prvi element s rezultatom false ili last. To ne potvrđuje da je tražena vrijednost prisutna; nemojte dereferencirati last.

Sortiranje prema istom poretku jamči takvu podjelu za svaki ključ. Za jedan ključ dovoljna je sama podjela: [2, 1, 4, 3] zadovoljava preduvjet za std::lower_bound uz value = 3 i usporedbu <, iako nije sortiran. Druge funkcije binarnog pretraživanja imaju vlastite zahtjeve za podjelu. std::lower_bound izvodi O(log N) usporedbi, no bez iteratora s nasumičnim pristupom može zahtijevati linearni broj koraka iteratora.

Primjer sortira cijele brojeve, a zatim istim comp dobiva indeks 3. Sadržaj je namijenjen za C++23; navedena referenca vodi na radni nacrt koji se mijenja, a ne na konačnu publikaciju C++23. Podrška prevoditelja i produkcijskog okruženja izvođenja nije potvrđena.

Primjeri

#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

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

Izvori