CKTIS / C++
Ricerca lineare
La ricerca lineare controlla gli elementi in successione senza richiedere che i dati siano ordinati. In C++, std::find restituisce un iteratore alla prima corrispondenza oppure l’iteratore di fine.
Versione: C++23; repository compiler flag, production runtime not attested
Sintassi
std::find(first, last, value)La ricerca lineare (linear search) controlla gli elementi in successione finché trova una corrispondenza o esaurisce l’intervallo. I dati non devono essere ordinati.
Usa std::find(first, last, value) di <algorithm>. L’intervallo [first, last) esclude last. Il risultato è un iteratore al primo elemento per cui vale *it == value, non un indice. Se non c’è alcuna corrispondenza, anche in un intervallo vuoto, il risultato è last; non dereferenziarlo.
Per n elementi servono al massimo n confronti: il costo nel caso peggiore è O(n). L’esempio mostra duplicati e un valore assente. La sottrazione degli iteratori produce un indice con base zero, perché std::array fornisce iteratori ad accesso casuale.
L’esempio è pensato per C++23. La pagina citata è una bozza di lavoro in evoluzione, non una pubblicazione C++23 definitiva.
Esempi
#include <algorithm>
#include <array>
#include <iostream>
int main() {
const std::array<int, 5> values{8, 3, 6, 3, 9};
for (int target : {3, 7}) {
const auto it = std::find(values.begin(), values.end(), target);
std::cout << target << ": ";
if (it != values.end()) {
std::cout << "index " << (it - values.begin()) << '\n';
} else {
std::cout << "not found\n";
}
}
}
Risultato
3: index 1 7: not found
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.