18.3 — Wprowadzenie do algorytmów bibliotek standardowych

Nowi programiści zazwyczaj spędzają dużo czasu na pisaniu niestandardowych pętli w celu wykonywania stosunkowo prostych zadań, takich jak sortowanie, liczenie lub przeszukiwanie tablic. Pętle te mogą być problematyczne, zarówno pod względem łatwości popełnienia błędu, jak i ogólnej łatwości konserwacji, ponieważ pętle mogą być trudne do zrozumienia.

Ponieważ wyszukiwanie, liczenie i sortowanie są częstymi operacjami, standardowa biblioteka C++ zawiera szereg funkcji umożliwiających wykonanie tych czynności w zaledwie kilku wierszach kodu. Dodatkowo te standardowe funkcje biblioteczne są wstępnie przetestowane, są wydajne, działają na różnych typach kontenerów, a wiele z nich obsługuje równoległość (możliwość przydzielenia wielu wątków procesora temu samemu zadaniu w celu szybszego jego wykonania).

Funkcjonalność dostępna w bibliotece algorytmów ogólnie można podzielić na jedną z trzech kategorii:

• Inspektorzy -- Używane do przeglądania (ale nie modyfikowania) danych w kontenerze. Przykłady obejmują wyszukiwanie i zliczanie.
• Mutatory -- Używane do modyfikowania danych w kontenerze. Przykłady obejmują sortowanie i tasowanie.
• Ułatwienia -- Używane do generowania wyniku na podstawie wartości elementów danych. Przykładami są obiekty mnożące wartości lub obiekty określające kolejność par elementów, w jakiej powinny być sortowane.

Algorytmy te znajdują się w algorytmy bibliotece. Podczas tej lekcji omówimy niektóre z bardziej powszechnych algorytmów — ale jest ich o wiele więcej. Zachęcamy do przeczytania połączonego odniesienia, aby zobaczyć wszystko, co jest dostępne!

Uwaga: wszystkie te algorytmy korzystają z iteratorów, więc jeśli nie znasz podstawowych iteratorów, przejrzyj lekcję 18.2 -- Wprowadzenie do iteratorów.

Używanie std::find do wyszukiwania elementu według wartości

std::find wyszukuje pierwsze wystąpienie wartości w kontenerze. std::find przyjmuje 3 parametry: iterator do elementu początkowego w sekwencji, iterator do elementu końcowego w sekwencji oraz wartość do wyszukania. Zwraca iterator wskazujący element (jeśli został znaleziony) lub koniec kontenera (jeśli element nie został znaleziony).

Na przykład:

#include <algorithm>
#include <array>
#include <iostream>

int main()
{
    std::array arr{ 13, 90, 99, 5, 40, 80 };

    std::cout << "Enter a value to search for and replace with: ";
    int search{};
    int replace{};
    std::cin >> search >> replace;

    // Input validation omitted

    // std::find returns an iterator pointing to the found element (or the end of the container)
    // we'll store it in a variable, using type inference to deduce the type of
    // the iterator (since we don't care)
    auto found{ std::find(arr.begin(), arr.end(), search) };

    // Algorithms that don't find what they were looking for return the end iterator.
    // We can access it by using the end() member function.
    if (found == arr.end())
    {
        std::cout << "Could not find " << search << '\n';
    }
    else
    {
        // Override the found element.
        *found = replace;
    }

    for (int i : arr)
    {
        std::cout << i << ' ';
    }

    std::cout << '\n';

    return 0;
}

Przykładowe uruchomienie, gdy element zostanie znaleziony

Enter a value to search for and replace with: 5 234
13 90 99 234 40 80

Przykładowe uruchomienie, gdy element nie zostanie znaleziony

Enter a value to search for and replace with: 0 234
Could not find 0
13 90 99 5 40 80

Użycie std::find_if do znalezienia elementu spełniającego jakiś warunek

