Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C++

std::lower_bound — prima posizione non minore di una chiave

std::lower_bound cerca il confine di un intervallo partizionato in modo adeguato: il primo elemento non minore della chiave oppure la fine dell’intervallo. Restituisce un iteratore, non conferma che esista un valore uguale.

Versione: C++23; repository compiler flag, production runtime not attested

Sintassi

#include <algorithm>
std::lower_bound(first, last, value)
std::lower_bound(first, last, value, comp)

std::lower_bound, dichiarata in <algorithm>, cerca in [first, last) e restituisce il primo iteratore per cui comp(*it, value) è falso, oppure last se non esiste un elemento del genere. Se comp non è specificato, usa il confronto predefinito «minore di». In un intervallo numerico crescente, il risultato punta al primo elemento >= value, compreso il primo duplicato.

La precondizione è che l’intervallo sia partizionato rispetto alla chiave specifica: tutti gli elementi per cui vale comp(element, value) devono precedere gli altri. Un ordinamento completo secondo lo stesso confronto è sufficiente, ma non necessario. La violazione di questa condizione causa un comportamento indefinito; la funzione non ordina i dati.

Il risultato non conferma che la chiave esista. Verifica it != last prima di usare *it. Nell’esempio con gli interi, il codice verifica soltanto it != values.end() prima di stampare il valore candidato; non lo confronta con la chiave. Una volta esclusa la fine dell’intervallo, puoi verificare l’uguaglianza separatamente con *it == key. Con un ordinamento personalizzato, l’equivalenza significa !comp(a, b) && !comp(b, a), e non necessariamente a == b.

Sono richiesti almeno iteratori in avanti. Per N elementi, il numero di confronti è O(log N), ma senza iteratori ad accesso casuale il numero di passi dell’iteratore può essere lineare. L’esempio ha come obiettivo C++23; il documento collegato è una bozza di lavoro in evoluzione, non un’edizione immutabile di C++23.

Esempi

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    const std::vector<int> values{1, 3, 3, 7};
    for (int key : {3, 4, 9}) {
        const auto it = std::lower_bound(values.begin(), values.end(), key);
        std::cout << key << ": index=" << (it - values.begin());
        if (it != values.end()) {
            std::cout << ", value=" << *it;
        } else {
            std::cout << ", end";
        }
        std::cout << '\n';
    }
}

Risultato

3: index=1, value=3
4: index=3, value=7
9: index=4, end

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