Алгоритмы в Стандартной Библиотеке С++

  Дмитрий Бушуев  | 

  Обновл. 8 Фев 2020  | 

 1002

В этом уроке мы рассмотрим использование алгоритмов из Стандартной Библиотеки С++.

Библиотека алгоритмов

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

Поскольку поиск, подсчёт и сортировка являются очень распространёнными операциями в программировании, то в состав Стандартной Библиотеки языка C++ изначально уже включен большой набор функций, которые выполняют данные задачи всего в несколько строчек кода. В дополнении к этому, эти функции уже предварительно протестированные, эффективные и имеют поддержку множества различных типов контейнеров. А некоторые из этих функций поддерживают и распараллеливание — возможность выделять несколько потоков ЦП для одной и той же задачи, чтобы выполнить её быстрее.

Функционал, предоставляемый библиотекой алгоритмов, обычно относится к одной из трёх категорий:

   Инспекторы — используются для просмотра (без изменений) данных в контейнере (например, операции поиска или подсчёта элементов).

   Мутаторы — используются для изменения данных в контейнере (например, операции сортировки или перестановки элементов).

   Фасилитаторы — используются для генерации результата на основе значений элементов данных (например, объекты, которые умножают значения, либо объекты, которые определяют, в каком порядке пары элементов должны быть отсортированы).

Данные алгоритмы расположены в библиотеке алгоритмов (заголовочный файл <algorithm>). В этом уроке мы рассмотрим некоторые из наиболее распространённых алгоритмов.

Примечание: Все эти алгоритмы используют итераторы.

Алгоритм std::find() и поиск элемента по значению


Функция std::find() выполняет поиск первого вхождения заданного значения в контейнере. В качестве аргументов std::find() принимает 3 параметра:

   итератор для начального элемента в последовательности;

   итератор для конечного элемента в последовательности;

   значение для поиска.

В результате будет возвращен итератор, указывающий на элемент с искомым значением (если он найден) или конец контейнера (если такой элемент не найден).

Например:

Пример, в котором элемент найден:

Enter a value to search for and replace with: 5 234
13 90 99 234 40 80

Пример, в котором элемент не найден:

Enter a value to search for and replace with: 0 234
Could not find 0
13 90 99 5 40 80

Алгоритм std::find_if() и поиск элемента с условием

Иногда мы хотим увидеть, есть ли в контейнере значение, которое соответствует некоторому условию (например, строка, содержащая заданную подстроку).

В таких случаях функция std::find_if() будет идеальным помощником. Она работает аналогично функции std::find(), но вместо того, чтобы передавать значение для поиска, мы передаём вызываемый объект, например, указатель на функцию (или лямбда — это мы рассмотрим в следующем уроке), который проверяет, найдено ли совпадение. Функция std::find_if() будет вызывать этот объект для каждого элемента, пока не найдёт искомый элемент (или в контейнере больше не останется элементов для проверки).

Вот пример, где мы используем функцию std::find_if(), чтобы проверить, содержат ли какие-либо элементы подстроку "nut":

Результат выполнения программы выше:

Found walnut

Если бы мы решали задачу выше обычным стандартным способом, то нам бы понадобилось, по крайней мере, два цикла (один для циклического перебора массива и один для сравнения подстроки). Функции Стандартной Библиотеки С++ позволяют сделать то же самое всего в несколько строчек кода!

Алгоритмы std::count()/std::count_if() и подсчёт вхождений элемента


Функции std::count() и std::count_if() ищут все вхождения элемента или элемент, соответствующий заданным критериям.

В следующем примере мы посчитаем, сколько элементов содержит подстроку "nut":

Результат выполнения программы выше:

Counted 2 nut(s)

Алгоритм std::sort() и пользовательская сортировка

Ранее мы использовали std::sort() для сортировки массива в порядке возрастания, но возможности std::sort() этим не ограничиваются. Существует версия std::sort(), которая принимает вспомогательную функцию в качестве третьего параметра, что позволяет выполнять сортировку так, как нам это захочется. Данная вспомогательная функция принимает два параметра для сравнения и возвращает true, если первый аргумент должен быть упорядочен перед вторым. По умолчанию, std::sort() сортирует элементы в порядке возрастания.

Давайте попробуем использовать std::sort() для сортировки массива в обратном порядке с помощью вспомогательной пользовательской функции для сравнения greater():

Результат выполнения программы выше:

99 90 80 40 13 5

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

Совет: Поскольку сортировка в порядке убывания также очень распространена, то C++ предоставляет пользовательский тип std::greater{} для этой задачи (который находится в заголовочном файле <functional>). В примере выше мы можем заменить:

на:

Обратите внимание, что std::greater{} нуждается в фигурных скобках, потому что это не вызываемая функция, а тип данных и для его использования нам нужно создать экземпляр данного типа. Фигурные скобки создают анонимный объект данного типа (который затем передаётся в качестве аргумента в std::sort()).

Алгоритм std::for_each() и все элементы контейнера


Функция std::for_each() принимает список в качестве входных данных и применяет пользовательскую функцию к каждому элементу этого списка. Это полезно, когда нам нужно выполнить одну и ту же операцию со всеми элементами списка.

Вот пример, где мы используем std::for_each() для удвоения всех чисел в массиве:

Результат выполнения программы выше:

2 4 6 8

Новичкам данный способ может показаться ненужным алгоритмом, потому что эквивалентный код с использованием цикла for с явным указанием диапазона будет короче и проще. Но плюс std::for_each() состоит в том, что у нас есть возможность повторного использования тела цикла и его распараллеливание, что делает std::for_each() более подходящим инструментом для больших проектов с большим объемом данных.

Порядок выполнения

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

Следующие алгоритмы гарантируют последовательное выполнение:

   std::for_each()

   std::copy()

   std::copy_backward()

   std::move()

   std::move_backward()

Совет: Если не указано иное, считайте, что для алгоритмов из Стандартной Библиотеки С++ порядок выполнения является неопределённым. Алгоритмы выше дают гарантию последовательного выполнения.

Диапазоны в C++20


Необходимость для каждого алгоритма явно передавать arr.begin() и arr.end() может немного раздражать. Но в стандарте C++20 добавлен такой инструмент, как диапазоны, который позволит нам просто передавать arr. Благодаря этому мы сможем сделать наш код ещё короче и читабельнее.

Заключение

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

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

Оценить статью:

Звёзд: 1Звёзд: 2Звёзд: 3Звёзд: 4Звёзд: 5 (8 оценок, среднее: 4,88 из 5)
Загрузка...

Добавить комментарий

Ваш E-mail не будет опубликован. Обязательные поля помечены *