CKTIS / C++
std::upper_bound — il limite dopo gli elementi equivalenti
`std::upper_bound` trova il confine della partizione per il valore cercato: restituisce un iteratore al primo elemento rispetto al quale `value` risulta minore secondo il confronto usato, oppure `last` se non esiste un elemento del genere. Con il confronto predefinito e numeri ordinati in senso crescente, si tratta del primo numero maggiore di `value`.
Versione: C++23; repository compiler flag, production runtime not attested
Sintassi
#include <algorithm>
std::upper_bound(first, last, value)
std::upper_bound(first, last, value, comp)std::upper_bound, dichiarato in <algorithm>, cerca nell’intervallo semiaperto [first, last). Con il confronto predefinito e un intervallo crescente, restituisce il primo elemento maggiore di value, saltando tutti i duplicati di quel valore. Il risultato è un iteratore, non un indice né un’indicazione di presenza. Se non esiste un elemento che soddisfa la condizione, anche in un intervallo vuoto, il risultato è last. Prima di dereferenziarlo, verifica che il risultato sia diverso da last.
L’overload che accetta comp cerca il primo elemento e per cui comp(value, e) è vero. Come precondizione, l’intervallo deve essere partizionato: prima devono venire tutti gli elementi per cui vale !comp(value, e), poi gli altri. Un ordinamento completo secondo un ordine compatibile è sufficiente, ma non necessario per una singola ricerca. Non cercare in dati arbitrariamente non ordinati: violare la precondizione causa comportamento indefinito. Il significato di «maggiore» dipende dal comparatore, non necessariamente dall’operatore numerico >.
In un intervallo crescente, std::lower_bound trova il primo elemento non minore di value, mentre std::upper_bound trova il primo elemento maggiore. In un intervallo ordinato, questi limiti delimitano gli elementi equivalenti secondo il confronto. Nota l’ordine degli argomenti: std::upper_bound usa comp(value, element), non comp(element, value).
Sono richiesti almeno iteratori forward. Il numero di confronti è O(log N), ma senza accesso casuale il numero di passi dell’iteratore può essere O(N); con gli iteratori di std::vector, è logaritmico. L’esempio usa una sintassi compatibile con C++23. La bozza di lavoro collegata è in evoluzione e può contenere dichiarazioni più recenti.
Esempi
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
const std::vector<int> values{1, 2, 2, 2, 4, 7};
const auto it = std::upper_bound(values.begin(), values.end(), 2);
std::cout << "index=" << (it - values.begin()) << '\n';
if (it != values.end()) {
std::cout << "value=" << *it << '\n';
}
const auto end = std::upper_bound(values.begin(), values.end(), 7);
std::cout << "at_end=" << std::boolalpha << (end == values.end()) << '\n';
}
Risultato
index=4 value=4 at_end=true
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.