Czasami chcemy sprawdzić, czy istnieje wartość kontener pasujący do jakiegoś warunku (np. ciąg znaków zawierający określony podciąg), a nie dokładna wartość. W takich przypadkach std::find_if jest idealny.

Klasa std::find_if funkcja działa podobnie do std::find, ale zamiast przekazywać konkretną wartość do wyszukania, przekazujemy obiekt wywoływalny, taki jak wskaźnik funkcji (lub lambda, o czym porozmawiamy później). Dla każdego elementu podlegającego iteracji std::find_if wywoła tę funkcję (przekazując element jako argument do funkcji), a funkcja może zwrócić true jeśli zostanie znalezione dopasowanie, lub false w przeciwnym razie.

Oto przykład, w którym używamy std::find_if do sprawdzenia, czy którykolwiek element zawiera podciąg „nut”:

#include <algorithm>
#include <array>
#include <iostream>
#include <string_view>

// Our function will return true if the element matches
bool containsNut(std::string_view str)
{
    // std::string_view::find returns std::string_view::npos if it doesn't find
    // the substring. Otherwise it returns the index where the substring occurs
    // in str.
    return str.find("nut") != std::string_view::npos;
}

int main()
{
    std::array<std::string_view, 4> arr{ "apple", "banana", "walnut", "lemon" };

    // Scan our array to see if any elements contain the "nut" substring
    auto found{ std::find_if(arr.begin(), arr.end(), containsNut) };

    if (found == arr.end())
    {
        std::cout << "No nuts\n";
    }
    else
    {
        std::cout << "Found " << *found << '\n';
    }

    return 0;
}

Wyjście

Found walnut

Gdybyś miał napisać powyższy przykład ręcznie, potrzebujesz co najmniej trzech pętli (jednej do przeglądania tablicy i dwóch do dopasowania podciągu). Standardowe funkcje biblioteczne pozwalają nam zrobić to samo w zaledwie kilku linijkach kodu!

Używając std::count i std::count_if do zliczenia liczby wystąpień

std::count i std::count_if wyszukaj wszystkie wystąpienia elementu lub elementu spełniającego warunek.

W poniższym przykładzie policzymy, ile elementów zawiera podciąg „nut”:

#include <algorithm>
#include <array>
#include <iostream>
#include <string_view>

bool containsNut(std::string_view str)
{
	return str.find("nut") != std::string_view::npos;
}

int main()
{
	std::array<std::string_view, 5> arr{ "apple", "banana", "walnut", "lemon", "peanut" };

	auto nuts{ std::count_if(arr.begin(), arr.end(), containsNut) };

	std::cout << "Counted " << nuts << " nut(s)\n";

	return 0;
}

Wyjście

Counted 2 nut(s)

Używanie std::sort do sortowania niestandardowego

Wcześniej używaliśmy std::sort do sortowania tablicy w kolejności rosnącej, ale std::sort może zrobić więcej. Istnieje wersja std::sort który jako trzeci parametr przyjmuje funkcję, która pozwala nam sortować według własnego uznania. Funkcja pobiera dwa parametry do porównania i zwraca wartość true, jeśli pierwszy argument powinien być uporządkowany przed drugim. Domyślnie std::sort sortuje elementy w kolejności rosnącej.

Użyjmy std::sort by posortować tablicę w odwrotnej kolejności za pomocą niestandardowej funkcji porównania o nazwie greater:

#include <algorithm>
#include <array>
#include <iostream>

bool greater(int a, int b)
{
    // Order @a before @b if @a is greater than @b.
    return (a > b);
}

int main()
{
    std::array arr{ 13, 90, 99, 5, 40, 80 };

    // Pass greater to std::sort
    std::sort(arr.begin(), arr.end(), greater);

    for (int i : arr)
    {
        std::cout << i << ' ';
    }

    std::cout << '\n';

    return 0;
}

Wyjście

99 90 80 40 13 5

Po raz kolejny, zamiast pisać własne niestandardowe funkcje pętli, możemy posortować naszą tablicę w dowolny sposób w zaledwie kilku linijkach kodu!

