5.11 Алгоритмы

В стандартной библиотеке имеется большое количество различных алгоритмов, реализованных в виде шаблонных функций. Для использования большинства из них необходимо подключить заголовочный файл algorithm.

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

• std::sort − сортировка

• std::stable_sort − устойчивая сортировка

• std::unique − удаление дубликатов

• std::binary_search − двоичный поиск

• std::lower_bound − нижняя граница

• std::upper_bound − нижняя граница

Одной из наиболее востребованных задач в программировании является сортировка данных. Для сортировки в C++ можно использовать две функции − std::sort и std::stable_sort. Отличие между ними состоит в том, что вторая функция выполняет устойчивую сортировку (то есть гарантируется, что элементы с одинаковыми ключами не поменяют свой порядок относительно друг друга). Для некоторых задач это может быть важно. Вычислительная сложность обеих функций составляет O(N∙log(N)). Однако, std::stable_sort требует больше памяти для работы, и на практике работает несколько медленнее, чем std::sort.

По умолчанию сортировка выполняется по возрастанию (точнее, по неубыванию). Однако, порядок можно поменять путём указания дополнительного аргумента функции. Примеры:

std::sort(a.begin(), a.end()); // отсортировать a по возрастанию

std::sort(a.begin(), a.end(), std::greater<int>()); // по убыванию

// по возрастанию последней цифры

std::sort(a.begin(), a.end(), [](int a, int b) {return a%10<b%10;});

В последней строчке для сравнения чисел по последней цифре используется лямбда-выражение (лямбда-выражения поддерживаются начиная с С++11).

Функция std::unique удаляет дубликаты из каждой группы стоящих подряд одинаковых элементов и возвращает итератор на элемент после последнего элемента результата (размер контейнера не изменяется). Например, если вектор a содержал числа 2, 2, 5, 5, 5, 3, 3, 2, 2, то после вызова

auto last = std::unique(a.begin(), a.end());

в векторе будет находиться 2, 5, 3, 2, 5, 3, 3, 2, 2, а итератор last будет ссылаться на пятый элемент вектора. В большинстве случаев функция std::unique применяется к уже отсортированному контейнеру, чтобы убрать в нём все повторяющиеся элементы.

Для примера решим задачу, которую мы уже решали выше с помощью множеств (см. пример 5.17): вводится N целых чисел, требуется вывести их в порядке возрастания без повторов. Решение: прочитаем входные числа в вектор, отсортируем его с помощью std::sort, уберём дубликаты с помощью std::unique, отрежем "хвост" с дубликатами с помощью метода erase, выведем результат:

// Пример 5.21 - вывод чисел по возрастанию без повторов

#include <iostream>

#include <algorithm>

int main() {

int n;

std::cin >> n;

std::vector<int> a(n);

for (int i = 0; i < n; i++)

std::cin >> a[i];

std::sort(a.begin(), a.end());

auto last = std::unique(a.begin(), a.end());

a.erase(last, a.end());

for (int x : a)

std::cout << x << " ";

}

Функции std::binary_search, std::lower_bound и std::upper_bound предназначены для выполнения двоичного поиска в упорядоченном контейнере. Заметим, что логарифмическая сложность достигается лишь для контейнеров, поддерживающих итераторы произвольного доступа − к ним относятся std::vector и std::deque.

Функция std::binary_search возвращает логическое значение − с её помощью можно эффективно определить, присутствует ли элемент в контейнере, но нельзя получить его позицию. Если нам также нужна позиция элемента, то можно использовать функцию std::lower_bound − она возвращает итератор на первый элемент, который больше или равен искомому. Функция std::upper_bound возвращает итератор на первый элемент строго больше искомого.

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

// Пример 5.21 - вывод чисел из второй последовательности,

// которые имеются также и в первой

#include <iostream>

#include <vector>

#include <algorithm>

int main() {

int n, m;

std::cin >> n;

std::vector<int> f(n);

for(int i = 0; i < n; i++)

std::cin >> f[i];

std::sort(f.begin(), f.end());

std::cin >> m;

for(int i = 0; i < m; i++) {

int x; std::cin >> x;

if (std::binary_search(f.begin(), f.end(), x))

std::cout << x << " ";

}

}

Заметим, что в стандартной библиотеке имеется целый ряд других алгоритмов, которые мы не рассмотрели: линейный поиск, копирование и перемещение, слияние, работа с двоичными кучами, генерация перестановок, частичная сортировка, переворот, случайное перемешивание и др. Рекомендуется найти время для более глубокого знакомства со стандартной библиотекой языка C++.