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

Добавлено 11 июня 2021 в 23:22
Глава 9 – Массивы, строки, указатели и ссылки  (содержание)

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

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

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

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

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

Примечание. Все они используют итераторы, поэтому, если вы не знакомы с основами итераторов, просмотрите урок «9.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 использует под капотом. Подробнее об указателях на функции мы поговорим в одной из следующих глав.

Совет


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

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>{});

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

Для продвинутых читателей


Чтобы подробнее объяснить, как std::sort использует функцию сравнения, нам нужно вернуться к модифицированной версии примера сортировки выбором из урока «9.4 – Сортировка массива с помощью сортировки выбором».

#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;
}

Пока в этом нет ничего нового, и sort всегда сортирует элементы по убыванию. Чтобы добавить функцию сравнения, мы должны использовать новый тип std::function для хранения функции, которая принимает 2 параметра типа int и возвращает значение типа bool. Относитесь к этому типу как к магии, мы объясним это в главе 10.

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

Теперь мы можем передать функцию сравнения, например, greater, в sort, но как sort ее использует? Всё, что нам нужно сделать, это заменить строку

if (*currentElement < *smallestElement)

на следующее

if (compare(*currentElement, *smallestElement))

Теперь функция, вызывающая sort, может выбрать, как сравнивать два элемента.

#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.

Лучшая практика


Если не указано иное, не предполагайте, что алгоритмы стандартной библиотеки будут выполняться в определенной последовательности. std::for_each, std::copy, std::copy_backward, std::move и std::move_backward гарантировано выполняются последовательно.

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

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

Заключение

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

Лучшая практика


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

Теги

C++ / CppLearnCppstd::countstd::count_ifstd::findstd::find_ifstd::for_eachSTL / Standard Template Library / Стандартная библиотека шаблоновАлгоритмДля начинающихОбучениеПрограммирование

На сайте работает сервис комментирования DISQUS, который позволяет вам оставлять комментарии на множестве сайтов, имея лишь один аккаунт на Disqus.com.

В случае комментирования в качестве гостя (без регистрации на disqus.com) для публикации комментария требуется время на премодерацию.