Nasz greater funkcja potrzebuje 2 argumentów, ale ich nie przekazujemy, więc gdzie skąd pochodzą? Kiedy używamy funkcji bez nawiasów (), jest to tylko wskaźnik funkcji, a nie wywołanie. Być może pamiętasz to z sytuacji, gdy próbowaliśmy wydrukować funkcję bez nawiasów i std::cout wypisać „1”. std::sort używa tego wskaźnika i wywołuje rzeczywistą funkcję greater z dowolnymi 2 elementami tablicy. Nie wiemy, z jakimi elementami greater zostanie wywołane, ponieważ pod maską nie jest zdefiniowany, jakiego algorytmu sortowania std::sort używa. Więcej o wskaźnikach funkcji porozmawiamy w późniejszym rozdziale.

  std::sort(arr.begin(), arr.end(), greater); // call our custom greater function

  std::sort(arr.begin(), arr.end(), std::greater{}); // use the standard library greater comparison
  // Before C++17, we had to specify the element type when we create std::greater
  std::sort(arr.begin(), arr.end(), std::greater<int>{}); // use the standard library greater comparison

#include <iostream>
#include <iterator>
#include <utility>

void sort(int* begin, int* end)
{
    for (auto startElement{ begin }; startElement != end-1; ++startElement)
    {
        auto smallestElement{ startElement };

        // std::next returns a pointer to the next element, just like (startElement + 1) would.
        for (auto currentElement{ std::next(startElement) }; currentElement != end; ++currentElement)
        {
            if (*currentElement < *smallestElement)
            {
                smallestElement = currentElement;
            }
        }

        std::swap(*startElement, *smallestElement);
    }
}

int main()
{
    int array[]{ 2, 1, 9, 4, 5 };

    sort(std::begin(array), std::end(array));

    for (auto i : array)
    {
        std::cout << i << ' ';
    }

    std::cout << '\n';

    return 0;
}

void sort(int* begin, int* end, std::function<bool(int, int)> compare)

if (*currentElement < *smallestElement)

if (compare(*currentElement, *smallestElement))

#include <functional> // std::function
#include <iostream>
#include <iterator>
#include <utility>

// sort accepts a comparison function
void sort(int* begin, int* end, std::function<bool(int, int)> compare)
{
    for (auto startElement{ begin }; startElement != end-1; ++startElement)
    {
        auto smallestElement{ startElement };

        for (auto currentElement{ std::next(startElement) }; currentElement != end; ++currentElement)
        {
            // the comparison function is used to check if the current element should be ordered
            // before the currently "smallest" element.
            if (compare(*currentElement, *smallestElement))
            {
                smallestElement = currentElement;
            }
        }

        std::swap(*startElement, *smallestElement);
    }
}

int main()
{
    int array[]{ 2, 1, 9, 4, 5 };

    // use std::greater to sort in descending order
    // (We have to use the global namespace selector to prevent a collision
    // between our sort function and std::sort.)
    ::sort(std::begin(array), std::end(array), std::greater{});

    for (auto i : array)
    {
        std::cout << i << ' ';
    }

    std::cout << '\n';

    return 0;
}

Używając std::for_each, aby zrobić coś ze wszystkimi elementami kontenera

std::for_each pobiera listę jako dane wejściowe i stosuje niestandardową funkcję do każdego elementu. Jest to przydatne, gdy chcemy wykonać tę samą operację na każdym elemencie listy.

Oto przykład, w którym używamy std::for_each do podwajania wszystkich liczb w tablicy:

#include <algorithm>
#include <array>
#include <iostream>

void doubleNumber(int& i)
{
    i *= 2;
}

int main()
{
    std::array arr{ 1, 2, 3, 4 };

    std::for_each(arr.begin(), arr.end(), doubleNumber);

    for (int i : arr)
    {
        std::cout << i << ' ';
    }

    std::cout << '\n';

    return 0;
}

Wyjście

2 4 6 8

