CKTIS / C++
Ordinamento, confronti e intervalli di ricerca
Un ordinamento corretto richiede un comparatore che definisca un ordinamento stretto debole. La ricerca binaria richiede un intervallo partizionato secondo la condizione pertinente; ordinare l’intero intervallo è sufficiente, ma non sempre necessario.
Versione: C++23; repository compiler flag, production runtime not attested
Sintassi
std::sort(first, last, comp);
std::lower_bound(first, last, value, comp);std::sort di <algorithm> ordina l’intervallo semiaperto [first, last) secondo comp: nessun elemento successivo precede uno precedente. Richiede iteratori ad accesso casuale ed elementi che soddisfino i requisiti di spostamento e scambio. Esegue O(N log N) confronti. Non garantisce di conservare l’ordine degli elementi equivalenti; per questo si usa std::stable_sort.
Il comparatore deve definire un ordinamento stretto debole. comp(a, b) significa che a precede b, e comp(a, a) deve essere falso. La relazione deve essere transitiva. Anche l’equivalenza definita da !comp(a, b) && !comp(b, a) deve essere transitiva e non deve necessariamente corrispondere a operator==. Non usare <=: viola il requisito per argomenti identici. Se i requisiti del comparatore non sono rispettati, le garanzie dell’algoritmo non sono valide.
L’ordinamento stretto debole e la partizione degli intervalli di ricerca sono requisiti collegati, ma distinti. In un intervallo partizionato rispetto a un predicato, tutti gli elementi che danno true precedono quelli che danno false; una delle due parti può essere vuota. Per std::lower_bound(first, last, value, comp), il predicato è comp(e, value). La funzione restituisce il confine: il primo elemento che dà false, oppure last. Ciò non dimostra che il valore cercato sia presente; non dereferenziare last.
Ordinare secondo lo stesso ordinamento garantisce questa partizione per ogni chiave. Per una singola chiave basta la partizione: [2, 1, 4, 3] soddisfa la precondizione di std::lower_bound per value = 3 e il confronto <, pur non essendo ordinato. Le altre funzioni di ricerca binaria hanno requisiti di partizione propri. std::lower_bound esegue O(log N) confronti, ma senza iteratori ad accesso casuale può richiedere un numero lineare di passi dell’iteratore.
L’esempio ordina numeri interi e poi usa lo stesso comp per ottenere l’indice 3. Il contenuto ha come obiettivo C++23; il riferimento fornito rimanda a una bozza di lavoro in evoluzione, non a una pubblicazione C++23 definitiva. Il supporto da parte del compilatore e dell’ambiente di esecuzione di produzione non è attestato.
Esempi
#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';
}
Risultato
1 1 2 3 4 index=3
Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.