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.