10.25 – Знакомство с алгоритмами стандартной библиотеки

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

Поскольку поиск, подсчет и сортировка – это довольно распространенные операции, стандартная библиотека C++ поставляется с набором функций, позволяющих делать эти вещи всего в нескольких строках кода. Кроме того, эти функции стандартной библиотеки проходят предварительное тестирование, они эффективны, работают с различными типами контейнеров, и многие поддерживают распараллеливание (возможность выделить несколько потоков CPU для одной и той же задачи, чтобы выполнить ее быстрее).

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

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

Эти алгоритмы находятся в библиотеке алгоритмов. В этом уроке мы рассмотрим некоторые из наиболее распространенных алгоритмов, но их гораздо больше!

Примечание. Все они используют итераторы, поэтому, если вы не знакомы с основами итераторов, просмотрите урок «10.24 – Знакомство с итераторами».

Использование std::find для поиска элемента по значению

std::find ищет первое вхождение значения в контейнере. std::find принимает 3 параметра: итератор для начального элемента в последовательности, итератор для конечного элемента в последовательности и значение для поиска. Она возвращает итератор, указывающий на элемент (если он найден) или конец контейнера (если элемент не найден).

Например:

#include <algorithm>
#include <array>
#include <iostream>
 
int main()
{
  std::array arr{ 13, 90, 99, 5, 40, 80 };
 
  std::cout << "Enter a value to search for and replace with: ";  
  int search{};
  int replace{};
  std::cin >> search >> replace;
 
  // Проверка ввода опущена
 
  // std::find возвращает итератор, указывающий на найденный элемент
  // (или конец контейнера)
  // мы сохраним его в переменной, используя вывод типа, чтобы
  // определить тип итератора (так как нам он не важен)
  auto found{ std::find(arr.begin(), arr.end(), search) };
 
  // Алгоритмы, которые не находят то, что искали, возвращают конечный итератор.
  // Мы можем получить к нему доступ, используя функцию-член end().
  if (found == arr.end())
  {
    std::cout << "Could not find " << search << '\n';
  }
  else
  {
    // Заменить найденный элемент.
    *found = replace;
  }
 
  for (int i : arr)
  {
    std::cout << i << ' ';
  }
 
  std::cout << '\n';
 
  return 0;
}

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

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_if работает аналогично std::find, но вместо передачи значения для поиска мы передаем вызываемый объект, такой как указатель на функцию (или лямбда-функцию, которую мы рассмотрим позже), которая проверяет, найдено ли совпадение. std::find_if будет вызывать эту функцию для каждого элемента, пока не будет найден соответствующий элемент (или в контейнере больше не останется элементов для проверки).

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

#include <algorithm>
#include <array>
#include <iostream>
#include <string_view>
 
// Наша функция вернет true, если элемент соответствует условию
bool containsNut(std::string_view str)
{
  // std::string_view::find возвращает std::string_view::npos, если не находит
  // подстроку. В противном случае он возвращает индекс, в котором подстрока
  // встречается в str.
  return (str.find("nut") != std::string_view::npos);
}
 
int main()
{
  std::array<std::string_view, 4> arr{ "apple", "banana", "walnut", "lemon" };
 
  // Сканируем наш массив, чтобы увидеть, содержат ли какие-либо 
  // элементы подстроку "nut"
  auto found{ std::find_if(arr.begin(), arr.end(), containsNut) };
 
  if (found == arr.end())
  {
    std::cout << "No nuts\n";
  }
  else
  {
    std::cout << "Found " << *found << '\n';
  }
 
  return 0;
}

Вывод программы

Found walnut

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

Использование std::count и std::count_if для подсчета количества вхождений

std::count и std::count_if ищут все вхождения значения элемента или элемента, удовлетворяющего условию.

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

#include <algorithm>
#include <array>
#include <iostream>
#include <string_view>
 
bool containsNut(std::string_view str)
{
  return (str.find("nut") != std::string_view::npos);
}
 
int main()
{
  std::array<std::string_view, 5> arr{ "apple", "banana", "walnut", "lemon", "peanut" };
 
  auto nuts{ std::count_if(arr.begin(), arr.end(), containsNut) };
 
  std::cout << "Counted " << nuts << " nut(s)\n";
 
  return 0;
}

Вывод программы:

Counted 2 nut(s)

Использование std::sort для настраиваемой сортировки

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

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

#include <algorithm>
#include <array>
#include <iostream>
 
bool greater(int a, int b)
{
  // Порядок "a перед b", если a больше, чем b.
  return (a > b);
}
 
int main()
{
  std::array arr{ 13, 90, 99, 5, 40, 80 };
 
  // Передаем greater в std::sort
  std::sort(arr.begin(), arr.end(), greater);
 
  for (int i : arr)
  {
    std::cout << i << ' ';
  }
 
  std::cout << '\n';
 
  return 0;
}

Вывод программы:

99 90 80 40 13 5

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

