CKTIS / C++
Linearno iskanje
Linearno iskanje preverja zaporedne elemente, ne da bi morali biti podatki urejeni. V C++ std::find vrne iterator do prvega zadetka ali končni iterator.
Različica: C++23; repository compiler flag, production runtime not attested
Sintaksa
std::find(first, last, value)Linearno iskanje (linear search) preverja zaporedne elemente, dokler ne najde zadetka ali izčrpa območja. Podatkov ni treba urediti.
Uporabite std::find(first, last, value) iz <algorithm>. Območje [first, last) ne vključuje last. Rezultat je iterator do prvega elementa, za katerega velja *it == value, ne indeks. Če zadetka ni, tudi v praznem območju, je rezultat last; tega iteratorja nikoli ne dereferencirajte.
Za n elementov je potrebnih največ n primerjav: najslabša časovna zahtevnost je O(n). Primer prikaže podvojene vrednosti in manjkajočo vrednost. Z odštevanjem iteratorjev dobimo indeks, ki se začne z nič, saj std::array zagotavlja iteratorje z naključnim dostopom.
Primer je namenjen C++23. Navedena stran je razvijajoči se delovni osnutek, ne nespremenjena izdaja C++23.
Primeri
#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";
}
}
}
Rezultat
3: index 1 7: not found
Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.