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

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

  Обновл. 20 Окт 2020  | 

 10640

 ǀ   8 

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

Примечание: Для корректной работы всех примеров данного урока ваш компилятор должен поддерживать стандарт С++17. Детально о том, как использовать функционал C++17 вашей IDE, читайте здесь.

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

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 (71 оценок, среднее: 4,86 из 5)
Загрузка...

Комментариев: 8

  1. Аватар KiberCyber:

    <Необходимость для каждого алгоритма явно передавать arr.begin() и arr.end() может немного раздражать. Но в стандарте C++20 добавлен такой инструмент, как диапазоны, который позволит нам просто передавать arr. Благодаря этому мы сможем сделать наш код ещё короче и читабельнее.>
    Так-то круто конечно, вот только как это сделать то? Ну, не сочтите прям совсем глупым, но погуглив я нашел лишь вот это: https://habr.com/ru/company/otus/blog/456452/ , но мало что прояснилось(+- ничего). Я пробовал не многое: только лишь заменить arr.begin() и arr.end() на просто arr, однако был вежливо послан компилятором со словами "candidate function template not viable: requires 3 arguments, but 2 were provided".

    1. Аватар VEX:

      Если пользуетесь VS19, то почитайте вот это(главное меню — это правое окошко в VS19, где показаны все файлы вашего проекта)

    2. Аватар Andrey:

      Просто вместо std::find, нужно написать std::ranges::find, и прописать массив без begin() и end()

  2. Аватар Константин:

    Может быть глупый вопрос, но почему std::array записывается как

    А не array<int, 3> arr {1, 2, 3}?
    Разве это будет работать?

    1. Дмитрий Бушуев Дмитрий Бушуев:

      >>Может быть глупый вопрос, но почему std::array записывается как…
      Начиная со С++17, в стандарт включен т.н. "Вывод Параметров Шаблонов Классов (Class Template Argument Deduction)".
      Благодаря этому объявлять массив можно как:

      >>Разве это будет работать?
      Да, при условии, что ваш компилятор поддерживает стандарт C++17. Только что проверил это у себя (Qt 5.14.2 + MinGW 7.3.0), дописав в файл проекта параметр:
      CONFIG += c++17 console

      1. Аватар Константин:

        Спасибо большое

  3. Аватар Yerda:

    Почему все пользовательские функции, которые передаются в качестве параметров записываются в виде "func" нежели "func()"?

    1. Дмитрий Бушуев Дмитрий Бушуев:

      Ответ на ваш вопрос находится здесь:
      Урок №104. Указатели на функции (параграф — Передача функций в качестве аргументов другим функциям)
      https://ravesli.com/urok-104-ukazateli-na-funktsii/#toc-3
      🙂

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

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