Dokumentacja C++ z przykładami: Algorytmy

Q: Jak sprawdzić, czy wartość istnieje w wektorze w C++?

Użyj std::find: auto it = find(v.begin(), v.end(), target);. Jeśli it == v.end(), wartości nie ma; w przeciwnym razie it wskazuje pierwsze trafienie. Aby sprawdzić warunek zamiast konkretnej wartości, użyj std::any_of z predykatem.

Q: Dlaczego std::remove tak naprawdę nie usuwa elementów z kontenera?

Algorytmy widzą tylko iteratory, a nie kontener, więc std::remove nie może go zmniejszyć. Przesuwa zachowane elementy na początek i zwraca iterator do nowego logicznego końca. Musisz potem wywołać v.erase(...) (idiom erase-remove), aby fizycznie pozbyć się resztek.

Pętle, których nie musisz pisać

Na poprzedniej stronie widać było, że każdy kontener udostępnia iteratory, czyli lekkie kursory z begin() i end(). Ta abstrakcja to cały powód istnienia standardowych algorytmów. Zamiast pisać surową pętlę for za każdym razem, gdy chcesz coś wyszukać, policzyć lub przekształcić, wywołujesz nazwaną funkcję z <algorithm> i przekazujesz jej zakres.

Zakres to po prostu dwa iteratory: gdzie zacząć i miejsce tuż za końcem. Ponieważ każdy algorytm mówi tym samym językiem iteratorów, to samo find działa na vector, string i zwykłej tablicy.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {4, 8, 15, 16, 23, 42};

    // Czy 16 jest w zakresie [begin, end)?
    auto it = find(v.begin(), v.end(), 16);

    if (it != v.end())
        cout << "found " << *it << " at index " << (it - v.begin()) << "\n";
    else
        cout << "not found\n";
    return 0;
}

Wzorzec do zapamiętania: algorytm wyszukujący zwraca iterator end(), żeby powiedzieć "nic nie znaleziono". Zawsze porównuj wynik z end(), zanim go wyłuskasz, bo wyłuskanie end() to niezdefiniowane zachowanie.

Liczenie i testowanie predykatami

Wiele algorytmów przyjmuje predykat, czyli funkcję (zwykle lambdę), która dla każdego elementu zwraca bool. count_if liczy trafienia; all_of, any_of i none_of odpowiadają tak lub nie na pytania o cały zakres.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> scores = {42, 88, 17, 95, 63, 71};

    int passed = count_if(scores.begin(), scores.end(),
                          [](int s) { return s >= 60; });

    bool allPositive = all_of(scores.begin(), scores.end(),
                              [](int s) { return s > 0; });

    bool anyPerfect = any_of(scores.begin(), scores.end(),
                             [](int s) { return s == 100; });

    cout << passed << " passed\n";          // 4 passed
    cout << "all positive? " << allPositive << "\n";  // 1
    cout << "any perfect? " << anyPerfect << "\n";    // 0
    return 0;
}

std::count (bez _if) to prostszy krewny, który liczy konkretną wartość zamiast warunku. Po wersje z predykatem sięgaj w chwili, gdy twój test brzmi "wszystko, co spełnia regułę", a nie "ta konkretna wartość".

Przekształcanie i redukcja zakresu

Dwa woły robocze pokrywają większość przetwarzania danych: std::transform przepuszcza każdy element przez funkcję, a std::accumulate (z <numeric>, nie z <algorithm>) zwija zakres do jednej wartości.

transform zapisuje wyniki przez iterator wyjściowy. Częsty i groźny błąd to skierowanie wyjścia do pustego wektora: algorytm zakłada, że miejsce już istnieje, i pisze za końcem. Albo najpierw ustaw rozmiar celu, albo użyj back_inserter, żeby każdy wynik trafiał tam przez push_back.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
    vector<int> nums = {1, 2, 3, 4};
    vector<int> squares;   // pusty, jeszcze bez miejsca

    // back_inserter powiększa `squares` w miarę napływu wyników
    transform(nums.begin(), nums.end(), back_inserter(squares),
              [](int n) { return n * n; });

    for (int s : squares) cout << s << " ";  // 1 4 9 16
    cout << "\n";
    return 0;
}

accumulate zaczyna od wartości początkowej i łączy elementy od lewej do prawej. Typ wartości początkowej ma znaczenie: przekaż 0 (czyli int), a suma będzie liczona w int, co może spowodować przepełnienie lub obcięcie, zależnie od typu danych elementów.

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main() {
    vector<double> prices = {9.99, 4.50, 19.95};

    // Zacznij od 0.0 (double), żeby suma pozostała typu double.
    double total = accumulate(prices.begin(), prices.end(), 0.0);

    cout << "total: " << total << "\n";  // total: 34.44
    return 0;
}

