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

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

  |

  Обновл. 15 Сен 2021  | 

 56374

 ǀ   17 

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

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

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

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

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

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

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

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

Данные алгоритмы расположены в библиотеке алгоритмов (заголовочный файл 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 (141 оценок, среднее: 4,87 из 5)
Загрузка...

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

  1. Сергей:

    Не знаю… возможно пользуюсь старым стандартом компилятора в Code::Blocks 17.12, но у меня greater потребовал тип шабона, в нашем случае <int>

    сработало так

  2. Pavel:

    Как это работает?

    1. Kayfor:

      Знаю, что уже поздно, но возможно будет полезно кому-то в будующем)

    2. Павел:

      Я так понял, что  метод std::string::find() (или std::string_view::find()) возвращает std::string::npos / std::string_view::npos (несуществующая позиция) если не нашлось совпадений до конца строки.

      И при использовании этого метода лучше ловить результат таким образом, потому что иначе он вернет страшное число:

      https://cplusplus.com/reference/string/string/npos/

  3. Евгений:

    Я правильно понимаю, что в

    при нахождении "nut" значение параметра return становится true и это логическое значение возвращается в main? И соответственно, при ненахождении оно становится false

  4. Рустем:

    Не пойму третий пункт этой главы, именно как решается эта задача с поиском "nut" std::find_if() и поиск элемента с условием.

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

      С какой конкретно строки начинается недопонимание? 🙂

      1. Рустем:

        Не могу уловить связь в функции main со строки

        c функцией

        И где эта строка std::string_view::npos????? для чего нужна?

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

          Начнём с последнего.

          >>И где эта строка std::string_view::npos????? для чего нужна?

          Если прочитать статью с самого начала, то во втором фрагменте кода есть вот такой комментарий: "std::string_view::find возвращает std::string_view::npos, если он не нашел подстроку. Или же возвращает индекс, где происходит вхождение подстроки в строку."

          std::string_view::npos — это не строка, а константа, чем-то похожая на константу EOF (End of File) при работе с файлами. Когда она используется вместе со строками, то её значение воспринимается как "признак достижения конца строки ". То есть, получается мы как бы говорим — "искать, пока не достигнем конца строки".
          Например:
          str.find("nut") != std::string_view::npos — выполнять поиск вхождения "nut" в заданной строке, пока не достигнем её конца. И тут возможны два варианта: мы либо найдем такую подстроку, и тогда str.find() вернет индекс, с которого начинается вхождение подстроки "nut"; либо str.find() вернет признак достижения конца строки (std::string_view::npos).

          Далее, std::find_if(arr.begin(), arr.end(), containsNut). Ну с arr.begin() и arr.end() я думаю всё понятно, это обычные итераторы, указывающие на начало и конец строки, в рамках которой мы будем производить поиск. А containsNut — это "условие", по которому мы производим поиск. В данном случае в качестве условия мы передали функцию, которая (как написано выше), ищет вхождение подстроки "nut".

  5. 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()

  6. Константин:

    Может быть глупый вопрос, но почему 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. Константин:

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

  7. Yerda:

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

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

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

Добавить комментарий для Евгений Отменить ответ

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