Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

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.

Źródła