Язык C++

Алгоритмы стандартной библиотеки C++

iota, for_each и transform
all_of, any_of, none_of
count, count_if, find, find_if
sort, stable_sort, nth_element
lower_bound, upper_bound, binary_search
Резюме
Источники

Стандартная библиотека <algorithms> содержит большое количество алгоритмов для работы с контейнерами стандартной библиотеки. Доступные инструменты покрывают значительную часть встречающихся алгоритмических задач. Использование стандартных алгоритмов вместо их самостоятельной реализации является хорошим стилем программирования по следующим причинам:

Экономия времени. Мы не тратим время на реализацию и отладку алгоритма.
Гарантия отсутствия ошибок в логике работы алгоритма. Алгоритмы стандартной библиотеки протестированы многими программистами.
Лаконичность и выразительность кода. Вместо некоторого количества строчек, которые выполняют неочевидные манипуляции, мы видим название хорошо документированного алгоритма.

Мы рассмотрим лишь некоторые из доступных алгоритмов. Полный список можно найти в документации. Мы рекомендуем всегда проверять наличие стандартного решения при встрече с алгоритмической задачей.

iota, for_each и transform

Большое количество циклов for в коде, который выполняет манипуляции со структурами данных, обычно говорит о недостаточном использовании стандартных алгоритмов. Так, если необходимо применить некоторую функцию ко всем элементам контейнера, то можно рассмотреть использование алгоритма for_each.

Решим следующую задачу: вывести в стандартный поток квадраты натуральных чисел от 1 до 100. Следующий код показывает, что эта задача может быть решена в четырех строчках кода и без явного использования циклов:

#include <vector>
#include <iostream>
#include <numeric>  // iota
#include <algorithm>  // for_each

using namespace std;

int main() {
    vector<int> v(100);
    iota(v.begin(), v.end(), 1);  // v = [1, 2, 3, ..., 100]
    for_each(v.begin(), v.end(), [](int& a){a = a*a;});
    // v = [1, 4, 9, ..., 10000]
    for_each(v.begin(), v.end(), [](int a){cout << a << ' ';});
    return 0;
}

Мы воспользовались алгоритмом iota из библиотеки <numeric>, чтобы проинициализировать массив набором последовательных целых чисел. Затем мы два раза использовали алгоритм for_each: для вычисления квадратов и для вывода значений в стандартный поток.

Третьим аргументом алгоритм for_each принимает функцию одного аргумента. Тип аргумента должен соответствовать типу элементов контейнера. Вместо обычной функции бывает удобно передать лямбда-выражение, что мы и сделали оба раза в этом примере. Лямбда-выражение позволяет определить функцию в месте ее использования. Квадратные скобки [] указывают на начало лямбда-выражения; в круглых скобках указываются аргументы выражения; в фигурных скобках содержится тело лямбда-выражения.

Модифицируем немного нашу задачу. Предположим, что мы не хотим изменять исходный вектор, а значения квадратов хотим сохранить в другом векторе. Алгоритм transform позволяет выполнить такое преобразование:

#include <vector>
#include <iostream>
#include <numeric>  // iota
#include <algorithm>  // for_each, transform

using namespace std;

int main() {
    vector<int> source(100);
    iota(source.begin(), source.end(), 1);  // v = [1, 2, 3, ..., 100]
    vector<int> target(source.size());
    transform(source.begin(), source.end(), target.begin(),
        [](int& a){return a*a;});  // v = [1, 4, 9, ..., 10000]
    for_each(target.begin(), target.end(),
        [](int a){cout << a << ' ';});
    return 0;
}

Третьим аргументом алгоритм transform принимает итератор на место целевого контейнера, с которого нужно начать заполнять значения. Обратите внимание, что мы заранее инициализировали вектор target нужной длины.

all_of, any_of, none_of

Довольно часто возникает задача проверки какого-либо условия для всех объектов контейнера. Здесь на помощь приходят алгоритмы all_of, any_of и none_of с очевидным поведением, которые принимают диапазон значений и унарный предикат — функцию одного аргумента, которая возвращает true или false. Так, например, можно проверить содержит ли множество хотя бы один отрицательный элемент:

set<double> s{1.1, -0.9, 2.4, 10.1, 3.1415};
bool neg_in_set = any_of(
    s.begin(), s.end(), [](double x){return x < 0;});
// true

Вторая строчка этого примера не поменяется, если вместо контейнера set будет использован другой контейнер, например, list, vector, array или unordered_set.

