CKTIS / C++
Wyszukiwanie liniowe
Wyszukiwanie liniowe sprawdza kolejne elementy bez wymogu sortowania. W C++ std::find zwraca iterator do pierwszego dopasowania albo iterator końca.
Wersja: C++23; repository compiler flag, production runtime not attested
Składnia
std::find(first, last, value)Wyszukiwanie liniowe (linear search) sprawdza kolejne elementy aż do znalezienia dopasowania lub wyczerpania zakresu. Dane nie muszą być posortowane.
Użyj std::find(first, last, value) z <algorithm>. Zakres [first, last) nie obejmuje last. Wynikiem jest iterator do pierwszego elementu spełniającego *it == value, a nie indeks. Brak dopasowania, także w pustym zakresie, daje last; nie wolno go dereferencjonować.
Dla n elementów potrzeba najwyżej n porównań: pesymistyczny koszt to O(n). Przykład pokazuje duplikaty i brak wyniku. Odejmowanie iteratorów wyznacza indeks od zera, ponieważ std::array zapewnia iteratory dostępu swobodnego.
Przykład jest przeznaczony dla C++23. Cytowana strona to rozwijany projekt standardu, nie zamrożona publikacja C++23.
Przykłady
#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";
}
}
}
Wynik
3: index 1 7: not found
Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.