CKTIS / C++
Intervallo di ricerca partizionato
`std::lower_bound` non richiede un ordinamento completo: per la chiave data, gli elementi che soddisfano il test devono precedere tutti quelli che non lo soddisfano.
Versione: ISO C++23; implementation support may vary
Sintassi
#include <algorithm>
std::lower_bound(first, last, key);
std::lower_bound(first, last, key, comp);
std::ranges::lower_bound(first, last, key, comp, proj);
std::ranges::lower_bound(range, key, comp, proj);
// For this key, the predicate must be true for a prefix and false for the rest.
// Classic: bool(comp(element, key))
// Ranges: bool(std::invoke(comp, std::invoke(proj, element), key))Un intervallo [first, last) è partizionato rispetto alla chiave quando bool(comp(element, key)) restituisce prima solo true e poi solo false. Entrambe le parti possono essere vuote e nessuna deve essere ordinata al proprio interno. Lo std::lower_bound classico, in <algorithm>, restituisce il primo iteratore per cui il test è falso, oppure last se non ce n’è uno. Il risultato non deve necessariamente essere uguale alla chiave. Se la precondizione di partizionamento non è rispettata, il comportamento è indefinito.
L’overload classico con comparatore confronta solo nella direzione elemento–chiave. Accetta quindi una lambda [](const Sale& row, int key) che verifica row.sales > key; [] non cattura nulla. std::ranges::lower_bound (da C++20) accetta una coppia iteratore–sentinella o un intervallo. Il comparatore deve soddisfare indirect_strict_weak_order per gli elementi proiettati e per la chiave; &Sale::sales permette di confrontare interi. Entrambe le versioni richiedono almeno iteratori in avanti ed eseguono un numero logaritmico di confronti, ma senza accesso casuale il numero di avanzamenti può essere lineare. L’overload che riceve un intervallo restituisce std::ranges::dangling se l’intervallo temporaneo non è un borrowed_range. Non dereferenziare iteratori di fine o invalidati.
std::nth_element e std::partial_sort richiedono iteratori ad accesso casuale e un ordinamento debole stretto: comp(x, x) deve essere falso, e sia il confronto sia l’equivalenza definita da due confronti falsi devono essere transitivi. Per valori interi delle vendite, a.sales > b.sales rispetta queste regole, >= no. nth_element colloca l’elemento del rango scelto nella posizione che avrebbe dopo l’ordinamento e separa le due parti senza garantire che siano ordinate. partial_sort ordina il prefisso richiesto e lascia il resto in un ordine non specificato. Nessuno dei due garantisce il partizionamento dell’intero intervallo per una chiave arbitraria. Per ricerche ripetute con chiavi diverse, ordina l’intero intervallo secondo lo stesso criterio.
Esempi
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
struct Sale {
int sales;
};
int main() {
const std::vector<Sale> rows{{95}, {120}, {70}, {85}, {60}};
const int key = 90;
const auto before_key = [](const Sale& row, int key) {
return row.sales > key;
};
const auto classic = std::lower_bound(rows.begin(), rows.end(), key, before_key);
const auto ranged = std::ranges::lower_bound(rows, key, std::ranges::greater{}, &Sale::sales);
if (classic != rows.end() && ranged != rows.end()) {
std::cout << classic->sales << '\n' << ranged->sales << '\n';
}
}Risultato
70 70
Con `90`, entrambe le chiamate stampano `70`, il primo valore che non supera la soglia, anche se l’intervallo non è ordinato in senso decrescente. Con `100`, `95` dà `false` prima che `120` dia `true`: nessuna delle due chiamate è valida con `100` su questo intervallo.
Lezioni correlate
- C++ · Lezione 23 · Avanzato · Versione: 3