count, count_if, find, find_if

Алгоритм count позволяет посчитать количество элементов в контейнере, равных заданному. Модификация этого алгоритма count_if подсчитывает количество элементов, удовлетворяющих определенному условию. Рассмотрим следующий пример: мы имеем дело с историей авторизации пользователей на сайте, которая хранится в виде вектора строк. Каждая строка — это логин пользователя. Подсчитаем сколько раз авторизовывался пользователь с логином david:

vector<string> history = {/*...*/};
size_t david_count = count(history.begin(), history.end(), "david");

Если нам захочется удалить запись для логина david, мы можем это сделать с помощью алгоритма find и метода vector::erase:

if (auto item = find(history.begin(), history.end(), "david");
        item != history.end()) {
    history.erase(item);
}

Алгоритм find возвращает итератор на найденный элемент. Версия алгоритма find_if позволяет найти первый элемент, удовлетворяющий некоторому условию.

Как и другие алгоритмы, find и count могут работать с контейнерами разных типов. Они проходят переданный диапазон значений последовательно, начиная с первого элемента. Использование такого подхода для контейнеров set и map — плохая идея, ведь они созданы для того чтобы выполнять поиск объектов быстрее. Это общее правило: если контейнер имеет метод, аналогичный общему алгоритму, то следуем использовать метод контейнера. В большинстве случаев это даст выигрыш в производительности.

sort, stable_sort, nth_element

Алгоритмы сортировки — это важный и интересный раздел теории алгоритмов. Работать с отсортированными элементами во многих ситуациях удобнее, в частности, сложность поиска элементов становится логарифмической вместо линейной. Стандартная библиотека C++ предлагает алгоритмы sort и stable_sort, которые выполняют сортировку за время, пропорциональное N log(N), где N — количество элементов массива. Стабильная сортировка stable_sort при этом гарантирует, что равные объекты не меняют своего относительного положения в контейнере.

Рассмотрим простой пример сортировки:

vector<string> v {"David", "Ivan", "Adam", "Dmitry"};
sort(v.begin(), v.end());  // ["Adam", "David", "Dmitry", "Ivan"]

По умолчанию сортировка выполняется по возрастанию, а для сравнения используется оператор меньше <. Это поведение можно изменить, передав свой компаратор — объект, который принимает два объекта и возвращает логическое значение. Отсортируем наш вектор строк по длине строки по убыванию:

bool string_cmp(const string& lhs, const string& rhs) {
    return lhs.size() > rhs.size();
}

vector<string> v {"David", "Ivan", "Adam", "Dmitry"};
stable_sort(v.begin(), v.end(), string_cmp);
// ["Dmitry", "David", "Ivan", "Adam"]

Мы использовали стабильную версию сортировки. В этом случае Ivan гарантировано окажется левее Adam в отсортированном векторе.

Оказывается, что задача поиска n-го элемента (как если бы элементы стояли по порядку по какому-либо признаку) может быть решена быстрее, чем сортировка всего массива — за линейное время. Стандартная библиотека предлагает алгоритм nth_element для решения этой задачи.

lower_bound, upper_bound, binary_search

Коль скоро мы научились получать отсортированные массивы, рассмотрим алгоритмы для поиска элементов в них. Алгоритмы lower_bound и upper_bound позволяют найти в отсортированном массиве первый элемент не меньше данного и первый элемент больше данного, соответственно. Эти алгоритмы возвращают итератор, соответствующий найденному элементу.

Алгоритм binary_search проверяет, есть ли в отсортированном массиве данный элемент и возвращает true или false в зависимости от результата поиска.

Все три алгоритма выполняются за логарифмическое время.

Резюме

В этом материале мы рассмотрели примеры использования нескольких основных алгоритмов стандартной библиотеки C++. Обсудили, что применение стандартных алгоритмов является хорошим стилем программирования, позволяет писать код быстрее, и делает его более легким для прочтения.

Полезные алгоритмы стандартной библиотеки не ограничиваются рассмотренными выше. Мы рекомендуем посмотреть на полный список доступных алгоритмов, среди которых можно обратить внимание на алгоритмы copy, remove, generate и partition, которые вполне могут пригодиться.

Конечно, мы не ожидаем, что после прочтения этого материала вы сразу начнете свободно применять разнообразные алгоритмы. Только с практикой использование алгоритмов становится естественным и полезным инструментом разработки.