To często wydaje się najbardziej niepotrzebnym algorytmem dla nowych programistów, ponieważ równoważny kod z pętlą for opartą na zakresie jest krótszy i łatwiejszy. Ale std::for_each ma zalety. Porównajmy std::for_each z pętlą for opartą na zakresie.

std::ranges::for_each(arr, doubleNumber); // Since C++20, we don't have to use begin() and end().
// std::for_each(arr.begin(), arr.end(), doubleNumber); // Before C++20

for (auto& i : arr)
{
    doubleNumber(i);
}

Przy std::for_each, nasze intencje są jasne. Wywołaj doubleNumber z każdym elementem arr. W pętli for opartej na zakresie musimy dodać nową zmienną i. Prowadzi to do kilku błędów, które programista może popełnić, gdy jest zmęczony lub nie zwraca uwagi. Po pierwsze, może wystąpić niejawna konwersja, jeśli nie użyjemy auto. Moglibyśmy zapomnieć ampersand i doubleNumber nie miałoby to wpływu na tablicę. Moglibyśmy przypadkowo przekazać zmienną inną niż i Do doubleNumber. Te błędy nie mogą się zdarzyć w przypadku std::for_each.

Dodatkowo std::for_each można pominąć elementy na początku lub na końcu kontenera, na przykład pominięcie pierwszego elementu arr, std::next można zastosować do przejścia do następnego elementu.

std::for_each(std::next(arr.begin()), arr.end(), doubleNumber);
// Now arr is [1, 4, 6, 8]. The first element wasn't doubled.

Nie jest to możliwe w przypadku pętli for opartej na zakresie.

Podobnie jak wiele algorytmów, std::for_each można łączyć równolegle, aby osiągnąć szybsze przetwarzanie, dzięki czemu lepiej nadaje się do dużych projekty i duże zbiory danych niż pętla for oparta na zakresach.

Wydajność i kolejność wykonywania

Wiele algorytmów w bibliotece algorytmów daje pewnego rodzaju gwarancję dotyczącą sposobu ich wykonania. Zazwyczaj są to albo gwarancje wykonania, albo gwarancje dotyczące kolejności ich wykonania. Na przykład std::for_each gwarantuje, że dostęp do każdego elementu będzie tylko raz i że dostęp do elementów będzie następował w kolejności do przodu.

Podczas gdy większość algorytmów zapewnia pewnego rodzaju gwarancję wydajności, mniej z nich ma gwarancje kolejności wykonania. W przypadku takich algorytmów musimy uważać, aby nie przyjmować założeń dotyczących kolejności uzyskiwania dostępu do elementów lub ich przetwarzania.

Na przykład, gdybyśmy używali standardowego algorytmu bibliotecznego do pomnożenia pierwszej wartości przez 1, drugiej wartości przez 2, trzeciej przez 3 itd., chcielibyśmy uniknąć stosowania jakichkolwiek algorytmów, które nie gwarantowały kolejności wykonywania sekwencyjnego w przód!

Poniższe algorytmy gwarantują sekwencyjne wykonanie wykonanie: std::for_each, std::copy, std::copy_backward, std::move, I std::move_backward. Wiele innych algorytmów (szczególnie tych, które używają iteratora do przodu) jest domyślnie sekwencyjnych ze względu na wymagania iteratora do przodu.

Zakresy w C++20

Konieczność jawnego przekazywania arr.begin() i arr.end() do każdego algorytmu jest trochę denerwująca. Ale nie bójcie się — C++20 dodaje zakresy, które pozwalają nam po prostu przejść arr. Dzięki temu nasz kod będzie jeszcze krótszy i bardziej czytelny.

Wnioski

Biblioteka algorytmów zawiera mnóstwo przydatnych funkcji, dzięki którym Twój kod będzie prostszy i solidniejszy. W tej lekcji omawiamy tylko niewielki podzbiór, ale ponieważ większość tych funkcji działa bardzo podobnie, gdy już wiesz, jak działa kilka, możesz skorzystać z większości z nich.