Алгоритми в Стандартній бібліотеці С++ / aCode

На цьому уроці ми розглянемо використання алгоритмів зі Стандартної бібліотеки С++.

Зміст:

Бібліотека алгоритмів
Алгоритм std::find() і пошук елемента по значенню
Алгоритм std::find_if() і пошук елемента з умовою
Алгоритми std::count()/std::count_if() і підрахунок входжень елемента
Алгоритм std::sort() і користувацьке сортування
Алгоритм std::for_each() і всі елементи контейнера
Порядок виконання
Діапазони в C++20
Висновки

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

Початківці зазвичай витрачають досить багато часу на написання користувацьких циклів для виконання відносно простих завдань, таких як: сортування, пошук або підрахунок елементів масивів. Ці цикли можуть стати проблематичними як з точки зору того, наскільки легко в них можна зробити помилку, так і з точки зору загальної надійності і зручності використання.

Оскільки пошук, підрахунок і сортування є дуже поширеними операціями в програмуванні, то до складу Стандартної бібліотеки C++ вже додано великий набір функцій, які виконують ці завдання всього лише за декілька рядків коду. На додаток до цього, ці функції вже попередньо протестовані, ефективні і мають підтримку безлічі різних типів контейнерів. А деякі з цих функцій підтримують і розпаралелювання — можливість виділяти кілька потоків ЦП для однієї і тієї ж задачі, щоб виконати її швидше.

Функціонал, що надається бібліотекою алгоритмів, зазвичай відноситься до однієї з наступних трьох категорій:

Інспектори — використовуються для перегляду (без змін) даних в контейнері (наприклад, операції пошуку або підрахунку елементів).

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

Фасилітатори — використовуються для генерації результату на основі значень елементів даних (наприклад, об’єкти, які множать значення, або об’єкти, які визначають, в якому порядку пари елементів повинні бути відсортовані).

Дані алгоритми розташовані в бібліотеці алгоритмів (заголовок algorithm). На цьому уроці ми розглянемо деякі з найбільш поширених алгоритмів.

Примітка: Всі ці алгоритми використовують ітератори.

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

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

ітератор для початкового елементу в послідовності;

ітератор для кінцевого елементу в послідовності;

значення для пошуку.

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

#include <algorithm>
#include <array>
#include <iostream>
 
int main()
{
  std::array<int, 6> 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;
}

#include <algorithm>

#include <array>

#include <iostream>

int main()

{

std::array<int, 6> 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;

}

Примітка: Для коректної роботи всіх прикладів даного уроку ваш компілятор повинен підтримувати стандарт С++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":

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

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

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

#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

Знову ж таки, замість того, щоб самостійно писати з нуля свої цикли/функції, ми можемо впорядкувати наш масив так, як нам подобається, з використанням всього лише декількох рядків коду!

Порада: Оскільки сортування в порядку спадання також дуже поширене, то C++ надає користувацький тип std::greater{} (який знаходиться в заголовку functional) для цього завдання. У прикладі, наведеному вище, ми можемо замінити:

std::sort(arr.begin(), arr.end(), greater); // виклик нашої функції greater

1	std::sort(arr.begin(), arr.end(), greater); // виклик нашої функції greater

на

std::sort(arr.begin(), arr.end(), std::greater{}); // використовуємо greater зі Стандартної бібліотеки С++

1	std::sort(arr.begin(), arr.end(), std::greater{}); // використовуємо greater зі Стандартної бібліотеки С++

Зверніть увагу, std::greater{} потребує фігурні дужки, тому що це не функція, що викликається, а тип даних, і для його використання нам потрібно створити екземпляр. Фігурні дужки створюють анонімний об’єкт даного типу (який потім передається в якості аргументу в функцію std::sort()).

Алгоритм 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;
}

#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() більш підходящим інструментом для великих проектів з великим об’ємом даних.

Порядок виконання

Зверніть увагу, що більшість алгоритмів з бібліотеки алгоритмів не гарантують певного порядку виконання. Для використання таких алгоритмів вам потрібно подбати про те, щоб будь-які функції, що передаються, не мали заданого порядку виконання, так як порядок виклику цих функцій може бути різним у залежності від використовуваного компілятора.

Наступні алгоритми гарантують послідовне виконання:

std::for_each()

std::copy()

std::copy_backward()

std::move()

std::move_backward()

Порада: Якщо не вказано інше, то вважайте, що для алгоритмів зі Стандартної бібліотеки С++ порядок виконання є невизначеним. Вищенаведені алгоритми дають гарантію послідовного виконання.

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

Необхідність для кожного алгоритму явно передавати arr.begin() і arr.end() може трохи дратувати. Але в стандарті C++20 доданий такий інструмент, як діапазони, який дозволяє просто передавати arr. Завдяки цьому ми можемо зробити наш код коротшим і читабельнішим.

Висновки

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

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

Оцінити статтю: