Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

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.

Fonti