В стандартной библиотеке 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 считают накопленную сумму элементов диапазона Причем, i-ый элемент включается в i-ую сумму. В отличие от std::partial_sum, алгоритм std::inclusive_scan поддерживает параллельное исполнение.
std::exclusive_scan
На рисунке приведены результаты работы std::exclusive_scan для разных значений параметра init. Отличием данного алгоритма от std::inclusive_scan является то, что в i-ую сумму не включается i-тый элемент из исходного диапазона. Так как 0-ой элемент не включается в сумму с индексом 0, то используется инициализирующий параметр init.
std::adjacent_difference
std::adjacent_difference считает разность между смежными парами в диапазоне и записывает результат в заданный контейнер, начиная со второй позиции. В первую позицию контейнера копируется первый элемент источника.
std::transform_reduce
std::transform_reduce применяет процедуру transform к каждому элементу контейнера, а затем выполняет reduce для полученного результата. В приведенной таблице операция transform представляет собой возведение в квадрат, а reduce - суммирование. Полученный результат работы алгоритма над контейнером src из пяти элементов равен 55.
std::transform_inclusive_scan
std::transform_inclusive_scan применяет процедуру transform к каждому элементу контейнера, а затем выполняет inclusive_scan для полученного результата. В приведенной таблице операция transform представляет собой возведение в квадрат. Результатом работы алгоритма для контейнера src из пяти элементов является диапазон в колонке inclusive_scan.
std::transform_exclusive_scan
std::transform_exclusive_scan применяет процедуру transform к каждому элементу контейнера, а затем выполняет exclusive_scan для полученного результата. В приведенной таблице операция transform представляет собой возведение в квадрат. Результатом работы алгоритма для контейнера src из пяти элементов является диапазон в колонке exclusive_scan. Инициализирующий параметр равен -10.
Заключение
Алгоритмы стандартной библиотеки C++ достаточно просты, если в них разобраться. Каждый из них направлен на решение какой-либо практической задачи. Как правило, все из них предоставляют возможность существенно расширить область своего применения, позволяя настраивать своё поведение с помощью функциональных объектов. Умелое использование инструментов, представляемых стандартной библиотекой, позволит улучшить, как качество кода, так и скорость разработки.