Gdyby zamiast tego stało accumulate(prices.begin(), prices.end(), 0) z wartością startową typu int, każde dodawanie odbywałoby się w int, a grosze by zniknęły. Typ wartości startowej po cichu wyznacza typ wyniku.

Idiom erase-remove

Oto pułapka, która zaskakuje wszystkich. std::remove nie usuwa niczego z kontenera. Algorytmy mają tylko iteratory, więc nie mogą zmienić rozmiaru kontenera; nawet nie wiedzą, że jakiś kontener istnieje. remove w rzeczywistości przesuwa wszystkie zachowane elementy na początek, zostawia ogon w nieokreślonym stanie i zwraca iterator do nowego logicznego końca.

// samo remove nie zmienia rozmiaru, oto błąd:
remove(v.begin(), v.end(), 0);  // zwraca iterator, który zignorowano
// v ma nadal pierwotny rozmiar; ogon to śmieci

Aby naprawdę usunąć elementy, łączysz remove z metodą erase kontenera, i stąd nazwa idiom erase-remove:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {3, 0, 7, 0, 1, 0, 9};

    // 1. remove przesuwa niezerowe elementy do przodu, zwraca nowy koniec
    // 2. erase odcina wszystko od tego miejsca do prawdziwego końca
    v.erase(remove(v.begin(), v.end(), 0), v.end());

    for (int n : v) cout << n << " ";  // 3 7 1 9
    cout << "\n";
    return 0;
}

Użyj remove_if, gdy zamiast konkretnej wartości masz predykat. W C++20 możesz całkiem pominąć ten taniec dzięki wolnym funkcjom std::erase / std::erase_if, które wykonują oba kroki za ciebie: erase(v, 0);.

Iteratory żyjące dłużej niż ich ważność

Ponieważ algorytmy zwracają iteratory, podlegają one tym samym regułom unieważniania, które znasz z poprzedniej strony. Zapisanie iteratora, a potem modyfikacja kontenera (push_back, który wywoła realokację, albo erase) może zostawić zapisany iterator wiszący, a użycie go to niezdefiniowane zachowanie.

auto it = find(v.begin(), v.end(), 16);
v.push_back(99);   // może przenieść pamięć v
cout << *it;       // BŁĄD: `it` może teraz wskazywać zwolnioną pamięć

Bezpieczny nawyk: używaj iteratora zwróconego przez algorytm od razu, przed jakąkolwiek operacją, która mogłaby zmienić rozmiar kontenera lub przenieść jego pamięć. Jeśli musisz zmienić kontener na podstawie wyniku, zapamiętaj indeks (it - v.begin()), bo indeksy przetrwają realokację.

Dalej: sortowanie

Znasz już wyszukiwanie, liczenie, przekształcanie i redukcję, ale jeden algorytm jest na tyle ważny, że zasługuje na osobną stronę. std::sort porządkuje zakres w miejscu, a gdy dane są posortowane, otwiera się cała rodzina szybszych algorytmów dla danych posortowanych (binary_search, lower_bound, equal_range). Następnie zajmiemy się sortowaniem: jak podać własny komparator, czym różni się sort od stable_sort i jakich reguł musi przestrzegać funkcja porównująca, aby uniknąć niezdefiniowanego zachowania.

Najczęściej zadawane pytania

Czym jest nagłówek <algorithm> w C++?

<algorithm> to nagłówek biblioteki standardowej z funkcjami generycznymi, takimi jak std::find, std::sort, std::count_if i std::transform. Działają one na zakresach opisanych parą iteratorów (zwykle begin() i end()), więc ten sam algorytm działa na vector, array, string i każdym kontenerze, który udostępnia iteratory.

Jak sprawdzić, czy wartość istnieje w wektorze w C++?

Użyj std::find: auto it = find(v.begin(), v.end(), target);. Jeśli it == v.end(), wartości nie ma; w przeciwnym razie it wskazuje pierwsze trafienie. Aby sprawdzić warunek zamiast konkretnej wartości, użyj std::any_of z predykatem.

Dlaczego std::remove tak naprawdę nie usuwa elementów z kontenera?

Algorytmy widzą tylko iteratory, a nie kontener, więc std::remove nie może go zmniejszyć. Przesuwa zachowane elementy na początek i zwraca iterator do nowego logicznego końca. Musisz potem wywołać v.erase(...) (idiom erase-remove), aby fizycznie pozbyć się resztek.

Powiązane zagadnienia