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

Продолжаем визуализировать алгоритмы стандартной библиотеки C++.

Отбор

std::partition_copy

На практике часто возникает задача, когда необходимо выделить из контейнера данные, удовлетворяющие определенному критерию. Для этого отлично подходят такие алгоритмы, как std::find_if, std::copy_if, std::partition_copy. std::partition_copy обладает особенностью: он дополнительно формирует последовательность элементов не удовлетворяющих критерию.

На приведенной записи критерием отбора является равенство элементов заданному значению. По этой причине в контейнере dst true все элементы равны. Но данный алгоритм может работать и для более сложных предикатов.

std::partition и std::stable_partition

Если нужно выделить данные по какому-либо критерию и переместить их в начало контейнера, то для этой цели подойдет std::partition. Относительный порядок элементов сохраняет std::stable_partition.

Упорядочивание

std::nth_element и std::partial_sort

std::nth_element получает на вход позицию контейнера и меняет положение элементов контейнера таким образом, что:

На заданную позицию встает элемент, который был бы на этой позиции в отсортированном контейнере.
Все элементы слева данной позиции меньше его, все элементы справа - больше.

std::partial_sort получает на вход некоторую позицию middle в диапазоне [first; last) и размещает middle - first наименьших элементов диапазона в его начале в отсортированном порядке. Частичная сортировка это не то же, что сортировка части контейнера. Элементы в отсортированной части контейнера в общем случае могут располагаться не там, где они были бы при сортировке всего контейнера.

На записи для std::nth_element и std::partial_sort передана позиция соответствующая середине контейнера. В данном случае std::nth_element находит медиану переданного диапазона. А std::partial_sort размещает половину элементов диапазона на позиции, на которых они находились бы в отсортированном контейнере.

std::partial_sort_copy

Стандартная библиотека также поставляет вариант частичной сортировки с копированием в другой контейнер std::partial_sort_copy. В данном случае более нагляден факт использования кучи (в смысле структуры данных, а не области памяти).

std::stable_sort

Если нужно сохранить порядок равных элементов относительно друг друга после сортировки, то используется std::stable_sort. На записи видно, что реализован этот алгоритм через сортировку слиянием.

Разное

std::clamp

std::clamp меняет значение аргумента таким образом, чтобы оно лежало в заданном диапазоне. Если аргумент меньше нижней границы, то он приравнивается к значению нижней границы. Если больше верхней, то приравнивается к значению большей границы. На записи случайные числа из диапазона от 1 до 1000 сводятся к диапазону от 300 до 600.

std::sample

std::sample выбирает случайным образом заданное количество элементов из диапазона, сохраняя относительный порядок между элементами. На видео с помощью std::sample из последовательности в 100 элементов получено случайным образом 20 элементов.

std::unique

std::unique для каждой последовательности из равных элементов удаляет всё, кроме первого элемента. Возвращаемое значение - итератор, указывающий на новый конец последовательности.

Работа с числами

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

std::inner_product

Для понимания работы std::inner_product можно представить два вектора, координаты которых равны значениям элементов контейнеров. Скалярное произведение этих векторов и будет результатом работы std::inner_product. В приведенной таблице результат работы std::inner_product для диапазонов first и second равен 130.

std::partial_sum и std::inclusive_scan

Результат работы std::partial_sum и std::inclusive_scan

std::partial_sum и std::inclusive_scan считают накопленную сумму элементов диапазона Причем, i-ый элемент включается в i-ую сумму. В отличие от std::partial_sum, алгоритм std::inclusive_scan поддерживает параллельное исполнение.

std::exclusive_scan

Результат работы std::exclusive_scan для разных значений параметра init

На рисунке приведены результаты работы std::exclusive_scan для разных значений параметра init. Отличием данного алгоритма от std::inclusive_scan является то, что в i-ую сумму не включается i-тый элемент из исходного диапазона. Так как 0-ой элемент не включается в сумму с индексом 0, то используется инициализирующий параметр init.

std::adjacent_difference

Результат работы std::adjacent_difference

std::adjacent_difference считает разность между смежными парами в диапазоне и записывает результат в заданный контейнер, начиная со второй позиции. В первую позицию контейнера копируется первый элемент источника.

std::transform_reduce

std::transform_reduce применяет процедуру transform к каждому элементу контейнера, а затем выполняет reduce для полученного результата. В приведенной таблице операция transform представляет собой возведение в квадрат, а reduce - суммирование. Полученный результат работы алгоритма над контейнером src из пяти элементов равен 55.

std::transform_inclusive_scan

Результат работы std::transform_exclusive_scan

std::transform_inclusive_scan применяет процедуру transform к каждому элементу контейнера, а затем выполняет inclusive_scan для полученного результата. В приведенной таблице операция transform представляет собой возведение в квадрат. Результатом работы алгоритма для контейнера src из пяти элементов является диапазон в колонке inclusive_scan.

std::transform_exclusive_scan

Результат работы std::transform_exclusive_scan

std::transform_exclusive_scan применяет процедуру transform к каждому элементу контейнера, а затем выполняет exclusive_scan для полученного результата. В приведенной таблице операция transform представляет собой возведение в квадрат. Результатом работы алгоритма для контейнера src из пяти элементов является диапазон в колонке exclusive_scan. Инициализирующий параметр равен -10.

Заключение

Алгоритмы стандартной библиотеки C++ достаточно просты, если в них разобраться. Каждый из них направлен на решение какой-либо практической задачи. Как правило, все из них предоставляют возможность существенно расширить область своего применения, позволяя настраивать своё поведение с помощью функциональных объектов. Умелое использование инструментов, представляемых стандартной библиотекой, позволит улучшить, как качество кода, так и скорость разработки.

Визуализация алгоритмов стандартной библиотеки C++ (продолжение)