Наша большая функция требует 2 аргумента, но мы их не передаем, так откуда они берутся? Когда мы используем имя функции без скобок (), это всего лишь указатель на функцию, а не вызов. Возможно, вы вспомните, как мы пытались напечатать функцию без скобок, а std::cout напечатал '1'. std::sort использует этот указатель и вызывает фактическую функцию greater с любыми двумя элементами массива. Мы не знаем, с какими элементами будут вызываться greater, потому что не определено, какой алгоритм сортировки std::sort использует под капотом. Подробнее об указателях на функции мы поговорим в одной из следующих глав.

std::sort(arr.begin(), arr.end(), greater); // вызываем нашу пользовательскую функцию greater

// использовать сравнение greater из стандартной библиотеки
std::sort(arr.begin(), arr.end(), std::greater{}); 

// До C++17 нам приходилось указывать тип элемента при создании std::greater
// использовать сравнение greater из стандартной библиотеки
std::sort(arr.begin(), arr.end(), std::greater<int>{});

#include <iostream>
#include <iterator>
#include <utility>
 
void sort(int *begin, int *end)
{
  for (auto startElement{ begin }; startElement != end; ++startElement)
  {
    auto smallestElement{ startElement };
    
    // std::next возвращает указатель на следующий элемент, как и (startElement + 1)
    for (auto currentElement{ std::next(startElement) }; currentElement != end; ++currentElement)
    {
      if (*currentElement < *smallestElement)
      {
        smallestElement = currentElement;
      }
    }
 
    std::swap(*startElement, *smallestElement);
  }
}
 
int main()
{
  int array[]{ 2, 1, 9, 4, 5 };
 
  sort(std::begin(array), std::end(array));
 
  for (auto i : array)
  {
    std::cout << i << ' ';
  }
 
  std::cout << '\n';
 
  return 0;
}

void sort(int *begin, int *end, std::function<bool(int, int)> compare)

if (*currentElement < *smallestElement)

if (compare(*currentElement, *smallestElement))

#include <functional> // std::function
#include <iostream>
#include <iterator>
#include <utility>
 
// sort принимает функцию сравнения
void sort(int *begin, int *end, std::function<bool(int, int)> compare)
{
  for (auto startElement{ begin }; startElement != end; ++startElement)
  {
    auto smallestElement{ startElement };
    
    for (auto currentElement{ std::next(startElement) };
         currentElement != end;
         ++currentElement)
    {
      // функция сравнения используется, чтобы проверить,
      // нужно ли переставить текущий элемент на место
      // перед самым "наименьшим" (smallestElement) в данный
      // момент элементом.
      if (compare(*currentElement, *smallestElement))
      {
        smallestElement = currentElement;
      }
    }
 
    std::swap(*startElement, *smallestElement);
  }
}
 
int main()
{
  int array[]{ 2, 1, 9, 4, 5 };
 
  // использовать std::greater для сортировки по убыванию
  // (Мы должны использовать селектор глобального пространства
  // имен, чтобы предотвратить конфликт имен
  // между нашей функцией sort и std::sort.)
  ::sort(std::begin(array), std::end(array), std::greater{});
 
  for (auto i : array)
  {
    std::cout << i << ' ';
  }
 
  std::cout << '\n';
 
  return 0;
}

Использование std::for_each для выполнения каких-либо действий со всеми элементами контейнера

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

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

#include <algorithm>
#include <array>
#include <iostream>
 
void doubleNumber(int &i)
{
  i *= 2;
}
 
int main()
{
  std::array arr{ 1, 2, 3, 4 };
 
  std::for_each(arr.begin(), arr.end(), doubleNumber);
 
  for (int i : arr)
  {
    std::cout << i << ' ';
  }
 
  std::cout << '\n';
 
  return 0;
}

Вывод программы:

2 4 6 8

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

// начиная с C++20, нам не нужно использовать begin() и end()
std::ranges::for_each(arr, doubleNumber); 
// std::for_each(arr.begin(), arr.end(), doubleNumber); // до C++20
 
for (auto& i : arr)
{
  doubleNumber(i);
}

С std::for_each наши намерения ясны. Вызов doubleNumber с каждым элементом arr. В цикле for на основе диапазона мы должны добавить новую переменную i. Это приводит к нескольким ошибкам, которые программист может совершить, когда он устал или не внимателен. Во-первых, может произойти неявное преобразование, если мы не будем использовать auto. Мы могли бы забыть об амперсанде, и doubleNumber не повлияет на массив. Мы могли случайно передать в doubleNumber переменную, отличную от i. Этих ошибок не может произойти с std::for_each.

Кроме того, std::for_each может пропускать элементы в начале или конце контейнера, например, чтобы пропустить первый элемент arr, для перехода к следующему элементу может использоваться std::next.

std::for_each(std::next(arr.begin()), arr.end(), doubleNumber);
// Теперь arr равен [1, 4, 6, 8]. Первый элемент не удвоился.

Это невозможно с циклом for на основе диапазона.

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

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

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

Следующие алгоритмы действительно гарантируют последовательное выполнение: std::for_each, std::copy, std::copy_backward, std::move и std::move_backward.

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

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

Заключение

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

Теги