21.4 – Обзор алгоритмов STL

Помимо контейнерных классов и итераторов, STL также предоставляет ряд обобщенных алгоритмов для работы с элементами контейнерных классов. Они позволяют вам выполнять такие действия, как поиск, сортировка, вставка, переупорядочивание, удаление и копирование элементов объекта контейнерного класса.

Обратите внимание, что алгоритмы реализованы как функции, которые работают с итераторами. Это означает, что каждый алгоритм необходимо реализовать только один раз, и, как правило, он будет автоматически работать для всех контейнеров, которые предоставляют набор итераторов (включая ваши пользовательские классы контейнеров). Хотя они очень мощные и могут дать возможность очень быстро писать сложный код, у них есть и обратная сторона: какая-либо комбинация алгоритмов и типов контейнеров может не работать, может вызывать бесконечные циклы или может работать, но очень плохо. Поэтому используйте их на свой страх и риск.

STL предоставляет довольно много алгоритмов – здесь мы коснемся только некоторых из наиболее распространенных и простых в использовании. Остальное (и все подробности) мы сохраним для главы об алгоритмах STL.

Чтобы использовать любой из алгоритмов STL, просто включите заголовочный файл algorithm.

min_element и max_element

Алгоритмы std::min_element и std::max_element находят минимальный и максимальный элементы в объекте контейнерного класса. std::iota генерирует непрерывную последовательность значений.

#include <algorithm> // std::min_element и std::max_element
#include <iostream>
#include <list>
#include <numeric>   // std::iota

int main()
{
    std::list<int> li(6);
    // Заполняем li числами, начиная с 0.
    std::iota(li.begin(), li.end(), 0);

    std::cout << *std::min_element(li.begin(), li.end()) << ' '
              << *std::max_element(li.begin(), li.end()) << '\n';

    return 0;
}

Этот код печатает:

0 5

find (и list::insert)

В этом примере мы будем использовать алгоритм std::find(), чтобы найти значение в списке, а затем используем функцию list::insert(), чтобы добавить новое значение в список в этой точке.

#include <algorithm>
#include <iostream>
#include <list>
#include <numeric>

int main()
{
    std::list<int> li(6);
    std::iota(li.begin(), li.end(), 0);

    // Находим значение 3 в списке
    auto it{ find(li.begin(), li.end(), 3) };

    // Вставляем 8 прямо перед 3.
    li.insert(it, 8);

    for (int i : li) // цикл for с итератором
        std::cout << i << ' ';

    std::cout << '\n';

    return 0;
}

Этот код напечатает значения

0 1 2 8 3 4 5

Когда алгоритм поиска не находит то, что искал, он возвращает итератор end.

Если бы мы не знали наверняка, что среди элементов li есть значение 3, то, прежде чем использовать возвращенный итератор для чего-либо еще, нам нужно было бы проверить, нашла ли его std::find.

if (it == li.end())
{
  std::cout << "3 was not found\n";
}
else
{
  // ...
}

sort и reverse

В этом примере мы отсортируем вектор, а затем перевернем его.

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<int> vect{ 7, -3, 6, 2, -5, 0, 4 };

    // сортируем вектор
    std::sort(vect.begin(), vect.end());

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

    std::cout << '\n';

    // переворачиваем вектор
    std::reverse(vect.begin(), vect.end());

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

    std::cout << '\n';

    return 0;
}

Этот дает следующий результат:

-5 -3 0 2 4 6 7
7 6 4 2 0 -3 -5

В качестве альтернативы мы могли бы передать в качестве третьего аргумента std::sort пользовательскую функцию сравнения. В заголовке <functional> есть несколько функций сравнения, которые мы можем использовать, поэтому нам не нужно писать свои собственные. Мы можем передать в std::sort функцию std::greater и удалить вызов std::reverse. Вектор сразу будет отсортирован по убыванию.

Обратите внимание, что std::sort() не работает с контейнерным классом списка – класс list предоставляет свою собственную функцию-член sort(), которая намного эффективнее, чем обобщенная версия.

Заключение

Хотя это лишь часть алгоритмов, которые предоставляет STL, этого должно быть достаточно, чтобы показать, насколько легко их использовать в сочетании с итераторами и базовыми классами контейнеров. Оставшихся алгоритмов хватит, чтобы заполнить целую главу!

Теги